樸素的運籌思想古已有之,在我國古代文獻中有許多記載。如戰(zhàn)國時期流傳后世的賽馬比賽——田忌賽馬,就是一個經典的博弈案例。田忌賽馬的故事說明事前的籌劃安排是十分重要的。在已有的條件下,經過精心籌劃、安排,選擇一個好的方案,就會取得滿意的效果。敵我雙方交戰(zhàn),要克敵制勝就要在了解雙方情況的基礎上,研究制定最佳的對付敵人的策略和戰(zhàn)術,這就是所謂的“運籌帷幄之中,決勝千里之外”。
運籌學這個名詞最早出現于1938年,當時的英國為了研究整個防空作戰(zhàn)系統的合理運行,以便有效地防備德國飛機入侵,成立了由來自物理、數學等不同學科領域的科學家組成的研究小組,他們的研究工作在有效打擊敵人和減少盟軍的損失方面發(fā)揮了重要作用。他們在一份研究報告中首次使用了Operation Reseach一詞。第二次世界大戰(zhàn)結束后,運籌學研究的重點轉向民用領域,并獲得成功。1947年,美國數學家G.B.Dantzig提出了求解線性規(guī)劃模型的有效方法——單純形法,并于20世紀50年代初應用電子計算機求解線性規(guī)劃問題獲得成功。到20世紀50年代末,學者們對企業(yè)中的一些普遍性優(yōu)化問題,如庫存、資源分配、設備更新、任務分派等問題進行研究,并成功地應用到建筑、紡織、鋼鐵、煤炭、石油、電力、農業(yè)等諸多行業(yè)。20世紀60年代,運籌學方法又廣泛應用到了服務性行業(yè)和社會公共事業(yè)。
運籌學一詞在英國稱為OperationalResearch,在美國稱為OperationsResearch,縮寫為O.R.。《大英百科全書》中闡明:“運籌學是一門應用于管理有組織系統的科學,運籌學為掌握這類系統的人提供決策目標和數量分析工具”。
運籌學最早主要研究經濟活動和軍事活動中能用數量來表達的有關策劃、管理方面的問題。隨著時代的進步和科學技術的發(fā)展,運籌學的應用更為廣泛,而且解決問題的規(guī)模也越來越大、越來越復雜。現實中的優(yōu)化問題雖然千差萬別,但用運籌學來分析和處理問題時,一般都遵循以下幾個工作步驟:確定目標、制訂方案、建立模型、提出解法。不同類型的問題可歸結為多類不同的數學模型,從而形成了不同的運籌學學科分支,如數學規(guī)劃(包含線性規(guī)劃、非線性規(guī)劃、整數規(guī)劃、動態(tài)規(guī)劃等)、圖論與網絡流、決策論、對策論、排隊論、存儲論,等等。
數學規(guī)劃的研究對象是最為一般的優(yōu)化問題,即在給定的限制條件下,按某一衡量指標來尋找最優(yōu)方案。它可以表示為求函數在滿足約束條件下的極大或極小值問題。數學規(guī)劃中最簡單的一種問題就是線性規(guī)劃。線性規(guī)劃及其單純形法對運籌學的發(fā)展起到了重大的推動作用。許多實際問題都可以轉化成線性規(guī)劃來解決,單純形法是解決線性規(guī)劃的一個行之有效的算法,而計算機技術的發(fā)展,使一些大型復雜的實際優(yōu)化問題的解決成為現實。
圖論是一種用直觀的圖形來表述和解決一類優(yōu)化問題的運籌學分支。最小支撐樹、最短路、最大流等問題是圖論中經典的最優(yōu)化問題。一些不具有圖形特征的優(yōu)化問題也可以用圖形來表述和求解,并且更為直觀和簡便,如匹配問題、設備更新問題等。網絡分析技術則利用圖形來描述一個工程項目中各項活動之間的關聯和時間進度,從而可以對項目進度進行控制和優(yōu)化。
現實生活中,人們常常需要在一些可選方案中進行選擇,而選擇的情景可能是不確定的或有風險的,或者是評價方案的目標有多個。如何進行選擇或決策,就是決策論要解決的問題。而如果決策者面對一個與他有競爭的決策者時,決策問題就變成了一個博弈問題,前面提到的田忌賽馬就是典型的博弈案例。研究博弈問題的理論和方法就是博弈論(也叫作對策論)。
排隊論是運籌學的一個重要分支,它又叫作隨機服務系統理論。它的研究目的是要回答如何改進服務機構或如何組織被服務的對象,使得某種指標達到最優(yōu)的問題。比如一個港口應該有多少個碼頭,銀行營業(yè)廳應設置多少服務窗口等。排隊是一個隨機現象,因此在研究排隊問題時,需要以概率論作為分析工具。
存儲論是研究如何平衡供給與需求之間矛盾的理論與方法。其基本的數學問題就是在特定的需求假設下,確定最優(yōu)的訂貨量或生產量。
和所有的其他數學分支一樣,運籌學的內容有其經典不變的一面,但是隨著社會經濟的發(fā)展和科學技術的變革,其應用對象所呈現出的豐富性和復雜性也與日俱增。因此,運籌學的理論研究和應用前景都面臨更大的機遇和挑戰(zhàn)。比如,隨著人們對決策行為的關注,已經提出行為運籌學的概念。此外,隨著移動互聯網技術的發(fā)展,可獲得海量的實際數據,這些為運籌學的應用提供了更為廣闊的空間,使其能夠發(fā)揮越來越重要的作用。迪士尼游樂場的Fastpass系統中就運用了排隊論方法。又如目前交通出行的叫車App應用軟件,其中也包含了最優(yōu)匹配等優(yōu)化算法。
本書著重介紹運籌學的主要分支內容,在選材上詳略得當,重點突出,對專業(yè)詞匯給出中英文對照;注重內容闡述的啟發(fā)性和新穎性,對經典方法的講解由淺入深,適當增加了運籌學的最新研究理論和方法,拓展讀者視野;注重內容理論闡述的嚴密性,給出必要的理論性證明和推理;注重案例的時代性,教材中引入了一些新的應用案例,由案例問題引出理論分析方法,再回到實際問題的解決過程;案例及附件中介紹了如何用Excel來求解模型,增強了本書的實用性。
本書由周晶擔任主編,徐薇擔任副主編,負責教材內容選擇和審定。其中周晶參與編寫了第7章、第9章、第10章和第11章。徐薇負責編寫第1章、第2章和第5章;朱振濤、魯濤負責編寫第3章和第4章;安智宇負責編寫第6章;伊俊敏負責編寫第7章;徐紅利負責編寫第8章;吳孝靈負責編寫第9章;王虹負責編寫第10章;孫玉玲負責編寫第11章。
編者
前言
第1章線性規(guī)劃1
1.1線性規(guī)劃建模1
1.2線性規(guī)劃的解6
1.3線性規(guī)劃的圖解法7
1.4線性規(guī)劃的基本定理11
1.5單純形法12
1.6單純形法的進一步討論18
1.7應用舉例28
習題31
第2章線性規(guī)劃的對偶理論35
2.1線性規(guī)劃的對偶問題35
2.2對偶理論40
2.3影子價格44
2.4對偶單純形法45
2.5靈敏度分析48
習題53
第3章線性規(guī)劃的擴展56
3.1運輸問題56
3.2目標規(guī)劃80
3.3數據包絡分析89
習題98
第4章整數規(guī)劃104
4.1整數規(guī)劃問題及其數學模型104
4.2分支定界法106
4.3割平面法113
4.40-1整數規(guī)劃116
4.5指派問題121
4.6整數規(guī)劃案例125
習題128
第5章非線性規(guī)劃132
5.1概述132
5.2非線性規(guī)劃問題的解134
5.3凸函數和凸規(guī)劃137
5.4下降迭代算法140
5.5一維搜索142
5.6無約束極值問題的求解算法148
5.7約束極值問題的最優(yōu)性條件154
5.8約束極值問題的求解算法159
習題164
第6章動態(tài)規(guī)劃166
6.1多階段決策問題166
6.2動態(tài)規(guī)劃的基本概念和基本方程168
6.3最優(yōu)化原理與最優(yōu)性定理175
6.4動態(tài)規(guī)劃問題的求解177
6.5動態(tài)規(guī)劃的應用舉例182
習題194
第7章圖與網絡198
7.1圖與網絡基礎概念198
7.2樹202
7.3最短路問題205
7.4最大流問題210
7.5最小費用流問題215
7.6中國郵遞員問題219
7.7網絡計劃222
習題229
第8章決策論233
8.1決策的概念與分類233
8.2確定型決策分析236
8.3不確定型決策分析236
8.4風險型決策分析239
8.5多準則決策分析246
8.6效用函數 255
8.7行為決策理論258
習題263
第9章博弈論266
9.1博弈的基本要素與分類266
9.2完全信息靜態(tài)博弈268
9.3零和博弈277
習題289
第10章排隊論292
10.1排隊服務系統的基本概念292
10.2到達間隔與服務時間的分布 296
10.3生滅過程與系統狀態(tài)方程 299
10.4單服務臺負指數分布排隊模型301
10.5多服務臺排隊模型307
10.6其他類型排隊模型312
10.7排隊系統的優(yōu)化317
習題319
第11章存儲論321
11.1存儲論概述321
11.2確定性需求的存儲模型 323
11.3隨機需求的基本存儲模型334
習題344
附錄A線性規(guī)劃問題的Excel
求解346
附錄B名詞術語中英文對照361
參考文獻365