组合最优化 算法和复杂性PDF电子书下载

前言 1

第一章 最优化问题 1

1.1 引言 1

1.2 最优化问题 4

1.3 领域 8

1.4 局部最优与整体最优 10

1.5 凸集与凸函数 12

1.6 凸规划问题 15

习题 17

注释与参考资料 20

A.1 线性代数 21

附录：术语与符号 21

A.2 图论 22

A3 拟Algol语言 27

第二章 单纯形算法 30

2.1 线性规划问题的形式 30

2.2 基本可行解 33

2.3 线性规划的几何 39

2.3.1 线性空间和仿射空间 39

2.3.2 有界凸多面体 40

2.3.3 有界多面体与LP 43

2.4 基本可行解的替换 49

2.5 单纯形表 53

2.6 进入基列的选择 55

2.7 旋转元的选择和Bland反循环算法 61

2.8 单纯形算法的初始基本可行解 68

2.9 旋转变换的几何说明 73

习题 79

注释与参考资料 82

第三章 对偶性 86

3.1 一般形式的线性规划的对偶 86

3.2 互补松弛性 91

3.3 Farkas引理 93

3.4 最短路问题及其对偶 95

3.5 单纯形表中对偶解的信息 100

3.6 对偶单纯形算法 102

3.7 对偶单纯形算法的解释 104

习题 106

注释与参考资料 110

第四章 关于单纯形算法的计算讨论 112

4.1 修正的单纯形算法 112

4.2 修正的单纯形算法在计算上的意义 114

4.3 最大流问题及用修正的单纯形方法求其解 116

4.4 Dantzig-Wolfe的分解算法 122

习题 129

注释与参考资料 131

5.1 引言 132

第五章 原始-对偶算法 132

5.2 原始-对偶算法 133

5.3 原始-对偶算法的说明 137

5.4 最短路问题的原始-对偶算法 138

5.5 关于方法思路的说明 143

5.6 最大流问题的原始-对偶算法 144

习题 146

注释与参考资料 147

第六章 最大流和最短路的原始-对偶算法：Ford-Fulkerson算法和Dijkstra算法 148

6.1 最大流最小截定理 148

6.2 Ford和Fulkerson标号算法 152

6.3 标号算法的有限性问题 153

6.4 Dijkstra算法 161

6.5 Floyd-Warshall算法 163

习题 167

注释与参考资料 170

第七章 最小费用流的原始-对偶算法 172

7.1 最小费用流问题 172

7.2 组合化容量-圈算法 173

7.3 组合化费用-迭加算法 177

7.4 Hitchcock问题的原始-对偶算法-αβ算法 179

7.5 最小费用流问题变换为Hitchcock问题 185

7.6 结束语 189

习题 190

注释与参考资料 192

第八章 算法与复杂性 198

8.1 可计算性 198

8.2 时间界 199

8.3 例子的规模 202

8.4 算法分析 206

8.5 多项式时间算法 207

8.6 单纯形算法不是多项式时间的算法 210

8.7 椭球算法 216

8.7.1 LP，LI和LSI 216

8.7.2 仿射变换与椭球 221

8.7.3 算法 223

8.7.4 算法的精度 230

习题 235

注释与参考资料 241

第九章 最大流问题的有效算法 248

9.1 图的搜索 248

9.2 标号算法的病症是什么 254

9.3 网络标号与有向图的搜索 258

9.4 一个0(？3)的最大流算法 263

9.5 具有单位容量的情况 269

习题 272

注释与参考资料 275

第十章 匹配算法 279

10.1 匹配问题 279

10.2 二部图的匹配算法 283

10.3 二部图匹配与网络流 287

10.4 非二部图的匹配：花 289

10.5 非二部图匹配：一个算法 298

习题 309

注释与参考资料 313

第十一章 赋权匹配 316

11.1 引言 316

11.2 指派问题的匈牙利方法 317

11.3 非二部图赋权匹配问题 326

11.4 小结 341

习题 342

注释与参考资料 346

第十二章 支撑树与拟阵 348

12.1 最小支撑树问题 348

12.2 最小支撑树问题的O(？)算法 352

12.3 Greedy算法 356

12.4 拟阵 358

12.5 两个拟阵的交 369

12.6.1 赋权拟阵交 381

12.6 拟阵交问题的某些推广 381

12.6.2 拟阵对 382

12.6.3 三个拟阵交 383

习题 385

注释与参考资料 391

第十三章 整数线性规划 395

13.1 引言 395

13.2 全单位模性质 406

13.3 ILP解的上界 409

习题 416

注释与参考资料 417

14.1 Gomory割 420

第十四章 整数线性规划的割平面算法 420

14.2 字典序 429

14.3 分数对偶算法的有限性 434

14.4 其它的割平面算法 436

习题 437

注释与参考资料 439

第十五章 NP-完备问题 441

15.1 引言 441

15.2 一个最优化问题的三种提法 442

15.3 P类与NP类 447

15.4 多项式时间的归结 452

15.5 Cook定理 454

15.6 几个NP-完备问题：团与货郎问题 461

15.7 另一些NP-完备问题：匹配、覆盖和划分 476

习题 483

注释与参考资料 488

第十六章 再论NP-完备性 493

16.1 co-NP类 493

16.2 拟多项式算法和“强”NP-完备性 497

16.3 NP-完备问题的特例和一般化 502

16.3.1 使用限制方法证明NP-完备性 503

16.3.2 NP-完备问题的容易特例 504

16.3.3 NP-完备问题的困难特例 506

16.4.2 NP困难问题 509

16.4 一些有关的概念 509

16.4.1 多项式时间约化 509

16.4.3 非确定的图灵机 511

16.4.4 多项式空间完备问题 513

16.5 结束语 514

习题 515

注释与参考资料 519

第十七章 近似算法 523

17.1 点覆盖的启发式方法：一个例子 523

17.2 货郎问题的近似算法 527

17.3 近似方法 539

17.4 一些否定的结果 549

习题 554

注释与参考资料 555

第十八章 分枝定界和动态规划 559

18.1 整数线性规划的分枝定界 559

18.2 一般意义下的分枝定界 564

18.3 优势关系 570

18.4 分枝定界策略 571

18.5 应用于流水作业车间时间表问题 573

18.6 动态规划 578

习题 581

注释与参考资料 583

19.1 引言 586

第十九章 局部寻优法 586

19.2 问题1：货郎问题 587

19.3 问题2：最小费用残存网络 589

19.4 问题3：海底天然气管道系统拓朴结构 595

19.5 问题4：均匀图划分 599

19.6 局部寻优法的一些普遍性问题 604

19.7 局部寻优法的几何 608

19.8 一个大的极小精确领域的例子 613

19.9 货郎问题的精确局部寻优法的复杂性 616

习题 621

注释与参考资料 624