第1章 引言 1
1.1 图和流 2
1.1.1 路和环 3
1.1.2 流和散度 4
1.1.3 路流和共轭分解 6
1.2 网络流模型—例子 7
1.2.1 最小费用流问题 7
1.2.2 凸费用网络流问题 14
1.2.3 多商品流问题 15
1.2.4 离散网络优化问题 16
1.3 网络流算法—综述 18
1.3.1 原费用改进 18
1.3.2 对偶费用改进 21
1.3.3 拍卖 23
1.3.4 好算法，坏算法及多项式算法 30
1.4 注释，文献和习题 32
第2章 最短路问题 45
2.1 问题表述与应用 46
2.2 通用最短路算法 50
2.3 标记设置（Dijkstra）法 56
2.3.1 标记设置法的性能 59
2.3.2 二叉堆法 59
2.3.3 Dial算法 60
2.4 标记修正法 63
2.4.1 Bellman-Ford算法 63
2.4.2 D'Esopo-Pape算法 65
2.4.3 SLF算法和LLL算法 65
2.4.4 阈值算法 67
2.4.5 标记设置法和标记修正法的比较 68
2.5 单起点单终点算法 69
2.5.1 标记设置 69
2.5.2 标记修正 70
2.6 拍卖算法 73
2.7 多起点多终点算法 81
2.8 注释，文献和习题 83
第3章 最大流问题 99
3.1 最大流最小割问题 100
3.1.1 图的割集 102
3.1.2 最大流最小割定理 104
3.1.3 最大和最小饱和割集 106
3.1.4 不可行网络问题的分解 106
3.2 Ford-Fulkerson算法 108
3.3 基于价格的增广路算法 114
3.3.1 基于价格的路构造算法 116
3.3.2 基于价格的最大流算法 119
3.4 注释，文献和习题 120
第4章 最小费用流问题 129
4.1 变换和等价 130
4.1.1 置流量下限为零 130
4.1.2 消除流量上限 130
4.1.3 简化为循环形式 131
4.1.4 简化为指派问题 132
4.2 对偶 132
4.2.1 互补松弛条件和对偶问题的解释 138
4.2.2 非负约束的对偶和互补松弛条件 139
4.3 注释，文献和习题 140
第5章 单纯形法 145
5.1 单纯形法的主要思想 146
5.1.1 利用价格确定入边 151
5.1.2 确定出边 153
5.1.3 处理退化情况 156
5.2 基本单纯形法 159
5.2.1 单纯形法的终止性质 159
5.2.2 单纯形法的初始化 160
5.3 推广到具有上下界约束的问题 166
5.4 实现问题 169
5.5 注释，文献和习题 173
第6章 对偶上升方法 181
6.1 对偶上升 182
6.2 原对偶（序贯最短路）方法 188
6.3 松弛方法 198
6.4 求解已解决问题的变形 206
6.5 实现问题 207
6.6 注释，文献和习题 209
第7章 拍卖算法 213
7.1 指派问题的拍卖算法 214
7.1.1 主拍卖算法 215
7.1.2 近似坐标下降解释 218
7.1.3 拍卖算法的变形 218
7.1.4 复杂性—ε-伸缩 220
7.1.5 处理不可行性 224
7.2 拍卖算法的推广 226
7.2.1 逆向拍卖 226
7.2.2 非对称指派问题的拍卖算法 230
7.2.3 同类人员拍卖算法 236
7.3 最大流的预流推进法 238
7.3.1 分析与复杂性 241
7.3.2 实现问题 247
7.3.3 与拍卖算法的关系 247
7.4 ε-松弛方法 256
7.4.1 计算复杂性—ε-伸缩 260
7.4.2 实现问题 267
7.5 拍卖／序贯最短路算法 268
7.6 注释，文献和习题 272
第8章 非线性网络优化 283
8.1 凸可分问题 285
8.2 有附加约束的问题 290
8.3 多商品流问题 292
8.4 整数约束 298
8.5 有增益的网络 302
8.6 最优性条件 306
8.7 对偶性 310
8.8 算法和近似 314
8.8.1 可行方向法 314
8.8.2 分片线性近似 319
8.8.3 内点法 321
8.8.4 罚函数和增广Lagrange方法 322
8.8.5 近邻最小化 323
8.8.6 光滑化 324
8.8.7 变换 326
8.9 注释，文献和习题 333
第9章 凸可分网络问题 341
9.1 单变量凸函数 342
9.2 最优性条件 345
9.3 对偶性 347
9.4 对偶函数可微性 357
9.5 可微对偶问题算法 360
9.6 拍卖算法 362
9.6.1 ε-松弛法 369
9.6.2 拍卖／序贯最短路算法 372
9.7 单变规划 374
9.8 注释，文献和习题 385
第10章 整数约束网络问题 389
10.1 整数约束问题的描述 390
10.2 分支定界 402
10.3 Lagrange松弛 410
10.3.1 对偶函数的次梯度 414
10.3.2 次梯度法 416
10.3.3 割平面法 419
10.3.4 分解和多商品流 422
10.4 局部搜索方法 426
10.4.1 遗传算法 428
10.4.2 禁忌搜索 429
10.4.3 模拟退火 429
10.5 部署算法 430
10.6 注释，文献和习题 436
附录A 有关数学知识回顾 453
A.1 集合 454
A.2 Euclid空间 455
A.3 矩阵 455
A.4 分析 456
A.5 凸集和凸函数 458
A.6 次梯度 459
参考文献 463
索引 493