《网络流规划》求取 ⇩

第一章网络流模型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 所有的弧费用均为正，所有的弧增益均小于或等于1228

10.3 弧费用为负，弧增益大于1230

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