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

本书主要聚焦于大规模整数规划模型的求解方法和策略，深入浅出地阐明了求解大规模整数规划模型主流方法的基本思想、原理、执行步骤以及在实际问题中的应用，共分为引言、整数规划建模、线性规划、准确离散优化方法、割平面法、列生成算法、拉格朗日松弛算法、Benders分解算法和启发式算法九章。每种算法和分析都注重结合问题实际，加入众多现实案例，并配有相应习题。《整数规划：基础、扩展及应用》还附有相关阅读材料，以便有兴趣的读者进一步钻研探索。作为一本研究性与教学性并重的专业教材，本书既可以作为高等院校经济管理类和理工类等专业本科生、研究生的必修教材，又可作为研究人员、专业人员的自学及参考用书。

前言
第1章引言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