本書共9章,內(nèi)容包括運籌學(xué)概述、樸素優(yōu)化范式、線性規(guī)劃、網(wǎng)絡(luò)最優(yōu)化、動態(tài)規(guī)劃、網(wǎng)絡(luò)計劃、排隊系統(tǒng)分析、庫存優(yōu)化、旅行商問題等。在內(nèi)容選擇方面,本書遵循“重打基礎(chǔ)、直抵核心、精心留白”的原則,突出內(nèi)容的基礎(chǔ)性、理論的簡潔性、案例建模計算的完整性,以激發(fā)讀者的學(xué)習(xí)興趣,使其快速入門。
本書適合有一定線性代數(shù)、概率論基礎(chǔ)的初學(xué)者使用,也可供各類數(shù)學(xué)建模競賽、計算機算法設(shè)計競賽的人員參考。
運籌學(xué)應(yīng)用高級分析技術(shù)優(yōu)化決策,而能夠優(yōu)化決策的高級分析技術(shù)有很多,因此運籌學(xué)的分支很龐大,應(yīng)用領(lǐng)域也很廣泛。最初運籌學(xué)應(yīng)用于軍事領(lǐng)域,后來擴展到工業(yè)、商業(yè)、政府等民用領(lǐng)域。
運籌學(xué)緊密結(jié)合數(shù)學(xué)、計算機、經(jīng)濟學(xué)、管理學(xué)等各領(lǐng)域的知識解決優(yōu)化問題。雖然運籌學(xué)的基礎(chǔ)理論在起源后的幾十年已經(jīng)基本成熟,但是由于計算機、經(jīng)濟學(xué)、管理學(xué)以及應(yīng)用領(lǐng)域的不斷發(fā)展變化,運籌學(xué)面臨的新問題以及優(yōu)化決策的基本范式也在不斷發(fā)展。本書將運籌學(xué)的優(yōu)化范式總結(jié)梳理為樸素優(yōu)化范式、機械優(yōu)化范式、仿真優(yōu)化范式、智能優(yōu)化范式、數(shù)據(jù)驅(qū)動優(yōu)化范式等,便于讀者在入門階段對運籌學(xué)有一個宏觀的認(rèn)識。
運籌學(xué)是一門學(xué)科,也是一個專業(yè),還是一門課程。作為入門課程,給學(xué)生開好頭,激發(fā)其學(xué)習(xí)興趣,保持對未來實踐有益的方向和理念,是運籌學(xué)課程的重要任務(wù)。像學(xué)習(xí)鋼琴一樣,一般有一定樂理知識的人都能夠在短期內(nèi)上手彈奏簡單的曲目,但是更高級別的演奏,需要付出更加持續(xù)的努力和進(jìn)行系統(tǒng)的練習(xí)。 在開始的時候,保持持續(xù)學(xué)習(xí)的動力和興趣,是走得更遠(yuǎn)的重要因素。
本書是編者在多年運籌學(xué)學(xué)習(xí)、研究和教學(xué)的基礎(chǔ)上編寫而成的,力求將運籌學(xué)的基礎(chǔ)理論學(xué)習(xí)與計算機求解、系統(tǒng)化的解決方案訓(xùn)練等統(tǒng)籌結(jié)合,將運籌學(xué)面向?qū)嵺`和應(yīng)用的特色突顯出來。在內(nèi)容選擇方面,本書遵循“重打基礎(chǔ)、直抵核心、精心留白”的原則,突出內(nèi)容的基礎(chǔ)性、理論的簡潔性、案例建模計算的完整性,以激發(fā)讀者的學(xué)習(xí)興趣,使其快速入門。首先,如果在有限的時間內(nèi),學(xué)習(xí)的都是關(guān)于運籌學(xué)的數(shù)學(xué)理論和技術(shù),則很容易讓人認(rèn)為運籌學(xué)是數(shù)學(xué)工具的集合,從而喪失學(xué)習(xí)興趣。運籌學(xué)不是單純的數(shù)學(xué)工具的集合,因此,在內(nèi)容的設(shè)計上,本書力求與計算機算法的設(shè)計和求解緊密結(jié)合,用理論解決“為什么”的問題,用算法解決“怎么做”的問題,用代碼拋磚引玉解決實際中“動手難”的問題。其次,運籌學(xué)需要給出解決問題的系統(tǒng)方案。因此,在典型案例或者應(yīng)用中,力爭開放、發(fā)散,有時即使是一道簡單的習(xí)題,也會展開發(fā)散性的思考討論,這看似小題大做,實則對培養(yǎng)學(xué)生的系統(tǒng)意識會有意想不到的好處。最后,凡非必要,盡量減少了非應(yīng)用領(lǐng)域的概念,而重在分析問題、解決問題的方法思路和解決手段上。
本書由宋志華和周中良主編。本書編寫組的楊建軍、魏靚、陳士濤、許建虹、李宗哲、趙保軍、張晗、盛晟、周宇、方甲永、劉銘、古清月、高楊軍、傅超琦、宋曉博、何蘋等在素材收集、算法設(shè)計、案例編寫、書稿校對等方面做了許多工作,對本書的出版有著非常重要的貢獻(xiàn),張多林、楊建軍等對本書提出了許多寶貴的意見,在此表示衷心的感謝。
由于編者水平有限,書中不足之處在所難免,敬請廣大讀者批評指正。
第1章 運籌學(xué)概述 1
1.1 運籌學(xué)的起源 1
1.2 運籌學(xué)的定義 3
1.3 運籌學(xué)的模型 4
1.3.1 線性規(guī)劃模型 4
1.3.2 網(wǎng)絡(luò)模型 5
1.3.3 動態(tài)規(guī)劃模型 5
1.3.4 生滅過程模型 5
1.3.5 神經(jīng)網(wǎng)絡(luò)模型 6
1.3.6 啟發(fā)式模型 6
1.3.7 仿真模型 6
1.4 運籌學(xué)的優(yōu)化范式 7
1.4.1 樸素優(yōu)化范式 7
1.4.2 機械優(yōu)化范式 8
1.4.3 仿真優(yōu)化范式 8
1.4.4 智能優(yōu)化范式 8
1.4.5 數(shù)據(jù)驅(qū)動優(yōu)化范式 8
1.5 運籌學(xué)應(yīng)用的過程 8
1.5.1 定位 10
1.5.2 問題定義 10
1.5.3 數(shù)據(jù)收集 10
1.5.4 模型構(gòu)建 11
1.5.5 模型求解 12
1.5.6 驗證與分析 12
1.5.7 實施與監(jiān)控 12
習(xí)題1 13
第2章 樸素優(yōu)化范式 14
2.1 生成測試范例 14
2.2 枚舉法 15
2.3 深度優(yōu)先搜索 16
2.4 廣度優(yōu)先搜索 18
2.5 貪婪算法 21
2.6 啟發(fā)式算法 22
2.7 拓展應(yīng)用:玻璃球硬度測試實驗設(shè)計問題 23
習(xí)題2 25
第3章 線性規(guī)劃 26
3.1 約束目標(biāo)標(biāo)準(zhǔn)型 26
3.1.1 線性規(guī)劃的一般形式 26
3.1.2 線性規(guī)劃的標(biāo)準(zhǔn)形式 26
3.1.3 整數(shù)線性規(guī)劃 27
3.2 從無窮到有限之基解 28
3.2.1 可行解 28
3.2.2 基解 29
3.2.3 基解三定理 29
3.2.4 基解的枚舉 31
3.2.5 基解的啟發(fā)尋優(yōu) 33
3.3 單純形法 33
3.3.1 起點 33
3.3.2 鄰域中的改進(jìn)解 33
3.3.3 終止 35
3.3.4 算例 35
3.4 對偶問題 38
3.4.1 機會成本與影子價格 38
3.4.2 對偶問題的模型 39
3.5 運輸問題 40
3.5.1 真假運輸問題 40
3.5.2 運輸問題模型 41
3.5.3 運輸問題算法 44
3.5.4 從不平衡到平衡 49
3.6 典型案例 50
3.6.1 投資方案的規(guī)劃 50
3.6.2 防御兵力的部署 54
3.6.3 火車站售票的規(guī)劃 56
3.6.4 武器目標(biāo)分配問題 58
習(xí)題3 59
第4章 網(wǎng)絡(luò)最優(yōu)化 63
4.1 最小支撐樹問題 63
4.1.1 最小費用連通問題 63
4.1.2 兩個屬性 64
4.1.3 三大算法 66
4.1.4 拓展應(yīng)用:k聚類分析 71
4.1.5 拓展應(yīng)用:戰(zhàn)備通信節(jié)點的建設(shè)問題 73
4.2 最短路問題 77
4.2.1 線性規(guī)劃模型 77
4.2.2 最優(yōu)性條件 78
4.2.3 標(biāo)號法 78
4.2.4 拓展應(yīng)用:數(shù)據(jù)約減 82
4.3 最大流問題 86
4.3.1 線性規(guī)劃模型 86
4.3.2 剩余容量圖 86
4.3.3 增廣鏈法 86
4.3.4 拓展應(yīng)用:彈藥目標(biāo)最大化匹配問題 88
4.3.5 拓展應(yīng)用:最大投送能力評估問題 89
4.4 最小費用流問題 91
4.4.1 線性規(guī)劃模型 91
4.4.2 三個最優(yōu)性條件 92
4.4.3 兩個算法 93
4.4.4 拓展應(yīng)用:網(wǎng)絡(luò)上的最小費用最大流問題 94
4.5 二分匹配問題 97
4.5.1 指派問題 97
4.5.2 穩(wěn)定婚配問題 99
習(xí)題4 102
第5章 動態(tài)規(guī)劃 106
5.1 多階段決策問題 106
5.2 網(wǎng)絡(luò)模型 108
5.3 Bellman遞歸方程 109
5.3.1 最優(yōu)性原則 109
5.3.2 兩個推論 112
5.3.3 兩個方程 112
5.3.4 多階段最短路問題的求解 113
5.4 典型案例 114
5.4.1 背包問題 114
5.4.2 設(shè)備更新問題 117
5.4.3 過河問題 121
5.4.4 炮兵陣地問題 125
5.4.5 巡邏隊分配問題 131
習(xí)題5 135
第6章 網(wǎng)絡(luò)計劃 139
6.1 網(wǎng)絡(luò)計劃的發(fā)展歷程 140
6.2 網(wǎng)絡(luò)建模 140
6.3 關(guān)鍵路線法CPM 142
6.3.1 關(guān)鍵路線的計算 142
6.3.2 幾個時間參數(shù)的計算 143
6.4 計劃評審技術(shù)PERT 145
6.5 時間費用優(yōu)化 149
習(xí)題6 152
第7章 排隊系統(tǒng)分析 154
7.1 排隊現(xiàn)象及范例 154
7.2 排隊系統(tǒng)分類 155
7.3 Little定律 155
7.4 排隊系統(tǒng)的解析 156
7.4.1 指數(shù)分布 157
7.4.2 生滅過程 158
7.4.3 應(yīng)用案例:自助洗車機排隊系統(tǒng)解析 159
7.5 排隊系統(tǒng)仿真 161
7.5.1 問題描述 161
7.5.2 仿真想定 161
7.5.3 仿真運行 163
7.5.4 仿真優(yōu)化 164
7.6 排隊系統(tǒng)的多目標(biāo)優(yōu)化 165
習(xí)題7 166
第8章 庫存優(yōu)化 168
8.1 庫存系統(tǒng) 168
8.2 經(jīng)典EOQ 168
8.3 分段價格EOQ 170
8.4 帶有儲存上限的多種貨物EOQ 172
8.5 動態(tài)EOQ 174
習(xí)題8 176
第9 章 旅行商問題 178
9.1 TSP的構(gòu)造啟發(fā)式算法 178
9.2 線性規(guī)劃模型 179
9.3 TSP路徑構(gòu)造的貪婪啟發(fā)式算法 179
9.3.1 最近鄰算法 179
9.3.2 插入算法 181
9.3.3 Merger算法 183
9.4 TSP的改進(jìn)啟發(fā)式算法 183
9.4.1 2opt操作 184
9.4.2 kopt操作 186
9.5 TSP的遺傳算法 186
9.5.1 基本原理與步驟 186
9.5.2 算法設(shè)計要點 187
習(xí)題9 188
參考文獻(xiàn) 190