上篇 线性规划和整数线性规划 2
第一章 预备知识 2
1．1 凸集的定义及性质 2
1．2 超平面 3
1．3 凸集的极点 4
习题 5
第二章 线性规划的基本性质 6
2．1 线性规划问题的标准型 7
2．2 基本解和基本可行解 10
2．3 线性规划的基本定理 11
2．4 基本可行解与极点的关系 12
习题 15
第三章 单纯形法 17
3．1 最优基本可行解的判断 17
3．2 基本可行解的改进 20
3．3 单纯形法概述 22
3．4 初始基本可行解的确定 22
3．5 退化情况与Bland法则 26
习题 29
第四章 对偶线性规划 31
4．1 对偶线性规划的定义 31
4．2 原问题与对偶问题解之间的关系 33
4．3 对偶单纯形法 35
4．4 灵敏度分析 38
习题 41
第五章 运输问题 44
5．1 系数矩阵A的特征 45
5．2 有关闭回路的一些基本概念 47
5．3 求初始基本可行解的最小元素法 50
5．4 最优解的判别方法——位势法 51
5．5 基本可行解的改进 52
5．6 产销不平衡的运输问题及其求解方法 54
5．7 应用举例 56
习题 58
第六章 线性规划的多项式时间算法 60
6．1 线性规划与严格线性不等式组关系 60
6．2 仿射变换与椭球 61
6．3 求解严格线性不等式组的椭球算法 62
6．4 求解Karmarkar标准型的算法 64
6．5 Karmarkar算法的收敛性 66
6．6 化一般线性规划问题为Karmarkar标准型 67
第七章 整数线性规划 69
7．1 整数线性规划问题及实例 69
7．2 分枝定界法 71
7．3 Gomory割平面法 73
7．4 0-1规划 76
习题 79
中篇 组合优化 84
第八章 组合优化问题和计算复杂性 84
8．1 组合优化问题与算法 84
8．2 算法时间复杂性 85
8．3 NP类 88
8．4 NP-完全问题与NP-难问题 89
8．5 处理NP-难问题 91
第九章 背包问题 93
9．1 问题的描述 93
9．2 分枝定界法 94
9．3 近似算法 97
9．4 0-1背包问题的一些相关问题 100
习题 102
第十章 装箱与平行机排序问题 104
10．1 装箱问题及其最优算法 104
10．2 装箱问题的近似算法 106
10．3 平行机排序问题 109
10．4 平行机排序问题的近似算法 111
习题 114
第十一章 图与网络优化问题 117
11．1 基本概念 117
11．2 最小支撑树问题 121
11．3 最短路问题 124
11．4 最大流问题 130
11．5 最小费用流问题 134
11．6 最大基数匹配问题 136
习题 140
第十二章 指派问题和旅行售货商问题 142
12．1 指派问题 142
12．2 旅行售货商问题的描述 145
12．3 易解的旅行售货商问题 146
12．4 旅行售货商问题的近似算法 150
习题 152
第十三章 斯坦纳最小树问题 154
13．1 问题的描述 154
13．2 欧氏平面上的斯坦纳最小树 155
13．3 正权无向网络上的斯坦纳最小树 162
习题 165
下篇 非线性规划 168
第十四章 一般的非线性规划问题 168
14．1 问题的概述 168
14．2 最优解的分类 169
14．3 凸函数 170
14．4 广义凸函数简介 174
14．5 凸规划 177
习题 178
第十五章 最优性的充分和必要条件 180
15．1 无约束极小化问题 180
15．2 带有等式约束的极小化问题 181
15．3 带有不等式约束的极小化问题 183
习题 186
第十六章 迭代算法收敛性的描述 188
16．1 算法的全局收敛性 188
16．2 算法的二次有限终止性 190
16．3 收敛速度的描述 191
习题 192
第十七章 一维极值问题的最优化方法 193
17．1 仅比较函数值的最优化方法 193
17．2 利用函数逼近的一维极小化方法 196
17．3 牛顿方法 197
习题 199
第十八章 无约束极值问题的最优化方法 200
18．1 最速下降法 201
18．2 牛顿法 203
18．3 共轭方向及共轭梯度法 205
18．4 变尺度法（DFP方法） 208
18．5 无约束极值问题的直接法 210
习题 211
第十九章 可行方向方法 213
19．1 Zoutendijk可行方向法 213
19．2 Frank-Wolfe方法 223
19．3 既约梯度法 225
19．4 广义既约梯度法（GRG方法） 229
19．5 投影梯度法 233
习题 236
第二十章 序列无约束极小化方法 238
20．1 惩罚函数法和障碍函数法 238
20．2 恰当惩罚函数法 244
习题 247
第二十一章 割平面方法 248
21．1 割平面方法的综述 249
21．2 Kelley割平面方法 250
21．3 Veinott支撑超平面法 252
习题 254
参考文献 255