本書介紹了運籌學(xué)的主要理論和方法, 共分為八章, 包括無處不在的運籌學(xué)、線性規(guī)劃、線性規(guī)劃的對偶理論、運輸問題、非線性規(guī)劃、圖與網(wǎng)絡(luò)、整數(shù)規(guī)劃、動態(tài)規(guī)劃、決策論、博弈論和大數(shù)據(jù)時代的運籌學(xué)。本書在選材上詳略得當(dāng), 重點突出, 對專業(yè)詞匯給出了中英文對照; 注重內(nèi)容闡述的啟發(fā)性和新穎性, 對經(jīng)典方法的講解由淺入深, 適當(dāng)增加了運籌學(xué)的最新研究理論和方法, 拓展讀者的視野;強調(diào)理論闡述的嚴(yán)密性, 給出必要的算法思路和邏輯推演過程; 引入了具有時代性的應(yīng)用案例分析; 介紹了如何用Excel 和Gurobi 來求解模型, 增強了本書的實用性。
本書適合作為普通高等院校相關(guān)專業(yè)開設(shè)運籌學(xué) 課程的教材或參考書。
本書遵循教指委相關(guān)指導(dǎo)文件和高等院校學(xué)生學(xué)習(xí)規(guī)律編寫而成。踐行四新理念,融入思政元素,注重理論與實踐相結(jié)合。
第2 版前言
本書自2016 年6 月首次出版以來, 得到了廣大讀者的喜愛, 被一些高等院校選作教材和教學(xué)參考書, 總體反映良好。作者團隊在運籌學(xué) 課程的教學(xué)中也一直使用本書,收到了比較滿意的效果。結(jié)合多年的教學(xué)經(jīng)驗和讀者反饋, 我們收集了書中存在的一些問題和有待改進(jìn)之處。為更好地提升教材質(zhì)量, 并更進(jìn)一步反映運籌學(xué)領(lǐng)域近年來的新發(fā)展, 在江蘇省高等學(xué)校重點教材(修訂) 項目的支持下, 我們對本書進(jìn)行了再版修訂。
在保持原書特色的前提下, 本次修訂對全書內(nèi)容做了較多增刪, 優(yōu)化了章節(jié)結(jié)構(gòu)和內(nèi)容編排, 主要的修改和調(diào)整如下。第一, 新增了第1 章無處不在的運籌學(xué), 對運籌學(xué)的起源發(fā)展、應(yīng)用場景、學(xué)科特點, 以及運籌學(xué)在中國的發(fā)展與近年來取得的實踐進(jìn)展做了介紹。第二, 新增了第11 章大數(shù)據(jù)時代的運籌學(xué), 結(jié)合當(dāng)下運籌學(xué)與數(shù)據(jù)科學(xué)、人工智能等領(lǐng)域緊密結(jié)合的發(fā)展趨勢, 介紹了兩種數(shù)據(jù)驅(qū)動的決策模式; 針對不同適用場景, 介紹了常用的優(yōu)化求解工具和針對大規(guī)模問題的求解算法設(shè)計。同時結(jié)合實際案例,展示了如何依照數(shù)據(jù)驅(qū)動的模式開展科學(xué)決策。第三, 對原書第4 章整數(shù)規(guī)劃 做了較大幅度改寫, 并調(diào)整了章節(jié)次序; 完善了對分支定價和割平面算法的介紹, 增加了對分支割平面算法和啟發(fā)式算法的介紹, 以及應(yīng)用案例。第四, 在第2 章線性規(guī)劃 部分增加了修正單純形法, 并在應(yīng)用舉例中補充了建模過程中的線性化轉(zhuǎn)換技巧。此外, 在第8 章動態(tài)規(guī)劃 中增加了對強化學(xué)習(xí)的簡要介紹; 在第10 章博弈論 中增加了對動態(tài)博弈的介紹。最后, 考慮到使修訂后的教材更加突出運籌學(xué)最核心的基本內(nèi)容, 以一般性建模方法和求解算法為主, 同時限于篇幅, 我們刪除了原書最后兩章排隊論 和存儲論 的內(nèi)容。
除了上述內(nèi)容修改, 本次修訂還對書中的部分例題、案例和習(xí)題做了更新和調(diào)整, 剔除了一些問題背景描述過時的, 重新改寫了一些題意表達(dá)不清的, 以使舉例更具時代感和真實性。本書大部分核心章節(jié)的最后都單獨給出了應(yīng)用舉例小節(jié), 旨在突出運籌學(xué)的應(yīng)用實踐意義。
同時, 本書更加注重思政教育的引領(lǐng)作用, 并努力將其有機融入教學(xué)內(nèi)容之中。以第一章為例, 該章節(jié)緊密結(jié)合運籌學(xué)在我國的發(fā)展歷程和科技強國戰(zhàn)略, 展示了中國企業(yè)近年來在運籌優(yōu)化技術(shù)與業(yè)務(wù)場景深度融合方面的顯著成就, 涵蓋了國民經(jīng)濟多個領(lǐng)域的重大突破。這些內(nèi)容不僅能激發(fā)學(xué)生讀者的愛國熱情和民族自豪感, 還能增強他們對國家發(fā)展的責(zé)任感和使命感。
本書為提升學(xué)習(xí)體驗和提高學(xué)習(xí)效率, 還進(jìn)行了新形態(tài)教材的設(shè)計。在正文中, 針對一些重難點部分, 我們不僅提供了深入的解析, 還鏈接了書本外的豐富資料, 讀者只需使用智能手機掃描相關(guān)處出現(xiàn)的二維碼, 即可輕松訪問這些數(shù)字化資源, 實現(xiàn)跨媒體鏈接。
本書第2 版由周晶任主編, 徐薇任副主編, 她們負(fù)責(zé)內(nèi)容的選擇和審定。各章節(jié)的編寫和修訂任務(wù)具體分工為: 周晶參與編寫第4 章、第6 章和第10 章; 徐薇負(fù)責(zé)編寫第1章、第2 章、第3 章和第5 章, 并參與第4 章的修訂; 朱振濤負(fù)責(zé)編寫第4 章; 伊俊敏負(fù)責(zé)編寫第6 章; 胡騫、羅志興負(fù)責(zé)編寫第7 章; 安智宇負(fù)責(zé)編寫第8 章; 徐紅利負(fù)責(zé)編寫第9 章; 占楊負(fù)責(zé)編寫第10 章, 并參與第8 章的修訂; 陳彩華負(fù)責(zé)編寫第11 章。
在本書的編寫和修訂過程中, 我們被許多使用本書的教師和學(xué)生的積極反饋和寶貴建議所鼓舞, 對于他們的支持我們表示衷心感謝。一本優(yōu)秀的教材是持續(xù)精進(jìn)和打磨的成果。盡管我們不懈努力, 但書中一定還會存在疏漏或不妥之處, 懇請廣大讀者批評指正。
編 者第1 版前言
樸素的運籌思想古已有之, 在我國古代文獻(xiàn)中有許多記載, 如戰(zhàn)國時期流傳后世的賽馬比賽田忌賽馬, 就是一個經(jīng)典的博弈案例。田忌賽馬的故事說明事前的籌劃安排是十分重要的。在已有的條件下, 經(jīng)過精心籌劃、安排, 選擇一個好的方案, 就會取得滿意的效果。敵我雙方交戰(zhàn), 要克敵制勝就要在了解雙方情況的基礎(chǔ)上, 研究制定最佳的對付敵人的策略和戰(zhàn)術(shù), 這就是所謂的運籌帷幄之中, 決勝千里之外。
運籌學(xué)這個名詞最早出現(xiàn)于1938 年, 當(dāng)時的英國為了研究整個防空作戰(zhàn)系統(tǒng)的合理運行, 以便有效地防備德國飛機入侵, 成立了由來自物理、數(shù)學(xué)等不同學(xué)科領(lǐng)域的科學(xué)家組成的研究小組, 他們的研究工作在有效打擊敵人和減少盟軍的損失方面發(fā)揮了重要作用。他們在一份研究報告中首次使用了Operation Reseach 一詞。第二次世界大戰(zhàn)結(jié)束后,運籌學(xué)研究的重點轉(zhuǎn)向民用領(lǐng)域, 并獲得成功。1947 年, 美國數(shù)學(xué)家G.B.Dantzig 提出了求解線性規(guī)劃模型的有效方法單純形法, 并于20 世紀(jì)50 年代初應(yīng)用電子計算機求解線性規(guī)劃問題獲得成功。到20 世紀(jì)50 年代末, 學(xué)者們對企業(yè)中的一些普遍性優(yōu)化問題,如庫存、資源分配、設(shè)備更新和任務(wù)分派等問題進(jìn)行研究, 并成功地應(yīng)用到建筑、紡織、鋼鐵、煤炭、石油、電力和農(nóng)業(yè)等諸多行業(yè)。20 世紀(jì)60 年代, 運籌學(xué)方法又廣泛應(yīng)用到了服務(wù)性行業(yè)和社會公共事業(yè)。
運籌學(xué)一詞在英國稱為Operational Research, 在美國稱為Operations Research, 縮寫為O.R.!洞笥倏迫珪分嘘U明: 運籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué), 運籌學(xué)為掌握這類系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析工具。運籌學(xué)最早主要研究經(jīng)濟活動和軍事活動中能用數(shù)量來表達(dá)的有關(guān)策劃、管理方面的問題。隨著時代的進(jìn)步和科學(xué)技術(shù)的發(fā)展, 運籌學(xué)的應(yīng)用更為廣泛, 而且解決問題的規(guī)模也越來越大、越來越復(fù)雜,F(xiàn)實中的優(yōu)化問題雖然千差萬別, 但用運籌學(xué)來分析和處理時, 一般都遵循以下幾個工作步驟: 確定目標(biāo)、制訂方案、建立模型、提出解法。不同類型的問題可歸結(jié)為多類不同的數(shù)學(xué)模型, 從而形成了不同的運籌學(xué)學(xué)科分支, 如數(shù)學(xué)規(guī)劃(包含線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃和動態(tài)規(guī)劃等)、圖論與網(wǎng)絡(luò)流、決策論、對策論、排隊論、存儲論, 等等。
數(shù)學(xué)規(guī)劃的研究對象是最為一般的優(yōu)化問題, 即在給定的限制條件下, 按某一衡量指標(biāo)來尋找最優(yōu)方案。它可以表示為求函數(shù)在滿足約束條件下的極大或極小值問題。數(shù)學(xué)規(guī)劃中最簡單的一種問題就是線性規(guī)劃。線性規(guī)劃及其單純形法對運籌學(xué)的發(fā)展起到了重大的推動作用。許多實際問題都可以轉(zhuǎn)化成線性規(guī)劃來解決, 單純形法是解決線性規(guī)劃的一個行之有效的算法, 而計算機技術(shù)的發(fā)展, 使一些大型復(fù)雜的實際優(yōu)化問題的解決成為現(xiàn)實。
圖論是一種用直觀的圖形來表述和解決一類優(yōu)化問題的運籌學(xué)分支。最小支撐樹、最短路和最大流等問題是圖論中經(jīng)典的最優(yōu)化問題。一些不具有圖形特征的優(yōu)化問題也可以用圖形來表述和求解, 并且更為直觀和簡便, 如匹配問題、設(shè)備更新問題等。網(wǎng)絡(luò)分析技術(shù)則利用圖形來描述一個工程項目中各項活動之間的關(guān)聯(lián)和時間進(jìn)度, 從而可以對項目進(jìn)度進(jìn)行控制和優(yōu)化。
現(xiàn)實生活中, 人們常常需要在一些可選方案中進(jìn)行選擇, 而選擇的情景可能是不確定的或有風(fēng)險的, 或者是評價方案的目標(biāo)有多個。如何進(jìn)行選擇或決策, 就是決策論要解決的問題。而如果決策者面對一個與他有競爭的決策者時, 決策問題就變成了一個博弈問題, 前面提到的田忌賽馬就是典型的博弈案例。研究博弈問題的理論和方法就是博弈論(也叫作對策論)。
排隊論是運籌學(xué)的一個重要分支, 它又叫作隨機服務(wù)系統(tǒng)理論。它的研究目的是要回答如何改進(jìn)服務(wù)機構(gòu)或如何組織被服務(wù)的對象, 使得某種指標(biāo)達(dá)到最優(yōu)的問題。比如一個港口應(yīng)該有多少個碼頭, 銀行營業(yè)廳應(yīng)設(shè)置多少服務(wù)窗口等。排隊是一個隨機現(xiàn)象, 因此在研究排隊問題時, 需要以概率論作為分析工具。
存儲論是研究如何平衡供給與需求之間矛盾的理論與方法。其基本的數(shù)學(xué)問題就是在特定的需求假設(shè)下, 確定最優(yōu)的訂貨量或生產(chǎn)量。
和所有的其他數(shù)學(xué)分支一樣, 運籌學(xué)的內(nèi)容有其經(jīng)典不變的一面, 但是隨著社會經(jīng)濟的發(fā)展和科學(xué)技術(shù)的變革, 其應(yīng)用對象所呈現(xiàn)出的豐富性和復(fù)雜性也與日俱增。因此, 運籌學(xué)的理論研究和應(yīng)用前景都面臨更大的機遇和挑戰(zhàn)。比如, 隨著人們對決策行為的關(guān)注, 已經(jīng)提出行為運籌學(xué)的概念。此外, 隨著移動互聯(lián)網(wǎng)技術(shù)的發(fā)展, 可獲得海量的實際數(shù)據(jù), 這些為運籌學(xué)的應(yīng)用提供了更為廣闊的空間, 使其能夠發(fā)揮越來越重要的作用。迪士尼游樂場的Fastpass 系統(tǒng)中就運用了排隊論方法。又如目前交通出行的叫車App 應(yīng)用軟件, 其中也包含了最優(yōu)匹配等優(yōu)化算法。
本書著重介紹運籌學(xué)的主要分支內(nèi)容, 在選材上詳略得當(dāng), 重點突出, 對專業(yè)詞匯給出了中英文對照; 注重內(nèi)容闡述的啟發(fā)性和新穎性, 對經(jīng)典方法的講解由淺入深, 適當(dāng)增加了運籌學(xué)的最新研究理論和方法, 拓展讀者視野; 注重內(nèi)容理論闡述的嚴(yán)密性, 給出必要的理論性證明和推理; 注重案例的時代性, 教材中引入了一些新的應(yīng)用案例, 由案例問題引出理論分析方法, 再回到實際問題的解決過程; 案例及附件中介紹了如何用Excel 來求解模型, 增強了本書的實用性。
本書由周晶擔(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 章。
編 者
1983年東南大學(xué)應(yīng)用數(shù)學(xué)專業(yè)本科,1986年東南大學(xué)控制理論與應(yīng)用專業(yè)碩士,2000年獲東南大學(xué)系統(tǒng)工程專業(yè)博士學(xué)位。1986年至2000年12月在東南大學(xué)任教,2001年1月起至今在南京大學(xué)任教。現(xiàn)為南京大學(xué)工程管理學(xué)院副院長,教授、博士生導(dǎo)師。中國管理科學(xué)與工程學(xué)會常務(wù)理事。
目 錄
第2 版前言
第1 版前言
第1 章
無處不在的
運籌學(xué)
1.1 運籌學(xué)的起源與發(fā) 001
1.2 運籌學(xué)的應(yīng)用場 003
1.3 運籌學(xué)的學(xué)科特點和研究分 005
1.4 運籌學(xué)解決問題的步 007
1.5 運籌學(xué)在中國的發(fā)展與實 009
第2 章
線性規(guī)劃
2.1 線性規(guī)劃建 011
2.2 線性規(guī)劃的圖解 016
2.3 線性規(guī)劃解的特征與基本定 020
2.4 單純形 022
2.5 單純形法的進(jìn)一步討 028
2.6 修正單純形 038
2.7 應(yīng)用舉 043
第3 章
線性規(guī)劃的
對偶理論
3.1 線性規(guī)劃的對偶問 052
3.2 對偶理 057
3.3 對偶理論的應(yīng) 062
3.4 對偶單純形 065
3.5 靈敏度分 067
第4 章
運輸問題
4.1 運輸問題的數(shù)學(xué)模 076
4.2 運輸單純形法(表上作業(yè)法) 082
4.3 運輸問題的擴 089
4.4 應(yīng)用舉 095
第5 章
非線性規(guī)劃
5.1 非線性規(guī)劃模型及解的定 105
5.2 凸函數(shù)和凸規(guī) 110
5.3 下降迭代算法框 113
5.4 一維搜 114
5.5 無約束優(yōu)化問題的求解算 120
5.6 約束極值問題的最優(yōu)性條 128
5.7 約束優(yōu)化問題的求解算 132
5.8 應(yīng)用舉 138
第6 章
圖與網(wǎng)絡(luò)
6.1 圖與網(wǎng)絡(luò)基礎(chǔ)概 144
6.2 148
6.3 最短路問 152
6.4 最大流問 157
6.5 最小費用流問 161
6.6 中國郵遞員問 165
6.7 網(wǎng)絡(luò)計 168
第7 章
整數(shù)規(guī)劃
7.1 整數(shù)規(guī)劃問題及模 179
7.2 整數(shù)規(guī)劃的集合與幾何特 183
7.3 割平面 185
7.4 分支定界 190
7.5 0 -1 整數(shù)規(guī) 194
7.6 啟發(fā)式算 199
7.7 應(yīng)用案例配送系統(tǒng)設(shè) 201
第8 章
動態(tài)規(guī)劃
8.1 多階段決策問 208
8.2 動態(tài)規(guī)劃的基本概念和基本方 211
8.3 最優(yōu)化原理與最優(yōu)性定 217
8.4 動態(tài)規(guī)劃問題的求 219
8.5 應(yīng)用舉 224
第9 章
決策論
9.1 決策的概念與分 241
9.2 確定型決策分 244
9.3 不確定型決策分 244
9.4 風(fēng)險型決策分 247
9.5 多準(zhǔn)則決策分 254
9.6 效用函 263
9.7 行為決策理 266
第10 章
博弈論
10.1 博弈的基本概念與分 275
10.2 完全信息靜態(tài)博 277
10.3 零和博 286
10.4 完全信息動態(tài)博 289第11 章
第11 章
大數(shù)據(jù)時代
的運籌學(xué)
11.1 大數(shù)據(jù)時代的決策模式和運籌建 296
11.2 大數(shù)據(jù)背景下的運籌優(yōu)化問題求 302
11.3 數(shù)據(jù)驅(qū)動的運籌優(yōu)化案 308
11.4 材料來 312
附 錄
附錄A 線性規(guī)劃問題的Excel 求 314
附錄B 線性規(guī)劃問題的Gurobi 求 327
附錄C 名詞術(shù)語中英文對 337
參考文 341