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

目录 1

第一章 概论 1

§1-1 引言 1

§1-2 图的基本知识 2

§1-3 LP问题的三种形式 4

§1-4 复杂性概念 8

第二章 线性规划问题 10

§2-1 线性规划的解 10

§2-2 多维空间的基本结构 13

§2-3 线性规划与凸多面体 16

第三章 单纯形法 20

§3-1 解的判别 20

§3-2 单纯形迭代 21

§3-3 单纯形表 24

§3-4 换元选择规则 26

§3-5 迭代循环和克服循环的规则 27

§3-6 初始基可行解 32

第四章 对偶理论和灵敏度分析 36

§4-1 原问题和对偶问题 36

§4-2 灵敏度分析 40

第五章 单纯形算法的计算复杂性 43

§5-1 概述 43

§5-2 摄动 48

§5-3 最大改进规则 51

§5-4 T-变换及其性质 54

§5-5 最大迭代次数 59

§5-6 降维算法 61

§5-7 单纯形算法的复杂性 63

第六章 降维算法和解基变量法 67

§6 1 ？形LP问题的降维算法 67

§6-2 解基变量法 73

§6-3 最优基变量 77

第七章 网络问题与LP 82

§7-1 网络和网络矩阵 82

§7-2 典型网络优化问题的LP模型 84

§7-3 算法比较 94

第八章 网络优化难题 96

§8-1 几个难算问题 96

§8-2 启发式方法 106

§8-3 分枝定界方法 108

§8-4 局部寻优方法 111

第九章 整数线性规划与NP问题 115

§9-1 整数约束与非线性 115

§9-2 ZOLP的隐枚举法 117

§9-3 ILP的割平面算法 119

§9-4 整数背包问题的算法 124

§9-5 ？多项式算法和强NP完备问题 126

§9-6 ILP和NP＝P？ 128

第十章 最大改进割平面法 132

§10-1 使用最大改进规则的对偶单纯形算法 132

§10-2 最大改进割平面算法 139

§10-3 用最大改进割平面法解ILP 145

§10-4 NP＝P？ 148

参考文献 156