目錄
前言
第一版前言
第1章 引言 1
1.1 最優(yōu)化 1
1.2 整數(shù)規(guī)劃 2
1.3 整數(shù)規(guī)劃的發(fā)展歷程 4
1.3.1 模型和應(yīng)用角度 4
1.3.2 模型求解角度 5
1.4 整數(shù)規(guī)劃的求解軟件 7
1.5 本書(shū)結(jié)構(gòu) 8
第2章 整數(shù)規(guī)劃建模 10
2.1 背包模型 10
2.1.1 模型介紹 10
2.1.2 應(yīng)用實(shí)例 11
2.2 廣義指派模型 15
2.2.1 模型介紹 15
2.2.2 應(yīng)用實(shí)例 16
2.3 集合包裝、覆蓋和劃分模型 19
2.3.1 模型介紹 19
2.3.2 應(yīng)用實(shí)例 19
2.4 含固定成本的整數(shù)規(guī)劃模型 28
2.4.1 設(shè)施選址模型 29
2.4.2 網(wǎng)絡(luò)設(shè)計(jì)模型 33
2.5 旅行商模型 37
2.5.1 模型介紹 37
2.5.2 應(yīng)用實(shí)例 40
習(xí)題二 43
第3章 線性規(guī)劃 45
3.1 線性規(guī)劃的規(guī)范型 45
3.1.1 線性規(guī)劃模型的一般形式 45
3.1.2 線性規(guī)劃模型的標(biāo)準(zhǔn)型 45
3.1.3 線性規(guī)劃模型的規(guī)范型 46
3.1.4 線性規(guī)劃模型的矩陣形式 49
3.2 線性規(guī)劃的基本定理 51
3.2.1 凸集與極點(diǎn) 51
3.2.2 基本定理 53
3.3 單純形法 57
3.3.1 單純形法的思想 57
3.3.2 單純形法的步驟 57
3.3.3 單純形法一般步驟 63
3.3.4 單純形法的矩陣形式 64
3.4 對(duì)偶理論 66
3.4.1 對(duì)偶問(wèn)題的基本形式 67
3.4.2 對(duì)偶問(wèn)題的性質(zhì) 70
3.4.3 對(duì)偶問(wèn)題的經(jīng)濟(jì)學(xué)解釋 72
3.4.4 對(duì)偶單純形法 74
習(xí)題三 78
第4章 精確離散優(yōu)化方法 85
4.1 全枚舉法 85
4.1.1 全枚舉法介紹 85
4.1.2 全枚舉法復(fù)雜度分析 86
4.2 模型松弛 87
4.3 分支定界算法.90
4.3.1 分支定界算法介紹 90
4.3.2 分支定界算法 99
4.3.3 分支定界算法的進(jìn)一步討論 106
4.4 分支定界算法的應(yīng)用 110
4.4.1 背包問(wèn)題 110
4.4.2 購(gòu)買(mǎi)商品問(wèn)題 115
習(xí)題四 121
第5章 割平面法 125
5.1 有效不等式 125
5.1.1 有效不等式定義 125
5.1.2 強(qiáng)有效不等式 128
5.1.3 多面體、面和刻面 130
5.2 Chvatal-Gomory 割平面 132
5.3 Gomory 割平面 135
5.3.1 純整數(shù)線性規(guī)劃模型 135
5.3.2 混合整數(shù)線性規(guī)劃模型 141
5.4 混合整數(shù)舍入切 142
5.5 覆蓋不等式 144
5.6 分支定切算法 146
習(xí)題五 149
第6章 列生成算法 154
6.1 Dantzig-Wolfe分解 155
6.1.1 基本定理 155
6.1.2 Dantzig-Wolfe分解 155
6.1.3 塊角結(jié)構(gòu) 157
6.2 列生成算法 159
6.2.1 列生成算法 159
6.2.2 列生成算法的改進(jìn)策略 169
6.3 分支定價(jià)算法 175
6.3.1 分支定價(jià)算法思想 175
6.3.2 分支策略 178
6.4 分支定價(jià)定切算法 180
6.4.1 分支定價(jià)定切算法思想 180
6.4.2 常見(jiàn)魯棒切 181
6.4.3 非魯棒切 .183
6.5 列生成算法的應(yīng)用 187
6.5.1 乘務(wù)調(diào)度問(wèn)題 187
6.5.2 平行機(jī)調(diào)度問(wèn)題 190
習(xí)題六 193
第7章 拉格朗日松弛算法 197
7.1 拉格朗日原問(wèn)題和對(duì)偶問(wèn)題 197
7.2 拉格朗日松弛的進(jìn)一步討論 200
7.2.1 等式約束的松弛 200
7.2.2 含兩類(lèi)約束的拉格朗日松弛 200
7.3 拉格朗日對(duì)偶問(wèn)題的求解算法 202
7.3.1 次梯度算法 202
7.3.2 外逼近算法 206
7.3.3 Bundle算法 208
7.4 拉格朗日松弛算法的應(yīng)用 212
7.4.1 廣義指派問(wèn)題 212
7.4.2 開(kāi)放車(chē)間調(diào)度問(wèn)題 214
習(xí)題七 217
第8章 Benders分解算法 221
8.1 Benders分解算法 221
8.1.1 Benders重表示 222
8.1.2 Benders分解算法 224
8.2 改進(jìn)策略 235
8.2.1 Benders主問(wèn)題加速策略 235
8.2.2 Benders切的選擇策略 236
8.2.3 基于CPLEX的Benders-分支定切算法 238
8.3 經(jīng)典Benders分解算法的擴(kuò)展 240
8.3.1 整數(shù)Benders分解算法 240
8.3.2 邏輯Benders分解算法 243
8.4 Benders分解算法的應(yīng)用 245
8.4.1 無(wú)容量限制的多倉(cāng)庫(kù)選址分配問(wèn)題 245
8.4.2 概率旅行商問(wèn)題 248
8.4.3 帶有準(zhǔn)備時(shí)間的不相關(guān)平行機(jī)調(diào)度問(wèn)題 251
習(xí)題八 255
第9章 啟發(fā)式算法 258
9.1 精確整數(shù)優(yōu)化方法的局限性 258
9.2 局部搜索算法 258
9.3 元啟發(fā)式方法 262
9.3.1 禁忌搜索算法 262
9.3.2 模擬退火算法 269
9.3.3 遺傳算法.274
習(xí)題九 279
參考文獻(xiàn) 281
附錄 285