数学规划与组合优化PDF电子书下载

上篇 线性规划和整数线性规划 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