目 錄
第 I 部分 基本理論和建模方法
第 1 章 幾種重要的數(shù)學(xué)規(guī)劃模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 數(shù)學(xué)規(guī)劃模型的分類(lèi) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 幾種數(shù)學(xué)規(guī)劃模型的一般形式及簡(jiǎn)單案例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
1.2.1 線性規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 混合整數(shù)規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 二次規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 二次約束規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 二次約束二次規(guī)劃. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8
1.2.6 二階錐規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.7 半定規(guī)劃 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 數(shù)學(xué)規(guī)劃求解器. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12
第 2 章 邏輯約束和大 M 建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1 命題和邏輯連接詞 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 邏輯運(yùn)算與建模. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15
2.2.1 邏輯非 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 邏輯與 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 邏輯或 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.4 邏輯異或 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 邏輯約束與大 M 建模方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.1 常見(jiàn)邏輯條件建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.2 大 M 建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.3 If-then 約束. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23
2.4 其他邏輯約束建模案例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 至少有 m 個(gè)不等式約束成立. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25
2.4.2 至少有 m 個(gè)等式約束成立 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.3 計(jì)數(shù)問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.4 設(shè)施選址問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
第 3 章 線性化方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1 乘積式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32
3.1.1 兩個(gè)或多個(gè) 0-1 變量相乘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1.2 0-1 變量乘以連續(xù)變量：情形 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33
3.1.3 0-1 變量乘以連續(xù)變量：情形 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34
3.1.4 兩個(gè)連續(xù)變量相乘的凸松弛方法：McCormick 包絡(luò) . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.1.5 調(diào)用求解器驗(yàn)證乘積式線性化方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 取整 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3 絕對(duì)值. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38
3.4 min/max 函數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.1 max {x1, x2} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.2 min {x1, x2} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5 分式函數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.6 分段線性函數(shù). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.7 特殊有序集約束及其在線性化中的應(yīng)用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.7.1 特殊有序集約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.7.2 應(yīng)用案例 1：絕對(duì)值表達(dá)式的線性化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.7.3 應(yīng)用案例 2：分段線性函數(shù)的線性化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.7.4 應(yīng)用案例 3：平方根表達(dá)式的近似線性化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.8 學(xué)術(shù)論文中線性化方法的應(yīng)用案例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
第 4 章 計(jì)算復(fù)雜性理論簡(jiǎn)介. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2 時(shí)間復(fù)雜度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.1 什么是時(shí)間復(fù)雜度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.2 時(shí)間復(fù)雜度的分析方法與案例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3 P、NP、NPC 和 NP-hard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3.1 P 和 NP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65
4.3.2 判定問(wèn)題和優(yōu)化問(wèn)題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66
4.3.3 約化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.3.4 NPC 和 NP-Hard. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .67
4.4 常見(jiàn)的 NPC 和 NP-hard 問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.5 小結(jié) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
第 II 部分 建模案例詳解
第 5 章 生產(chǎn)計(jì)劃優(yōu)化問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.1 問(wèn)題介紹 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2 問(wèn)題建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.3 完整數(shù)學(xué)模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.4 編程實(shí)戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.4.1 算例準(zhǔn)備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.4.2 建立模型并求解: Python 調(diào)用 COPT 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.4.3 建立模型并求解: Python 調(diào)用 Gurobi 實(shí)現(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .78
5.5 拓展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
第 6 章 數(shù)論方程的數(shù)學(xué)規(guī)劃模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.1 問(wèn)題簡(jiǎn)介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.2 方法 1：引入輔助變量進(jìn)行轉(zhuǎn)換 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.3 方法 2：消去除法運(yùn)算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.4 問(wèn)題拓展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.5 總結(jié) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
第 7 章 機(jī)組排班優(yōu)化問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.1 問(wèn)題描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.2 問(wèn)題分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.3 問(wèn)題建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.3.1 模型假設(shè) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.3.2 符號(hào)說(shuō)明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.3.3 數(shù)學(xué)模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.4 航班鄰接網(wǎng)絡(luò)的相關(guān)問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.5 編程實(shí)戰(zhàn)：Python 調(diào)用 COPT 實(shí)現(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.6 編程實(shí)戰(zhàn)：Python 調(diào)用 Gurobi 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.7 算例參數(shù)設(shè)計(jì)與求解結(jié)果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.8 小結(jié) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
第 8 章 配送網(wǎng)絡(luò)規(guī)劃問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.1 問(wèn)題描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.2 問(wèn)題建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8.3 完整數(shù)學(xué)模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102
8.4 編程實(shí)戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
8.4.1 算例數(shù)據(jù)準(zhǔn)備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.4.2 建立模型并求解: Python 調(diào)用 COPT 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
8.4.3 建立模型并求解: Python 調(diào)用 Gurobi 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
8.4.4 求解結(jié)果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
8.5 拓展. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
第 9 章 數(shù)字華容道問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
9.1 數(shù)字華容道問(wèn)題簡(jiǎn)介. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
9.2 建模思路詳解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .108
9.3 完整數(shù)學(xué)模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112
9.4 編程實(shí)戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
9.4.1 參數(shù)準(zhǔn)備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
9.4.2 測(cè)試算例及其相關(guān)參數(shù)初始化. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .115
9.4.3 建立模型并求解: Python 調(diào)用 COPT 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
9.4.4 建立模型并求解: Python 調(diào)用 Gurobi 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
9.4.5 數(shù)值實(shí)驗(yàn)結(jié)果及分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
9.5 拓展. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
9.5.1 允許區(qū)塊移動(dòng) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
9.5.2 模型的收緊 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
第 10 章 密集存儲(chǔ)倉(cāng)庫(kù)取貨路徑優(yōu)化問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
10.1 密集存儲(chǔ)倉(cāng)庫(kù)簡(jiǎn)介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
10.2 建模思路詳解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .122
10.2.1 建模方法 1：基于物品編號(hào)的模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
10.2.2 建模方法 2：不考慮非目標(biāo)貨物編號(hào)的模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
10.2.3 完整數(shù)學(xué)模型：以建模方法 2 為例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
10.3 編程實(shí)戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
10.3.1 參數(shù)準(zhǔn)備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
10.3.2 建立 NIPA 模型并求解: Python 調(diào)用 COPT 實(shí)現(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . .133
10.3.3 建立 NIPA 模型并求解: Python 調(diào)用 Gurobi 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . 134
10.3.4 建立 NIPF 模型并求解: Python 調(diào)用 COPT 實(shí)現(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . .134
10.3.5 建立 NIPF 模型并求解: Python 調(diào)用 Gurobi 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . 135
10.4 數(shù)值實(shí)驗(yàn)結(jié)果展示及分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
10.5 模型拓展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
10.5.1 NIPF 模型的約束分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
10.5.2 允許同時(shí)移動(dòng) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
第 11 章 機(jī)器人組裝生產(chǎn)計(jì)劃優(yōu)化問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
11.1 問(wèn)題介紹與分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
11.2 問(wèn)題一的建模和求解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
11.2.1 問(wèn)題分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
11.2.2 模型參數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
11.2.3 決策變量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
11.2.4 目標(biāo)函數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
11.2.5 構(gòu)建約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
11.2.6 完整數(shù)學(xué)模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
11.2.7 編程實(shí)戰(zhàn)：Python 調(diào)用 COPT 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
11.2.8 編程實(shí)戰(zhàn)：Python 調(diào)用 Gurobi 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
11.2.9 求解結(jié)果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
11.3 問(wèn)題二的建模和求解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
11.3.1 發(fā)生變化的約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
11.3.2 完整數(shù)學(xué)模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
11.3.3 編程實(shí)戰(zhàn)：Python 調(diào)用 COPT 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
11.3.4 編程實(shí)戰(zhàn)：Python 調(diào)用 Gurobi 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
11.3.5 求解結(jié)果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
11.4 總結(jié)與拓展. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
第 12 章 車(chē)輛路徑規(guī)劃問(wèn)題及其若干變體 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
12.1 車(chē)輛路徑規(guī)劃問(wèn)題簡(jiǎn)介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
12.2 帶容量約束的車(chē)輛路徑規(guī)劃問(wèn)題的建模. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .150
12.2.1 基于弧的建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
12.2.2 基于路徑的建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
12.3 多車(chē)場(chǎng)車(chē)輛路徑規(guī)劃問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
12.3.1 問(wèn)題介紹 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
12.3.2 MDVRP1：允許返回不同車(chē)場(chǎng). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
12.3.3 MDVRP2：必須返回原車(chē)場(chǎng). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162
12.3.4 小結(jié) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
12.4 帶時(shí)間窗的車(chē)輛路徑規(guī)劃問(wèn)題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .163
12.4.1 問(wèn)題介紹 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
12.4.2 帶硬時(shí)間窗的車(chē)輛路徑規(guī)劃問(wèn)題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .164
12.4.3 帶軟時(shí)間窗的車(chē)輛路徑規(guī)劃問(wèn)題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .166
12.4.4 小結(jié) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
12.5 帶時(shí)間窗的多行程車(chē)輛路徑規(guī)劃問(wèn)題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
12.5.1 問(wèn)題介紹 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
12.5.2 第一種建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
12.5.3 第二種建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
12.5.4 小結(jié) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
12.6 帶時(shí)間窗的電動(dòng)車(chē)輛路徑規(guī)劃問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
12.6.1 背景簡(jiǎn)介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
12.6.2 問(wèn)題描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
12.6.3 問(wèn)題建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
12.6.4 小結(jié) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
12.7 編程實(shí)戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
12.7.1 算例數(shù)據(jù)讀取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
12.7.2 Python 調(diào)用 COPT 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
12.7.3 Python 調(diào)用 Gurobi 實(shí)現(xiàn). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .191
12.8 數(shù)值實(shí)驗(yàn)和結(jié)果分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
12.8.1 CVRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
12.8.2 MDVRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
12.8.3 VRPTW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
12.8.4 MTVRPTW. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
12.8.5 EVRPTW. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .204
12.9 總結(jié). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .205
第 13 章 取送貨問(wèn)題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .206
13.1 問(wèn)題描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
13.2 問(wèn)題建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
13.2.1 一對(duì)一的場(chǎng)景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
13.2.2 多對(duì)多的場(chǎng)景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
13.2.3 一對(duì)多對(duì)一的場(chǎng)景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
13.3 一對(duì)一場(chǎng)景的編程實(shí)戰(zhàn)及結(jié)果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
13.3.1 算例的生成和讀取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
13.3.2 建立模型并求解: Python 調(diào)用 COPT 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
13.3.3 建立模型并求解: Python 調(diào)用 Gurobi 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
13.3.4 算例參數(shù)設(shè)計(jì)與結(jié)果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
13.4 多對(duì)多場(chǎng)景的編程實(shí)戰(zhàn)及結(jié)果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
13.4.1 算例的生成和讀取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
13.4.2 建立模型并求解: Python 調(diào)用 COPT 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
13.4.3 建立模型并求解: Python 調(diào)用 Gurobi 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
13.4.4 算例參數(shù)設(shè)計(jì)與結(jié)果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
13.5 一對(duì)多對(duì)一場(chǎng)景的編程實(shí)戰(zhàn)及結(jié)果展示. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .220
13.5.1 算例的生成和讀取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
13.5.2 建立模型并求解: Python 調(diào)用 COPT 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
13.5.3 建立模型并求解: Python 調(diào)用 Gurobi 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
13.5.4 算例參數(shù)設(shè)計(jì)與結(jié)果展示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
13.6 總結(jié). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .222
第 14 章 無(wú)人機(jī)與卡車(chē)聯(lián)合配送問(wèn)題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .223
14.1 問(wèn)題背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
14.2 兩種聯(lián)合配送模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
14.2.1 聯(lián)合但無(wú)交互的模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
14.2.2 聯(lián)合有交互的模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
14.3 建模過(guò)程詳解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .226
14.4 完整數(shù)學(xué)模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .231
14.5 編程實(shí)戰(zhàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
14.5.1 算例設(shè)計(jì) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
14.5.2 算例讀取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
14.5.3 建立模型并求解：Python 調(diào)用 COPT 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
14.5.4 建立模型并求解：Python 調(diào)用 Gurobi 實(shí)現(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
14.5.5 解的提取和可視化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
14.6 數(shù)值實(shí)驗(yàn)及結(jié)果展示. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
14.7 拓展. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .238
第 III 部分 編程實(shí)戰(zhàn)：COPT
第 15 章 基本建模求解方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
15.1 杉數(shù)求解器 COPT 基本介紹. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .241
15.2 COPT 建模求解的準(zhǔn)備工作和基本步驟 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
15.2.1 準(zhǔn)備工作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
15.2.2 基本步驟 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
15.3 COPT 建模求解入門(mén)：食譜搭配問(wèn)題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
15.4 獲取模型的屬性和結(jié)果信息 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
第 16 章 建模求解方法進(jìn)階. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
16.1 建模技巧和輔助工具函數(shù)的使用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
16.1.1 構(gòu)建表達(dá)式的技巧 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
16.1.2 批量添加決策變量/約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
16.2 COPT 的重要求解參數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
16.3 COPT 建模求解進(jìn)階：下料問(wèn)題. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
第 17 章 非線性?xún)?yōu)化問(wèn)題建模與求解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .253
17.1 半定規(guī)劃（SDP） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
17.2 二階錐規(guī)劃（SOCP） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
17.3 凸二次規(guī)劃和凸二次約束規(guī)劃（Convex QP/Convex QCP）. . . . . . . . . . . . . . .257
第 18 章 不可行問(wèn)題的處理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
18.1 計(jì)算 IIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
18.1.1 實(shí)例演示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
18.1.2 獲取 IIS 計(jì)算結(jié)果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
18.2 可行化松弛. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
18.2.1 計(jì)算可行化松弛 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
18.2.2 可行化松弛結(jié)果解讀與模型改進(jìn). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .262
第 19 章 參數(shù)調(diào)優(yōu)工具 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
19.1 引言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .265
19.2 參數(shù)調(diào)優(yōu)工具的重要功能及參數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
19.3 代碼示例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
第 20 章 初始解和解池 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
20.1 初始解和解池簡(jiǎn)介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
20.2 初始解重要參數(shù)介紹. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
20.3 代碼示例：木材切割問(wèn)題的初始解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
20.4 初始解日志解讀 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
第 21 章 回調(diào)函數(shù)的使用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
21.1 引言. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .274
21.2 使用步驟 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
21.3 詳細(xì)案例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
第 IV 部分 編程實(shí)戰(zhàn)：Gurobi
第 22 章 基本建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
22.1 Gurobi 中的建模方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
22.1.1 建模流程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
22.1.2 按行建模和按非零系數(shù)建模. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .283
22.1.3 按列建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
22.1.4 按矩陣建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
22.1.5 Gurobi 中的模型屬性與求解參數(shù). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .289
22.2 Gurobi 中的各類(lèi)文件格式與相關(guān)操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
22.2.1 一個(gè)簡(jiǎn)單的例子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
22.2.2 各種類(lèi)型的文件格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
22.2.3 模型導(dǎo)入與導(dǎo)出的方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
22.3 模型拷貝與模型松弛. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
22.3.1 模型淺拷貝與深拷貝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
22.3.2 模型松弛 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
第 23 章 高級(jí)建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
23.1 多目標(biāo)優(yōu)化模型的相關(guān)操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
23.1.1 Gurobi 多目標(biāo)函數(shù)詳解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
23.1.2 多目標(biāo)優(yōu)化模型的建模方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .300
23.1.3 一些注意事項(xiàng) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
23.2 惰性約束的使用技巧. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
23.2.1 Gurobi 中的惰性更新機(jī)制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .305
23.2.2 Gurobi 中的回調(diào)函數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
23.2.3 惰性約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
23.2.4 惰性約束與割平面的區(qū)別 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
23.3 特殊約束的表達(dá)方式及建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
23.3.1 一般約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
23.3.2 廣義約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
23.3.3 其他類(lèi)型的約束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
第 24 章 基本求解進(jìn)程控制方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
24.1 設(shè)置求解終止條件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
24.1.1 設(shè)置 TimeLimit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
24.1.2 設(shè)置 MIPGap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
24.1.3 其他常見(jiàn)的終止條件參數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
24.2 設(shè)置預(yù)處理算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
24.3 設(shè)置割平面算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
24.4 設(shè)置啟發(fā)式算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
24.4.1 Gurobi 中的啟發(fā)式方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
24.4.2 Gurobi 啟發(fā)式算法的參數(shù)設(shè)置. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .321
24.5 設(shè)置優(yōu)化求解策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
24.5.1 全局優(yōu)化策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
24.5.2 提升可行解質(zhì)量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
24.5.3 加速根節(jié)點(diǎn)松弛求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
24.5.4 變量分支選擇 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
第 25 章 高級(jí)求解進(jìn)程控制方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
25.1 解池管理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
25.1.1 解池的參數(shù)與屬性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
25.1.2 解池功能詳解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
25.1.3 案例演示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
25.1.4 一些注意事項(xiàng) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
25.2 給 MIP 模型賦初始解的方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .331
25.2.1 相關(guān)屬性與參數(shù)匯總 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
25.2.2 為 MIP 模型賦一個(gè)初始解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
25.2.3 為 MIP 模型賦多個(gè)初始解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
25.2.4 案例演示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
25.2.5 其他相關(guān)操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
第 26 章 各種信息的解讀與獲取方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .335
26.1 求解日志信息. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .335
26.1.1 Gurobi 中的日志類(lèi)型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
26.1.2 頭部信息 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
26.1.3 MIP 日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
26.1.4 單純形法日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
26.1.5 解池與多場(chǎng)景日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
26.1.6 多目標(biāo)日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
26.1.7 分布式 MIP 日志 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
26.1.8 IIS 日志. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
26.1.9 日志的相關(guān)操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
26.2 解的狀態(tài)信息. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .344
26.3 對(duì)偶信息獲取. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .345
26.3.1 通過(guò)文件操作直接獲取對(duì)偶模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .345
26.3.2 當(dāng)模型可行時(shí)，獲取對(duì)偶變量 Pi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .345
26.3.3 當(dāng)模型無(wú)界時(shí)，獲取極射線 UnbdRay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
26.3.4 當(dāng)模型不可行時(shí)，獲取 FarkasDual 與 FarkasProof . . . . . . . . . . . . . . . . . . . . . . . 346
26.3.5 對(duì)偶信息的應(yīng)用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
第 27 章 求解參數(shù)調(diào)優(yōu)與模型報(bào)錯(cuò)調(diào)試 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
27.1 參數(shù)調(diào)優(yōu) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
27.1.1 主要功能及相關(guān)參數(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
27.1.2 案例演示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
27.2 模型的錯(cuò)誤診斷 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
27.2.1 使用 IIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
27.2.2 對(duì)模型進(jìn)行逐步診斷 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
參考文獻(xiàn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355