運籌優化常用模型、算法及案例實戰 — Python + Java 實現

目  錄

第I部分  運籌優化常用模型及建模技巧

第1章  運籌優化算法相關概念  3

1.1  幾類常見的數學規劃模型  3

1.1.1  線性規劃  3

1.1.2  混合整數規劃  3

1.1.3  二次規劃  4

1.1.4  二次約束規劃  4

1.1.5  二次約束二次規劃  4

1.1.6  二階錐規劃  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  一些結論  8

第2章  運籌優化經典問題數學模型  9

2.1  指派問題  9

2.2  最短路問題  11

2.3  最大流問題  12

2.3.1  問題描述  12

2.3.2  問題建模及最優解  13

2.3.3  最大流問題的一般模型  14

2.3.4  Ford–Fulkerson 算法求解最大流問題  15

2.3.5  Java實現Ford–Fulkerson算法求解最大流問題  18

2.4  最優整數解特性和幺模矩陣  23

2.4.1  指派問題的最優解特性驗證  24

2.4.2  最短路問題的整數最優解特性驗證  27

2.4.3  最優整數解特性的理解  31

2.4.4  幺模矩陣和整數最優解特性  32

2.5  多商品網絡流問題  34

2.6  多商品流運輸問題  37

2.7  設施選址問題  38

2.8  旅行商問題  39

2.8.1  TSP建模方法1：子環路消除約束  41

2.8.2  TSP建模方法2：MTZ約束消除子環路  42

2.8.3  TSP建模方法3：1-tree建模方法  45

2.9  車輛路徑規劃問題  47

2.9.1  概述  47

2.9.2  VRPTW的一般模型  48

第3章  整數規劃建模技巧  51

3.1  邏輯約束  51

3.1.1  兩個命題  51

3.1.2  二選一約束條件  51

3.1.3  指示約束條件  53

3.2  線性化  54

3.2.1  分段線性函數線性化  54

3.2.2  含絕對值形式的線性化  58

3.2.3  含乘積形式的線性化  60

3.2.4  含分式形式的線性化  61

3.2.5  含max/min形式的線性化  62

第4章  大規模線性規劃的對偶  64

4.1  對偶理論概述  64

4.2  原問題與對偶問題之間的關系  65

4.3  對偶理論相關重要定理  66

4.4  最短路問題的對偶  73

4.4.1  借助Excel和具體小算例寫出大規模SPP的對偶  74

4.4.2  SPP中存在負環的特例  76

4.5  多商品網絡流問題的對偶  81

4.5.1  借助Excel和具體小算例寫出大規模MCNF的對偶  81

4.5.2  將Excel中的對偶問題表轉化成公式形式  83

4.5.3  Python調用Gurobi求解MCNF  83

第II部分  常用優化求解器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  基本環境配置  97

5.2.2  環境設置中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  目標函數   104

5.3.6  建模方式  105

5.3.7  模型求解  108

5.3.8  獲取解的信息  108

5.3.9  模型導出與模型導入  109

5.3.10  參數  109

5.3.11  其他  114

5.4  傳統回調  114

5.4.1  參考回調  115

5.4.2  查詢或診斷回調  116

5.4.3  控制回調  117

5.4.4  回調的終止  118

5.4.5  傳統回調示例  119

5.5  通用回調  121

5.5.1  簡介  121

5.5.2  功能  121

5.5.3  通用回調的上下文  121

5.5.4  通用回調示例  123

5.6  Java調用CPLEX求解整數規劃的小例子  124

5.6.1  書架生產問題  124

5.6.2  包裝盒選擇問題  128

第6章  Gurobi的Python API詳解及簡單案例  132

6.1  Python調用Gurobi環境配置  132

6.1.1  完整步驟  132

6.1.2  相關問題  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  設置啟發式的參數  144

6.2.7  Branching  144

6.3  Gurobi能夠求解的模型類別  145

6.3.1  線性規劃  145

6.3.2  混合整數規劃  147

6.3.3  二次規劃  148

6.3.4  二次約束二次規劃  150

6.3.5  二階錐規劃  152

6.4  Python 調用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  多個解、目標函數和場景  162

6.6.4  不可行的模型  162

6.6.5  查詢和修改模型屬性  163

6.6.6  其他修改模型信息的方法  163

6.6.7  惰性更新  164

6.6.8  參數管理  164

6.6.9  管理求解進程：日誌和回調  165

6.6.10  修改求解器的行為：回調  165

6.7  Python調用Gurobi常用類和函數  165

6.7.1  全局函數  165

6.7.2  Model類  166

6.7.3  Var類和MVar類  169

6.7.4  Column類  170

6.7.5  目標函數  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類中的參數：GRB.Param 185

6.9  Gurobi的回調函數  190

6.9.1  什麽是Gurobi的回調函數  190

6.9.2  Gurobi回調函數的用法  192

6.10  Python 調用Gurobi的參數調優  193

6.11  Python調用Gurobi求解整數規劃的簡單例子  194

第7章  調用CPLEX和Gurobi求解MIP的復雜案例：VRPTW和TSP  197

7.1  調用CPLEX和Gurobi求解VRPTW  197

7.1.1  VRPTW的一般模型  197

7.1.2  Java調用CPLEX求解VRPTW  198

7.1.3  Java調用Gurobi求解VRPTW  213

7.1.4  Python調用Gurobi求解VRPTW  221

7.2  Python調用Gurobi求解TSP  232

7.2.1  TSP的MTZ建模及調用Gurobi求解  235

7.2.2  TSP：Python調用Gurobi實現callback添加消除子環路約束  237

第III部分  運籌優化常用算法及實戰

第8章  單純形法  249

8.1  線性規劃問題的標準形式  249

8.2  單純形法流程圖及詳細案例  251

8.3  大$M$法和兩階段法  257

8.4  單純形法偽代碼  259

8.5  Python實現單純形法  260

第9章  Dijkstra算法  265

9.1  Dijkstra算法求解最短路問題詳解  265

9.2  Dijkstra算法步驟及偽代碼  269

9.3  Python實現Dijkstra算法  271

9.3.1  網絡數據準備  271

9.3.2  Dijkstra算法實現  272

9.3.3  算例測試  273

9.4  拓展  274

第10章  分支定界算法  275

10.1  整數規劃和混合整數規劃  275

10.2  分支定界算法求解混合整數規劃  276

10.3  分支定界算法的一般步驟和偽代碼  286

10.4  分支定界算法執行過程的直觀展示  290

10.5  分支定界算法的分支策略  291

10.6  分支定界算法的搜索策略  292

10.7  分支定界算法的剪枝策略  292

10.8  Python調用Gurobi實現分支定界算法的簡單案例  293

10.9  Python調用Gurobi實現分支定界算法求解TSP  300

10.10  Python調用Gurobi實現分支定界算法求解VRPTW  301

第11章  分支切割算法  303

11.1  什麽是分支切割算法  303

11.2  有效不等式  306

11.3  割平面算法  308

11.3.1  Gomory's分數割平面算法  309

11.3.2  其他割平面算法  313

11.4  分支切割算法: 分支定界+割平面  314

11.4.1  分支切割算法偽代碼  314

11.4.2  分支切割算法: 一個詳細的例子  317

11.5  Java調用CPLEX實現分支切割算法求解VRPTW  319

11.5.1  分支定界  319

11.5.2  割平面  320

11.6  Python調用Gurobi實現分支切割算法求解VRPTW完整代碼  321

11.7  Java 調用 CPLEX 實現分支切割算法求解CVRP: 回調函數添加割平面  322

11.7.1  CVRP的基本模型  322

11.7.2  割平面  323

第12章  拉格朗日鬆弛  326

12.1  最優性和鬆弛  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調用Gurobi實現拉格朗日鬆弛求解選址--運輸問題  342

12.7.1  拉格朗日鬆弛應用案例：選址--運輸問題  342

12.7.2  Python代碼實現  345

第13章  列生成算法  347

13.1  為什麽用列生成算法  347

13.2  下料問題  349

13.2.1  引例  349

13.2.2  列生成求解下料問題的一般模型及其偽代碼  352

13.2.3  列生成最優性的幾個小問題  355

13.3  列生成求解下料問題的實現  356

13.3.1  Python調用Gurobi實現列生成求解下料問題示例算例：版本1  357

13.3.2  Python調用Gurobi實現列生成求解下料問題示例算例：版本2

（以人工變量為初始列的方式）  360

13.3.3  Python調用Gurobi實現列生成求解下料問題 : 版本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章  動態規劃  393

14.1  動態規劃  393

14.1.1  動態規劃求解最短路問題  394

14.1.2  問題建模和求解  394

14.1.3  一個較大規模的例子  396

14.2  動態規劃的實現  397

14.2.1  偽代碼  397

14.2.2  Java代碼  398

14.3  動態規劃求解TSP  403

14.3.1  一個簡單的TSP算例  403

14.3.2  偽代碼  408

14.3.3  Python實現：示例算例  409

14.3.4  Python實現：中大規模算例  412

14.4  標簽算法求解帶資源約束的最短路問題  419

14.4.1  帶資源約束的最短路問題  419

14.4.2  標簽算法  424

14.4.3  標簽算法的偽代碼   425

14.4.4  標簽設定算法和標簽校正算法  426

14.4.5  優超準則和優超算法  426

14.4.6  Python實現標簽算法求解SPPRC  427

14.5  Python實現標簽算法結合列生成求解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分解求解大規模混合整數規劃  464

16.4.1  兩階段法實現Dantzig-Wolfe分解算法介紹  465

16.4.2  第1階段  465

16.4.3  第2階段  471

16.5  Python調用Gurobi實現Dantzig-Wolfe分解求解多商品流運輸問題  482

16.5.1  多商品網絡流模型的區塊結構  482

16.5.2  多商品流運輸問題 : Dantzig-Wolfe分解求解  483

16.5.3  Python調用Gurobi實現Dantzig-Wolfe分解求解多商品流運輸問題  487

16.5.4  完整代碼  487

16.5.5  算例格式說明  497

16.5.6  算例運行結果  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  問題描述和模型轉換  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