運(yùn)籌學(xué)（原書第2版）

目　錄
譯者序
前　言
作者簡介
第1章　運(yùn)用數(shù)學(xué)模型解決問題1
　1.1　運(yùn)籌學(xué)應(yīng)用案例1
　1.2　優(yōu)化及運(yùn)籌學(xué)方法的步驟3
　1.3　系統(tǒng)邊界、敏感性分析、易處理性以及有效性7
　1.4　描述性模型與仿真模擬9
　1.5　數(shù)值搜索，精確解與啟發(fā)解12
　1.6　確定模型與隨機(jī)模型14
　1.7　本章小結(jié)16
　練習(xí)題17
第2章　運(yùn)籌學(xué)中的確定性優(yōu)化模型19
　2.1　決策變量、約束條件以及目標(biāo)函數(shù)19
　2.2　圖解法和最優(yōu)化產(chǎn)出22
　2.3　大型優(yōu)化模型及其標(biāo)引32
　2.4　線性規(guī)劃與非線性規(guī)劃38
　2.5　離散（或者整數(shù)）規(guī)劃43
　2.6　多目標(biāo)優(yōu)化模型50
　2.7　優(yōu)化模型分類小結(jié)54
　2.8　計(jì)算機(jī)求解技術(shù)以及AMPL54
　練習(xí)題61
　參考文獻(xiàn)76
第3章　搜索算法77
　3.1　搜索算法、局部和全局最優(yōu)77
　3.2　沿可行改進(jìn)方向的搜索86
　3.3　可行改進(jìn)方向的代數(shù)條件93
　3.4　線性目標(biāo)和凸集的易處理性102
　3.5　尋找初始可行解109
　練習(xí)題116
　參考文獻(xiàn)119
第4章　線性規(guī)劃120
　4.1　資源分配模型120
　4.2　混料模型124
　4.3　運(yùn)營規(guī)劃模型128
　4.4　排班和人員規(guī)劃模型137
　4.5　多階段模型141
　4.6　可線性化的非線性目標(biāo)模型146
　4.7　隨機(jī)規(guī)劃152
　練習(xí)題157
　參考文獻(xiàn)175
第5章　線性規(guī)劃的單純形法176
　5.1　線性規(guī)劃的最優(yōu)解和標(biāo)準(zhǔn)型176
　5.2　頂點(diǎn)搜索和基本解187
　5.3　單純形法196
　5.4　字典和單純形表204
　5.5　兩階段法208
　5.6　退化與零步長217
　5.7　單純形法的收斂和循環(huán)220
　5.8　力求高效：修正單純形法222
　5.9　有簡單上下限的單純形法233
　練習(xí)題240
　參考文獻(xiàn)245
第6章　線性規(guī)劃的對偶理論與靈敏度分析246
　6.1　通用的活動(dòng)視角與資源視角246
　6.2　對線性規(guī)劃模型系數(shù)變化的定性靈敏度分析250
　6.3　線性規(guī)劃模型系數(shù)靈敏度的定量分析：對偶模型259
　6.4　構(gòu)造線性規(guī)劃的對偶問題267
　6.5　計(jì)算機(jī)輸出結(jié)果與單個(gè)參數(shù)變化的影響271
　6.6　模型大幅度改動(dòng)，再優(yōu)化以及參數(shù)規(guī)劃285
　6.7　線性規(guī)劃中的對偶問題和最優(yōu)解292
　6.8　對偶單純形法的搜索304
　6.9　原始—對偶單純形法搜索308
　練習(xí)題313
　參考文獻(xiàn)327
第7章　線性規(guī)劃內(nèi)點(diǎn)法328
　7.1　在可行域內(nèi)部搜索328
　7.2　對當(dāng)前解進(jìn)行尺度變換336
　7.3　仿射尺度變換搜索342
　7.4　內(nèi)點(diǎn)搜索的對數(shù)障礙法348
　7.5　原始對偶內(nèi)點(diǎn)法358
　7.6　線性規(guī)劃搜索算法的復(fù)雜性364
　練習(xí)題365
　參考文獻(xiàn)371
第8章　目標(biāo)規(guī)劃372
　8.1　多目標(biāo)優(yōu)化模型372
　8.2　有效點(diǎn)和有效邊界377
　8.3　搶占式優(yōu)化和加權(quán)目標(biāo)382
　8.4　目標(biāo)規(guī)劃387
　練習(xí)題396
　參考文獻(xiàn)407
第9章　最短路與離散動(dòng)態(tài)規(guī)劃408
　9.1　最短路模型408
　9.2　利用動(dòng)態(tài)規(guī)劃解決最短路問題415
　9.3　一對多的最短路問題：貝爾曼—福特算法422
　9.4　多對多最短路問題：弗洛伊德—瓦爾肖算法428
　9.5　無負(fù)權(quán)一對多最短路問題：迪杰斯特拉算法435
　9.6　一對多無環(huán)圖最短路問題440
　9.7　CPM項(xiàng)目計(jì)劃和最長路444
　9.8　離散動(dòng)態(tài)規(guī)劃模型450
　9.9　利用動(dòng)態(tài)規(guī)劃解決整數(shù)規(guī)劃問題458
　9.10　馬爾科夫決策過程461
　練習(xí)題466
　參考文獻(xiàn)476
第10章　網(wǎng)絡(luò)流與圖477
　10.1　圖、網(wǎng)絡(luò)與流477
　10.2　用于網(wǎng)絡(luò)流搜索的圈方向487
　10.3　消圈算法求最優(yōu)流497
　10.4　網(wǎng)絡(luò)單純形法求最優(yōu)流504
　10.5　最優(yōu)網(wǎng)絡(luò)流的整性512
　10.6　運(yùn)輸及分配模型514
　10.7　用匈牙利算法求解分配問題521
　10.8　最大流與最小割527
　10.9　多商品及增益／損耗流533
　10.10　最?。畲笊蓸?39
　練習(xí)題544
　參考文獻(xiàn)560
第11章　離散優(yōu)化模型561
　11.1　塊狀/批量線性規(guī)劃及固定成本561
　11.2　背包模型與資本預(yù)算模型566
　11.3　集合包裝、覆蓋和劃分模型571
　11.4　分配模型及匹配模型579
　11.5　旅行商和路徑模型588
　11.6　設(shè)施選址和網(wǎng)絡(luò)設(shè)計(jì)模型596
　11.7　處理機(jī)調(diào)度及排序模型602
　練習(xí)題613
　參考資料630
第12章　離散優(yōu)化求解方法631
　12.1　全枚舉法求解631
　12.2　離散優(yōu)化模型的松弛模型及其應(yīng)用633
　12.3　分支定界搜索649
　12.4　分支定界法的改良660
　12.5　分支切割法671
　12.6　有效不等式組676
　12.7　割平面理論681
　練習(xí)題688
　參考資料702
第13章　大規(guī)模優(yōu)化方法703
　13.1　列生成算法和分支定價(jià)算法703
　13.2　拉格朗日松弛算法713
　13.3　Dantzig-Wolfe分解算法726
　13.4　Benders分解算法731
　練習(xí)題737
　參考文獻(xiàn)742
第14章　計(jì)算復(fù)雜性理論743
　14.1　問題、實(shí)例和求解的難度743
　14.2　衡量算法復(fù)雜性及問題的難度745
　14.3　可解問題的多項(xiàng)式時(shí)間驗(yàn)證標(biāo)準(zhǔn)748
　14.4　多項(xiàng)式可解和非確定多項(xiàng)式可解749
　14.5　多項(xiàng)式時(shí)間歸約和NP難問題753
　14.6　P問題和NP問題755
　14.7　求解NP難問題757
　練習(xí)題760
　參考文獻(xiàn)764
第15章　離散優(yōu)化的啟發(fā)式算法765
　15.1　構(gòu)造型啟發(fā)式算法765
　15.2　針對離散優(yōu)化INLPs問題改進(jìn)搜索啟發(fā)式算法771
　15.3　元啟發(fā)式算法：禁忌搜索和模擬退火777
　15.4　進(jìn)化元啟發(fā)式算法和遺傳算法784
　練習(xí)題787
　參考文獻(xiàn)793
第16章　無約束的非線性規(guī)劃794
　16.1　無約束非線性規(guī)劃模型794
　16.2　一維搜索803
　16.3　導(dǎo)數(shù)、泰勒級(jí)數(shù)和多維的局部最優(yōu)解條件812
　16.4　凹凸函數(shù)和全局最優(yōu)822
　16.5　梯度搜索827
　16.6　牛頓法831
　16.7　擬牛頓法和BFGS搜索835
　16.8　無導(dǎo)數(shù)優(yōu)化和Nelder-Mead法842
　練習(xí)題849
　參考文獻(xiàn)854
第17章　帶約束的非線性規(guī)劃855
　17.1　帶約束的非線性規(guī)劃模型855
　17.2　特殊的NLP：凸規(guī)劃、可分離規(guī)劃、二次規(guī)劃和正項(xiàng)幾何規(guī)劃862
　17.3　拉格朗日乘子法876
　17.4　KARUSH-KUHN-TUCKER最優(yōu)性條件882
　17.5　懲罰與障礙法890
　17.6　既約梯度法898
　17.7　二次規(guī)劃求解方法909
　17.8　序列二次規(guī)劃917
　17.9　可分離規(guī)劃方法920
　17.10　正項(xiàng)幾何規(guī)劃方法927
　練習(xí)題934
　參考文獻(xiàn)945