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