正版新书]运筹优化常用模型、算法及案例实战——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

《运筹优化常用模型、算法及案例实战》主要讲述运筹优化领域常用的数学模型、精确算法以及相应的代码实现。

《运筹优化常用模型、算法及案例实战》主要讲述运筹优化领域常用的数学模型、精确算法以及相应的代码实现。首先简要介绍基本理
论，然后用丰富的配套案例讲解多个经典的精确算法框架，最后结合常用的优化求解器（CPLEX 和
Gurobi）说明如何用 Python 和 Java 语言实现书中提到的所有精确算法。
全书共分 3 部分。第 I 部分（第 1~4 章）为运筹优化常用模型及建模技巧。该部分着重介绍整数规
划的建模技巧和常见的经典模型。第 II 部分（第 5~7 章）为常用优化求解器 API 详解及应用案例。该
部分主要介绍两款常用的商业求解器（CPLEX 和 Gurobi）的使用方法，包括 Python 和 Java 的 API 详
解、简单案例以及复杂案例。第 III 部分（第 8~17 章）为运筹优化常用算法及实战。该部分详细介绍几
个经典的精确算法的理论、相关案例、伪代码以及相应的代码实现。
本书适合作为高等院校工业工程、管理科学与工程、信息管理与信息系统、数学与应用数学、物流
工程、物流管理、控制科学与工程等开设运筹学相关课程的高年级本科生、研究生教材，同时也可供在
物流与供应链、交通、互联网、制造业、医疗、金融、能源等领域从事有关运筹优化的开发人员以及广
大科技工作者和研究人员参考。