運籌學與最優(yōu)化技術_吳滄浦專家文選運籌學與最優(yōu)化技術吳淪浦一、運籌學與最優(yōu)化技術的發(fā)展之間的聯(lián)系作為具有相對獨立性質的學科與技術，運籌學與最優(yōu)化技術，其發(fā)展過程具有密切聯(lián)系，并且彼此之間在其發(fā)展中起著相輔相成的作用。在運籌學發(fā)展的初期，經(jīng)典運籌學強調定量研究。這里的定量研究主要包括兩個方面:其一是對于作為研究對象的運籌系統(tǒng)作出定量的描述，該描述可以用數(shù)學模型或仿真模型表達;其二是給出能夠定量地衡量運籌系統(tǒng)的運作的優(yōu)劣程度的效力度量，該度量必須能夠明確地顯示出它自身與系統(tǒng)的決策（控制）變量之間的依賴關系。經(jīng)典運籌學之所以強調定量研究，其目的在于使決策與對于其所能選擇或控制下的決策變量作出最優(yōu)的選擇。這里的最優(yōu)是在下述的意義下理解的，即該選擇能夠使上述的效力度量達到最大值或最小值。由于在經(jīng)典運籌學中，效力度量是以實數(shù)表示的，而且它能定量地反映運籌系統(tǒng)的運作的優(yōu)劣程度，因而上述意義下的最優(yōu)性是有意義的。由此不難理解，最優(yōu)化技術成為經(jīng)典運籌學中的主要工具，后者成為前者發(fā)展的主要推動力;反過來，最優(yōu)化技術的發(fā)展又在運籌學經(jīng)歷了從經(jīng)典運籌學到現(xiàn)代運籌學的進化中起了重大的作用。在運籌學的奠基性專著一莫爾斯與金博爾合著的《運籌學方法》中，專門辟出一章論述效力度量的使用。人們由此可以看到最優(yōu)化技術在經(jīng)典運籌學中所占有的重要位置。另一方面，從國際運籌學會聯(lián)合會所舉辦的最近兩屆（1996年于加拿大溫哥華、1999年于中國北京）運籌學國際會議上發(fā)表的論文，以及新近出版的有關專著，例如，由美國普渡大學教授拉丁的《運籌學的最優(yōu)化》及印地安那大學教授溫斯頓的（（運籌學:應用與算法》中，人們可以明顯地看到，盡管時過半個世紀，最優(yōu)化技術在現(xiàn)代運籌學中仍然起著舉足輕重的重要作用。二、最優(yōu)化技術的發(fā)展在文學界和藝術界，存在一種流傳頗廣的看法，即在文學和藝術中，存在一些“永恒”的主題，例如，善與惡之間的斗爭、真理與謬誤之間的斗爭、人與人之間的博愛（友情、愛情等）。從類似的角度出發(fā)，或許可以說，最優(yōu)化技術是科學與技術中的一個“永恒”的主題。118錢學森科學貢獻暨學術思想研討會論文集因為科學與技術無非是人類認識世界和改造世界的產(chǎn)物，而人類在認識世界和改造世界的行動過程中，在一定的主觀和客觀的條件下，自然而然地會要求其行為能夠達到最優(yōu)的效果。事實上，最優(yōu)化的思想的淵源可以追溯到人類的早期文明。早在公元前一個世紀左右之時，古埃及的科學家就曾斷言光在兩點之間以最短途徑傳播。另一富有詩意的例子是由古羅馬詩人威吉爾所給出的關于邇太基皇后狄多索取領地的傳奇故事，她在北非洲面臨大海處索取一塊領地，其面積一張牛皮即可覆蓋。然后她將一張牛皮做成一根繩子，以這根繩子面對大海以半圓弧劃出一塊地域作為領地。在給定周長的條件下，半圓弧劃出的地域的面積達到最大。早在公元前兩個世紀左右，阿基米德就曾對此事實作出猜測，但是直到兩千多年后發(fā)明了變分法，此一事實才得到嚴格的證明。上述兩個例子從一個側面表明，作為一門科學與技術，最優(yōu)化理論與最優(yōu)化技術最初是在物理學和幾何學的研究中得到發(fā)展的，隨著歐拉一拉格朗日最小作用原理，哈密爾頓最小勢能原理以及吉布斯最小自由能原理的發(fā)現(xiàn)，最優(yōu)化理論和最優(yōu)化技術在自然科學中的應用于18,19世紀間獲得了輝煌的成就，相形之下，它們在包含運籌學的系統(tǒng)科學萬面的應用的發(fā)展，卻要晚得多。這一情況緣于具有實際背景的運籌學的最優(yōu)化問題遠比上述自然科學中的最優(yōu)化問題復雜得多。線性規(guī)劃與單純形方法的創(chuàng)立者丹齊克在回憶他于開發(fā)單純形方法之初在美國空軍后勤部門所遇到的運籌問題的復雜性質，他在此提到的運籌問題乃一人事安排問題，即假設有70位工作人員要安排到70種不同的工作LUd岡位上去，要求在某種線性的效力度量函數(shù)下使工作安排方案達到最優(yōu)。在此問題中，可供選擇的工作安排方案為70!如果以窮舉法搜尋最優(yōu)方案，即使使用當時計算速度最高的計算機，也需要超過150億年的時間。另一運籌學中著名的最優(yōu)化問題乃是“旅行推銷商問題”，如果推銷商需遍歷70個地點，則可供選擇的不同的旅行路線數(shù)與前一問題的方案數(shù)相同。除去復雜程度的區(qū)別外，運籌學中的最優(yōu)化問題與在自然科學中得到廣泛應用的基于經(jīng)典變分學的最優(yōu)化問題相比較，還具有下述的重要區(qū)別。在經(jīng)典變分學中，問題的最優(yōu)解一般是在其鄰域內的相對最優(yōu)解，由于問題的實際背景的特點，此相對最優(yōu)解通常也是問題的全局最優(yōu)解。例如，對經(jīng)典變分學的研究起到推動作用，于歐洲文藝復興后期被提出的著名的“最速下降線”問題就是如此。伽利略曾作出該問題的最優(yōu)解是圓弧的猜測，但直到變分學出現(xiàn)之后，它的最優(yōu)解才被嚴格證明為擺線而非圓弧。在運籌學中，最優(yōu)化問題的解一般是在全部可行解（滿足問題的約束條件的解，亦稱滿足約束解）的集合中達到最優(yōu)的全局最優(yōu)解。例如，在動態(tài)規(guī)劃理論中建立起來的哈密爾頓一雅可比一貝爾曼方程以及與其關聯(lián)的龐特里雅金最大值原理，就給出了全局最優(yōu)解所須滿足的條件。有一些早期的最優(yōu)化技術的學者認為，如果效力變量不是一個實數(shù)，而是出現(xiàn)同時存專家文選119在若干以實數(shù)表示的效力度量，且彼此間存在矛盾，即決策變量的變動可能使某些變量下降而其他上升，或者相反，則這類問題不可能被進行最優(yōu)化。多目標最優(yōu)化技術的出現(xiàn)，徹底改變了這種情況。多目標最優(yōu)化的思想起源于19世紀帕雷托在經(jīng)濟學上的研究，但它形成比較成熟的理論和完整的技術，卻是在20世紀70年代以后。由于帕雷托最優(yōu)性的思想具有很強的理性基礎，它已成為多目標最優(yōu)化中的最通用的基本概念。多目標最化的特征是它的目標（效力度量）空間是多維歐氏空間，或許因為有些多目標最優(yōu)化的解是通化將其化成單指標最優(yōu)化問題，因而使某些學者存在錯覺，認為前者只是后者的在多維空間的簡單推廣。事實并非如此，兩者具有實質上的區(qū)別。在單指標情況下，解空間到度量最優(yōu)值是一解集到實數(shù)集上一點的映射，求最優(yōu)解是此映射的逆映射，它是一點集映射;而在多指標情況下，解空間到度量最優(yōu)值是一解集到多維歐氏空間上一集的映射，該逆映射是集一集映射。此情況使集一集映射成為多目標最優(yōu)技術中的重復工具。此外，現(xiàn)代的研究已將目標空間擴展為一般的函數(shù)空間中。與多目標最優(yōu)化密切關聯(lián)的是多人（決策者）決策問題，此處最優(yōu)化的概念又有所不同，它要達到多人效益的平衡。J.vonNe~的專著《博奕論與經(jīng)濟行為》是該領域的奠基著作。多目標和多人決策最優(yōu)化問題的出現(xiàn)標志著最優(yōu)化技術進人人類社會活動的重要領域一人類的經(jīng)濟行為。運籌學中有不少問題是無法建立模型的，不論是數(shù)學的或仿真的。為適應此情況，最優(yōu)化技術發(fā)展出一系列無模型情況下的方法。一個最簡單情況就是菲波那契搜索法與黃金分割搜索法。這是極接近于無模型的方法。因它除對變量的函數(shù)作出單峰的要求外，不需該函數(shù)的其他信息。許多啟發(fā)或搜索法也具有類似性質。特別值得一提的是，近來發(fā)展起來的智能計算方法諸如遺傳算法、進化算法、進化規(guī)劃等，更是可以完全脫離模型的最優(yōu)化技術。在運籌學的最優(yōu)化問題中，通常會出現(xiàn)一些由決策者考慮其他因素時所出現(xiàn)的問題描述（包括模型）中包含的參數(shù)，這些參數(shù)也可以是環(huán)境變動或問題描述的不精確性所引人的。在這種情況下，研究這些參數(shù)的微小變動對最優(yōu)解的影響就顯得很重要。近代最優(yōu)化技術引人的靈敏度分析，對于決策者采用最優(yōu)化技術成果時具有重要作用，它可使決策者在環(huán)境變動或問題描述不精確時，有更大的回旋余地以作出決策。現(xiàn)代最優(yōu)化技術的最顯著特點是它的多學科跨學科性，除去運籌學外，它與系統(tǒng)工程、人工智能、模式識別、知識工程等學科的發(fā)展聯(lián)系密切，并在發(fā)展過程中起著相輔相成的作用。其中尤其重要的是與人工智能的聯(lián)系。除去以上的智能計算外，以霍費爾為先驅的神經(jīng)網(wǎng)絡最優(yōu)化方法的工作，以沃特金與伯契卡斯為先驅的機器學習最優(yōu)化方法的工作，為現(xiàn)代的最優(yōu)化技術開辟了一個極高前景的廣闊領域，這一點從新近出版的來翁德斯的專著《最優(yōu)化技術》可以明顯地看出來。錢學森科學貢獻暨學術思想研討會論文集三、運籌學的發(fā)展在西方國家，如果從運籌學的醞釀（1935年）算起，至今已有66年時間，但是多數(shù)研究運籌學的學者認為，從國際上學術界的運籌工作的廣度和深度看，運籌學作為一門獨立學科出現(xiàn)，還是從20世紀60年代開始的。我國的運籌學研究工作，是由錢學森先生于1956年在中國科學院力學研究所建立運籌學研究室開始的，錢先生以其敏銳的科學洞察力和遠大的眼光，在西方運籌學發(fā)展的初期就將它引進我國，為我國運籌學的發(fā)展做出了重大貢獻。因為有了這樣快速的引進，我國的運籌學發(fā)展與西方比較，可以說差不多是同步的。目前我國運籌學工作者的隊伍規(guī)模比西方國家的規(guī)模大，在研究工作方面我國也有不少成果處于國際前沿。從運籌學成為一門獨立學科之后，運籌學的研究內容已經(jīng)經(jīng)歷過重大的變化。在經(jīng)典運籌學中，決策者并不包含在運籌學的研究對象之中，決策者是運籌學提供其研究成果的對象，即運籌學工作者的客戶。自從人機交互形式的決策支持系統(tǒng)的研究出現(xiàn)以來，決策者與其提供決策根據(jù)的進行系統(tǒng)分析的工具（計算機和計算機網(wǎng)絡）一起，整個地形成運籌學的研究對象，決策者已被包含在運籌學的研究對象之中。新近出現(xiàn)的研究專題“組織化智能”，已將決策者、專家、計算機及其網(wǎng)絡一起，以及它們之間的交互作用，整個地形成運籌學的研究對象。可以這么認為，作為一門科學的運籌學，隨著整個科學技術的進步而不斷進行自身的進化。尤其因為它具有多學科、跨學科的特點，它的進化將具有如下特點:它在新學科或新技術中找到新的生長點，它從其應用背景的新需要中得到其擴展研究領域的推動力，它隨新的硬件工具或裝置的出現(xiàn)得到其擴展研究領域的基礎。運籌學的研究核心是決策，而決策是人類智能活動的高級形式。因之，運籌學的發(fā)展無疑將與智能科學的發(fā)展密切相關，這與最優(yōu)化技術的未來發(fā)展動向是一致的。四、結論當前世界經(jīng)濟的發(fā)展特點，一是知識經(jīng)濟的未來主導地位，二是經(jīng)濟全球化。運籌學與最優(yōu)化技術的發(fā)展，必然與此特點相適應。新發(fā)展起來的高科技，將成為面臨新世紀的經(jīng)濟發(fā)展的主要推動力。因此，與這些高科技緊密結合，無疑是運籌學與最優(yōu)化技術在新世紀里的發(fā)展方向。參考文獻莫爾斯?金博爾.運籌學方法.北京:科學出版社，1988專家文選121RavelinRR.娜timizationinOperationsResearchPrenticeHallNewJersey.1998WinstonWW.Research:Application