离散最优化算法2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

离散最优化算法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