運籌學（原書第2版）

內容簡介

本書是羅納德L.拉丁所著的經典教材，時隔18年首次修訂，面向本科生（姊妹篇DiscreteOptimization針對研究生階段的學生，1988年問世），首版於1998年，被美國工業工程師協會（IIE）評選為年度圖罪項訂書。本書宗旨是給不同學科背景的讀者提供運籌學學習的全面指南。涵蓋運籌學的全部內容（整數、非整數算法，網路編程，動態數學建模等），加入了眾多主題和案例，每種算法和分析都配有一個小故事和計算練習。修訂版本提升了本書作為本科生教材的難度，與研究生階段的內容銜接更為緊密，同時又可作為研究、專業人員的自學和參考用書。已被普渡大學、加州大學歐文分校、華盛頓大學等高校採用。

圖書目錄

譯者序

前　言

作者簡介

第1章　運用數學模型解決問題1

1.1　運籌學套用案例1

1.2　最佳化及運籌學方法的步驟3

1.3　系統邊界、敏感性分殼戲再析、易處理性以及有效性7

1.4　描述性模型與仿真模擬9

1.5　數值搜尋，精確解與啟發解12

1.6　確定模型與隨機模型14

1.7　本章小結16

練習題17

第2章　運籌學中的確定性最佳化模型19

2.1　決策變數、約束條件以及目標函式19

2.2　圖解法和最最佳化產出22

2.3　大型最佳化模型及其標引32

2.4　線性規劃與非線性規劃38

2.5　離散（或者整數）規劃43

2.6　多目標最佳化模型50

2.7　最佳化模型分類小結54

2.8　計算機求解技術以及AMPL54

練習題61

參考文獻76

第3章　搜尋算法77

3.1　搜尋算法、局部和全局最優77

3.2　沿可行改進方向的搜尋86

3.3　可行改進方向的代數條件93

3.4　線性目標和凸集的易處理性102

3.5　尋找初始可行解109

練習題116

參考文獻119

第4章　線性規劃120

4.1　資源分配模型120

4.2　混料模型124

4.3　運營規劃模型128

4.4　排班和人員規劃模型137

4.5　多階段模型141

4.6　可線性化的非線性目標模型146

4.7　隨機規劃152

練習題157

參考文獻175

第5章　線性規劃的單純形法176

5.1　線性規劃的最優解和標準型176

5.2　頂點搜尋和基本解187

5.3　單純形法196

5.4　字典和單純形表204

5.5　兩階段法208

5.6　退化與零汽地步長217

5.7　單純形法的收斂和循環220

5.8　力求高效：修正單純形法222

5.9　有簡單上下限的單純形法233

練習題240

參考文獻245

第6章　線性規劃的對偶理論與靈敏度分析246

6.1　通用的活動視角與資源視角艱格棗員246

6.2　對線性規劃模型係數變化的定性靈敏度分析250

6.3　線性規劃模型係數靈敏度的定量分析：對偶模型259

6.4　構造想屑踏線性規劃的對偶問題267

6.5　計算機輸出結果與單個參數變化的影響271

6.6　捆槳去模型大幅度改動，再最佳化以及參數規劃285

6.7　線性規劃中的對偶問題和最優解292

6.8　對偶單純形法的搜尋304

6.9　原始—對偶單純形法搜尋308

練習題313

參考文獻327

第7章　線性規劃內點法328

7.1　在可行域內部搜尋328

7.2　對當前解進行尺度變換336

7.3　仿射尺度變換搜尋342

7.4　內點搜尋的對數障礙法348

7.5　原始對偶內點法淚連欠希358

7.6　線性規劃搜尋算法的複雜性364

練習題365

參考文獻371

第8章　目標規劃372

8.1　多目標最佳化模型372

8.2　有效點和有效邊界377

8.3　搶占式最佳化和加權目標382

8.4　目標規劃387

練習題396

參考文獻407

第9章　最短路與離散動態規劃408

9.1　最短路模型408

9.2　利用動態規劃解決最短路問題415

9.3　一對多的最短路問題：貝爾曼—福特算法422

9.4　多對多最短路問題：弗洛伊德—瓦爾肖算法428

9.5　無負權一對多最短路問題：迪傑斯特拉算法435

9.6　一對多無環圖最短路問題440

9.7　CPM項目計畫和最長路444

9.8　離散動態規劃模型450

9.9　利用動態規劃解決整數規劃問題458

9.10　馬爾科夫決策過程461

練習題466

參考文獻476

第10章　網路流與圖477

10.1　圖、網路與流477

10.2　用於網路流搜尋的圈方向487

10.3　消圈算法求最優流497

10.4　網路單純形法求最優流504

10.5　最優網路流的整性512

10.6　運輸及分配模型514

10.7　用匈牙利算法求解分配問題521

10.8　最大流與最小割527

10.9　多商品及增益/損耗流533

10.10　最小/最大生成樹539

練習題544

參考文獻560

第11章　離散最佳化模型561

11.1　塊狀/批量線性規劃及固定成本561

11.2　背包模型與資本預算模型566

11.3　集合包裝、覆蓋和劃分模型571

11.4　分配模型及匹配模型579

11.5　旅行商和路徑模型588

11.6　設施選址和網路設計模型596

11.7　處理機調度及排序模型602

練習題613

參考資料630

第12章　離散最佳化求解方法631

12.1　全枚舉法求解631

12.2　離散最佳化模型的鬆弛模型及其套用633

12.3　分支定界搜尋649

12.4　分支定界法的改良660

12.5　分支切割法671

12.6　有效不等式組676

12.7　割平面理論681

練習題688

參考資料702

第13章　大規模最佳化方法703

13.1　列生成算法和分支定價算法703

13.2　拉格朗日鬆弛算法713

13.3　Dantzig-Wolfe分解算法726

13.4　Benders分解算法731

練習題737

參考文獻742

第14章　計算複雜性理論743

14.1　問題、實例和求解的難度743

14.2　衡量算法複雜性及問題的難度745

14.3　可解問題的多項式時間驗證標準748

14.4　多項式可解和非確定多項式可解749

14.5　多項式時間歸約和NP難問題753

14.6　P問題和NP問題755

14.7　求解NP難問題757

練習題760

參考文獻764

第15章　離散最佳化的啟發式算法765

15.1　構造型啟發式算法765

15.2　針對離散最佳化INLPs問題改進搜尋啟發式算法771

15.3　元啟發式算法：禁忌搜尋和模擬退火777

15.4　進化元啟發式算法和遺傳算法784

練習題787

參考文獻793

第16章　無約束的非線性規劃794

16.1　無約束非線性規劃模型794

16.2　一維搜尋803

16.3　導數、泰勒級數和多維的局部最優解條件812

16.4　凹凸函式和全局最優822

16.5　梯度搜尋827

16.6　牛頓法831

16.7　擬牛頓法和BFGS搜尋835

16.8　無導數最佳化和Nelder-Mead法842

練習題849

參考文獻854

第17章　帶約束的非線性規劃855

17.1　帶約束的非線性規劃模型855

17.2　特殊的NLP：凸規劃、可分離規劃、二次規劃和正項幾何規劃862

17.3　拉格朗日乘子法876

17.4　KARUSH-KUHN-TUCKER最優性條件882

17.5　懲罰與障礙法890

17.6　既約梯度法898

17.7　二次規劃求解方法909

17.8　序列二次規劃917

17.9　可分離規劃方法920

17.10　正項幾何規劃方法927

練習題934

參考文獻945

運籌學（原書第2版）

基本介紹

內容簡介

圖書目錄

相關詞條

熱門詞條