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

目录 \n
前言 \n
第1章　引言　1　 \n
1.1　*优化　1　 \n
1.2　整数规划　2　 \n
1.3　整数规划的发展历程　4　 \n
1.3.1　模型和应用角度　4　 \n
1.3.2　模型求解角度　5　 \n
1.4　整数规划的求解软件　6　 \n
1.5　本书结构　8　 \n
第2章　整数规划建模　9　 \n
2.1　背包模型　9　 \n
2.1.1　模型介绍　9　 \n
2.1.2　应用实例　10　 \n
2.2　广义指派模型　14　 \n
2.2.1　模型介绍　14　 \n
2.2.2　应用实例　15　 \n
2.3　集合包装、覆盖和划分模型　18　 \n
2.3.1　模型介绍　18　 \n
2.3.2　应用实例　18　 \n
2.4　含固定成本的整数规划模型　27　 \n
2.4.1　设施选址模型　28　 \n
2.4.2　网络设计模型　32　 \n
2.5　旅行商模型　36　 \n
2.5.1　模型介绍　36　 \n
2.5.2　模型应用　39　 \n
习题二　42　 \n
第3章　线性规划　44　 \n
3.1　线性规划的规范型　44 \n
3.1.1　线性规划模型的一般形式　44　 \n
3.1.2　线性规划模型的标准型　44　 \n
3.1.3　线性规划模型的规范型　45　 \n
3.1.4　线性规划模型的矩阵形式　48　 \n
3.2　线性规划的基本定理　50　 \n
3.2.1　凸集与极点　50　 \n
3.2.2　基本定理　52　 \n
3.3　单纯形法　56　 \n
3.3.1　单纯形法的思想　56　 \n
3.3.2　单纯形法的步骤　56　 \n
3.3.3　单纯形法一般步骤　63　 \n
3.3.4　单纯形法的矩阵形式　64　 \n
3.4　对偶理论　66　 \n
3.4.1　对偶问题的基本形式　66　 \n
3.4.2　对偶问题的性质　69　 \n
3.4.3　对偶问题的经济学解释　71　 \n
3.4.4　对偶单纯形法　73　 \n
习题三　77　 \n
第4章　精确离散优化方法　84　 \n
4.1　全枚举法　84　 \n
4.1.1　全枚举法介绍　84　 \n
4.1.2　全枚举法复杂度分析　85　 \n
4.2　模型松弛　86　 \n
4.3　分支定界　89　 \n
4.3.1　分支定界介绍　89　 \n
4.3.2　分支定界算法　98　 \n
4.3.3　分支定界算法的进一步讨论　105　 \n
4.4　分支定界算法的应用　109　 \n
4.4.1　背包问题　109　 \n
4.4.2　购买商品问题　113　 \n
习题四　119　 \n
第5章　割平面法　123　 \n
5.1　有效不等式　123　 \n
5.1.1　有效不等式定义　123　 \n
5.1.2　强有效不等式　126　 \n
5.1.3　多面体、面和刻面　128　 \n
5.2　Chvatal-Gomory割平面　130　 \n
5.3　Gomory割平面　133　 \n
5.3.1　纯整数线性规划模型　133　 \n
5.3.2　混合整数线性规划模型　139　 \n
5.4　混合整数舍入切　140　 \n
5.5　覆盖不等式　142　 \n
5.6　分支定切算法　144　 \n
习题五　147　 \n
第6章　列生成算法　152　 \n
6.1　Dantzig-Wolfe分解　153　 \n
6.1.1　基本定理　153　 \n
6.1.2　Dantzig-Wolfe分解　153　 \n
6.1.3　块角结构　155　 \n
6.2　列生成算法　157　 \n
6.2.1　列生成算法　157　 \n
6.2.2　列生成算法的改进策略　167　 \n
6.3　分支定价算法　173　 \n
6.3.1　分支定价算法思想　173　 \n
6.3.2　分支策略　176　 \n
6.4　分支定价定切算法　177　 \n
6.4.1　分支定价定切算法思想　177　 \n
6.4.2　常见鲁棒切　179　 \n
6.4.3　非鲁棒切　181　 \n
6.5　列生成算法的应用　185　 \n
6.5.1　乘务调度问题　185　 \n
6.5.2　平行机调度问题　188　 \n
习题六　191　 \n
第7章　拉格朗日松弛算法　195　 \n
7.1　拉格朗日原问题和对偶问题　195　 \n
7.2　拉格朗日松弛的进一步讨论　198　 \n
7.2.1　等式约束的松弛　198　 \n
7.2.2　含两类约束的拉格朗日松弛　198　 \n
7.3　拉格朗日对偶问题的求解算法　200　 \n
7.3.1　次梯度算法　200　 \n
7.3.2　外逼近算法　204　 \n
7.3.3　Bundle算法　207　 \n
7.4　拉格朗日松弛算法的应用　210　 \n
7.4.1　广义指派问题　210　 \n
7.4.2　开放车间调度问题　212　 \n
习题七　215　 \n
第8章　Benders分解算法　219　 \n
8.1　Benders分解算法　219　 \n
8.1.1　Benders重表示　220　 \n
8.1.2　Benders分解算法　222　 \n
8.2　改进策略　229　 \n
8.2.1　Benders主问题加速策略　229　 \n
8.2.2　Benders切的选择策略　231　 \n
8.2.3　基于CPLEX的Benders分支定切算法　232　 \n
8.3　经典Benders分解算法的扩展　234　 \n
8.3.1　整数Benders分解算法　234　 \n
8.3.2　逻辑Benders分解算法　237　 \n
8.4　Benders分解算法的应用　239　 \n
8.4.1　无容量限制的多仓库选址分配问题　239　 \n
8.4.2　概率旅行商问题　242　 \n
8.4.3　带有准备时间的不相关平行机调度问题　245　 \n
习题八　249　 \n
第9章　启发式算法　252　 \n
9.1　精确整数优化方法的局限性　252　 \n
9.2　局部搜索算法　253　 \n
9.3　元启发式方法　256　 \n
9.3.1　禁忌搜索算法　257　 \n
9.3.2　模拟退火算法　262　 \n
9.3.3　遗传算法　267　 \n
习题九　272　 \n
参考文献　274