運籌優(yōu)化常用模型、算法及案例實戰(zhàn)（Python+Java實現(xiàn)）

第I部分  運籌優(yōu)化常用模型及建模技巧
第1章  運籌優(yōu)化算法相關(guān)概念  3
1.1  幾類常見的數(shù)學規(guī)劃模型  3
1.1.1  線性規(guī)劃  3
1.1.2  混合整數(shù)規(guī)劃  3
1.1.3  二次規(guī)劃  4
1.1.4  二次約束規(guī)劃  4
1.1.5  二次約束二次規(guī)劃  4
1.1.6  二階錐規(guī)劃  5
1.2  凸集和極點  6
1.2.1  凸集  6
1.2.2  極點  7
1.3  多面體、超平面與半平面  7
1.3.1  多面體  7
1.3.2  超平面與半平面  7
1.4  凸組合和凸包  8
1.4.1  凸組合和凸包的概念  8
1.4.2  一些結(jié)論  8
第2章  運籌優(yōu)化經(jīng)典問題數(shù)學模型  9
2.1  指派問題  9
2.2  最短路問題  11
2.3  最大流問題  12
2.3.1  問題描述  12
2.3.2  問題建模及最優(yōu)解  13
2.3.3  最大流問題的一般模型  14
2.3.4  Ford–Fulkerson 算法求解最大流問題  15
2.3.5  Java實現(xiàn)Ford–Fulkerson算法求解最大流問題  18
2.4  最優(yōu)整數(shù)解特性和幺模矩陣  23
2.4.1  指派問題的最優(yōu)解特性驗證  24
2.4.2  最短路問題的整數(shù)最優(yōu)解特性驗證  27
2.4.3  最優(yōu)整數(shù)解特性的理解  31
2.4.4  幺模矩陣和整數(shù)最優(yōu)解特性  32
2.5  多商品網(wǎng)絡流問題  34
2.6  多商品流運輸問題  37
2.7  設施選址問題  38
2.8  旅行商問題  39
2.8.1  TSP建模方法1：子環(huán)路消除約束  41
2.8.2  TSP建模方法2：MTZ約束消除子環(huán)路  42
2.8.3  TSP建模方法3：1-tree建模方法  45
2.9  車輛路徑規(guī)劃問題  47
2.9.1  概述  47
2.9.2  VRPTW的一般模型  48
第3章  整數(shù)規(guī)劃建模技巧  51
3.1  邏輯約束  51
3.1.1  兩個命題  51
3.1.2  二選一約束條件  51
3.1.3  指示約束條件  53
3.2  線性化  54
3.2.1  分段線性函數(shù)線性化  54
3.2.2  含絕對值形式的線性化  58
3.2.3  含乘積形式的線性化  60
3.2.4  含分式形式的線性化  61
3.2.5  含max/min形式的線性化  62
第4章  大規(guī)模線性規(guī)劃的對偶  64
4.1  對偶理論概述  64
4.2  原問題與對偶問題之間的關(guān)系  65
4.3  對偶理論相關(guān)重要定理  66
4.4  最短路問題的對偶  73
4.4.1  借助Excel和具體小算例寫出大規(guī)模SPP的對偶  74
4.4.2  SPP中存在負環(huán)的特例  76
4.5  多商品網(wǎng)絡流問題的對偶  81
4.5.1  借助Excel和具體小算例寫出大規(guī)模MCNF的對偶  81
4.5.2  將Excel中的對偶問題表轉(zhuǎn)化成公式形式  83
4.5.3  Python調(diào)用Gurobi求解MCNF  83
第II部分  常用優(yōu)化求解器API詳解及應用案例
第5章  CPLEX的Java API詳解及簡單案例  93
5.1  基于Eclipse的CPLEX Java API的安裝與配置：適用于macOS  93
5.2  基于Eclipse的CPLEX Java API的安裝與配置：適用于Windows  97
5.2.1  基本環(huán)境配置  97
5.2.2  環(huán)境設置中java.library.path的問題  98
5.2.3  Javadoc的設置  100
5.3  CPLEX建模  102
5.3.1  類與接口  102
5.3.2  變量   102
5.3.3  表達式   102
5.3.4  范圍約束   104
5.3.5  目標函數(shù)   104
5.3.6  建模方式  105
5.3.7  模型求解  108
5.3.8  獲取解的信息  108
5.3.9  模型導出與模型導入  109
5.3.10  參數(shù)  109
5.3.11  其他  114
5.4  傳統(tǒng)回調(diào)  114
5.4.1  參考回調(diào)  115
5.4.2  查詢或診斷回調(diào)  116
5.4.3  控制回調(diào)  117
5.4.4  回調(diào)的終止  118
5.4.5  傳統(tǒng)回調(diào)示例  119
5.5  通用回調(diào)  121
5.5.1  簡介  121
5.5.2  功能  121
5.5.3  通用回調(diào)的上下文  121
5.5.4  通用回調(diào)示例  123
5.6  Java調(diào)用CPLEX求解整數(shù)規(guī)劃的小例子  124
5.6.1  書架生產(chǎn)問題  124
5.6.2  包裝盒選擇問題  128
第6章  Gurobi的Python API詳解及簡單案例  132
6.1  Python調(diào)用Gurobi環(huán)境配置  132
6.1.1  完整步驟  132
6.1.2  相關(guān)問題  132
6.2  Gurobi算法框架介紹  138
6.2.1  Gurobi MIP Algorithms  138
6.2.2  Presolving  140
6.2.3  Node Selection  141
6.2.4  Cutting Planes  142
6.2.5  Heuristics  143
6.2.6  設置啟發(fā)式的參數(shù)  144
6.2.7  Branching  144
6.3  Gurobi能夠求解的模型類別  145
6.3.1  線性規(guī)劃  145
6.3.2  混合整數(shù)規(guī)劃  147
6.3.3  二次規(guī)劃  148
6.3.4  二次約束二次規(guī)劃  150
6.3.5  二階錐規(guī)劃  152
6.4  Python 調(diào)用Gurobi總體流程  154
6.5  Gurobi求解MIP輸出的日志信息解釋  156
6.5.1  MIP日志示例  156
6.5.2  預求解部分  157
6.5.3  求解進程部分  158
6.5.4  匯總部分  160
6.6  Python接口概述  161
6.6.1  模型概述  161
6.6.2  求解模型  162
6.6.3  多個解、目標函數(shù)和場景  162
6.6.4  不可行的模型  162
6.6.5  查詢和修改模型屬性  163
6.6.6  其他修改模型信息的方法  163
6.6.7  惰性更新  164
6.6.8  參數(shù)管理  164
6.6.9  管理求解進程：日志和回調(diào)  165
6.6.10  修改求解器的行為：回調(diào)  165
6.7  Python調(diào)用Gurobi常用類和函數(shù)  165
6.7.1  全局函數(shù)  165
6.7.2  Model類  166
6.7.3  Var類和MVar類  169
6.7.4  Column類  170
6.7.5  目標函數(shù)  170
6.7.6  表達式  171
6.7.7  約束類  172
6.7.8  求解  175
6.7.9  解的輸出  176
6.8  Python接口中的GRB類  176
6.8.1  GRB類中的常量  176
6.8.2  GRB類中的屬性：GRB.Attr 180
6.8.3  GRB類中的參數(shù)：GRB.Param 185
6.9  Gurobi的回調(diào)函數(shù)  190
6.9.1  什么是Gurobi的回調(diào)函數(shù)  190
6.9.2  Gurobi回調(diào)函數(shù)的用法  192
6.10  Python 調(diào)用Gurobi的參數(shù)調(diào)優(yōu)  193
6.11  Python調(diào)用Gurobi求解整數(shù)規(guī)劃的簡單例子  194
第7章  調(diào)用CPLEX和Gurobi求解MIP的復雜案例：VRPTW和TSP  197
7.1  調(diào)用CPLEX和Gurobi求解VRPTW  197
7.1.1  VRPTW的一般模型  197
7.1.2  Java調(diào)用CPLEX求解VRPTW  198
7.1.3  Java調(diào)用Gurobi求解VRPTW  213
7.1.4  Python調(diào)用Gurobi求解VRPTW  221
7.2  Python調(diào)用Gurobi求解TSP  232
7.2.1  TSP的MTZ建模及調(diào)用Gurobi求解  235
7.2.2  TSP：Python調(diào)用Gurobi實現(xiàn)callback添加消除子環(huán)路約束  237
第III部分  運籌優(yōu)化常用算法及實戰(zhàn)
第8章  單純形法  249
8.1  線性規(guī)劃問題的標準形式  249
8.2  單純形法流程圖及詳細案例  251
8.3  大$M$法和兩階段法  257
8.4  單純形法偽代碼  259
8.5  Python實現(xiàn)單純形法  260
第9章  Dijkstra算法  265
9.1  Dijkstra算法求解最短路問題詳解  265
9.2  Dijkstra算法步驟及偽代碼  269
9.3  Python實現(xiàn)Dijkstra算法  271
9.3.1  網(wǎng)絡數(shù)據(jù)準備  271
9.3.2  Dijkstra算法實現(xiàn)  272
9.3.3  算例測試  273
9.4  拓展  274
第10章  分支定界算法  275
10.1  整數(shù)規(guī)劃和混合整數(shù)規(guī)劃  275
10.2  分支定界算法求解混合整數(shù)規(guī)劃  276
10.3  分支定界算法的一般步驟和偽代碼  286
10.4  分支定界算法執(zhí)行過程的直觀展示  290
10.5  分支定界算法的分支策略  291
10.6  分支定界算法的搜索策略  292
10.7  分支定界算法的剪枝策略  292
10.8  Python調(diào)用Gurobi實現(xiàn)分支定界算法的簡單案例  293
10.9  Python調(diào)用Gurobi實現(xiàn)分支定界算法求解TSP  300
10.10  Python調(diào)用Gurobi實現(xiàn)分支定界算法求解VRPTW  301
第11章  分支切割算法  303
11.1  什么是分支切割算法  303
11.2  有效不等式  306
11.3  割平面算法  308
11.3.1  Gomory's分數(shù)割平面算法  309
11.3.2  其他割平面算法  313
11.4  分支切割算法: 分支定界 割平面  314
11.4.1  分支切割算法偽代碼  314
11.4.2  分支切割算法: 一個詳細的例子  317
11.5  Java調(diào)用CPLEX實現(xiàn)分支切割算法求解VRPTW  319
11.5.1  分支定界  319
11.5.2  割平面  320
11.6  Python調(diào)用Gurobi實現(xiàn)分支切割算法求解VRPTW完整代碼  321
11.7  Java 調(diào)用 CPLEX 實現(xiàn)分支切割算法求解CVRP: 回調(diào)函數(shù)添加割平面  322
11.7.1  CVRP的基本模型  322
11.7.2  割平面  323
第12章  拉格朗日松弛  326
12.1  最優(yōu)性和松弛  326
12.1.1  原始邊界  327
12.1.2  對偶邊界  328
12.2  對偶  328
12.3  拉格朗日松弛  329
12.3.1  拉格朗日松弛介紹  329
12.3.2  拉格朗日對偶問題  330
12.3.3  拉格朗日松弛應用案例：無容量限制的設施選址問題  331
12.4  拉格朗日對偶的加強  333
12.5  求解拉格朗日對偶  335
12.5.1  次梯度算法求解拉格朗日對偶  335
12.5.2  應用案例：拉格朗日松弛求解TSP  338
12.6  如何選擇拉格朗日松弛  340
12.7  Python調(diào)用Gurobi實現(xiàn)拉格朗日松弛求解選址--運輸問題  342
12.7.1  拉格朗日松弛應用案例：選址--運輸問題  342
12.7.2  Python代碼實現(xiàn)  345
第13章  列生成算法  347
13.1  為什么用列生成算法  347
13.2  下料問題  349
13.2.1  引例  349
13.2.2  列生成求解下料問題的一般模型及其偽代碼  352
13.2.3  列生成最優(yōu)性的幾個小問題  355
13.3  列生成求解下料問題的實現(xiàn)  356
13.3.1  Python調(diào)用Gurobi實現(xiàn)列生成求解下料問題示例算例：版本1  357
13.3.2  Python調(diào)用Gurobi實現(xiàn)列生成求解下料問題示例算例：版本2
（以人工變量為初始列的方式）  360
13.3.3  Python調(diào)用Gurobi實現(xiàn)列生成求解下料問題 : 版本3  362
13.4  列生成求解TSP  365
13.4.1  TSP的1-tree建模及列生成求解  365
13.4.2  主問題  366
13.4.3  子問題  367
13.5  列生成求解VRPTW  369
13.5.1  主問題  370
13.5.2  子問題  372
13.5.3  詳細案例演示  373
第14章  動態(tài)規(guī)劃  393
14.1  動態(tài)規(guī)劃  393
14.1.1  動態(tài)規(guī)劃求解最短路問題  394
14.1.2  問題建模和求解  394
14.1.3  一個較大規(guī)模的例子  396
14.2  動態(tài)規(guī)劃的實現(xiàn)  397
14.2.1  偽代碼  397
14.2.2  Java代碼  398
14.3  動態(tài)規(guī)劃求解TSP  403
14.3.1  一個簡單的TSP算例  403
14.3.2  偽代碼  408
14.3.3  Python實現(xiàn)：示例算例  409
14.3.4  Python實現(xiàn)：中大規(guī)模算例  412
14.4  標簽算法求解帶資源約束的最短路問題  419
14.4.1  帶資源約束的最短路問題  419
14.4.2  標簽算法  424
14.4.3  標簽算法的偽代碼   425
14.4.4  標簽設定算法和標簽校正算法  426
14.4.5  優(yōu)超準則和優(yōu)超算法  426
14.4.6  Python實現(xiàn)標簽算法求解SPPRC  427
14.5  Python實現(xiàn)標簽算法結(jié)合列生成求解VRPTW  435
14.5.1  初始化RMP  435
14.5.2  標簽算法求解子問題  437
第15章  分支定價算法  438
15.1  分支定價算法基本原理概述  438
15.2  分支定價算法求解VRPTW  440
15.2.1  VRPTW的通用列生成建模方法  440
15.2.2  分支定價算法完整流程及偽代碼  442
15.2.3  分支策略  445
15.2.4  界限更新  449
第16章  Dantzig-Wolfe分解算法  450
16.1  引例  450
16.2  塊角模型與Dantzig-Wolfe分解  454
16.2.1  塊角模型  454
16.2.2  Minkowski表示定理  455
16.2.3  模型分解  455
16.2.4  兩階段法  458
16.3  詳細案例  459
16.4  Dantzig-Wolfe分解求解大規(guī)?；旌险麛?shù)規(guī)劃  464
16.4.1  兩階段法實現(xiàn)Dantzig-Wolfe分解算法介紹  465
16.4.2  第1階段  465
16.4.3  第2階段  471
16.5  Python調(diào)用Gurobi實現(xiàn)Dantzig-Wolfe分解求解多商品流運輸問題  482
16.5.1  多商品網(wǎng)絡流模型的區(qū)塊結(jié)構(gòu)  482
16.5.2  多商品流運輸問題 : Dantzig-Wolfe分解求解  483
16.5.3  Python調(diào)用Gurobi實現(xiàn)Dantzig-Wolfe分解求解多商品流運輸問題  487
16.5.4  完整代碼  487
16.5.5  算例格式說明  497
16.5.6  算例運行結(jié)果  498
16.6  Dantzig-Wolfe分解求解VRPTW  500
第17章  Benders分解算法  504
17.1  分解方法  504
17.1.1  Benders分解的原理  504
17.1.2  Benders分解的全過程  509
17.1.3  算法框架圖  510
17.1.4  算法偽代碼  511
17.2  詳細案例  512
17.2.1  問題描述和模型轉(zhuǎn)換  512
17.2.2  第1次迭代  513
17.2.3  第2次迭代  515
17.2.4  第3次迭代  516
17.2.5  第4次迭代  517
17.3  Benders分解應用案例  518
17.3.1  固定費用運輸問題  518
17.3.2  設施選址問題  520
參考文獻  523