運(yùn)籌學(xué)發(fā)展的回顧與展望_胡曉東.pdf

院刊145 摘 要 運(yùn)籌學(xué)是20世紀(jì)三四十年代發(fā)展起來(lái)的一門(mén)新興交叉學(xué)科 它主要研究 如何應(yīng)用數(shù)學(xué)和計(jì)算的理論與方法對(duì)社會(huì)系統(tǒng)和工程系統(tǒng)做出最優(yōu)或滿(mǎn)意的決 策 本文概述了運(yùn)籌學(xué)的主要特征和方法 簡(jiǎn)述了運(yùn)籌學(xué)的發(fā)展歷程 綜述了運(yùn)籌 學(xué)幾個(gè)主要分支的發(fā)展?fàn)顩r 介紹了運(yùn)籌學(xué)中十幾個(gè)有代表性的難題 展望了運(yùn)籌 學(xué)未來(lái)發(fā)展的方向 關(guān)鍵詞 運(yùn)籌學(xué) 建模 優(yōu)化 算法 DOI 10 3969 j issn 1000 3045 2012 02 003 運(yùn)籌學(xué)發(fā)展的回顧與展望 文 胡曉東 袁亞湘 章祥蓀 中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院 北京10 0 190 收稿日期 2012年1月25日 1 引言 運(yùn)籌學(xué)是20世紀(jì)三四十年代發(fā)展起來(lái) 的一門(mén)新興交叉學(xué)科 它主要研究人類(lèi)對(duì) 各種資源的運(yùn)用及籌劃活動(dòng) 以期通過(guò)了解 和發(fā)展這種運(yùn)用及籌劃活動(dòng)的基本規(guī)律 發(fā) 揮有限資源的最大效益 達(dá)到總體最優(yōu)的目 標(biāo) 從問(wèn)題的形成開(kāi)始 到構(gòu)造模型 提出 解案 進(jìn)行檢驗(yàn) 建立控制 直至付諸實(shí)施為 止的所有環(huán)節(jié)構(gòu)成了運(yùn)籌學(xué)研究的全過(guò) 程 運(yùn)籌學(xué)研究對(duì)象的客觀普遍性 以及強(qiáng) 調(diào)研究過(guò)程完整性的重要特點(diǎn) 決定了運(yùn)籌 學(xué)應(yīng)用的廣泛性 它的應(yīng)用范圍遍及工農(nóng)業(yè) 生產(chǎn) 經(jīng)濟(jì)管理 工程技術(shù) 國(guó)防安全 自然 科學(xué)等各個(gè)方面和領(lǐng)域 運(yùn)籌學(xué)從創(chuàng)建開(kāi)始就表現(xiàn)出理論與實(shí) 踐結(jié)合的鮮明特點(diǎn) 在它的發(fā)展過(guò)程中還充 分表現(xiàn)出了多學(xué)科的交叉結(jié)合 物理學(xué)家 化學(xué)家 數(shù)學(xué)家 經(jīng)濟(jì)學(xué)家 工程師等聯(lián)合組 成研究隊(duì)伍 各自從不同學(xué)科的角度提出對(duì) 實(shí)際問(wèn)題的認(rèn)識(shí)和見(jiàn)解 促使解決大型復(fù)雜 現(xiàn)實(shí)問(wèn)題的新途徑 新方法 新理論更快地 形成 運(yùn)籌學(xué)主要包含3大部分 模型 理論和 算法 無(wú)論是早期解決二戰(zhàn)中的兵力部署 和武器調(diào)配 還是生產(chǎn)組織問(wèn)題或交通 通 訊問(wèn)題 相關(guān)領(lǐng)域的運(yùn)籌學(xué)工作者都建立了 各種各樣的模型 在這些模型下逐步地建立 了比較完整的理論體系 提出了求解相應(yīng)問(wèn) 題的各種類(lèi)型的算法 運(yùn)籌學(xué)經(jīng)過(guò)60多年的發(fā)展 已經(jīng)逐步形 成了一套系統(tǒng)的解決和研究實(shí)際問(wèn)題的方 學(xué)科發(fā)展 Disciplinary Development 2012年 第27卷 第2期 學(xué)科發(fā)展 Disciplinary Development 146 法 它可以概括為以下幾個(gè)階段 1 構(gòu)建所關(guān)心問(wèn) 題的數(shù)學(xué)模型 將一個(gè)實(shí)際問(wèn)題表示為一個(gè)運(yùn)籌學(xué) 問(wèn)題 2 分析問(wèn)題 最優(yōu) 解的性質(zhì)和求解的難易 程度 尋求合適的求解方法 3 設(shè)計(jì)求解相應(yīng)問(wèn)題 的算法 并對(duì)算法的性能進(jìn)行理論分析 4 編程實(shí) 現(xiàn)算法 并分析模擬數(shù)值結(jié)果 5 判斷模型和解法 的有效性 提出解決原始實(shí)際問(wèn)題的方案 這些階 段并不是相互獨(dú)立的 也決非依次進(jìn)行的 正如邦 德 美國(guó)工程院院士 曾任美國(guó)軍事運(yùn)籌學(xué)會(huì)主席 和美國(guó)運(yùn)籌學(xué)會(huì)主席 8 在談到他幾十年建模和分 析的體會(huì)時(shí)指出的那樣 對(duì)于模型的開(kāi)發(fā)應(yīng)該是 一種連續(xù)的研究 開(kāi)發(fā) 分析 改進(jìn) 的過(guò)程 是 一個(gè)原型化和呈螺旋狀發(fā)展的過(guò)程 而不是一個(gè)單 個(gè)事件 在短期內(nèi)建造一個(gè)原型 假若有必要 加 上一些不切實(shí)際的假設(shè) 然后通過(guò)去除那些不切 實(shí)際的假設(shè) 增加過(guò)程 增加系統(tǒng)等等不斷地將模 型改進(jìn) 邦德 8 在回顧運(yùn)籌學(xué)在美國(guó)軍事力量的改造中 所起的重要作用時(shí)指出 對(duì)一個(gè)過(guò)程 一個(gè)系統(tǒng)或 者一個(gè)企業(yè)的建模是一種藝術(shù) 這項(xiàng)藝術(shù)在于確 定哪些因素與活動(dòng)需要包含在模型之中 哪些是變 量 常數(shù) 隨機(jī)的 約束等 在建立變量之間關(guān)系時(shí) 應(yīng)做些什么假設(shè) 以及在逐步運(yùn)作中 如何排除在 建立初始模型時(shí)所引入的是某些不切實(shí)際的假 設(shè) 并且 這是一種可以學(xué)習(xí)的藝術(shù) 希望本文能 對(duì)我國(guó)運(yùn)籌學(xué)的普及 研究 應(yīng)用和發(fā)展有所幫助 2 運(yùn)籌學(xué)發(fā)展歷程 2 1 運(yùn)籌學(xué)發(fā)展簡(jiǎn)史 樸素的運(yùn)籌思想在中國(guó)古代歷史發(fā)展中源遠(yuǎn) 流長(zhǎng) 公元前6世紀(jì)的著作 孫子兵法 是我國(guó)古 代軍事運(yùn)籌思想最早的典籍 研究如何籌劃兵力以 爭(zhēng)取全局勝利 同一時(shí)期 我國(guó)創(chuàng)造的輪作制 間 作制與綠肥制等先進(jìn)的耕作技術(shù)暗含了現(xiàn)代運(yùn)籌 學(xué)中二階段決策問(wèn)題的雛形 總之 統(tǒng)籌 多階段 決策 多目標(biāo)優(yōu)化 合理運(yùn)輸 選址問(wèn)題 都市規(guī)劃 資源綜合利用等運(yùn)籌思想方法屢見(jiàn)不鮮 但很少有 人從數(shù)學(xué)的角度將這些運(yùn)籌思想和方法進(jìn)行提升 西方科學(xué)家一方面試圖從樸素的運(yùn)籌問(wèn)題和 運(yùn)籌思想中發(fā)展新的數(shù)學(xué)內(nèi)涵 另一方面又試圖利 用已經(jīng)建立的數(shù)學(xué)概念和方法解決實(shí)際問(wèn)題 1736年 歐拉用圖論思想成功地解決了哥尼斯堡 七橋問(wèn)題 1738年 貝努利首次提出了效用的概 念 并以此作為決策的標(biāo)準(zhǔn) 1777年 布馮發(fā)現(xiàn)了 用隨機(jī)投針試驗(yàn)來(lái)計(jì)算 的方法 這是隨機(jī)模擬方 法 蒙特卡洛法 最古老的試驗(yàn) 1896年 帕累托 首次從數(shù)學(xué)角度提出多目標(biāo)優(yōu)化問(wèn)題 引進(jìn)了帕累 托最優(yōu)的概念 1909年 丹麥電話(huà)工程師埃爾朗 利用概率論 開(kāi)展了關(guān)于電話(huà)局中繼線(xiàn)數(shù)目的話(huà)務(wù) 理論的研究 開(kāi)創(chuàng)了排隊(duì)論研究的先河 1912年 策梅洛首次用數(shù)學(xué)方法來(lái)研究博弈問(wèn)題 現(xiàn)代運(yùn)籌的思想萌芽于一戰(zhàn)時(shí)期 這段時(shí)間人 們開(kāi)始用數(shù)學(xué)的方法探討各種運(yùn)籌問(wèn)題 只是由于 人力不足 資料有限 經(jīng)費(fèi)不足的原因限制了運(yùn)籌 學(xué)研究的深度 1915年 哈里斯對(duì)商業(yè)庫(kù)存問(wèn)題 的研究是庫(kù)存論模型最早的工作 1916年 蘭徹 斯特提出了關(guān)于戰(zhàn)爭(zhēng)中兵力部署的理論 這是現(xiàn)代 軍事運(yùn)籌最早提出的戰(zhàn)爭(zhēng)模型 1921年 博雷爾 引進(jìn)了對(duì)策論中最優(yōu)策略的概念 對(duì)某些對(duì)策問(wèn)題 證明了最優(yōu)策略的存在 1926年 博魯夫卡最早 發(fā)現(xiàn)了擬陣與組合優(yōu)化算法之間的關(guān)系 1928 年 馮 諾依曼提出了二人零和博弈的一般理論 1932年 威布爾研究了維修問(wèn)題和替換問(wèn)題 這是 可靠性數(shù)學(xué)理論最早的工作 1939年 康托羅維 奇開(kāi)創(chuàng)性地提出線(xiàn)性規(guī)劃 并據(jù)此模型研究了工業(yè) 生產(chǎn)的資源合理利用和計(jì)劃等問(wèn)題 因而在1975 年獲得了諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng) 上述這些先驅(qū)性的成 就對(duì)運(yùn)籌學(xué)的發(fā)展有著深遠(yuǎn)的影響 現(xiàn)代運(yùn)籌學(xué)起源于20世紀(jì)二戰(zhàn)期間 并因其 在軍事作戰(zhàn)方面的大量成功運(yùn)用而得到蓬勃發(fā) 展 1935 1938 年被視作運(yùn)籌學(xué)基本概念醞釀 期 英國(guó)為了有效地運(yùn)用新研制的雷達(dá)系統(tǒng)來(lái)對(duì) 付德國(guó)飛機(jī)的空襲 在皇家空軍中組織了一批科學(xué) 家 進(jìn)行新戰(zhàn)術(shù)試驗(yàn)和戰(zhàn)術(shù)效率研究 并取得了滿(mǎn) 意的效果 他們這種工作叫做 Operational Re 院刊 運(yùn)籌學(xué)發(fā)展的回顧與展望 147 search 我國(guó)翻譯成 運(yùn)籌學(xué) 二戰(zhàn)期間 英軍每個(gè)大的指揮部大都成立了這種運(yùn)籌 研究小組 在美國(guó)和加拿大的軍事部門(mén)也 成立了若干運(yùn)籌研究小組 稱(chēng)之為 Opera tions Research 他們廣泛地研究有關(guān)戰(zhàn)果 評(píng)價(jià) 戰(zhàn)術(shù)革新 技術(shù)援助 戰(zhàn)略決策和戰(zhàn)術(shù) 計(jì)劃等問(wèn)題 1949年 美國(guó)成立了著名的蘭德公司 與此同時(shí) 許多運(yùn)籌學(xué)工作者逐步從軍方轉(zhuǎn) 移到政府及產(chǎn)業(yè)部門(mén)進(jìn)行研究 在新的 更 廣闊的環(huán)境中 運(yùn)籌學(xué)的理論和應(yīng)用研究得 到蓬勃發(fā)展 隨之產(chǎn)生的理論成果主要有 線(xiàn)性規(guī)劃 整數(shù)規(guī)劃 圖論 網(wǎng)絡(luò)流 幾何規(guī) 劃 非線(xiàn)性規(guī)劃 大型規(guī)劃 最優(yōu)控制理論 等 同時(shí)也為歐美等國(guó)創(chuàng)造巨大社會(huì)財(cái)富 研究?jī)?yōu)化模型的規(guī)劃論 研究排隊(duì) 或 服務(wù) 模型的排隊(duì)論 或隨機(jī)服務(wù)系統(tǒng) 以 及研究對(duì)策模型的對(duì)策論 或博弈論 是運(yùn) 籌學(xué)最早的3個(gè)重要分支 通常稱(chēng)為運(yùn)籌學(xué) 早期的3大支柱 隨著學(xué)科的發(fā)展和計(jì)算 機(jī)的出現(xiàn) 現(xiàn)在分支更細(xì) 名目更多 例如線(xiàn) 性與整數(shù)規(guī)劃 圖與網(wǎng)絡(luò) 組合優(yōu)化 非線(xiàn)性 規(guī)劃 多目標(biāo)規(guī)劃 動(dòng)態(tài)規(guī)劃 隨機(jī)規(guī)劃 對(duì) 策論 隨機(jī)服務(wù)系統(tǒng) 排隊(duì)論 庫(kù)存論 可靠 性理論 決策分析 馬爾可夫決策過(guò)程 或馬 爾可夫決策規(guī)劃 搜索論 隨機(jī)模擬 管理 信息系統(tǒng)等基礎(chǔ)學(xué)科分支 工程技術(shù)運(yùn)籌 學(xué) 管理運(yùn)籌學(xué) 工業(yè)運(yùn)籌學(xué) 農(nóng)業(yè)運(yùn)籌學(xué) 軍事運(yùn)籌學(xué)等交叉與應(yīng)用學(xué)科分支也先后 形成 在運(yùn)籌學(xué)飛速發(fā)展的過(guò)程中 至少還有 兩個(gè)因素起了非常重要的作用 1 運(yùn)籌學(xué) 方法的實(shí)質(zhì)性改進(jìn) 二次世界大戰(zhàn)以后 許 多參加過(guò)運(yùn)籌學(xué)小組或者聽(tīng)說(shuō)過(guò)這項(xiàng)工作 的科學(xué)家都對(duì)相關(guān)領(lǐng)域進(jìn)行了更深入的研 究 很多歐美國(guó)家的大學(xué)里設(shè)立了運(yùn)籌系 管理科學(xué)系 工業(yè)工程系 系統(tǒng)科學(xué)系 在這 些系和數(shù)學(xué)系及計(jì)算機(jī)科學(xué)系開(kāi)設(shè)了運(yùn)籌 學(xué)及其一些分支學(xué)科的課程 2 現(xiàn)代計(jì)算 機(jī)的誕生 發(fā)展和應(yīng)用 運(yùn)籌學(xué)中的復(fù)雜問(wèn) 題的求解通常需要進(jìn)行大量的計(jì)算工作 借 助于計(jì)算機(jī)人們所能完成的計(jì)算工作量要 比手工計(jì)算快千百萬(wàn)倍 計(jì)算機(jī)及相關(guān)軟 件的普及更易于人們應(yīng)用運(yùn)籌學(xué)的方法解 決實(shí)際問(wèn)題 從而大大地推動(dòng)了運(yùn)籌學(xué)的進(jìn) 一步發(fā)展 比克斯比 8 美國(guó)工程院院士 曾 任數(shù)學(xué)規(guī)劃學(xué)會(huì)主席 在回顧求解線(xiàn)性規(guī)劃 的實(shí)際問(wèn)題的幾十年的發(fā)展歷程時(shí)指出 計(jì)算機(jī)的進(jìn)步對(duì)線(xiàn)性規(guī)劃的實(shí)際應(yīng)用起到 了巨大的作用 我們知道 如果沒(méi)有計(jì)算機(jī) 的話(huà) 那么線(xiàn)性規(guī)劃根本就不可能存在 2 2 中國(guó)運(yùn)籌學(xué)發(fā)展簡(jiǎn)史 現(xiàn)代運(yùn)籌學(xué)被引入中國(guó)是在上世紀(jì)50 年代后期 中國(guó)第一個(gè)運(yùn)籌學(xué)小組是在錢(qián) 學(xué)森 許國(guó)志先生的推動(dòng)下 于1956年在中 科院力學(xué)所成立 錢(qián)學(xué)森先生在麻省理工 學(xué)院取得碩士學(xué)位 在加州理工大學(xué)取得博 士學(xué)位后成為該校的第一位戈達(dá)德講座教 授 許國(guó)志先生在堪薩斯大學(xué)取得博士學(xué) 位后 在馬里蘭大學(xué)流體力學(xué)和應(yīng)用數(shù)學(xué)研 究所當(dāng)研究員 他們兩人于1955年回到祖 國(guó)致力于新中國(guó)的科技事業(yè) 可見(jiàn)在中國(guó) 運(yùn)籌學(xué)一開(kāi)始就被理解為與工程有密切聯(lián) 系的學(xué)科 1959年 第二個(gè)運(yùn)籌學(xué)部門(mén)在中科院數(shù) 學(xué)所成立 這是 大躍進(jìn) 中數(shù)學(xué)家們投身于 國(guó)家建設(shè)的一個(gè)產(chǎn)物 力學(xué)所小組與數(shù)學(xué) 所的小組于1960年合并成為數(shù)學(xué)所的一個(gè) 研究室 當(dāng)時(shí)的主要研究方向?yàn)榕抨?duì)論 非 線(xiàn)性規(guī)劃和圖論 還有人專(zhuān)門(mén)研究運(yùn)輸理 論 動(dòng)態(tài)規(guī)劃和經(jīng)濟(jì)分析 例如投入產(chǎn)出方 法 1963年是中國(guó)運(yùn)籌學(xué)教育史上值得一 提的一年 數(shù)學(xué)所的運(yùn)籌學(xué)研究室為中國(guó)科 技大學(xué)應(yīng)用數(shù)學(xué)系的第一屆學(xué)生 58屆 開(kāi) 2012年 第27卷 第2期 學(xué)科發(fā)展 Disciplinary Development 設(shè)了較為系統(tǒng)的運(yùn)籌學(xué)專(zhuān)業(yè)課 這是第一次在中國(guó) 的大學(xué)里開(kāi)設(shè)運(yùn)籌學(xué)專(zhuān)業(yè)和授課 今天 運(yùn)籌學(xué)的 課程已成為幾乎所有大學(xué)的商學(xué)院 工學(xué)院乃至數(shù) 學(xué)系和計(jì)算機(jī)系的基本課程了 50年代后期 運(yùn)籌學(xué)在中國(guó)的應(yīng)用集中在運(yùn) 輸問(wèn)題上 其中一個(gè)代表性工作是研究 打麥場(chǎng)的 選址問(wèn)題 解決在手工收割為主的情況下如何節(jié) 省人力 此外 國(guó)際上著名的 中國(guó)郵路問(wèn)題 模型 也是在那個(gè)時(shí)期由管梅谷教授提出的 可以看出 現(xiàn)在非常熱門(mén)的 物流學(xué) 在當(dāng)時(shí)就形成了一些研 究雛形 但可惜中國(guó)在計(jì)劃經(jīng)濟(jì)體制下 大工業(yè)落 后 使我國(guó)在相當(dāng)長(zhǎng)的時(shí)期內(nèi)遠(yuǎn)離了當(dāng)代 物流學(xué) 的發(fā)展主流 中國(guó)運(yùn)籌學(xué)早期普及與推廣工作的亮點(diǎn)是由 華羅庚先生點(diǎn)燃的 在 文革 期間 他身為中國(guó)數(shù) 學(xué)會(huì)理事長(zhǎng)和中科院數(shù)學(xué)所所長(zhǎng) 親自率領(lǐng)一個(gè)小 組 大家稱(chēng)為 華羅庚小分隊(duì) 到農(nóng)村 工廠(chǎng)講解基 本的優(yōu)化技術(shù)和統(tǒng)籌方法 使之用于日常的生產(chǎn)和 生活中 自1965年起的10年中 他到了約20個(gè)省 和無(wú)數(shù)個(gè)城市 受到各界人士的歡迎 他的辛勤勞 動(dòng)得到了毛澤東主席的肯定和表?yè)P(yáng) 華羅庚先生 這一時(shí)期的推廣工作播下了運(yùn)籌學(xué)哲學(xué)思想的種 子 大大推動(dòng)了運(yùn)籌學(xué)在中國(guó)的普及和發(fā)展 直到 今天 許多中國(guó)人還記得 優(yōu)選法 和 統(tǒng)籌法 自上個(gè)世紀(jì)80年代以來(lái) 中國(guó)運(yùn)籌學(xué)有了快 速發(fā)展 取得了一批有國(guó)際影響的理論和應(yīng)用成 果 他們因在組合優(yōu)化 生產(chǎn)系統(tǒng)優(yōu)化 圖論和非線(xiàn) 性規(guī)劃領(lǐng)域的突出貢獻(xiàn)曾先后獲得國(guó)家自然科學(xué) 獎(jiǎng)二等獎(jiǎng)4項(xiàng) 因在經(jīng)濟(jì)信息系統(tǒng)評(píng)估和糧食產(chǎn)量 預(yù)測(cè)方面取得突出成績(jī)?cè)群螳@得國(guó)際運(yùn)籌學(xué)會(huì) 聯(lián)合會(huì)運(yùn)籌學(xué)進(jìn)展獎(jiǎng)一等獎(jiǎng)2項(xiàng) 2 3 運(yùn)籌學(xué)發(fā)展的動(dòng)力 人類(lèi)對(duì)物質(zhì)世界的不斷探索及認(rèn)識(shí)和人類(lèi)社 會(huì)進(jìn)步的需求是數(shù)學(xué)最初的 也是其能持續(xù)發(fā)展的 核心驅(qū)動(dòng)力 而數(shù)學(xué)自身矛盾的解決和體系的完善 是數(shù)學(xué)健康發(fā)展的內(nèi)在驅(qū)動(dòng)力 這兩股力量相互 作用和促進(jìn)也是運(yùn)籌學(xué)不斷向前發(fā)展的推動(dòng)力 著名科學(xué)家馮 諾伊曼 6 曾經(jīng)這樣分析這兩股 力量對(duì)數(shù)學(xué)的影響 當(dāng)數(shù)學(xué)學(xué)科走向遠(yuǎn)離其經(jīng)驗(yàn) 泉源或更遠(yuǎn)些時(shí) 當(dāng)這門(mén)學(xué)科進(jìn)入第二代 第三代 僅能依靠來(lái)自 現(xiàn)實(shí) 思想的間接的啟迪時(shí) 它就會(huì) 被很?chē)?yán)重的困難所包圍 它變得越來(lái)越純審美的 越來(lái)越純粹地為藝術(shù)而藝術(shù)的 當(dāng)然 這也不一定 是壞事 因?yàn)檫@個(gè)領(lǐng)域可能仍然與那些更接近經(jīng)驗(yàn) 的有關(guān)學(xué)科交融著 或者這個(gè)學(xué)科處在具有極高鑒 賞能力的人們的影響之下 但是存在著很大的危 險(xiǎn) 這個(gè)領(lǐng)域會(huì)沿著最省力的方向再向前發(fā)展 這 條發(fā)自源頭的川流會(huì)分道為數(shù)目眾多的無(wú)意義的 支流 這個(gè)學(xué)科將會(huì)成為既瑣碎又復(fù)雜的一團(tuán)雜亂 無(wú)章之物 換句話(huà)說(shuō) 在遠(yuǎn)離其經(jīng)驗(yàn)泉源之后 在 過(guò)于 抽象的 內(nèi)部繁殖之后 一個(gè)數(shù)學(xué)學(xué)科處于退 化的危險(xiǎn)之中 不論怎樣 只要到了這個(gè)地步 我 認(rèn)為唯一的解決辦法就是使之返老還童 回到其 源 回到或多或少的直接經(jīng)驗(yàn)的概念 我確信這樣 做是使這門(mén)學(xué)科保持新鮮的生命力的必要條件 這 一點(diǎn)在未來(lái)仍將是正確的 著名數(shù)學(xué)家韋爾 6 也曾經(jīng)說(shuō)道 當(dāng)一個(gè)數(shù)學(xué)分 支不再引起除去其專(zhuān)家以外的任何人的興趣時(shí) 這 分支就快要僵死了 只有把它重新栽入生氣勃勃的 科學(xué)土壤之中才能挽救它 這實(shí)際上也指出了運(yùn) 籌學(xué)研究一旦脫離現(xiàn)實(shí)世界將給其發(fā)展帶來(lái)的后 果 如何才能使得運(yùn)籌學(xué)保持活力 使其健康發(fā)展 呢 美國(guó)的運(yùn)籌學(xué)發(fā)展自始至終處于世界領(lǐng)先地 位 他們?cè)谶\(yùn)籌學(xué)的研究和應(yīng)用中所積累的豐富經(jīng) 驗(yàn)值得借鑒 庫(kù)珀 美國(guó)管理科學(xué)學(xué)會(huì)首任主席 8 回憶他與查尼斯等人開(kāi)展線(xiàn)性規(guī)劃在工業(yè)領(lǐng)域的 應(yīng)用時(shí)提到 他們兩位馮 諾伊曼理論獎(jiǎng)獲得者在 長(zhǎng)期合作中形成了 應(yīng)用驅(qū)動(dòng)理論 的運(yùn)籌學(xué)研究 方法 首先解決提出的問(wèn)題并導(dǎo)致成功的應(yīng)用 然后為了完善 擴(kuò)展與推廣這一應(yīng)用去研究文獻(xiàn) 最后將這些進(jìn)一步描述 獲得結(jié)果寫(xiě)成文章發(fā)表 并且報(bào)告應(yīng)用的結(jié)果 此外轉(zhuǎn)向更進(jìn)一步的應(yīng)用 等等 3 運(yùn)籌學(xué)發(fā)展?fàn)顩r 60多年以來(lái) 運(yùn)籌學(xué)在研究與解決復(fù)雜的實(shí) 148 院刊 際問(wèn)題中不斷地發(fā)展和創(chuàng)新 各種各樣的新 模型 新理論和新算法不斷涌現(xiàn) 有線(xiàn)性的 和非線(xiàn)性的 連續(xù)的和離散的 確定性的和 不確定性的 至今它已成為一個(gè)龐大的 包 含多個(gè)分支的學(xué)科 5 其中一些已經(jīng)發(fā)展得 比較成熟 另外一些還有待完善 還有一些 才剛剛形成 3 1 數(shù)學(xué)規(guī)劃 數(shù)學(xué)規(guī)劃是在決策變量滿(mǎn)足一定約束 下求一個(gè)或多個(gè)函數(shù)的極小值或者極大 值 它以大量實(shí)踐中抽象出來(lái)的典型最優(yōu) 化模型為研究對(duì)象 利用數(shù)學(xué)工具研究這些 模型的數(shù)學(xué)性質(zhì) 構(gòu)造與實(shí)現(xiàn)求解方法 以 及將算法應(yīng)用于實(shí)際問(wèn)題 自從1939年康 托羅維奇提出線(xiàn)性規(guī)劃模型 1947年丹齊格 提出求解線(xiàn)性規(guī)劃問(wèn)題的單純形法 卡羅胥 和庫(kù)恩與塔克先后分別獨(dú)立地給出一般非 線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)性條件以來(lái) 數(shù)學(xué)規(guī)劃 得到了快速發(fā)展 形成了多個(gè)分支 3 1 1 線(xiàn)性規(guī)劃 自1939年蘇聯(lián)數(shù)學(xué)家康托羅維奇提出 線(xiàn)性規(guī)劃問(wèn)題和1947年美國(guó)數(shù)學(xué)家丹齊格 求解線(xiàn)性規(guī)劃問(wèn)題的通用方法 單純形 法以來(lái) 線(xiàn)性規(guī)劃可以說(shuō)是研究得最為透徹 的一個(gè)研究方向 單純形法統(tǒng)治線(xiàn)性規(guī)劃 領(lǐng)域達(dá)40年之久 而且至今仍是最好的應(yīng)用 最廣泛的算法之一 雖然它在最壞情況具 有指數(shù)復(fù)雜性 但在平均意義下已經(jīng)證明是 一個(gè)多項(xiàng)式算法 目前 關(guān)于單純形算法的 研究主要在于如何選取主元 另一大類(lèi)算 法是內(nèi)點(diǎn)法 它起源于1979年蘇聯(lián)數(shù)學(xué)家卡 奇揚(yáng)提出的多項(xiàng)式橢球算法 而因1984年美 籍印度裔數(shù)學(xué)家卡瑪卡提出的多項(xiàng)式時(shí)間 算法而迅速成為國(guó)際熱點(diǎn) 各式各樣的算法 大量涌現(xiàn) 諸如仿射變換法 勢(shì)函數(shù)方法 對(duì) 數(shù)罰函數(shù)法 路徑跟蹤法 原始對(duì)偶法 不可 行內(nèi)點(diǎn)法等等 目前線(xiàn)性規(guī)劃的內(nèi)點(diǎn)法也 趨于成熟 這方面的研究者們目前大都致力 于以線(xiàn)性規(guī)劃作為特例的錐規(guī)劃 以及如何 利用線(xiàn)性規(guī)劃松弛求解整數(shù)規(guī)劃等方面的 研究 然而 就線(xiàn)性規(guī)劃而言 是否存在強(qiáng) 多項(xiàng)式算法仍然是一個(gè)重要且困難的理論 問(wèn)題 3 1 2 非線(xiàn)性規(guī)劃 等式約束規(guī)劃問(wèn)題的最優(yōu)性條件可追 溯到拉格朗日 一般非線(xiàn)性規(guī)劃問(wèn)題的最優(yōu) 性條件則歸功于卡羅胥和庫(kù)恩與塔克 是他 們奠定了非線(xiàn)性規(guī)劃的理論基礎(chǔ) 然而 目 前還有不少人試圖在沒(méi)有強(qiáng)互補(bǔ)的條件下 進(jìn)行理論分析和算法研究 對(duì)偶理論是非 線(xiàn)性規(guī)劃理論研究的另一個(gè)重點(diǎn) 在計(jì)算 方法方面 早期的方法以最速下降法和牛頓 法為主 1959年擬牛頓法的引入和1964年 非線(xiàn)性共軛梯度法的出現(xiàn) 吸引了許多研究 者研究非線(xiàn)性規(guī)劃 目前 序列二次規(guī)劃算 法是一類(lèi)被用于廣泛求解一般非線(xiàn)性規(guī)劃 的有效算法 同時(shí)也還有許多研究者在為改 善這類(lèi)算法努力 其中包括序列線(xiàn)性規(guī)劃算 法以及內(nèi)點(diǎn)算法等 非線(xiàn)性規(guī)劃算法通常 使用線(xiàn)搜索策略選取步長(zhǎng) 或通過(guò)求解信賴(lài) 域子問(wèn)題而得到新的迭代點(diǎn) 這兩個(gè)方面 的研究非?；?但仍有改善的空間 2001 年弗萊徹和勒斐通過(guò)將非線(xiàn)性規(guī)劃問(wèn)題視 為雙目標(biāo)問(wèn)題而提出的濾子方法和2002年 鮑威爾提出的基于二次插值的直接法是近 些年來(lái)兩個(gè)重要的算法進(jìn)展 對(duì)于約束規(guī) 劃問(wèn)題 如何推廣鮑威爾的直接法 對(duì)于大 規(guī)模問(wèn)題 如何設(shè)計(jì)子空間算法 以及如何 有效求解一般非線(xiàn)性規(guī)劃的全局最優(yōu) 和一 些來(lái)自于圖像處理等領(lǐng)域的特殊的非光滑 問(wèn)題是目前非線(xiàn)性規(guī)劃比較重要的研究問(wèn) 題 總之 盡管在表面上看非線(xiàn)性規(guī)劃已經(jīng) 有許許多多的研究 但由于非線(xiàn)性的存在 好的研究結(jié)果還將會(huì)不斷出現(xiàn) 并且隨著問(wèn) 運(yùn)籌學(xué)發(fā)展的回顧與展望 149 2012年 第27卷 第2期 學(xué)科發(fā)展 Disciplinary Development 題的不同而產(chǎn)生更加具有針對(duì)性的特殊算法 3 1 3 錐規(guī)劃 錐規(guī)劃是線(xiàn)性空間中凸錐上的數(shù)學(xué)規(guī)劃 它是 線(xiàn)性規(guī)劃與非線(xiàn)性規(guī)劃的推廣 自上世紀(jì)90年代 中期開(kāi)始 它一直是國(guó)際優(yōu)化領(lǐng)域的研究熱點(diǎn) 相 關(guān)的研究帶動(dòng)了數(shù)學(xué)規(guī)劃學(xué)科的深入發(fā)展 促進(jìn)了 代數(shù) 群論 拓?fù)鋵W(xué) 幾何學(xué) 非線(xiàn)性分析等分支在 數(shù)學(xué)規(guī)劃中的融合 以及優(yōu)化理論與技術(shù)在工程 交通 經(jīng)濟(jì)與金融 管理等領(lǐng)域的廣泛應(yīng)用 目前的錐規(guī)劃方面的研究成果主要包括以下 4個(gè)方面 1 二階錐優(yōu)化和半定優(yōu)化 線(xiàn)性二階 錐優(yōu)化和半定優(yōu)化已經(jīng)得到了很好的發(fā)展 并且廣 泛地應(yīng)用于各種實(shí)際問(wèn)題 近些年 人們開(kāi)始致力 于非線(xiàn)性二階錐優(yōu)化和非線(xiàn)性半定優(yōu)化的理論與 算法研究 2 對(duì)稱(chēng)錐優(yōu)化 上世紀(jì)末國(guó)際優(yōu)化專(zhuān) 家開(kāi)始致力于這一領(lǐng)域的研究 主要集中在求解對(duì) 稱(chēng)錐上線(xiàn)性?xún)?yōu)化問(wèn)題的內(nèi)點(diǎn)算法方面 近幾年 人 們開(kāi)始探討對(duì)稱(chēng)錐上的非線(xiàn)性?xún)?yōu)化問(wèn)題和非凸優(yōu) 化問(wèn)題的理論與各種算法 3 齊次錐優(yōu)化 齊次 錐的理論早在1963年就有相關(guān)研究 但齊次錐優(yōu) 化問(wèn)題的研究最近才開(kāi)始 4 雙曲錐優(yōu)化 這方 面目前只有很少的理論研究 需要尋求合適的工具 開(kāi)展其理論與算法的研究 3 1 4 矩陣規(guī)劃 在眾多的科學(xué)領(lǐng)域與社會(huì)經(jīng)濟(jì)中 很多優(yōu)化問(wèn) 題的決策變量是一個(gè)具有特殊結(jié)構(gòu)的矩陣 這樣的 優(yōu)化問(wèn)題被稱(chēng)為矩陣優(yōu)化或者矩陣規(guī)劃 矩陣規(guī) 劃的早期研究可以追溯到1981年 然而真正的研 究是在20世紀(jì)90年代 它以被譽(yù)為21世紀(jì)的線(xiàn)性 規(guī)劃 半定規(guī)劃為研究起點(diǎn) 至今 線(xiàn)性半定規(guī)劃 的理論趨于完善 人們正在發(fā)掘它在實(shí)際中的應(yīng) 用 然而 目前的數(shù)值軟件只能有效地求解矩陣維 數(shù)小于500的小規(guī)模線(xiàn)性半定規(guī)劃問(wèn)題 因此 開(kāi) 展大規(guī)模半定規(guī)劃的數(shù)值方法研究是當(dāng)前一項(xiàng)十 分迫切而又重要的課題 此外 由著名華裔數(shù)學(xué)家 陶哲軒等人在2006年提出的壓縮傳感理論而引發(fā) 的低秩矩陣問(wèn)題 其理論與算法研究是當(dāng)今優(yōu)化領(lǐng) 域與信息科學(xué)領(lǐng)域 例如 信號(hào)處理 圖像恢復(fù)與重 建 共同關(guān)心的熱點(diǎn)研究課題 在未來(lái)一段時(shí)期 里 矩陣 錐 優(yōu)化理論與算法 張量 錐 優(yōu)化理論 與算法 多項(xiàng)式優(yōu)化理論與算法研究等方向必將引 起人們的關(guān)注 3 1 5 變分不等式與互補(bǔ)問(wèn)題 變分不等式與互補(bǔ)問(wèn)題是一類(lèi)具有普遍意義 的均衡優(yōu)化模型 它不僅為非線(xiàn)性?xún)?yōu)化 極大極 小 對(duì)策論 非線(xiàn)性方程 微分方程等提供了一個(gè)統(tǒng) 一的理論框架 而且在力學(xué)工程 交通 經(jīng)濟(jì) 管理 等實(shí)際部門(mén)有廣泛的應(yīng)用 互補(bǔ)問(wèn)題首先由丹齊 格和科特爾于1963年提出 次年 科特爾在他的 博士論文中第一次提出求解它的非線(xiàn)性規(guī)劃算 法 變分不等式問(wèn)題首先由哈特曼和斯塔姆巴切 在1966年提出 后來(lái)發(fā)現(xiàn) 變分不等式是互補(bǔ)問(wèn) 題的一個(gè)推廣 且其數(shù)學(xué)性質(zhì)和應(yīng)用有驚人的相似 之處 所以 它們經(jīng)常在文獻(xiàn)中成對(duì)出現(xiàn) 變分不 等式與互補(bǔ)問(wèn)題被提出后 很快引起了當(dāng)時(shí)運(yùn)籌學(xué) 界和應(yīng)用數(shù)學(xué)界的廣泛關(guān)注和濃厚興趣 許多人參 與了這類(lèi)問(wèn)題的研究 經(jīng)過(guò)40余年的探索 特別 是20世紀(jì)最后10年的研究 人們?cè)诶碚撆c算法方 面取得了豐富 系統(tǒng)的成果 并在科技與經(jīng)濟(jì)中得 到了廣泛的應(yīng)用 當(dāng)前主要是對(duì)于廣義變分不等式和錐互補(bǔ)問(wèn) 題的研究 而對(duì)于不確定信息下變分不等式和互補(bǔ) 問(wèn)題的研究無(wú)疑是發(fā)展的必然 歸納起來(lái) 對(duì)它們 的研究可分為理論與算法兩方面 前者主要研究解 的存在性 唯一性 穩(wěn)定性與靈敏度分析以及它們 與其他數(shù)學(xué)問(wèn)題的聯(lián)系等 后者則主要建立有效的 求解方法及相應(yīng)的理論和數(shù)值分析 3 1 6 整數(shù)規(guī)劃 整數(shù)規(guī)劃是帶整數(shù)變量的最優(yōu)化問(wèn)題 即求解 一個(gè)全部或部分變量為整數(shù)的多元函數(shù)受約束于 一組等式和不等式條件的最優(yōu)化問(wèn)題 整數(shù)規(guī)劃 的歷史可以追溯到上世紀(jì)50年代 丹齊格首先發(fā) 現(xiàn)可以用0 1變量來(lái)刻畫(huà)最優(yōu)化模型中的固定費(fèi) 用 變量上界 非凸分片線(xiàn)性函數(shù)等 他和富爾克 150 院刊 森 約翰遜對(duì)旅行商問(wèn)題的研究成為后來(lái)分 支定界法和現(xiàn)代混合整數(shù)規(guī)劃算法的開(kāi) 端 1958年戈莫里發(fā)現(xiàn)了第一個(gè)一般線(xiàn)性 整數(shù)規(guī)劃的收斂算法 割平面方法 隨著整 數(shù)規(guī)劃理論和算法的發(fā)展 整數(shù)規(guī)劃已成為 應(yīng)用最廣泛的最優(yōu)化方法之一 特別是近年 來(lái)整數(shù)規(guī)劃算法技術(shù)和軟件系統(tǒng)的發(fā)展和 推廣 整數(shù)規(guī)劃得到了廣泛的應(yīng)用和發(fā)展 整數(shù)規(guī)劃問(wèn)題的困難和挑戰(zhàn)來(lái)源于3個(gè) 方面 一是大部分整數(shù)規(guī)劃問(wèn)題都是NP 難 的 故本質(zhì)上不太可能存在和線(xiàn)性規(guī)劃與凸 規(guī)劃一樣有效的算法 二是對(duì)整數(shù)點(diǎn)集合 如多面體格點(diǎn)理論和全單模理論 和整數(shù) 變量的函數(shù)在數(shù)學(xué)上缺乏有力的理論和工 具 三是實(shí)際問(wèn)題的規(guī)模往往超過(guò)現(xiàn)有算法 的求解能力 盡管現(xiàn)有的一些整數(shù)規(guī)劃軟件 可以求解任意線(xiàn)性 二次和非線(xiàn)性整數(shù)規(guī)劃 問(wèn)題 但往往不能處理來(lái)源于實(shí)際問(wèn)題的整 數(shù)規(guī)劃模型 例如運(yùn)輸和交通中的大規(guī)模 0 1混合線(xiàn)性整數(shù)規(guī)劃問(wèn)題 金融優(yōu)化中的 離散約束問(wèn)題等 整數(shù)規(guī)劃未來(lái)發(fā)展方向 和關(guān)鍵問(wèn)題包括 1 整數(shù)多面體凸包的刻 畫(huà) 2 隨機(jī)整數(shù)規(guī)劃 3 多層整數(shù)規(guī)劃 4 混合 0 1 二次整數(shù)規(guī)劃 5 協(xié)正規(guī)劃 6 半定整數(shù)規(guī)劃 3 1 7 動(dòng)態(tài)規(guī)劃 當(dāng)系統(tǒng)模型具備馬爾科夫性 同時(shí)目標(biāo) 函數(shù)可分且嵌套單調(diào)時(shí) 基于貝爾曼提出的 最優(yōu)性原理 運(yùn)用動(dòng)態(tài)規(guī)劃可將求解多階段 全局最優(yōu)決策問(wèn)題分解為一系列在各時(shí)間 段上的局部?jī)?yōu)化問(wèn)題 相比其他解法 特別 是在有擾動(dòng)或在隨機(jī)情況下 動(dòng)態(tài)規(guī)劃總能 有效地提供一個(gè)在當(dāng)前信息集下的最優(yōu)反 饋控制策略 在過(guò)去的若干年里 動(dòng)態(tài)規(guī)劃 取得了不少可喜的進(jìn)展 特別是它被擴(kuò)展到 多目標(biāo)動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃應(yīng)用在本世紀(jì)前 后的一個(gè)重大突破是其在海量數(shù)據(jù)分析中 的應(yīng)用 特別是人類(lèi)基因組計(jì)劃完成以后 它成為生物信息學(xué)的一個(gè)基本模型和工具 然而 在克服被貝爾曼稱(chēng)之為 維數(shù)災(zāi) 的這一動(dòng)態(tài)規(guī)劃致命弱點(diǎn)方面 至今尚未取 得突破性的進(jìn)展 所以尋求克服維數(shù)災(zāi)的 有效算法對(duì)動(dòng)態(tài)規(guī)劃在高維問(wèn)題中的應(yīng)用 具有緊迫性 另外 求解不可分優(yōu)化問(wèn)題得 到的最優(yōu)策略并不滿(mǎn)足最優(yōu)性原理 或不具 備時(shí)間一致性 這牽涉到不可分優(yōu)化問(wèn)題模 型本身的合理性 因此怎樣找出一組可分優(yōu) 化問(wèn)題來(lái)逼近一個(gè)給定的不可分優(yōu)化問(wèn)題 也對(duì)動(dòng)態(tài)規(guī)劃發(fā)展具有它顯然的重要性 3 1 8 向量?jī)?yōu)化 近幾十年來(lái)向量?jī)?yōu)化 亦稱(chēng)多目標(biāo)優(yōu) 化 理論研究有了迅猛發(fā)展 在各種解的存 在性 穩(wěn)定性以及最優(yōu)性條件等方面獲得了 豐富的結(jié)果 并創(chuàng)造性地建立了向量?jī)?yōu)化問(wèn) 題解集的結(jié)構(gòu)定理 連通性定理和稠密性定 理 并被應(yīng)用到經(jīng)濟(jì)問(wèn)題中 通過(guò)向量廣義 凸性的研究 很好地處理了一大類(lèi)非線(xiàn)性向 量?jī)?yōu)化問(wèn)題 通過(guò)提出向量變分不等式模 型 開(kāi)拓了研究向量?jī)?yōu)化問(wèn)題的新方向 由 于向量?jī)?yōu)化中衡量向量 大小 的是不完全 的偏序 致使大量的向量?jī)?yōu)化問(wèn)題沒(méi)有解 甚至在向量目標(biāo)函數(shù)光滑并有下界的情況 下沒(méi)有數(shù)值優(yōu)化意義下的近似解 由于任 何優(yōu)化問(wèn)題算法每一步獲得的迭代項(xiàng)都是 該優(yōu)化問(wèn)題的一個(gè)近似解 因此研究向量?jī)?yōu) 化問(wèn)題近似解的存在性以及拉格朗日和卡 羅胥 庫(kù)恩 塔克等優(yōu)化性條件 仍然是具有 基礎(chǔ)性作用的主要問(wèn)題 也是求解算法的有 力保障 分式向量?jī)?yōu)化問(wèn)題是具有重要經(jīng) 濟(jì)意義的數(shù)學(xué)模型 關(guān)于這類(lèi)模型的求解問(wèn) 題 是今后向量?jī)?yōu)化問(wèn)題研究的重點(diǎn) 利用 次微分 使用變分分析技術(shù)和方法研究非光 滑向量?jī)?yōu)化問(wèn)題 就變分分析和向量?jī)?yōu)化進(jìn) 行交叉研究仍將是未來(lái)很有生命力的方向 運(yùn)籌學(xué)發(fā)展的回顧與展望 151 2012年 第27卷 第2期 學(xué)科發(fā)展 Disciplinary Development 3 1 9 全局優(yōu)化 全局優(yōu)化是非線(xiàn)性規(guī)劃的一個(gè)分支 主要研究 求解非凸優(yōu)化問(wèn)題的全局最優(yōu)或近似全局最優(yōu) 解 由于非凸優(yōu)化問(wèn)題可能存在多個(gè)不同的局部 最優(yōu)點(diǎn) 基于導(dǎo)數(shù)信息的卡羅胥 庫(kù)恩 塔克最優(yōu)性 條件不再適用于刻畫(huà)非凸問(wèn)題的全局最優(yōu)性 從 而 經(jīng)典的局部?jī)?yōu)化方法不能保證收斂到全局最優(yōu) 解 全局優(yōu)化較系統(tǒng)的研究始于上世紀(jì)70年代 圖伊和霍斯特是早期全局優(yōu)化研究的先驅(qū)者 他們 在凹規(guī)劃的系統(tǒng)研究成果使全局優(yōu)化開(kāi)始形成一 個(gè)真正的學(xué)科 90年代初全局優(yōu)化作為非線(xiàn)性規(guī) 劃的一個(gè)分支開(kāi)始受到廣泛的關(guān)注 越來(lái)越多的研 究者開(kāi)始從事該領(lǐng)域的研究 特別是對(duì)一些具有特 殊結(jié)構(gòu)的非凸優(yōu)化問(wèn)題的研究取得了許多突破性 的成果 如非凸二次規(guī)劃 非凸多項(xiàng)式規(guī)劃 機(jī)會(huì)約 束問(wèn)題的凸逼近 以及在實(shí)際應(yīng)用中遇到的許多特 殊形式的非凸優(yōu)化問(wèn)題的研究都有很多深刻的研 究成果 一些基于分支 定界的全局優(yōu)化通用軟件 的發(fā)展及其在優(yōu)化建模系統(tǒng)中的嵌入應(yīng)用使學(xué)術(shù) 界和工業(yè)界可以方便地求解一定規(guī)模的非凸問(wèn)題 的全局解 全局優(yōu)化問(wèn)題的困難在于非凸性使卡羅胥 庫(kù) 恩 塔克條件一般不足以保證全局最優(yōu)性 從而我 們無(wú)法利用局部?jī)?yōu)化算法尋找全局最優(yōu)點(diǎn) 本質(zhì) 上 由于導(dǎo)數(shù)是局部性質(zhì) 因而不能期望基于導(dǎo)數(shù) 性質(zhì)的傳統(tǒng)優(yōu)化算法有希望求到全局解 全局算法 需要函數(shù)和問(wèn)題的全局性質(zhì) 目前的數(shù)學(xué)理論很 難或無(wú)法刻畫(huà)一般多元函數(shù)的全局性質(zhì) 這是全局 優(yōu)化問(wèn)題的本質(zhì)困難所在 全局優(yōu)化的未來(lái)發(fā)展 方向和關(guān)鍵問(wèn)題包括 1 凸逼近和凸松弛方法 2 非凸二次規(guī)劃 3 基于模擬仿真技術(shù)的全局優(yōu) 化算法 4 特殊結(jié)構(gòu)的全局優(yōu)化問(wèn)題 除了上面所介紹的9個(gè)分支外 數(shù)學(xué)規(guī)劃在近 些年來(lái)興起了若干新的分支 例如 近10年來(lái)國(guó) 際上對(duì)魯棒優(yōu)化 微分方程所控制的優(yōu)化 多項(xiàng)式 優(yōu)化 稀疏優(yōu)化的研究相當(dāng)重視 這些新方向的研 究十分活躍 在即將舉行的第21屆國(guó)際數(shù)學(xué)規(guī)劃 大會(huì)上這些新興的分支都安排了專(zhuān)題報(bào)告 我國(guó) 數(shù)學(xué)規(guī)劃工作者 特別是青年科技工作者要充分重 視這些新的方向 力爭(zhēng)在國(guó)際上剛剛起步階段參與 研究 這樣就有可能很快占領(lǐng)國(guó)際制高點(diǎn) 3 2 組合優(yōu)化 組合優(yōu)化是20世紀(jì)60年代逐漸發(fā)展起來(lái)的一 個(gè)交叉學(xué)科分支 它的研究對(duì)象是有限集合上的極 值問(wèn)題 一個(gè)組合優(yōu)化問(wèn)題由3部分構(gòu)成 已知條 件的輸入 可行解的描述 目標(biāo)函數(shù)的定義 經(jīng)典 的組合優(yōu)化問(wèn)題包括網(wǎng)絡(luò)流 旅行商 排序 裝箱 著色 覆蓋 最短網(wǎng)絡(luò)等等 組合優(yōu)化的一個(gè)理論 基礎(chǔ)是計(jì)算復(fù)雜性理論 據(jù)此組合優(yōu)化可以分為兩 類(lèi) P 問(wèn)題類(lèi)和NP 難問(wèn)題類(lèi) 屬于前者的問(wèn)題有 多項(xiàng)式時(shí)間算法 屬于后者的問(wèn)題一般認(rèn)為不存在 多項(xiàng)式時(shí)間算法 通常采用窮舉法 啟發(fā)式算法和 近似算法等方法求解 組合優(yōu)化與圖論 組合學(xué) 數(shù)理邏輯等有密切關(guān)系 在計(jì)算機(jī)科學(xué) 信息科學(xué) 管理科學(xué)和生命科學(xué)等學(xué)科有廣泛的應(yīng)用 3 2 1 圖論及算法 1736年歐拉解決了哥尼斯堡的七橋問(wèn)題 這 被公認(rèn)為圖論的第一個(gè)結(jié)果 此后的200多年里 圖論并不被視為是數(shù)學(xué)的一個(gè)分支 圖論的問(wèn)題通 常被看作一類(lèi)智力游戲 然而 自上個(gè)世紀(jì)30年 代始 圖論通過(guò)其廣泛的應(yīng)用以及與數(shù)學(xué)其他分支 的緊密聯(lián)系日顯其重要性 尤其是 圖論作為計(jì)算 機(jī)科學(xué)的基礎(chǔ)之一 在運(yùn)籌學(xué)中扮演著不可或缺的 角色 很多非常難解的組合優(yōu)化問(wèn)題都屬于NP 完 全的圖論問(wèn)題 在圖論近幾十年的研究中 學(xué)者們?cè)谌〉靡幌?列重要成果的同時(shí) 提出了包括整數(shù)流 子圖覆蓋 和經(jīng)典拉姆齊函數(shù)的估值在內(nèi)的許多猜想或未解 的難題 未來(lái)受人關(guān)注的一些課題包括 3 1 圖論 中大多數(shù)結(jié)果都可以推廣到超圖中 通常推廣方式 不止一種 相應(yīng)的超圖問(wèn)題有很多沒(méi)有解決 對(duì) 超圖的相應(yīng)性質(zhì)和問(wèn)題的研究不僅僅可以發(fā)現(xiàn)新 的有意義的研究課題 而且還有助于解決圖論中的 一些已有問(wèn)題 2 對(duì)隨機(jī)圖的一些特殊性質(zhì)的刻 152 院刊 畫(huà) 特別是隨機(jī)圖在生成的過(guò)程中 其結(jié)構(gòu) 有時(shí)會(huì)發(fā)生突變 這種變化常常與日常的某 種物理現(xiàn)象相關(guān) 對(duì)這種相變現(xiàn)象的研究是 非常具有挑戰(zhàn)性的課題 3 對(duì)超大圖或者 無(wú)限網(wǎng)絡(luò)的研究將是圖論的一個(gè)新熱點(diǎn)方 向 它有廣泛的應(yīng)用背景 其中包括實(shí)實(shí)在 在的計(jì)算機(jī)通訊網(wǎng)絡(luò) 無(wú)形而無(wú)處不在的萬(wàn) 維網(wǎng) 基于因特網(wǎng)的社交網(wǎng)絡(luò) 人腦的神經(jīng) 網(wǎng)絡(luò)等等 對(duì)這些超大圖性質(zhì)的研究 需要 新的數(shù)學(xué)工具 引入連續(xù)化方法 讓這些超 大圖趨于 無(wú)窮 然后研究其 極限圖 的性 質(zhì) 是一個(gè)探索方向 這一方向同目前受到 物理學(xué)界 控制論界重視的 復(fù)雜網(wǎng)絡(luò) 研究 相重合 3 2 2 近似算法設(shè)計(jì)與分析 近似算法是求解組合優(yōu)化問(wèn)題的一類(lèi) 多項(xiàng)式時(shí)間算法 它們盡管不能確保對(duì)問(wèn)題 的每一個(gè)實(shí)例都可以求得最優(yōu)解 但是可以 保證求得的解的目標(biāo)值與最優(yōu)解的目標(biāo)值 相差不多 自上世紀(jì)60年代末格雷厄姆在 研究排序問(wèn)題時(shí)提出第一個(gè)近似算法以后 特別是70年代初庫(kù)克首次證明了存在NP 完全問(wèn)題以來(lái) 為各種各樣的組合優(yōu)化問(wèn)題 設(shè)計(jì)近似算法就一直是組合優(yōu)化領(lǐng)域的一 個(gè)重要研究方向 它主要包括3個(gè)方面 設(shè) 計(jì)近似比越來(lái)越小的近似算法 設(shè)計(jì)運(yùn)行時(shí) 間越來(lái)越短的近似算法 證明近似比的下界 或者不可近似性 已有的大量研究主要都 集中在第一個(gè)方面 人們先后提出了對(duì)偶 半定規(guī)劃 隨機(jī)算法 平面劃分和次模函數(shù) 等技巧 第二方面的工作主要是針對(duì)存在 多項(xiàng)式時(shí)間近似方案的NP 難問(wèn)題 而第三 方面的工作主要是利用上個(gè)世紀(jì)90年代阿 羅拉等人提出的概率可驗(yàn)證明系統(tǒng) 這一 方向中有很多問(wèn)題有待解決 3 2 3 組合多面體 給定一個(gè)線(xiàn)性系統(tǒng) 判定其是否定義了 一個(gè)整數(shù)多面體 是否為全對(duì)偶整數(shù)系統(tǒng) 是否為盒式對(duì)偶整數(shù)系統(tǒng) 這3個(gè)判定問(wèn)題 是整數(shù)規(guī)劃的核心問(wèn)題 也構(gòu)成了組合多面 體理論的基本內(nèi)容 這是因?yàn)楫?dāng)一個(gè)整數(shù)規(guī) 劃實(shí)例是由一個(gè)整數(shù)多面體所定義的 那么 它可以在多項(xiàng)式時(shí)間內(nèi)求解 一般的整數(shù)規(guī) 劃是NP 難解的 包括羅瓦茲 施瓦維爾和 埃德蒙茲在內(nèi)的許多著名數(shù)學(xué)家都研究過(guò) 組合多面體的結(jié)構(gòu)刻畫(huà) 計(jì)算復(fù)雜性等相關(guān) 問(wèn)題 另外 由于很多組合優(yōu)化問(wèn)題都可以 非常容易地表示為整數(shù)規(guī)劃問(wèn)題 因而這些 問(wèn)題也是組合優(yōu)化的重要研究課題 比如 組合優(yōu)化中的一大類(lèi)問(wèn)題都可以用超圖中 的裝填問(wèn)題和覆蓋問(wèn)題來(lái)描述 裝填問(wèn)題是 求含有邊數(shù)最多的裝填 而覆蓋問(wèn)題是求一 個(gè)頂點(diǎn)覆蓋其中所有頂點(diǎn)的權(quán)值之和最 小 已經(jīng)知道裝填問(wèn)題和覆蓋問(wèn)題都是NP 難解的 因此除非P NP 它們都不存在多項(xiàng) 式時(shí)間的算法 這兩個(gè)組合優(yōu)化問(wèn)題都可 以通過(guò)組合多面體的理論和方法研究 特別 是 有向圖和無(wú)向圖上的圈裝填和覆蓋對(duì)偶 關(guān)系以及有向圖上的裝填和反饋集覆蓋對(duì) 偶關(guān)系 3 2 4 生物分子網(wǎng)絡(luò) 生物分子網(wǎng)絡(luò)是系統(tǒng)生物學(xué)的基本出 發(fā)點(diǎn)和主要研究對(duì)象 因?yàn)閺南到y(tǒng)的觀點(diǎn) 看 生命系統(tǒng)是通過(guò)基因之間 蛋白之間 代 謝物之間以及基因 蛋白質(zhì) 代謝物 環(huán)境與 功能和表象之間的相互作用來(lái)運(yùn)行的 正是 這些相互作用確定了細(xì)胞 組織 器官和生 物個(gè)體的動(dòng)態(tài)行為 所以系統(tǒng)生物學(xué)的根 本挑戰(zhàn)在于建立完整的 細(xì)致的生物分子間 聯(lián)系的描述 并籍此在分子水平及系統(tǒng)的觀 點(diǎn)來(lái)探索生命機(jī)理 解釋復(fù)雜生命現(xiàn)象 最 優(yōu)化理論包括連續(xù)優(yōu)化 組合優(yōu)化和網(wǎng)絡(luò)優(yōu) 化等運(yùn)籌學(xué)方法和理論在生物分子網(wǎng)絡(luò)的 研究中都起到了重要作用 典型的研究?jī)?nèi) 運(yùn)籌學(xué)發(fā)展的回顧與展望 153 2012年 第27卷 第2期 學(xué)科發(fā)展 Disciplinary Development 容和問(wèn)題包括 基因調(diào)控網(wǎng)絡(luò)和蛋白質(zhì)相互作用網(wǎng) 絡(luò)的數(shù)學(xué)建模 從生物進(jìn)化角度出發(fā)的生物分子網(wǎng) 絡(luò)進(jìn)化模型和算法 從高通量生物實(shí)驗(yàn)數(shù)據(jù)出發(fā)的 網(wǎng)絡(luò)重構(gòu)算法 著眼于功能預(yù)測(cè)與標(biāo)注的基因蛋白 功能聯(lián)系網(wǎng)絡(luò)的構(gòu)建和分析 以及生物分子網(wǎng)絡(luò)的 功能模塊探測(cè) 網(wǎng)絡(luò)比對(duì)等系統(tǒng)生物學(xué)和生物信息 學(xué)算法 這些研究可以用于蛋白質(zhì)功能預(yù)測(cè)和注 釋 以及進(jìn)一步地為研究某些與特殊疾病相關(guān)的蛋 白質(zhì)功能注釋提供有效的工具 3 3 隨機(jī)最優(yōu)化 隨機(jī)最優(yōu)化問(wèn)題是特指帶有隨機(jī)因素的最優(yōu) 化問(wèn)題 需要利用概率統(tǒng)計(jì) 隨機(jī)過(guò)程以及隨機(jī)分 析等工具 所謂的隨機(jī)因素 包括環(huán)境的隨機(jī)因 素 控制變量不確定因素 準(zhǔn)則值的不確定因素等 等 例如 在考慮水庫(kù)優(yōu)化調(diào)度問(wèn)題的時(shí)候 天然 來(lái)水一般是三階皮爾遜分布的隨機(jī)變量 在考慮 庫(kù)存管理問(wèn)題時(shí) 變動(dòng)的需求常常考慮為外生的隨 機(jī)變量 這些都屬于環(huán)境的不確定因素 在排隊(duì) 系統(tǒng)中服務(wù)速率確定后 真實(shí)的服務(wù)時(shí)間依然是隨 機(jī)變化的 這屬于控制變量的不確定因素 使用藥 物最終能夠達(dá)到的效果往往不是確定的 評(píng)判最優(yōu) 的值函數(shù)在很多問(wèn)題中也具有不確定性等等 通 常人們處理隨機(jī)因素的方式有期望值方法 將隨機(jī) 的因素用它的期望值代替 將問(wèn)題轉(zhuǎn)化為確定性問(wèn) 題考慮 第二種方法是在概率意義下考慮優(yōu)化問(wèn) 題 例如在置信區(qū)間范圍內(nèi)考慮優(yōu)化問(wèn)題 將問(wèn)題 轉(zhuǎn)換為概率約束或者是機(jī)會(huì)約束的優(yōu)化問(wèn)題 又例 如考慮極大化某些事件的概率問(wèn)題 也稱(chēng)為相關(guān)機(jī) 會(huì)約束問(wèn)題 第二種方法相對(duì)于期望值方法的優(yōu) 點(diǎn)是考慮到各種風(fēng)險(xiǎn)的影響 缺點(diǎn)是使得問(wèn)題的處 理變得相對(duì)困難 3 3 1 排隊(duì)論 排隊(duì)論模型被人們廣泛用于半導(dǎo)體生產(chǎn)加工 與設(shè)計(jì) 計(jì)算機(jī)通訊網(wǎng)絡(luò) 交通運(yùn)輸?shù)刃袠I(yè) 隨著 科學(xué)技術(shù)的發(fā)展 描述上述類(lèi)型的排隊(duì)網(wǎng)絡(luò)變得極 為復(fù)雜 使得與傳統(tǒng)的排隊(duì)網(wǎng)絡(luò)有很多本質(zhì)的區(qū) 別 當(dāng)今人們對(duì)復(fù)雜的隨機(jī)排隊(duì)網(wǎng)絡(luò)關(guān)心的問(wèn)題 有 3 個(gè) 1 遍歷性問(wèn)題 即給定一個(gè)隨機(jī)排隊(duì)網(wǎng) 絡(luò) 若網(wǎng)絡(luò)中每一服務(wù)臺(tái)的服務(wù)強(qiáng)度嚴(yán)格小于1 那么描述系統(tǒng)的馬氏過(guò)程是不是遍歷 2 在便利 條件下 當(dāng)每一服務(wù)臺(tái)服務(wù)強(qiáng)度趨向于1 描述系 統(tǒng)的指標(biāo)如隊(duì)長(zhǎng) 等待時(shí)間其擴(kuò)散逼近是不是存 在 3 在遍歷的條件下如何找出最優(yōu)的服務(wù)規(guī) 則 第一個(gè)問(wèn)題歸結(jié)為針對(duì)排隊(duì)系統(tǒng) 找出構(gòu)造李 雅普諾夫函數(shù)的一般有效方法 第二個(gè)問(wèn)題的解決 歸結(jié)為具有可料性的動(dòng)態(tài)補(bǔ)問(wèn)題 3 3 2 馬氏決策的理論研究 隨著人們對(duì)實(shí)際問(wèn)題的深入理解 馬氏決策理 論的應(yīng)用范疇越來(lái)越廣泛 因此 提出的馬氏決策 理論問(wèn)題越來(lái)越具有特殊性和廣泛性 研究特殊 結(jié)構(gòu)的馬氏決策理論越來(lái)越具有重要的意義 例 如大規(guī)模對(duì)抗與合作系統(tǒng)的問(wèn)題 金融監(jiān)管的需 求 一般監(jiān)管理論的研究等等 都為馬氏決策理論 帶來(lái)了新挑戰(zhàn) 非標(biāo)準(zhǔn)準(zhǔn)則的深入研究是應(yīng)對(duì)這 些需求的必要條件 如有超大狀態(tài)空間問(wèn)題的求解 問(wèn)題 帶有納什均衡的多階段決策問(wèn)題 帶有適應(yīng) 性參數(shù)影響的非時(shí)齊問(wèn)題等等 這些研究工作對(duì) 于國(guó)民經(jīng)濟(jì)中的重大問(wèn)題研究有著重要的幫助 3 3 3 復(fù)雜系統(tǒng)可靠性理論 現(xiàn)代化技術(shù)和設(shè)備的飛速發(fā)展和更新 使得人 們面對(duì)的系統(tǒng)越來(lái)越復(fù)雜 而誘發(fā)了許多人們無(wú)法 理解的現(xiàn)象 例如 利用原來(lái)的系統(tǒng)可靠性理論得 到的可靠性與實(shí)際系統(tǒng)人們感覺(jué)到的完全不同 如何發(fā)展相關(guān)的數(shù)學(xué)分析工具以解釋這些問(wèn)題就 顯得非常重要 在人們已經(jīng)做出的工作中 出現(xiàn)一 些有意義研究 例如 功能相依性分析 功能冗余性 研究 概率理論的深入研究等等 因此 如何將系 統(tǒng)可靠性理論的結(jié)論和方法上升到解決復(fù)雜系統(tǒng) 可靠性問(wèn)題是核心的難點(diǎn) 3 3 4 軟件可靠性理論 軟件是隨著計(jì)算機(jī)硬件的誕生產(chǎn)生的 其重要 程度是不言而喻 現(xiàn)在已經(jīng)成為人們生活中必不可 缺的成分 特別是科技水平越高 就越離不開(kāi)軟件 的支持 由于軟件系統(tǒng)的高度復(fù)雜性 其復(fù)雜程度 154 院刊 遠(yuǎn)遠(yuǎn)高于通常的復(fù)雜系統(tǒng) 事實(shí)上 軟件系 統(tǒng)往往不是一個(gè)有限的系統(tǒng)了 導(dǎo)致了人們 通常在系統(tǒng)可靠性中使用的方法完全無(wú) 效 人們有必要探索有效的相關(guān)理論 特別 是數(shù)學(xué)工具 以有效地研究軟件可靠性問(wèn) 題 事實(shí)上 將軟件可靠性問(wèn)題與軟件測(cè)試 過(guò)程結(jié)合是一種有效的方法 一方面 可以 有效地指導(dǎo)軟件的測(cè)試過(guò)程 目前 用于軟 件測(cè)試的費(fèi)用已經(jīng)占到整個(gè)軟件開(kāi)發(fā)費(fèi)用 的50 一方面 可以正確地評(píng)估軟件的可 靠性 將測(cè)試過(guò)程與軟件可靠性分析結(jié)合 的過(guò)程中 人們發(fā)現(xiàn)必須發(fā)展諸如隨機(jī)過(guò) 程 排隊(duì)理論 馬氏決策理論以及相關(guān)的數(shù) 學(xué)方法 以適用于分析軟件的問(wèn)題 3 3 5 供應(yīng)鏈的優(yōu)化設(shè)計(jì) 隨機(jī)環(huán)境下的復(fù)雜供應(yīng)鏈系統(tǒng)的優(yōu)化 與設(shè)計(jì)問(wèn)題是從管理科學(xué)中提出的數(shù)學(xué)問(wèn) 題 與傳統(tǒng)的供應(yīng)鏈模型相比 描述系統(tǒng)的 隨機(jī)性不再由簡(jiǎn)單的普阿松過(guò)程與獨(dú)立同 分布隨機(jī)變量序列給出 而由相依的一些高 斯過(guò)程來(lái)刻畫(huà) 通常面臨 3 個(gè)基本數(shù)學(xué)問(wèn) 題 一是如何來(lái)找出求解人們所關(guān)心的系統(tǒng) 數(shù)量指標(biāo)的一般方法 二是找出這些求解 方法之后 基于這些解 如何找出最優(yōu)策 略 三是供應(yīng)鏈協(xié)調(diào)時(shí) 如何找出最優(yōu)的協(xié) 調(diào)策略即平衡點(diǎn) 這些問(wèn)題的解決需要借 助隨機(jī)分析 隨機(jī)最優(yōu)控制和博弈論 且根 據(jù)模型的自身特點(diǎn) 發(fā)展一套新的數(shù)學(xué)方法 和理論 3 4 其他方向 3 4 1 算法博弈論 現(xiàn)代博弈論起源于上個(gè)世紀(jì)初 以策梅 洛 博雷爾和馮 諾依曼等人的工作為代 表 二次世界大戰(zhàn)為博弈論的應(yīng)用提供了 廣泛的背景 加快了博弈論體系的形成 馮 諾伊曼和莫爾根施特恩在1944年合著的 博弈論與經(jīng)濟(jì)行為 完善了博弈論的數(shù)學(xué) 理論 使之系統(tǒng)化和公理化 此外 納什等 人也對(duì)博弈論做出了重大貢獻(xiàn) 奠定了非合 作博弈的基礎(chǔ) 博弈論的研究對(duì)象與社會(huì) 政治 軍事 經(jīng)濟(jì) 科學(xué) 技術(shù)等很多領(lǐng)域都 有密切關(guān)系和廣泛應(yīng)用 一直是運(yùn)籌學(xué)及相 關(guān)領(lǐng)域的重要研究熱點(diǎn) 近20年以來(lái) 算法博弈論逐漸成為博弈 論的一個(gè)熱點(diǎn)方向 它將一個(gè)系統(tǒng)的形成 和運(yùn)行看作一個(gè)博弈過(guò)程 假設(shè)規(guī)劃者從整 體利益出發(fā)優(yōu)化設(shè)計(jì)系統(tǒng)以達(dá)到全局最優(yōu) 但博弈的參與者卻從自身利益出發(fā) 做出自 私的行動(dòng)選擇以達(dá)到個(gè)體最優(yōu) 這常常使得 系統(tǒng)的實(shí)際性能低于規(guī)劃者期望的全局最 優(yōu) 算法博弈論研究的主要問(wèn)題包括 1 如何描述和計(jì)算參與者的自私行為所導(dǎo)致 的系統(tǒng)性能 2 如何分析和刻畫(huà)博弈中參 與者的自私行為與系統(tǒng)整體性能之間的關(guān) 系 3 如何設(shè)計(jì)一個(gè)合理的機(jī)制使得其系 統(tǒng)在實(shí)際運(yùn)行中能夠真正實(shí)現(xiàn)整體利益最 大化 算法博弈論的特點(diǎn)是 它不僅僅關(guān)心 均衡解和機(jī)制的存在性 還強(qiáng)調(diào)計(jì)算它們的 復(fù)雜性 并設(shè)計(jì)有效的算法求出 或者近似 它們 3 4 2 應(yīng)急管理 應(yīng)急管理主要是研究圍繞非常規(guī)突發(fā) 事件的一系列科學(xué)問(wèn)題 它是本世紀(jì)以來(lái) 人們十分關(guān)心的熱點(diǎn)問(wèn)題之一 得到國(guó)際學(xué) 術(shù)界和政府有關(guān)管理部門(mén)越來(lái)越多的關(guān) 注 應(yīng)急管理所涉及的突發(fā)公共事件包括 自然災(zāi)害 事故災(zāi)難 公共衛(wèi)生事件和社會(huì) 安全事件 它們具有突發(fā)性 緊迫性 弱經(jīng) 濟(jì)性 信息不確定性和物資需求量大等特 點(diǎn) 目前的研究大都局限在個(gè)案上 缺乏以 數(shù)學(xué)為基礎(chǔ)的系統(tǒng)理論 2 事實(shí)上 這種理 論的形成已經(jīng)有了雛形 例如 隨機(jī)混雜系 統(tǒng)的理論研究工作漸漸成為描述應(yīng)急過(guò)程 一種有效工具 隨著兩種時(shí)間尺度差異的 運(yùn)籌學(xué)發(fā)展的回顧與展望 155 2012年 第27卷 第2期 學(xué)科發(fā)展 Disciplinary Development 變大 微觀與宏觀之間的相互影響機(jī)制在這種變化 中不斷顯現(xiàn) 而應(yīng)急過(guò)程在不同環(huán)境下的差異性變 化被有效地刻畫(huà) 隨著環(huán)境變化的決策方案的適時(shí) 性和有效性可以充分體現(xiàn) 這正是應(yīng)急管理所關(guān) 心的核心內(nèi)容 即包括了應(yīng)急事件的發(fā)起 也包括 了應(yīng)急事件的發(fā)展 還包括了應(yīng)急事件恢復(fù)的控制 等等 另外 將預(yù)備階段的預(yù)案和實(shí)施階段的調(diào)整 方案緊密結(jié)合在一起 使預(yù)案在實(shí)際應(yīng)用時(shí)能根據(jù) 所得的實(shí)時(shí)信息做出迅速調(diào)整 這種研究非常必 要 針對(duì)應(yīng)急管理的不同問(wèn)題的數(shù)學(xué)模型需研究 它們相應(yīng)的求解算法 特別是大規(guī)模問(wèn)題的快速求 解算法的設(shè)計(jì) 也值得重視和深入研究 3 4 3 統(tǒng)計(jì)和優(yōu)化 統(tǒng)計(jì)學(xué)是一門(mén)研究如何有效地收集數(shù)據(jù)和分 析數(shù)據(jù)的學(xué)科 它以數(shù)據(jù)為對(duì)象 研究各種實(shí)驗(yàn)和 現(xiàn)象中的數(shù)量關(guān)系 以概率論等為基礎(chǔ) 發(fā)展了一 套系統(tǒng)地處理數(shù)據(jù)的統(tǒng)計(jì)理論和方法 隨著科技 進(jìn)步和社會(huì)經(jīng)濟(jì)的發(fā)展 我們面臨的數(shù)據(jù)量正以指 數(shù)量級(jí)的速度增長(zhǎng) 產(chǎn)生了許多高維數(shù)據(jù) 缺失數(shù) 據(jù)和復(fù)雜結(jié)構(gòu)數(shù)據(jù) 對(duì)這些復(fù)雜數(shù)據(jù) 人們很難依 賴(lài)直觀對(duì)現(xiàn)象進(jìn)行判斷 高維復(fù)雜數(shù)據(jù)的有效分析 遇到了前所未有的挑戰(zhàn) 這些挑戰(zhàn)為統(tǒng)計(jì)學(xué)的發(fā)展 創(chuàng)造了難得的歷史機(jī)遇 現(xiàn)在經(jīng)常遇到一些復(fù)雜 現(xiàn)象中產(chǎn)生的海量數(shù)據(jù) 我們對(duì)這些復(fù)雜現(xiàn)象缺乏 理解 需要從這些數(shù)據(jù)出發(fā)來(lái)尋找和發(fā)現(xiàn)規(guī)律 這 就要求開(kāi)展 數(shù)據(jù)驅(qū)動(dòng) 的研究 以概率論和隨機(jī) 分析為基礎(chǔ) 以計(jì)算機(jī)為工具 引入最優(yōu)化思想的 統(tǒng)計(jì)方法將會(huì)成為一個(gè)發(fā)展方向 4 運(yùn)籌學(xué)中若干難題 愛(ài)因斯坦曾經(jīng)說(shuō)過(guò) 提出一個(gè)問(wèn)題往往比解 決一個(gè)問(wèn)題更為重要 形成一個(gè)公認(rèn)的科學(xué)難題 的過(guò)程本身就是科學(xué)研究的一個(gè)結(jié)果 同時(shí)也是開(kāi) 啟新的 未知大門(mén)的敲門(mén)磚 在許多科學(xué)家看來(lái) 科學(xué)難題是科學(xué)進(jìn)步的階梯 隨著一個(gè)又一個(gè)科 學(xué)難題的解決 科學(xué)技術(shù)不斷登上新的臺(tái)階 人類(lèi) 文明上升到一個(gè)新的高度 上個(gè)世紀(jì)伊始 著名數(shù) 學(xué)家希爾伯特在國(guó)際數(shù)學(xué)家大會(huì)上提出了23個(gè)數(shù) 學(xué)難題 在過(guò)去的100年里 這些問(wèn)題激發(fā)了眾多 數(shù)學(xué)家的熱情 引導(dǎo)了數(shù)學(xué)研究的方向 對(duì)現(xiàn)代數(shù) 學(xué)的發(fā)展產(chǎn)生了難以估量的巨大影響 在運(yùn)籌學(xué)發(fā)展的60多年里 幾代運(yùn)籌學(xué)工作 者在運(yùn)籌學(xué)的各個(gè)方向取得了許許多多的成果 應(yīng) 用數(shù)學(xué)的理論和方法奠定了運(yùn)籌學(xué)的基礎(chǔ) 也對(duì)數(shù) 學(xué)的發(fā)展做出了貢獻(xiàn) 著名數(shù)學(xué)科普作家卡斯蒂 1 在總結(jié)上個(gè)世紀(jì)意義的重大數(shù)學(xué)成果時(shí) 從眾多的 數(shù)學(xué)定理中遴選出了5個(gè) 其中4個(gè)都與運(yùn)籌學(xué)有 非常緊密的關(guān)系 它們是 極小極大定理 博弈論 單純形法 線(xiàn)性規(guī)劃 停機(jī)定理 計(jì)算的理論 布 勞威爾不動(dòng)點(diǎn)定理 博弈論的基礎(chǔ)工具 著名數(shù)學(xué)家波利亞曾經(jīng)說(shuō)過(guò) 數(shù)學(xué)就是解決 問(wèn)題的藝術(shù) 隨著一個(gè)又一個(gè)運(yùn)籌學(xué)難題的解 決 新的難題不斷地從新的土壤里破土而出 其中 一些不僅僅是運(yùn)籌學(xué)的相關(guān)研究方向的重大問(wèn)題 也是數(shù)學(xué)及相關(guān)學(xué)科的一些核心問(wèn)題 在著名數(shù) 學(xué)家斯米爾 4 給出的本世紀(jì)18個(gè)數(shù)學(xué)難題中 其中 以下4個(gè)就與運(yùn)籌學(xué)相關(guān) 1 P是否等于NP 也 被列為本世紀(jì)的7個(gè)數(shù)學(xué)難題之一 2 單變量多 項(xiàng)式整解的個(gè)數(shù) 3 可描述價(jià)格調(diào)整的一般均衡 理論的數(shù)學(xué)模型 4 實(shí)系數(shù)線(xiàn)性規(guī)劃是否多項(xiàng)式 時(shí)間可解 以下12個(gè)問(wèn)題是運(yùn)籌學(xué)相關(guān)方向具有一定代 表性的未解難題 7 1 凸多面體的d 步猜想 2 有 限多個(gè)二次函數(shù)最大值的極小化問(wèn)題 3 推廣的 Lax猜想 4 DFP擬牛頓法的收斂性 5 最小阻 力凸體問(wèn)題 6 是否存在求解性線(xiàn)性規(guī)劃的強(qiáng)多 項(xiàng)式時(shí)間算法 7 組合優(yōu)化反問(wèn)題的計(jì)算復(fù)雜性 8 求解旅行商問(wèn)題的更好的近似算法 9 k 服務(wù) 器猜想 10 裝箱問(wèn)題是否存在絕對(duì)近似算法 11 隨機(jī)排隊(duì)網(wǎng)絡(luò)的遍歷性 12 PH 分布的最小 表示 顯然 運(yùn)籌學(xué)未解的難題遠(yuǎn)不止上述這些 特 別是 這些問(wèn)題在運(yùn)籌學(xué)的各個(gè)分支之間的分布不 平衡 個(gè)別方向甚至未能得到反映 它們對(duì)運(yùn)籌學(xué) 的理論及應(yīng)用的意義和重要性各不相同 難易程度 156 院刊 也有千差萬(wàn)別 有興趣的讀者可以在此基 礎(chǔ)上開(kāi)展研究 也可以提出和研究其他有意 義的問(wèn)題 畢竟發(fā)現(xiàn)問(wèn)題 提出問(wèn)題 分析 問(wèn)題和解決問(wèn)題的過(guò)程構(gòu)成了運(yùn)籌學(xué)的發(fā) 展