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