第1章 引言

1.1 图和流

1.1.1 路和环

1.1.2 流和散度

1.1.3 路流和共轭分解

1.2 网络流模型—例子

1.2.1 最小费用流问题

1.2.2 凸费用网络流问题

1.2.3 多商品流问题

1.2.4 离散网络优化问题

1.3 网络流算法—综述

1.3.1 原费用改进

1.3.2 对偶费用改进

1.3.3 拍卖

1.3.4 好算法，坏算法及多项式算法

1.4 注释，文献和习题

第2章 最短路问题

2.1 问题表述与应用

2.2 通用最短路算法

2.3 标记设置（Dijkstra）法

2.3.1 标记设置法的性能

2.3.2 二叉堆法

2.3.3 Dial算法

2.4 标记修正法

2.4.1 Bellman-Ford算法

2.4.2 D'Esopo-Pape算法

2.4.3 SLF算法和LLL算法

2.4.4 阈值算法

2.4.5 标记设置法和标记修正法的比较

2.5 单起点单终点算法

2.5.1 标记设置

2.5.2 标记修正

2.6 拍卖算法

2.7 多起点多终点算法

2.8 注释，文献和习题

第3章 最大流问题

3.1 最大流最小割问题

3.1.1 图的割集

3.1.2 最大流最小割定理

3.1.3 最大和最小饱和割集

3.1.4 不可行网络问题的分解

3.2 Ford-Fulkerson算法

3.3 基于价格的增广路算法

3.3.1 基于价格的路构造算法

3.3.2 基于价格的最大流算法

3.4 注释，文献和习题

第4章 最小费用流问题

4.1 变换和等价

4.1.1 置流量下限为零

4.1.2 消除流量上限

4.1.3 简化为循环形式

4.1.4 简化为指派问题

4.2 对偶

4.2.1 互补松弛条件和对偶问题的解释

4.2.2 非负约束的对偶和互补松弛条件

4.3 注释，文献和习题

第5章 单纯形法

5.1 单纯形法的主要思想

5.1.1 利用价格确定入边

5.1.2 确定出边

5.1.3 处理退化情况

5.2 基本单纯形法

5.2.1 单纯形法的终止性质

5.2.2 单纯形法的初始化

5.3 推广到具有上下界约束的问题

5.4 实现问题

5.5 注释，文献和习题

第6章 对偶上升方法

6.1 对偶上升

6.2 原对偶（序贯最短路）方法

6.3 松弛方法

6.4 求解已解决问题的变形

6.5 实现问题

6.6 注释，文献和习题

第7章 拍卖算法

7.1 指派问题的拍卖算法

7.1.1 主拍卖算法

7.1.2 近似坐标下降解释

7.1.3 拍卖算法的变形

7.1.4 复杂性—ε-伸缩

7.1.5 处理不可行性

7.2 拍卖算法的推广

7.2.1 逆向拍卖

7.2.2 非对称指派问题的拍卖算法

7.2.3 同类人员拍卖算法

7.3 最大流的预流推进法

7.3.1 分析与复杂性

7.3.2 实现问题

7.3.3 与拍卖算法的关系

7.4 ε-松弛方法

7.4.1 计算复杂性—ε-伸缩

7.4.2 实现问题

7.5 拍卖／序贯最短路算法

7.6 注释，文献和习题

第8章 非线性网络优化

8.1 凸可分问题

8.2 有附加约束的问题

8.3 多商品流问题

8.4 整数约束

8.5 有增益的网络

8.6 最优性条件

8.7 对偶性

8.8 算法和近似

8.8.1 可行方向法

8.8.2 分片线性近似

8.8.3 内点法

8.8.4 罚函数和增广Lagrange方法

8.8.5 近邻最小化

8.8.6 光滑化

8.8.7 变换

8.9 注释，文献和习题

第9章 凸可分网络问题

9.1 单变量凸函数

9.2 最优性条件

9.3 对偶性

9.4 对偶函数可微性

9.5 可微对偶问题算法

9.6 拍卖算法

9.6.1 ε-松弛法

9.6.2 拍卖／序贯最短路算法

9.7 单变规划

9.8 注释，文献和习题

第10章 整数约束网络问题

10.1 整数约束问题的描述

10.2 分支定界

10.3 Lagrange松弛

10.3.1 对偶函数的次梯度

10.3.2 次梯度法

10.3.3 割平面法

10.3.4 分解和多商品流

10.4 局部搜索方法

10.4.1 遗传算法

10.4.2 禁忌搜索

10.4.3 模拟退火

10.5 部署算法

10.6 注释，文献和习题

附录A 有关数学知识回顾

A.1 集合

A.2 Euclid空间

A.3 矩阵

A.4 分析

A.5 凸集和凸函数

A.6 次梯度

参考文献

索引