第一章 网络流模型 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