运筹优化常用模型、算法及案例实战（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