网络流规划PDF电子书下载

第一章 网络流模型 1

1.1 引言 1

1.2 各种网络流规划问题之间的关系 2

1.3 单纯线性最小费用流问题的几种特殊情形 2

1.4 增益网络模型 5

1.5 预观要做的事情 5

1.6 历史的透视 6

习题 7

第二章 建立网络规划的应用模型 8

2.1 引言 8

2.2 结点松弛参数 8

2.3 单纯线性最小费用流问题——应用举例 9

2.4 运输问题——应用举例 16

2.5 分配问题——应用举例 19

2.6 最短路问题——应用举例 24

2.7 最大流问题——应用举例 27

2.8 增益网络——应用举例 30

2.9 历史的透视 35

习题 36

第三章 网络模型的形式 43

3.1 网络符号 43

3.2 两种有用的变换 47

3.3 网络的代数模型 48

3.4 单纯最小费用问题的线性规划模型 50

3.5 图论术语 54

3.6 扩张网络与边际网络 56

3.7 弧费用为非线性的网络 58

3.8 单纯最小费用流问题的算法 60

3.10 历史的透视 63

3.9 网络流规划的局限性 63

习题 64

第四章 网络的操作算法 67

4.1 计算的费用 67

4.2 网络的表示 68

4.3 算法的描述方法 71

4.4 网络的读取与存贮 73

4.5 树的表示法 77

4.6 使用前序横表的等效算法 89

4.7 流的操作算法 93

4.8 历史的透视 95

习题 96

5.1 引言 97

5.2 如何表示为最小费用流问题 97

第五章 最短路问题 97

5.3 全部可接纳弧费用均为正的情形 100

5.4 一些弧费用为负而没有负圈 103

5.5 带有负圈的情形 107

5.6 一种非基算法 108

5.7 对偶最短路算法 110

5.8 历史的透视 113

应用性习题 114

理论性习题 115

第六章 最大流问题 116

6.1 问题的陈述 116

6.2 对偶问题的物理解释 117

6.3 论成果 118

6.4 基算法与非基算法 120

6.5 流量增广算法 121

应用性习题 132

6.6 历史的透视 132

理论性习题 133

第七章 单纯最小费用流问题 134

7.1 获得原本可行解的最大流算法 134

7.2 获得原本可行解的虚拟弧算法 138

7.3 原本非基算法 141

7.4 原本基算法 151

7.5 对偶结点不可行算法 158

7.6 历史的透视 165

习题 165

第八章 瑕疵算法 167

8.1 网络模型 167

8.2 线性规划模型 170

8.3 无瑕状态与瑕疵状态 171

8.4 流量的改变 174

8.5 位势的改变 179

8.6 应用瑕疵算法的一个例题 182

8.7 历史的透视 187

习题 187

第九章 广义网络的操作算法 189

9.1 引言 189

9.2 增益网络模型 190

9.3 线性规划模型 191

9.4 线性规划的对偶模型 195

9.5 基本网络的表示 196

9.6 广义网络流 207

9.7 结点位势 218

9.8 历史的透视 223

习题 223

10.1 广义最短路问题 227

第十章 广义最小费用流问题 227

10.2 所有的弧费用均为正，所有的弧增益均小于或等于1 228

10.3 弧费用为负，弧增益大于1 230

10.4 对偶广义最短路算法 237

10.5 广义最小费用流算法 249

10.6 流量增广法 249

10.7 原本法 256

10.8 历史的透视 271

习题 272

第十一章 凸的最小费用流问题 276

11.1 凸费用函数 276

11.2 解的特征 278

11.3 物理网络流问题 279

11.4 取决于随机变量的费用函数 284

11.5 分段线性近似 286

11.6 隐性的分段近似 288

11.7 历史的透视 294

习题 294

第十二章 凹费用 297

12.1 应用 297

12.2 记号 300

12.3 穷举法 301

12.4 隐枚举 303

12.5 下界 304

12.6 隐枚举算法 306

12.7 例题 311

12.8 历史的透视 314

习题 314

参考文献 316

汉英名词索引 326