整数规划：基础、扩展及应用

图书标准信息

• 作者 殷允强；王杜娟；余玉刚
• 出版社 科学出版社
• 出版时间 2022-06
• 版次 31
• ISBN 9787030720641
• 定价 89.00元
• 装帧 其他
• 开本 其他
• 纸张 胶版纸
• 页数 288页
• 字数 363千字

【内容简介】

本书主要聚焦于大规模整数规划模型的求解方法和策略，深入浅出地阐明了求解大规模整数规划模型主流方法的基本思想、原理、执行步骤以及在实际问题中的应用，共分为引言、整数规划建模、线性规划、精确离散优化方法、割平面法、列生成算法、拉格朗日松弛算法、Benders分解算法和启发式算法九章。每种算法和分析都注重结合问题实际，加入众多现实案例，并配有相应习题。书中还附有相关阅读材料，以便有兴趣的读者进一步钻研探索。

【目录】

前言

章引言1

1.1很优化1

1.2整数规划2

1.3整数规划的发展历程4

1.3.1模型和应用角度4

1.3.2模型求解角度5

1.4整数规划的求解软件6

1.5本书结构8

第2章整数规划建模9

2.1背包模型9

2.1.1模型介绍9

2.1.2应用实例10

2.2广义指派模型14

2.2.1模型介绍14

2.2.2应用实例15

2.3集合包装、覆盖和划分模型18

2.3.1模型介绍18

2.3.2应用实例18

2.4含固定成本的整数规划模型27

2.4.1设施选址模型28

2.4.2网络设计模型32

2.5旅行商模型36

2.5.1模型介绍36

2.5.2模型应用39

题二42

第3章线规划44

3.1线规划的规范型44

3.1.1线规划模型的一般形式44

3.1.2线规划模型的标准型44

3.1.3线规划模型的规范型45

3.1.4线规划模型的矩阵形式48

3.2线规划的基本定理50

3.2.1凸集与极点50

3.2.2基本定理52

3.3单纯形56

3.3.1单纯形的思想56

3.3.2单纯形的步骤56

3.3.3单纯形一般步骤63

3.3.4单纯形的矩阵形式64

3.4对偶理论66

3.4.1对偶问题的基本形式66

3.4.2对偶问题的质69

3.4.3对偶问题的经济学解释71

3.4.4对偶单纯形73

题三77

第4章准确离散优化方84

4.1全枚举84

4.1.1全枚举介绍84

4.1.2全枚举复杂度分析85

4.2模型松弛86

4.3分支定界89

4.3.1分支定界介绍89

4.3.2分支定界算98

4.3.3分支定界算的进一步讨论105

4.4分支定界算的应用109

4.4.1背包问题109

4.4.2购买商品问题113

题四119

第5章割面123

5.1有效不等式123

5.1.1有效不等式定义123

5.1.2强有效不等式126

5.1.3多面体、面和刻面128

5.2chvatal-gomory割面130

5.3gomory割面133

5.3.1纯整数线规划模型133

5.3.2混合整数线规划模型139

5.4混合整数舍入切140

5.5覆盖不等式142

5.6分支定切算144

题五147

第6章列生成算152

6.1dantzig-wolfe分解153

6.1.1基本定理153

6.1.2dantzig-wolfe分解153

6.1.3块角结构155

6.2列生成算157

6.2.1列生成算157

6.2.2列生成算的改进策略167

6.3分支定价算173

6.3.1分支定价算思想173

6.3.2分支策略176

6.4分支定价定切算177

6.4.1分支定价定切算思想177

6.4.2常见鲁棒切179

6.4.3非鲁棒切181

6.5列生成算的应用185

6.5.1乘务调度问题185

6.5.2行机调度问题188

题六191

第7章拉格朗松弛算195

7.1拉格朗原问题和对偶问题195

7.2拉格朗松弛的进一步讨论198

7.2.1等式约束的松弛198

7.2.2含两类约束的拉格朗松弛198

7.3拉格朗对偶问题的求解算200

7.3.1次梯度算200

7.3.2外逼近算204

7.3.3bundle算207

7.4拉格朗松弛算的应用210

7.4.1广义指派问题210

7.4.2开放车间调度问题212

题七215

第8章benders分解算219

8.1benders分解算219

8.1.1benders重表示220

8.1.2benders分解算222

8.2改进策略229

8.2.1benders主问题加速策略229

8.2.2benders切的选择策略231

8.2.3基于cplex的benders分支定切算232

8.3经典benders分解算的扩展234

8.3.1整数benders分解算234

8.3.2逻辑benders分解算237

8.4benders分解算的应用239

8.4.1无容量的多仓库选址分配问题239

8.4.2概率旅行商问题242

8.4.3带有准备时间的不相关行机调度问题245

题八249

第9章启发式算252

9.1准确整数优化方的局限252

9.2局部搜索算253

9.3元启发式方256

9.3.1禁忌搜索算257

9.3.2模拟退火算262

9.3.3遗传算267

题九272

参文献274