本书介绍网络优化的模型、理论和方法，作者为美国麻省理工学院Dimitri P. Bertsekas 教授。

网络优化是一类非常有趣的数学规划问题。首先，网络优化模型可用网络图表示，这种可视性为直观解释数学规划理论和方法提供了很好的途径；其次，对于线性网络优化问题，变量的整数性约束一般都能自动满足，从而可将离散问题当作连续问题求解，这是一个非常特别而有用的性质；另外，实践中遇到的经常是包含众多边和节点的大规模网络优化问题，用网络优化算法求解此类问题在速度和可靠性方面均具有明显优势。由于上述原因，无论从理论研究还是实际应用的角度来看，学习网络优化知识均大有裨益。

本书不仅详细介绍了经典的线性网络优化模型、理论和方法，还分别对非线性网络优化问题和具有一般性整数约束的网络优化问题进行了广泛而深入的讨论，所涉及的网络优化知识非常全面。书中不少材料源自作者本人在网络优化相关领域多年的研究成果和研究心得，内容新颖，富有启发性，与同类书籍相比具有鲜明的特色。通过阅读本书，能够对网络优化模型、理论和方法建立完整的认识。

本书每章都配备了大量习题，适合用作网络优化相关课程的教材。书中各章节内容既相互关联，又相对独立，便于教师根据课时安排进行适当的选择。

译者序

本书介绍网络优化的模型、理论和方法，作者为美国麻省理工学院Dimitri P. Bertsekas 教授。

网络优化是一类非常有趣的数学规划问题。首先，网络优化模型可用网络图表示，这种可视性为直观解释数学规划理论和方法提供了很好的途径；其次，对

于线性网络优化问题，变量的整数性约束一般都能自动满足，从而可将离散问题当作连续问题求解，这是一个非常特别而有用的性质；另外，实践中遇到的

经常是包含众多边和节点的大规模网络优化问题，用网络优化算法求解此类问题在速度和可靠性方面均具有明显优势。由于上述原因，无论从理论研究还是

实际应用的角度来看，学习网络优化知识均大有裨益。

本书不仅详细介绍了经典的线性网络优化模型、理论和方法，还分别对非线性网络优化问题和具有一般性整数约束的网络优化问题进行了广泛而深入的讨论，

所涉及的网络优化知识非常全面。书中不少材料源自作者本人在网络优化相关领域多年的研究成果和研究心得，内容新颖，富有启发性，与同类书籍相比具

有鲜明的特色。通过阅读本书，能够对网络优化模型、理论和方法建立完整的认识。

本书每章都配备了大量习题，适合用作网络优化相关课程的教材。书中各章节内容既相互关联，又相对独立，便于教师根据课时安排进行适当的选择。

本书第1、5、6、8章及附录部分由王书宁翻译，第2、3、4、10章由牟晓牧翻译，第7、9章由李星野翻译，最后由王书宁定稿。

感谢Dimitri P. Bertsekas教授提供本书英文版本的电子文件，为翻译本书提供了极大的便利。

优化问题可分为两种主要类型: 连续型和离散型。网络优化就居于这两类问题的分界线上。

线性规划和组合优化问题之间存在联系是因为可以将多面体约束集表示为其极点的凸包。

当涉及到网络时, 由于多面体的极点是整数向量, 并且它们所表示的是看上去和线性规划不相干的组合问题的解,

上述联系变得紧密得多。 正由于这种结构, 也由于\ziju{0.03}它们的直观特性, 网络模型为解释连续优化和离散优化中的很多基本思想提供了理想的工具。\ziju{0}

网络模型除了具有引人入胜的方法论方面的特点之外, 在实践中也被广泛应用, 其应用范围还在持续扩大。总体上看确实如此, 诸如最短路、指派、最大流、运输、转运、生成树、匹配、旅行商、广义指派、

车辆路径选择以及多商品流这些网络问题已构成大多数常见类型的实际优化问题。在网络问题的求解方法方面已经发生了稳定的进步, 事实上, 由于算法和技术的进步,

上述求解方法方面的进步在过去十五年里呈现加速发展的趋势。

本书目的是对线性、 非线性和离散网络优化问题提供相当全面的最新的介绍。书中突出连续结构和离散结构之间的联系, 从广泛的视野讨论相关的分析和算法问题,

并对重要的网络模型和应用提供指导。

关于连续网络优化, 我们主要集中于两个想法, 它们也是一般性数学规划的基本想法:

{\kaishu 对偶性}和{\kaishu 迭代费用改进\/}。 我们对用迭代算法解决最常见的线性费用问题、 最小费用流问题或转运问题

以及后者的凸费用版本, 进行广泛的讨论。 关于对偶性的讨论也相当全面: 从线性网络规划的对偶性开始,

直至 Rockafellar 关于单变规划对偶性的发展。

关于离散网络优化, 我们通过诸如旅行商、广义指派、 生成树、匹配和路径选择这些主要范例进行问题描述。

这样做是必要的, 因为和连续优化问题的结构相比, 对离散优化问题的结构很难进行简单高效的描述,

熟悉一些重要类型的问题对于建模、 分析和利用算法求解非常重要。 我们也要介绍主要的求解算法,

包括分支定界、Lagrange 松弛、Dantzig-Wolfe 分解、 启发式方法以及局部搜索方法。

这是一本涵盖广泛主题的导论性书籍。 因此, 不可避免地对某些主题的讨论不会像对别的主题那样详细。

有关内容的选择, 部分由于个人兴趣和专业知识, 部分由于作者对简单模型的偏好, 这种模型有可能以最有效的方式帮助读者认识相应问题的本质。

同时, 我们在分析和阐述时试图通过以下两种方式增强读者的数学建模能力: 界定各种算法能够有效求解的问题的范围,

为一般性公式描述的问题提供很多实例。

本书各章内容如下:

第1章:}本章为全书引言, 给出图的基本概念和术语, 讨论网络模型的若干例子, 并对线性网络优化算法有关情况进行初步介绍。

第2章:本章对最短路问题进行广泛讨论。 内容涉及主要方法以及它们的理论和实际性能。

第3章:本章集中讨论最大流问题以及求解该问题的增广路算法。 除了经典的 Ford-Fulkerson 方法的变形,

还介绍近期基于拍卖的想法发展的一种算法。

第4章:本章介绍最小费用流问题(线性费用, 单种商品, 无附加约束)及其等价变形。  随后对该问题给出基本的对偶理论以及相应的解释。

第5章:本章集中讨论求解最小费用流问题的单纯形法。 以构造方式导出有关这种方法的整数解的基本结果。 此外, 还显著地强化了第4章的对偶理论。

第6章:本章导出对偶上升方法, 包括原对偶、序贯最短路和松弛方法。

第7章:本章从介绍指派问题的拍卖算法开始, 进而说明如何将这种算法推广到更加复杂的问题。

由此得到最大流问题的预流推进法和最小成本流问题的$\e$-松弛法。 另外还给出了拍卖算法的若干种变形。

第8章:本章内容很重要, 它从线性网络优化转向非线性网络优化。 主要注意力集中于连续(凸)问题

以及和这些问题相关的结构和处理方法的广泛多样性。 具体地说, 本章将对非线性规划的多类算法进行综述,

这些算法可以用于解决不同的凸网络优化问题。 另外也会对离散(整数)问题进行一些讨论, 并着重强调它们和连续问题的联系。

第9章:本章内容复杂, 它的主要对象是高层次和/或研究导向的读者。 它处理可分凸问题,

讨论这些问题和经典的网络平衡问题之间的联系, 并导出它们的丰富的理论结构。

这种结构的突出特色是一个特别精致的对偶理论以及下降方向和流量守恒约束定义的子空间的基本向量有限集之间的组合关联。

除了讨论凸可分网络问题之外, 本章还对单变规划进行初步介绍, 这是具有线性规划的强对偶性和组合性质的最大类的非线性规划问题。

本章也要导出凸可分问题的拍卖算法, 并对它们的运行时间进行分析。

第10章:本章讨论整数约束问题的基本处理方法。 其中要讨论精确处理方法, 比如分支定界方法、

基于Lagrange松弛的有关方法、次梯度优化方法和割平面方法。 另外也要描述基于局部搜索的近似方法,

比如遗传算法、禁忌搜索和模拟退火方法。 最后还要讨论部署算法, 这是相对较新且可广泛应用的一类近似方法,

它可以代替局部搜索或和后者一起协同工作。

本书可以用作网络优化课程教材或者用作一年级研究生优化导论课程的部分教材。 除了第9章的一些内容,

阅读本书仅需要相当基本的预备知识。 主要要求是有一定程度的数学素养, 例如, 学习过微积分之外的严格的数学课程。

本书大部分内容可以用于线性和非线性优化课程。 其中第1至第5章和第8章可以构成一个短期课程的内容。

作为一种选择, 也可以选用第1至第5章, 第8章的一小部分, 以及第10章构成一门集中关注线性和离散网络优化的课程。

实际上, 如果满足于较弱的对偶结果(在第4章给出), 并且采用类似习题1.34给出的分析路径去建立最优解的整数性质,

那么上面的各章列表可以不包含第5章的内容。 下面的图说明了各章之间的依赖关系。

本书包含大量例题和习题, 适合课堂教学使用。 有些理论性习题可用作主要内容的重要补充材料。

对部分习题的解答(以及勘误表和附加材料)将放在本书网页

http://world.std.com/\~\ athenasc/netsbook.html

并会定期更新。 另外, 作者的网页

http://web.mit.edu/dimitrib/www/home.html

也包含一些 FORTRAN 编码, 它们实现了本书讨论的很多算法。

关于连续和离散网络优化有非常广泛的文献, 不可能将它们全部列出, 也不可能对导致目前状况的所有研究历史进行全面的回顾。

因此我不打算对该领域所有的原创性贡献列出完整的清单。 作者所引用的或者是已被作者广泛使用的文献,

或者是对本书内容提供了重要扩展的文献, 或者是综述一些重要主题的文献, 或者是特别适合进一步阅读的文献。

我们也选择性地引用了少数具有历史重要性的文献, 但这方面的相应列表远远不够完整。 一般而言, 为了有助于该领域的研究者,

对于所涉及的主题, 作者更偏好于引用相对比较成熟且对较近期的发展给出了大量参考文献的综述或教材。

本书相当一部分内容是基于作者在过去20年中对网络优化的研究。 在这些研究中作者很幸运地遇到一些优秀的合作者,

这里要提到已经和作者进行了广泛合作的一些人。  Eli Gafni 于1979年帮助作者进行了采用拍卖算法和松弛方法解决指派问题的计算试验。

作者和 Eli 在那段时期的交流中产生了$\e$-伸缩的想法。 另外, Eli 和作者在数据网络的各种路径选择方法中进行了广泛的合作,

包括凸的多商品流问题的投影方法。 Paul Tseng 从1982年起就和作者一起进行网络优化的工作。 我们一起开发了 RELAX 编码,

对基本的松弛方法进行了若干扩展, 并在其他多种课题中进行了密切的合作,

包括最近的解决凸网络问题和有增益的网络问题的拍卖算法。 自1987年以来, David Castanon 和作者一起研究了指派问题、 运输问题、

最小费用流问题的多种算法, 包括串行和并行算法。 John Tsitsiklis 多年以来一直是作者在优化和大规模计算问题方面的共同作者和紧密合作者,

其中包括网络问题。 除了 Eli, Paul, David 和 John, 作者和一些同事也有相当多的合作研究经历, 相应结果在本书也有反映。

在这方面, 作者要提到 Jon Eckstein,  Bob Gallager, Francesca Guerriero, Roberto Musmanno,  Stefano Pallottino 和 Maria-Grazia Scutell\`a。

若干同事校对了本书部分内容, 并贡献了极有价值的建议。

尤其是 David Castanon, Stefano Pallottino, Steve Patek, Serap Savari, Paul Tseng 和 John Tsitsiklis 在这方面给出了很多帮助。

非常感谢来自 DDM 和 CCI 部门的 NSF 研究经费支持。 作者的家庭一直是稳定和爱的支持的源泉, 没有这些本书不可能完成。

第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 复杂性—$\e$-伸缩 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 $\e$-松弛方法 256

7.4.1 计算复杂性—$\e$-伸缩 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 $\e$-松弛法 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

索引