第5章 网络 最优化问题
第5章
网络最优化问题
第5章 网络 最优化问题
本章内容要点
网络最优化问题的基本概念 网络最优化问题的四种主要类 型：最小费用流、最大流、最 短路、最小支撑树 各种网络最优化问题的建模与 应用
本章节内容
5.1 5.2 5.3 5.4 5.5 5.6
第5章 网络 最优化问题
网络最优化问题基本概念 最小费用流问题 最大流问题 最短路问题 最小支撑树问题 货郎担问题和中国邮路问题
本章主要内容框架图
第5章 网络 最优化问题
点 连线（边或弧） 基本概念 权（赋权图） 网络图 最小费用流问题 最大流问题 网络最优化问题 主要类型 最短路问题 最小支撑树问题 货郎担问题和中国邮路问题 节点（供应点、转运点、需求点） 净流量 建模和求解 数学模型 电子表格模型
5.2 最小费用流问题

第5章 网络 最优化问题
例5.1最小费用流问题的数学模型为： （ 1 ）决策变量：设 fij 为通过弧 ( 节点 i-> 节点 j) 的流量。 （2）目标函数 本问题的目标是总运输成本最小。
Min z = 700 f F1W 1 300 f F1DC 200 f DC W 1 400 f F 2DC 900 f F 2W 2 400 f DC W 2
5.2 最小费用流问题
第5章 网络 最优化问题
最小费用流问题有五种重要的特殊类型(续)： （ 4 ）最大流问题：有供应点、需求点、转运 点、弧的容量限制，但没有供应量和需求量的 限制，目标是通过网络到目的地的总流量最大 。 （ 5 ）最短路问题：有供应点 ( 供应量为 1) 、 需求点(需求量为1) 、转运点、没有弧的容量 限制，目标是通过网络到目的地的总距离最短 。
5.2 最小费用流问题


第5章 网络 最优化问题
最小费用流问题的数学模型为： （1）决策变量：设fij为通过弧（节点i->节点j） 的流量。 （2）目标是通过网络供应的总成本最小。 （3）约束条件
① ② ③ ④ ⑤ 所有供应点：净流量（总流出减总流入）为正； 所有转运点：净流量为零； 所有需求点：净流量为负； 所有弧的流量fij受到弧的容量限制； 所有弧的流量fij非负。
5.1 网络最优化问题基本概念

第5章 网络 最优化问题


许多研究的对象往往可以用一个图表示，研究 的目的归结为图的极值问题。 运筹学中研究的图具有下列特征： (1) 用点表示研究对象，用连线（不带箭头 的边或带箭头的弧）表示对象之间某种关系； (2) 强调点与点之间的关联关系，不讲究图 的比例大小与形状； (3) 每条边上都赋有一个权，其图称为赋权 图。实际中权可以代表两点之间的距离、费用 、利润、时间、容量等不同的含义； (4) 建立一个网络模型，求最大值或最小值 。
5.1 网络最优化问题基本概念
v1 8 v3 5 8 2 v2 3 v4 6 v6 1 7 v5
第5章 网络 最优化问题
5
4
对于该网络图，可以提出许多极值问题
5.1 网络最优化问题基本概念
第5章 网络 最优化问题
（1）将某个点vi的物资或信息送到另 一个点 vj ，使得运送成本最小。这属 于最小费用流问题。 （2）将某个点vi的物资或信息送到另 一个点 vj ，使得流量最大。这属于最 大流问题。 （ 3 ）从某个点 vi 出发到达另一个点 vj ，怎样安排路线使得总距离最短或总 费用最小。这属于最短路问题。
5.2 最小费用流问题


第5章 网络 最优化问题
（ 3 ）约束条件 (
节点净流量、弧的 容量限制、非负）Min z = 700 f F 1W 1 300 f F 1 DC 200 f DC W 1
400 f F 2 DC 900 f F 2W 2 400 f DC W 2 ① 供应点 F1: 供 应 点 F2: f F 1W 1 f F 1DC = 80
5.2 最小费用流问题

第5章 网络 最优化问题
例5.1 某公司有两个工厂生产产品，这些产品需要 运送到两个仓库中。其配送网络图如图所示。目标 是确定一个运输方案（即每条路线运送多少单位的 产品），使通过配送网络的运输成本最小。
（无限制，700） 80 F1 W1 60
（50，300） DC （50，400） F2 （无限制，900）
5.1 网络最优化问题基本概念

第5章 网络 最优化问题


网络在各种实际背景问题中以各种各样的形式 存在。交通、电子和通讯网络遍及我们日常生 活的各个方面，网络规划也广泛用于解决不同 领域中的各种问题，如生产、分配、项目计划 、厂址选择、资源管理和财务策划等等。 网络规划为描述系统各组成部分之间的关系提 供了非常有效的直观和概念上的帮助，广泛应 用于科学、社会和经济活动的各个领域中。 近些年来，运筹学（管理科学）中一个振奋人 心的发展是它的网络最优化问题的方法论和应 用方面都取得了不同寻常的飞速发展。
5.1 网络最优化问题基本概念
第5章 网络 最优化问题
（ 4 ）点vi表示自来水厂及用户， vi与 vj之间的 边表示两点间可以铺设管道，权为 vi 与 vj 间铺 设管道的距离或费用，极值问题是如何铺设 管道，将自来水送到其他 5个用户并且使总的 费用最小。这属于最小支撑树问题。 (5) 售货员从某个点 vi 出发走过其他所有点 后回到原点vi，如何安排路线使总路程最短。 这属于货郎担问题或旅行售货员问题。 （ 6 ）邮递员从邮局 vi 出发要经过每一条边将 邮件送到用户手中，最后回到邮局vi，如何安 排路线使总路程最短。这属于中国邮递员问
5.2 最小费用流问题

第5章 网络 最优化问题
大规模的最小费用流问题的求解一 般 采 用 “ 网 络 单 纯 法 （ Network Simplex Method ）”。现在，许多公 司都使用网络单纯法来解决他们的最 小费用流问题。有些问题是非常庞大 的，有着数万个节点和弧。有时，弧 的数量甚至可能会多得多，达到几百 万条。但Excel的规划求解中没有网络 单纯法，但其他的线性规划的商业软 件包通常都有这种方法。
5.1 网络最优化问题基本概念
第5章 网络 最优化问题
网络最优化问题类型主要包括 ：
（1）最小费用流问题； （2）最大流问题； （3）最短路问题； （4）最小支撑树问题； （5）货郎担问题和中国邮路问题，等 等
5.2 最小费用流问题
第5章 网络 最优化问题
最小费用流问题的模型在网络最优化中扮 演着重要的角色，因为它的适用性很广， 并且求解方法容易。通常最小费用流问题 用于最优化货物从供应点到需求点的网络 。目标是在通过网络配送货物时，以最小 的成本满足需求，一种典型的应用就是使 得配送网络的运营最优。 最小费用流问题的特殊类型包括运输问题 和指派问题，以及在下面将要提到的两种 重要类型：最大流问题和最短路问题。
5.2 最小费用流问题

第5章 网络 最优化问题

2、最小费用流问题的假设 （1）至少一个供应点； （2）至少一个需求点； （3）剩下都是转运点； （4）通过弧的流只允许沿着箭头方向流动，通过弧的最 大流量取决于该弧的容量； （5）网络中有足够的弧提供足够容量，使得所有在供应 点中产生的流都能够到达需求点；（有解） （6）在流的单位成本已知前提下，通过每一条弧的流的 成本和流量成正比；（目标是线性的） （7）最小费用流问题的目标在满足给定需求条件下，使 得通过网络供应的总成本最小（或总利润最大）。
5.2 最小费用流问题

第5章 网络 最优化问题

3、最小费用流问题的解的特征 （ 1 ）具有可行解的特征：在以上的假设下 ，当且仅当供应点所提供的流量总和等于需 求点所需要的流量总和时（即平衡条件）， 最小费用流问题有可行解； （ 2 ）具有整数解的特征：只要其所有的供 应、需求和弧的容量都是整数值，那么任何 最小费用流问题的可行解就一定有所有流量 都是整数的最优解（与运输问题和指派问题 的解一样）。因此，没有必要加上所有决策 变量都是整数的约束条件。
（50，200）
（50，400） W2
70
90
5.2 最小费用流问题
第5章 网络 最优化问题
最小费用流问题的三个基本概念： 1 、最小费用流问题的构成（网络表 示） （ 1 ）节点：包括供应点、需求点和 转运点； （2 ）弧：可行的运输线路（节点 i-> 节点 j ），经常有最大流量（容量） 的限制。
f F 2 DC + f F 2W 2 = 70 f DC W 1 f DC W 2 ( f F 1 DC f F 2 DC ) 0 ② 转 运 点 DC: s.t. f F 1W 1 f DC W 1 = 60 f DC W 2 f F 2 W 2 90 ③ 需求点 W1: f F 1 DC , f F 2 DC , f DC W 1 , f DC W 2 50 需 求 点 W2: f F 1W 1 , f F 1 DC , f DC W 1 , f F 2 DC , f F 2W 2 , f DC W 2 0
5.2 最小费用流问题

第5章 网络 最优化问题


最小费用流问题有五种重要的特殊类型： （ 1 ）运输问题：有出发地 ( 供应点 - 供应量 ) 和目 的地(需求点-需求量)，没有转运点和弧的容量限 制，目标是总运输成本最小（或总利润最大）。 （2）指派类型：出发地(供应点-供应量为1)是人 ，目的地 ( 需求点 - 需求量为 1) 是任务，没有转运 点和弧的容量限制，目标是总指派成本最小（或 总利润最大）。 （ 3 ）转运问题：有出发地 ( 供应点 - 供应量 ) 和目 的地(需求点-需求量)，有转运点，但没有弧的容 量限制 ( 或有容量限制 ) ，目标是总流量费用最小 （或总利润最大）。