运筹优化常用模型、算法及案例实战——Python+Java实现

图书标准信息

• 作者 刘兴禄；熊望祺；臧永森；段宏达；曾文佳；陈伟坚
• 出版社 清华大学出版社
• 出版时间 2022-10
• 版次 1
• ISBN 9787302600145
• 定价 128.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸

【内容简介】

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

【目录】

第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