一門新興的應用科學。由於它所研究的物件極其廣泛,有著許多不同的定義。

  1976年美國運籌學會定義“運籌學是研究用科學方法來決定在資源不充分的情況下如何最好地設計人-機系統,並使之最好地運行的一門學科。”1978年聯邦德國的科學辭典上定義“運籌學是從事決策模型的數位解法的一門學科”。前者著重於處理實際問題,而對“科學方法”則未加說明。後者強調數字解,而註重數學方法。

  英國運籌學雜誌認為““運籌學是運用科學方法(特別是數學方法)來解決那些在工業、商業、政府部門、國防部門中有關人力、機器、物資、金錢等的大型系統的指揮和管理方面所出現的問題,其目的是幫助管理者科學地決定其策略和行動”。有人則認為運籌學是近代應用數學的一個分支,主要是將生產、管理等實際中出現的一些帶普遍性的運籌問題加以提煉,然後利用數學方法去解決。前者提供模型,後者提供理論和方法。前者是後者發展的基礎,後者是前者進行工作的科學依據。其實,運籌學是這兩者有機結合而成的。英文oper ations research(運籌學)一詞的原意是作戰研究。早在1938年英國空軍就有瞭飛機定位和控制系統,並在沿海有幾個雷達站,可以用來發現敵機。但在一次空防大演習中發現,由這些雷達送來的(常常是相互矛盾的)信息,需要加以協調和關聯,以改進作戰效能。這一任務的提出即產生“運籌學”一詞。英國空軍成立瞭運籌學小組,主要從事警報和控制系統的研究。在1939年和1940年,這個小組的任務擴大到包含防衛戰鬥機的佈置,並對某些未來的戰鬥結果進行預測,以供決策之用。運籌學工作者在第二次世界大戰中研究並解決瞭許多戰爭的課題,例如通過適當配備護航艦隊減少瞭船隻受到潛艇攻擊的損失;通過改進深水炸彈投放的深度,使德國潛艇的死亡率提高;以及根據飛機出動架次作出維修安排,提高瞭飛機的作戰效率等等。在戰爭結束時,估計英國、美國和加拿大等三國的軍隊中,運籌學工作者已超過七百人。戰後,一些原在軍隊的運籌學工作者,在英國成立瞭一個民間組織“運籌學俱樂部”,定期討論如何將運籌學轉入民用工業,並取得瞭一些進展。第一份運籌學雜志和英國的運籌學會分別於1950年和1953年出現瞭。世界上第一個運籌學會“美國運籌學會”於1952年成立。1959年成立瞭國際運籌學會聯盟,到1986年已有35個會員國和6個兄弟學會會員3萬餘人,大多數會員國都辦有自己的雜志。中國的運籌學會“中國數學會運籌學會”於1980年成立,於1982年加入國際運籌學會聯盟並創刊《運籌學雜志》。

  運籌學作為一門用來解決實際問題的學科,在處理千差萬別的各種實際問題中,一般應該從以下幾方面考慮。

  ① 確定目標 首先必須弄清所提的任務想達到的目的。通常還必須弄清或預測隨著時間的推移決策者的認識和管理人員的水平是否會使所提目標發生變化,如何變化。

  ② 制定方案 訂出幾個大的步驟和完成各步驟的時間。一般說來,任務都是有時間性的,用於該任務的人力、物力、財力都是有限的。沒有比較切實的方案就難完成任務。

  ③ 建立模型 對於一個大型的復雜問題,首先要考慮是否將它分為若幹小型的能獨立進行的活動,以及在它們當中如何分配人力、物力、財力和對它們工作的具體要求,還要規定這些活動必須完成的時間。當問題完全明確後,就要收集有關的數據和確定問題所涉及的各種因素,弄清其中哪些是給定的,哪些是可以改變的(即變量),哪些是可以控制的,哪些是不確定的,並設法建立這些因素之間應滿足的各種關系,以及建立一種準則來衡量所作出的決策的效果。對於那些不可控制的因素要註意收集有關的數據或有經驗人士的看法。

  ④ 制訂解法 在模型已初步確定之後,就要考慮解法:是采用模擬,還是采用理論演算方法;假若有隨機因素,應如何對待;有無現成方法可資利用;需要做出什麼樣的假設才能創造新方法或使利用現成方法為可行的;問題本身要求的精度如何,等等。

  雖然不大可能存在處理對象極其廣泛的運籌學問題的統一途徑,但是在運籌學的發展過程中形成的某些抽象模型卻可以得出一些算法和結論,並用於實際之中。例如,城市的公共汽車問題,在公共汽車站候車的人時多時少,汽車公司究竟應派出多少輛汽車,如何派法,才能做到既使汽車公司增加收入,又使乘客比較滿意。這一問題,與一個百貨商店應有多少售貨員和一個工廠應有多少維修人員的問題甚為相似。它們都是存在著某種帶有隨機性的排隊現象,從而可形成具有普遍性的排隊模型。對排隊模型的研究形成瞭運籌學的分支學科排隊論。運籌學有許多分支學科。一個大型復雜的運籌學問題不一定僅屬於某一分支,它往往可以分解為許多子問題,每一子問題則可屬於某一分支。

  運籌學包含有以下一些分支:數學規劃(它又包含有線性規劃;非線性規劃;整數規劃、混合整數規劃、0-1規劃;組合規劃(組合最優化);參數規劃;隨機規劃;多目標規劃;幾何規劃;動態規劃;等等);圖論、網絡流;決策分析;排隊論、可靠性數學理論;庫存論;對策論;搜索論;模擬。

  下面對各分支作一簡單的綜合性介紹。

  數學規劃可以表示成求函數f(x1x2,…,xn),(目標函數)在規定(x1x2,…,xn)必須滿足(x1x2,…,xn)∈A(約束條件)的要求之下的極小(或極大)值,即тinf(x),xAARn。簡記為(P)。數學規劃與古典的極值問題有本質上的不同,古典方法隻能處理f(x)和A都具有簡單的表達式的情況,而現在的問題(P)的目標函數和約束條件一般都很復雜;古典方法隻考慮n很小的情況,例如n=3、4、5,而問題(P)中的n可能很大,有的n甚至超過百萬;古典方法在求解時往往滿足某一表達式,即可利用公式進行求解,因此隻能處理某些簡單類型的問題,而問題(P)則要求給出某種精確度的數字解答,因此算法研究特別受到重視。由於這些本質差別,求解數學規劃必須另辟途徑。

  若

,則稱(P)為線性規劃,否則稱為非線性規劃。若 x 1x 2,…, x n中有一部分(或全部)限制為隻取整數值,則稱(P)為整數規劃。若 f( x)不隻是一個函數,而是幾個函數,則稱(P)為多目標規劃,當然,多目標規劃的極值概念需要另加定義。

  線性規劃及其解法單純形法的出現,對運籌學的發展起瞭重大的推動作用。許許多多的實際問題都可化成線性規劃問題來解,而單純形法又是一個行之有效的算法。加上計算機的發展,使一些大型復雜的實際問題的解決成為現實,從而引起生產部門對數學方法的重視。有許多實際問題要求變量隻取整數值。例如某工廠選址,若令xi=0表示第i處供選地址未被選中;xi=1表示該地址被選中。此時xi隻能取0或1。對於這類問題,人們也許以為可用解一般的數學規劃的方法,求出近似解並經過四舍五入的辦法可以解決問題。但是有人舉出瞭一個簡單的線性規劃問題,按單純形法求出問題的解,然後經四舍五入求出整數解。如此進行瞭上萬次的運算,卻沒有一次能得出可行解,當然更不可能是最優解。因此對於整數規劃問題必須另尋新的解決方法。近年來,整數規劃的算法雖然取得瞭不少進展,但是對於許多離散問題仍然無能為力。例如對於4臺機器10個零件的排序問題,若用數學規劃來描述,則須引入40個連續變量、180個0-1變量、390個約束條件,而成為一個相當麻煩的混合整數規劃問題。目前對它還不存在象單純形法那樣有效的算法。在一個有限集上求極值的問題是所謂組合最優化問題,這類問題在實際中大量存在,為解決這類問題,於是又形成瞭一門新的分支組合最優化。它的內容主要包括四個方面:a.設計出求解某些特定問題的算法;b.估計某些近似解與最優解的差距;c.研究哪些問題屬於“難”題(計算的復雜性);d.對於一些復雜的實際問題,設計求出可供實用的數字解的方法。隨著組合最優化的發展,一些數學分支如組合數學、擬陣、廣義擬陣、圖論等也相應得到發展。

  非線性規劃是線性規劃的進一步發展和繼續。許多實際問題如設計問題、經濟平衡問題都屬於非線性規劃范疇,要求發展新的方法。非線性規劃擴大瞭數學規劃的應用范圍,同時也給數學工作者提出瞭許多基本理論問題,使數學中的許多學科如凸分析、數值分析等也得到發展。

  多目標問題也常出現於實際問題之中。例如在工業生產中,往往既要求產量提高,同時又要求資源消耗盡量少,這兩個指標是相互矛盾的。因此在這類問題上首先遇到的是“最優”概念如何定義。顯然它不象單目標問題那樣是惟一確定的。它牽涉到一個所謂偏序問題,即對可供選擇的方案及其屬性如何定義一種優劣“次序”,亦即如何描述目標對於可供選擇的方案的依賴關系。多目標規劃一般既涉及數學問題,也涉及到如何從外界(專傢或決策人)得到一些信息以作出“偏序”

  在數學規劃的應用中有一些問題,它們所涉及的輸入信息常隨時間而作微小的變動,這些變動有時會引起目標函數發生大的變動。基於這種現象而產生瞭一個新的分支參數規劃。它既要處理當有參數出現於目標函數和(或)約束條件時如何求解,同時也要處理解的性質對於參數的依賴性。

  圖論主要研究兩類問題:其一,在給定的圖中,具有某種性質的點和(或)線是否存在?若存在,有多少或至多(少)有多少?其二,如何構造一個具有某些給定性質的圖或子圖?就問題所討論的性質大致可分為五方面:連通性、極值問題、嵌入、陣與擬陣、網絡流。其中以極值問題和網絡流與運籌學中的問題關系最為密切。極值問題主要是研究滿足某種性質的點或邊的最小個數。網絡流理論研究的問題很多,其主要的有兩類:一類是網絡自身所固有的問題,如確定從甲地到乙地的最短路程、兩地之間的最大流通量問題。一類是屬於網絡流的管理方面,如在軍事中,當攻擊手段受到某種限制時,如何確定一最優阻止策略以破壞敵人的通訊及(或)交通網絡;在公用事業中,假若由於運輸量的增加已發覺現有網絡不能勝任,則應如何增加線路以使某種指標達到最優,等等。

  上述各種規劃問題的共同特點是:問題的結果決定於最後的階段,即問題本身是屬於一次性的。但是,生產實際中有一些問題是屬於多階段性的,要求在每一階段的開始必須作出某一決定,而整個問題的最終結果則與各階段所作的決定有關。以一個簡單的庫存問題為例說明如下:設有一個工廠要在一年中儲備某種元件,這種元件的購買都在每月月初進行。元件的單價決定於購買的月份和數量,即若第i個月月初買進μi個元件,設購買的單價為pi(μi)。設已知第i個月的消耗量為ri,每日的消耗量為常數。又設第i個月月末的儲存量為xix0=x12=0。要求元件的儲存量必須保證供應。問如何決定每月購買數量,使總的費用最省。顯然,這一問題的最終結果取決於每月月初(階段)所作的決策。這類問題在生產實際中出現很多,例如在控制問題、分配問題方面都會出現這類多階段決策問題。動態規劃方法就是用來處理這類問題的,它是在20世紀50年代由R.貝爾曼等人發展起來的,是數學規劃的主要組成部分之一。

  排隊論的研究目的是要回答如何改進服務機構或組織被服務的對象使得某種指標達到最優的問題。例如一個港口應有多少碼頭,一個工廠應有多少維修人員等等。排隊論最初是在20世紀初由丹麥工程師A.K.埃爾朗關於電話交換機的效率研究開始的,隻是在第二次世界大戰中為瞭對飛機場跑道的容納量進行估計,它才被納入運籌學的范疇。與排隊論問題較接近的有工廠設備的維修問題、元件的更換問題和可靠性問題等,其相應的學科更新論、可靠性理論等都已發展起來。

  運籌學中還有一大類問題是在有的場合它以確定性問題的面貌出現,有的場合則以隨機性問題的面貌出現。如庫存問題、對策問題等等。

  庫存論是研究所需項目的生產時間、數量、運輸、需要量(消耗量)的概率分佈、維修、變質等等問題,以制定某些庫存策略使得某種指標達到最優。根據生產時間、運輸、消費量等等因素出現情況的不同,庫存問題可以分成許多不同的類型。若其中的某些因素(例如消費量)是隨機的,則為隨機性模型。關於庫存論問題的研究早在20世紀20年代就出現瞭一些結果,到瞭40年代以後才得到深入研究和廣泛應用。

  對策論是通過抽象出一些共同的策略特征,從理論“模型”上來研究鬥爭中平衡狀態的性質、鬥爭各方的平衡策略的性質以及設計出確定這種狀態和策略的方法。對策論雖然在20世紀20年代初(F.-É.-J.-) É.波萊爾已著手研究,但隻是在J.馮·諾伊曼等人將它用於競爭中的經濟行為之後才受到廣泛的註意。這門學科在理論上已經有瞭深入發展,但在應用上仍處於定性階段。

  搜索論也是由於第二次世界大戰中戰爭的需要而出現的運籌學的一分支。所研究的是:在資源和探測手段受到限制的情況下如何設計尋找某種目標的方案,並如何加以實施的理論和方法,目的是以最大的可能或(和)最短的時間找到所說的目標。它是以搜索大西洋中襲擊盟軍商船的德國潛艇的研究而開始的。搜索論在實際應用中已取得不少成效,例如在20世紀60年代美國尋找在大西洋失蹤的核潛艇打谷者號和蠍子號以及在地中海丟失的氫彈,都是依據搜索論獲得成功的。

  決策分析是運籌學中發展較晚的一個分支。它的研究目的在於提供一種合理的論證或方法,使得人們能夠利用所有可資利用的信息,從可供選擇的方案之中選出那種按決策者的標準來說是“最優的”方案。假若問題所涉及的因素都是確定性的,這問題就屬於普通的最優化問題。通常所說的決策問題都包含有不確定因素,最終的結果並不完全能從所作出的選擇預先知道。例如,農田作物的選擇,雖然按照某種判斷選種瞭某類作物,但並不能保證一定會得到預期的收成。決策論所作的是要根據可資利用的信息以做出可能最好的合乎邏輯的決策。

  以上所述是運籌學目前所包含的各個相對獨立的分支,具有獨自的理論和方法。在生產實際中所出現的問題並不一定屬於單獨的某一分支,但往往可以把它分解成若幹子問題,使得每一子問題屬於某一分支。當然,對於一些結構復雜的問題,並不常能作出這種分解。它們有時可以用模擬方法來解決。所謂模擬方法,通常是指使用數字計算機,特別是統計抽樣於數學模型以得出某種反應出現的可能性大小的估計等一類的結果。

  運籌學在20世紀40年代以後得到迅速發展,其原因大致有以下幾個方面:①大規模的新興工業的出現,同行業間的競爭加劇,迫切需要對大型工業的復雜的生產結構和管理關系進行研究,作出科學的分析和設計;②產品的更新換代的加速,使得生產者必須密切註意市場情況和消費者的心理分析;③快速計算機的出現,一些復雜的問題能得到及時解決而使運籌學具有現實意義。總之,運籌學的每一分支學科的產生,都具有鮮明的實際背景。

  運籌學有廣闊的應用領域,它已滲透到諸如服務、庫存、搜索、人口、對抗、控制、時間表、資源分配、廠址定位、能源、設計、生產、可靠性、設備維修和更換、檢驗、決策、規劃、管理、行政、組織、信息處理及回復、投資、交通、市場分析、區域規劃、預測、教育、醫療衛生的各個方面。

  

參考書目

 J.J.Moder,et al.ed.,Handbook of Operations Research,Van Nostrond Reinhold Co.,New York.1978.

 B.Korte,ed.,Modern Applied Mathematics,North-Holland,Amsterdam,1982.

 L.D.Stone,Theory of OptiMal Search,AcademicPress,New York,1975.

 G.B.Dantzig,Linear Programming and Extensions,Princeton Univ.Press,Princeton,1963.

 L.R.Ford and D.R.Fulkerson,Flows in NetworksPrinceton Univ.Press,Princeton,1962.