数学建模与数学规划：方法、案例及编程实战（Python+COPT/Gurobi实现）

本书主要从数学规划的视角出发，系统地介绍了数学优化问题建模和求解的相关理论、方法、实际案例，以及基于 Python 和数学规划求解器（COPT 和 Gurobi）的编程实战。全书共分为四部分。第一部分为基本理论和建模方法，重点介绍了数学规划模型分类和建模方法（包括逻辑约束与大 M 建模方法、线性化方法）以及计算复杂性理论。第二部分为建模案例详解，通过理论、案例和实战相结合的方式，详细介绍了如何利用各种建模方法和数学规划求解器对实际生产活动中的优化问题进行建模和求解。这部分内容丰富，案例翔实，代码完整，旨在提高读者的实战能力。第三部分和第四部分聚焦于编程实战，主要讲解如何使用 COPT 和 Gurobi 求解器进行数学规划模型的编程求解。这两部分内容涵盖了调用数学规划求解器的各种高级用法，可以满足读者实现定制化求解的需求。本书适合用作运筹学、数学建模、最优化理论、离散优化等相关课程的高年级本科生、研究生的参考教材，也可供从事数学规划、运筹学、物流与供应链等领域的科研人员、算法开发人员，以及各类数学建模竞赛的参赛者阅读。

刘兴禄，2012年至2016年就读于东北大学工业工程专业（本科）；2016年至2018年就读于清华大学工业工程系（硕士），专业为物流工程；2018年至今，就读于清华大学（博士），清华-伯克利深圳学院，管理科学与工程专业。博士期间的主要研究方向为运筹优化模型与算法，强化学习及其应用等，主要应用场景为共享出行、交通优化、物流配送优化、物流仓库运作优化等；目前，本人已发表3篇SCI期刊论文，1篇SCI期刊论文二轮审稿，2篇EI期刊论文以及多篇EI会议论文和发明专利，并即将在清华大学出版社出版教材一本，名为《运筹优化常用模型、算法及案例实战：Python+Java实现》。本人于2020年11月创办”运小筹”公众号，迄今为止，已经发布技术、科普推文100余篇，粉丝量超过11000，总阅读量超过23万次。本人的CSDN账号，累计阅读量也超过了23万次。

目 录

第 I 部分 基本理论和建模方法

第 1 章 几种重要的数学规划模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1 数学规划模型的分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 几种数学规划模型的一般形式及简单案例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

1.2.1 线性规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.2 混合整数规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.3 二次规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.4 二次约束规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.5 二次约束二次规划. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8

1.2.6 二阶锥规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2.7 半定规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3 数学规划求解器. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12

第 2 章 逻辑约束和大 M 建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.1 命题和逻辑连接词 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2 逻辑运算与建模. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15

2.2.1 逻辑非 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.2 逻辑与 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.3 逻辑或 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.4 逻辑异或 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 逻辑约束与大 M 建模方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.1 常见逻辑条件建模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.2 大 M 建模方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3.3 If-then 约束. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23

2.4 其他逻辑约束建模案例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4.1 至少有 m 个不等式约束成立. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25

2.4.2 至少有 m 个等式约束成立 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.4.3 计数问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.4.4 设施选址问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

第 3 章 线性化方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.1 乘积式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32

3.1.1 两个或多个 0-1 变量相乘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.1.2 0-1 变量乘以连续变量：情形 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33

3.1.3 0-1 变量乘以连续变量：情形 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34

3.1.4 两个连续变量相乘的凸松弛方法：McCormick 包络 . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.1.5 调用求解器验证乘积式线性化方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2 取整 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.3 绝对值. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .38

3.4 min/max 函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.4.1 max {x1, x2} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.4.2 min {x1, x2} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.5 分式函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.6 分段线性函数. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.7 特殊有序集约束及其在线性化中的应用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.7.1 特殊有序集约束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.7.2 应用案例 1：绝对值表达式的线性化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.7.3 应用案例 2：分段线性函数的线性化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.7.4 应用案例 3：平方根表达式的近似线性化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.8 学术论文中线性化方法的应用案例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

第 4 章 计算复杂性理论简介. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.2 时间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.2.1 什么是时间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.2.2 时间复杂度的分析方法与案例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.3 P、NP、NPC 和 NP-hard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.3.1 P 和 NP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65

4.3.2 判定问题和优化问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66

4.3.3 约化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.3.4 NPC 和 NP-Hard. . . .