离散最优化算法PDF电子书下载

第一章 线性规划 1

1.1线性规划的基本概念 1

1.2单纯形算法 6

1.3线性规划的对偶理论 14

1.4对偶单纯形算法 15

1.5原始-对偶算法 25

1.6单纯形算法是非多项式算法 28

1.7线性规划问题的多项式时间算法 30

习题 32

参考文献 34

第二章 整数线性规划 36

2.1引言 36

2.2分数对偶割平面算法 38

2.3整数对偶割平面算法 43

2.4混合整数规划的割平面算法 46

2.5分支估界算法 48

2.6 0-1规划的隐数法（implicit enumeration） 54

习题 56

参考文献 58

第三章 网络规划 59

3.1图的搜索算法 59

3.1.1无向图的深探法（DFS） 59

3.1.2无向图的广探法（BFS） 60

3.2网络流模型及解的整数性 61

3.3网络中的最短路 63

3.3.1非负权网络的最短路算法 64

3.3.2无负回路网络中的最短路算法 67

3.3.3所有点对之间的最短路算法 68

3.4网络中的最大流 69

3.4.1最大流的Ford-Fulkerson算法 70

3.4.2最大流的Dinits算法 73

3.4.3容量具有上下界的最大流算法 78

3.4.4可行性定理及其组合应用 80

3.5最小费用流 86

3.5.1模型Ⅱ的相继最短路算法 86

3.5.2最小费用循环流的平均圈算法 91

习题 93

参考文献 95

第四章 树与拟阵 97

4.1树的基本性质 97

4.2树的中心与重心 99

4.3无向网络中的最优生成树 100

4.4有向树 102

4.5拟阵的基本概念与性质 105

4.5.1拟阵的定义与例子 105

4.5.2拟阵的一些基本性质 106

4.6拟阵与Greedy算法 108

4.7拟阵的最大交 112

4.8最大权交的算法 116

习题 122

参考文献 123

第五章 动态规划 125

5.1网络中两点间的最优路问题 126

5.2用动态规划方法解某些非线性规划 129

5.3用动态规划方法解某些整数规划 133

5.4生产计划与资源分配问题 137

5.4.1生产计划问题 137

5.4.2资源分配问题 139

5.5排序问题 140

5.5.1排序问题 141

5.5.2货郎问题 144

5.6矩阵链与公共子序列 145

5.6.1矩阵链中矩阵相乘的顺序问题 146

5.6.2最长公共子序列问题 147

习题 149

参考文献 150

第六章 逆最优化问题 151

6.1逆线性规划的一般模型 151

6.2在范数l1下式（6.1.5）和式（6.1.6）的解 153

6.2.1给定的可行解X0为0-1的解 153

6.2.2在范数l1下模型LP2的解 156

6.3在范数l∞下式（6.1.5）和式（6.1.6）的解 159

6.4组合优化的逆问题一般模型 161

6.5各种逆最优化问题的归结 163

6.6瓶颈扩张问题的一例 168

习题 171

参考文献 172

第七章 算法、复杂性与NP-完全理论 174

7.1问题、算法与复杂性 174

7.2多项式算法P类和NP类 180

7.3多项式变换与NPC类 182

7.4 NP-完全问题的证明举例 185

7.5关于NP-完全性的另一些概念 193

7.5.1 Co-NP类 193

7.5.2 NP-hard类 195

7.5.3伪多项式算法与强NP-完全性 196

习题 198

参考文献 199

第八章 近似算法及其分类 201

8.1近似算法的基本概念 201

8.2非空闲策略 202

8.3 Greedy算法 206

8.4局部搜索 210

8.5基于线性规划的近似算法 212

8.6基于动态规划的近似算法 214

8.7绝对近似类 215

8.8相对近似类 218

8.9 PTAS类与FPTAS类 220

8.10随机近似算法 223

8.11近似算法的概率分析 229

习题 230

参考文献 232