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