1、第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院实用运筹学实用运筹学运用运用ExcelExcel建模和求解建模和求解第第5 5章章网络最优化问题网络最优化问题第1页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院本章内容要点本章内容要点 网络最优化问题的基本概念网络最优化问题的基本概念 网络最优化问题的四种主要类网络最优化问题的四种主要类型：型：最小费用流最小费用流、最大流最大流、最短最短路路、最小支撑树最小支撑树 各种网络最优化问题的建模与各种网络最优化问题的建模与应用应用第2页，共73页。第第5
2、章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院本章节内容本章节内容5.1 5.1 网络最优化问题基本概念网络最优化问题基本概念5.2 5.2 最小费用流问题最小费用流问题5.3 5.3 最大流问题最大流问题5.4 5.4 最短路问题最短路问题5.5 5.5 最小支撑树问题最小支撑树问题5.6 5.6 货郎担问题和中国邮路问题货郎担问题和中国邮路问题第3页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院本章主要内容框架图本章主要内容框架图点连 线（边 或 弧）基 本 概 念权（赋 权 图）网 络 图最 小
3、 费 用 流 问 题最 大 流 问 题网 络 最 优 化 问 题主 要 类 型最 短 路 问 题最 小 支 撑 树 问 题货 郎 担 问 题 和 中 国 邮 路 问 题节 点（供 应 点、转 运 点、需 求 点）净 流 量建 模 和 求 解数 学 模 型电 子 表 格 模 型第4页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.1 5.1 网络最优化问题基本概念网络最优化问题基本概念网络在各种实际背景问题中以各种各样的形式存在。网络在各种实际背景问题中以各种各样的形式存在。交通、电子和通讯网络遍及我们日常生活的各个方面交通、电子和通讯网
4、络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问题，网络规划也广泛用于解决不同领域中的各种问题，如生产、分配、项目计划、厂址选择、资源管理和财如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。务策划等等。网络规划为描述系统各组成部分之间的关系提供网络规划为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的帮助，广泛应用于了非常有效的直观和概念上的帮助，广泛应用于科学、社会和经济活动的各个领域中。科学、社会和经济活动的各个领域中。近些年来，运筹学（管理科学）中一个振奋人心近些年来，运筹学（管理科学）中一个振奋人心的发展是它的的发展是它的网络最优化问题的方法论
5、网络最优化问题的方法论和和应用方面应用方面都取得了不同寻常的飞速发展都取得了不同寻常的飞速发展。第5页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.1 5.1 网络最优化问题基本概念网络最优化问题基本概念许多研究的对象往往可以用一个许多研究的对象往往可以用一个图图表示，研究的表示，研究的目的归结为图的极值问题。目的归结为图的极值问题。运筹学中研究的图具有下列特征：运筹学中研究的图具有下列特征：(1)(1)用用点点表示研究对象，用表示研究对象，用连线连线（不带箭头的（不带箭头的边边或带或带箭头的箭头的弧弧）表示对象之间某种关系；）表示对
6、象之间某种关系；(2)(2)强调点与点之间的关联关系，不讲究图的比例大强调点与点之间的关联关系，不讲究图的比例大小与形状；小与形状；(3)(3)每条边上都赋有一个权，其图称为每条边上都赋有一个权，其图称为赋权图赋权图。实际中权可以代表两点之间的距离、费用、利润实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义；、时间、容量等不同的含义；(4)(4)建立一个建立一个网络模型网络模型，求最大值或最小值。，求最大值或最小值。第6页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.1 5.1 网络最优化问题基本概念网络最优化问题基
7、本概念v1v3v5v2v4v68736548521对于该网络图，可以提出许多极值问题对于该网络图，可以提出许多极值问题 第7页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.1 5.1 网络最优化问题基本概念网络最优化问题基本概念（1 1）将某个点）将某个点vi的物资或信息送到另一个点的物资或信息送到另一个点vj，使得运送成本最小。这属于，使得运送成本最小。这属于最小费用最小费用流流问题。问题。（2 2）将某个点）将某个点vi的物资或信息送到另一个点的物资或信息送到另一个点vj，使得流量最大。这属于，使得流量最大。这属于最大流最大流问题
8、问题。（3 3）从某个点）从某个点vi出发到达另一个点出发到达另一个点vj，怎，怎样安排路线使得总距离最短或总费用最样安排路线使得总距离最短或总费用最小。这属于小。这属于最短路最短路问题。问题。第8页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.1 5.1 网络最优化问题基本概念网络最优化问题基本概念（4 4）点）点vi表示自来水厂及用户，表示自来水厂及用户，vi与与vj之间的边之间的边表示两点间可以铺设管道，权为表示两点间可以铺设管道，权为vi与与vj间铺设间铺设管道的距离或费用，极值问题是如何铺设管管道的距离或费用，极值问题是如何
9、铺设管道，将自来水送到其他道，将自来水送到其他5 5个用户并且使总的费个用户并且使总的费用最小。这属于用最小。这属于最小支撑树最小支撑树问题。问题。(5)(5)售货员从某个点售货员从某个点vi出发走过其他出发走过其他所有点所有点后回后回到原点到原点vi，如何安排路线使总路程最短。这属，如何安排路线使总路程最短。这属于于货郎担问题货郎担问题或旅行售货员问题。或旅行售货员问题。（6 6）邮递员从邮局）邮递员从邮局vi出发要经过出发要经过每一条边每一条边将邮件将邮件送到用户手中，最后回到邮局送到用户手中，最后回到邮局vi，如何安排路，如何安排路线使总路程最短。这属于线使总路程最短。这属于中国邮递员问
10、题中国邮递员问题。第9页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.1 5.1 网络最优化问题基本概念网络最优化问题基本概念网络最优化问题类型网络最优化问题类型主要包括：主要包括：（1 1）最小费用流问题；）最小费用流问题；（2 2）最大流问题；）最大流问题；（3 3）最短路问题；）最短路问题；（4 4）最小支撑树问题；）最小支撑树问题；（5 5）货郎担问题和中国邮路问题，等等）货郎担问题和中国邮路问题，等等第10页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2
11、最小费用流问题最小费用流问题最小费用流问题的模型在网络最优化中扮最小费用流问题的模型在网络最优化中扮演着重要的角色，因为它的适用性很广，演着重要的角色，因为它的适用性很广，并且求解方法容易。通常并且求解方法容易。通常最小费用流问题最小费用流问题用于最优化货物从供应点到需求点的网络用于最优化货物从供应点到需求点的网络。目标是在通过网络配送货物时，以最小。目标是在通过网络配送货物时，以最小的成本满足需求，一种典型的应用就是使的成本满足需求，一种典型的应用就是使得配送网络的运营最优得配送网络的运营最优。最小费用流问题的最小费用流问题的特殊类型特殊类型包括包括运输问题运输问题和和指派问题指派问题，以及
12、在下面将要提到的两种，以及在下面将要提到的两种重要类型：重要类型：最大流问题最大流问题和和最短路问题最短路问题。第11页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2 最小费用流问题最小费用流问题例例5.1 5.1 某公司有两个工厂生产产品，这些产品需要运送到两某公司有两个工厂生产产品，这些产品需要运送到两个仓库中。其配送网络图如图个仓库中。其配送网络图如图5 52 2所示。目标是确定一所示。目标是确定一个运输方案（即每条路线运送多少单位的产品），使通个运输方案（即每条路线运送多少单位的产品），使通过配送网络的运输成本最小。
13、过配送网络的运输成本最小。（5050，400400）（5050，200200）（5050，400400）（5050，300300）F1F1F2F2DCDCW2W2W1W18080707060609090（无限制，（无限制，700700）（无限制，（无限制，900900）第12页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2 最小费用流问题最小费用流问题最小费用流问题的三个基本概念：最小费用流问题的三个基本概念：1 1、最小费用流问题的构成（、最小费用流问题的构成（网络表示网络表示）（1 1）节点节点：包括供应点、需求点和转运
14、点：包括供应点、需求点和转运点；（2 2）弧弧：可行的运输线路（节点：可行的运输线路（节点i-i-节点节点j j），经常有最大流量（容量）的限制。，经常有最大流量（容量）的限制。第13页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2 最小费用流问题最小费用流问题2 2、最小费用流问题的假设、最小费用流问题的假设（1 1）至少一个）至少一个供应点供应点；（2 2）至少一个）至少一个需求点需求点；（3 3）剩下都是）剩下都是转运点转运点；（4 4）通过）通过弧弧的流只允许沿着箭头方向流动，通过弧的最大流量取决的流只允许沿着箭头方
15、向流动，通过弧的最大流量取决于该于该弧的容量弧的容量；（5 5）网络中有足够的弧提供足够容量，使得所有在供应点中产生的流都）网络中有足够的弧提供足够容量，使得所有在供应点中产生的流都能够到达需求点；（能够到达需求点；（有解有解）（6 6）在流的）在流的单位成本单位成本已知前提下，通过每一条弧的流的成本和流量成已知前提下，通过每一条弧的流的成本和流量成正比；（正比；（目标是线性的目标是线性的）（7 7）最小费用流问题的目标在满足给定需求条件下，使得通过网）最小费用流问题的目标在满足给定需求条件下，使得通过网络供应的络供应的总成本最小总成本最小（或总利润最大）。（或总利润最大）。第14页，共73页
16、。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2 最小费用流问题最小费用流问题3 3、最小费用流问题的解的特征、最小费用流问题的解的特征（1 1）具有可行解具有可行解的特征：在以上的假设下，当且的特征：在以上的假设下，当且仅当仅当供应点所提供的流量总和供应点所提供的流量总和等于等于需求点所需需求点所需要的流量总和要的流量总和时（即平衡条件），最小费用流时（即平衡条件），最小费用流问题有可行解；问题有可行解；（2 2）具有整数解具有整数解的特征：只要其所有的的特征：只要其所有的供应供应、需求需求和和弧的容量弧的容量都是都是整数整数值，那么
17、任何最小费用流值，那么任何最小费用流问题的可行解就一定有所有流量都是问题的可行解就一定有所有流量都是整数的整数的最优解最优解（与运输问题和指派问题的解一样）。因（与运输问题和指派问题的解一样）。因此，没有必要加上所有决策变量都是整数的约束此，没有必要加上所有决策变量都是整数的约束条件。条件。第15页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2 最小费用流问题最小费用流问题最小费用流问题的最小费用流问题的数学模型数学模型为：为：（1 1）决策变量：设）决策变量：设fij为通过弧（节点为通过弧（节点i-i-节点节点j j）的流
18、量。）的流量。（2 2）目标是通过网络供应的总成本最小。）目标是通过网络供应的总成本最小。（3 3）约束条件）约束条件 所有所有供应点供应点：净流量（总流出减总流入）为：净流量（总流出减总流入）为正正；所有所有转运点转运点：净流量为：净流量为零零；所有所有需求点需求点：净流量为：净流量为负负；所有弧的流量所有弧的流量fij受到弧的受到弧的容量限制容量限制；所有弧的流量所有弧的流量fij非负非负。第16页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2 最小费用流问题最小费用流问题例例5.15.1最小费用流问题的最小费用流问题的
19、数学模型数学模型为：为：（1 1）决策变量：设）决策变量：设fij为通过弧为通过弧(节点节点i-节点节点j)的流量。的流量。（2 2）目标函数）目标函数 本问题的目标是总运输成本最小。本问题的目标是总运输成本最小。11112222Min z=700300200 400900400FWFDCDCWFDCFWDCWffffff第17页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2 最小费用流问题最小费用流问题（3 3）约束条件）约束条件(节点净节点净流量、弧的容量限制流量、弧的容量限制、非负）、非负）供应点供应点 F1:F1:供
20、应点供应点 F2:F2:转运点转运点 DC:DC:需求点需求点 W1:W1:需求点需求点 W2:W2:弧的容量限制：弧的容量限制：非负：非负：1111222211122212121112221Min z=700300200 400900400=80+=70 ()0s.t.=60 90,FWFDCDC WFDCFWDC WFWFDCFDCFWDC WDC WFDCFDCFWDC WDC WFWFDCfffffffffffffffffff21211112222,50,0FDCDC WDC WFWFDCDC WFDCFWDC Wfffffffff第18页，共73页。第第5章章 网络网络最优化问题最优
21、化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2 最小费用流问题最小费用流问题 例例5.15.1的的电子表格模型电子表格模型：列出了网络中的弧和各弧所对应的容量、单位：列出了网络中的弧和各弧所对应的容量、单位成本。决策变量为通过弧的流量。目标是计算流量的总成本。每个成本。决策变量为通过弧的流量。目标是计算流量的总成本。每个节点的净流量为约束条件。供应点的净流量为正，需求点的净流量节点的净流量为约束条件。供应点的净流量为正，需求点的净流量为负，而转运点的净流量为为负，而转运点的净流量为0 0。这里用了一个这里用了一个窍门窍门：用两个：用两个SUMIFSUMIF函数的差来计算
22、每个节点的净流量，函数的差来计算每个节点的净流量，这样快捷且不容易犯错。这样快捷且不容易犯错。第19页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2 最小费用流问题最小费用流问题 大规模的最小费用流问题的求解一般采用大规模的最小费用流问题的求解一般采用“网络单纯法网络单纯法（Network Simplex MethodNetwork Simplex Method）”。现在，许多公司都使用网络单纯法来。现在，许多公司都使用网络单纯法来解决他们的最小费用流问题。有些问题是解决他们的最小费用流问题。有些问题是非常庞大的，有着数万个
23、节点和弧。有时非常庞大的，有着数万个节点和弧。有时，弧的数量甚至可能会多得多，达到几百，弧的数量甚至可能会多得多，达到几百万条。但万条。但ExcelExcel的规划求解中没有网络单的规划求解中没有网络单纯法纯法，但其他的线性规划的商业软件包，但其他的线性规划的商业软件包通常都有这种方法。通常都有这种方法。第20页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2 最小费用流问题最小费用流问题最小费用流问题有五种重要的特殊类型：最小费用流问题有五种重要的特殊类型：（1 1）运输问题运输问题：有出发地：有出发地(供应点供应点-供应量
24、供应量)和目的地和目的地(需求需求点点-需求量需求量)，没有转运点和弧的容量限制没有转运点和弧的容量限制，目标是总，目标是总运输成本最小（或总利润最大）。运输成本最小（或总利润最大）。（2 2）指派类型指派类型：出发地：出发地(供应点供应点-供应量为供应量为1)1)是人，目的地是人，目的地(需求点需求点-需求量为需求量为1)1)是任务，是任务，没有转运点和弧的容量没有转运点和弧的容量限制限制，目标是总指派成本最小（或总利润最大）。，目标是总指派成本最小（或总利润最大）。（3 3）转运问题转运问题：有出发地：有出发地(供应点供应点-供应量供应量)和目的地和目的地(需求需求点点-需求量需求量)，有
25、转运点，但没有弧的容量限制，有转运点，但没有弧的容量限制(或有容量或有容量限制限制)，目标是总流量费用最小（或总利润最大）。，目标是总流量费用最小（或总利润最大）。第21页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.2 5.2 最小费用流问题最小费用流问题最小费用流问题有五种重要的特殊类型最小费用流问题有五种重要的特殊类型(续续)：（4 4）最大流问题最大流问题：有供应点、需求点、转运：有供应点、需求点、转运点、弧的容量限制，但点、弧的容量限制，但没有供应量和需求没有供应量和需求量的限制量的限制，目标是通过网络到目的地的总，目标是通
26、过网络到目的地的总流量最大。流量最大。（5 5）最短路问题最短路问题：有供应点：有供应点(供应量为供应量为1)1)、需求点需求点(需求量为需求量为1)1)、转运点、转运点、没有弧的没有弧的容量限制容量限制，目标是通过网络到目的地的总，目标是通过网络到目的地的总距离最短。距离最短。第22页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题在许多实际的网络系统中都存在着流量和最大流问题在许多实际的网络系统中都存在着流量和最大流问题。例如。例如铁路运输系统中的车辆流铁路运输系统中的车辆流，城市给排水系统城市给排水
27、系统的水流问题的水流问题等。而网络系统最大流问题是图与网络流等。而网络系统最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产中的理论中十分重要的最优化问题，它对于解决生产中的实际问题起着十分重要的作用。实际问题起着十分重要的作用。最大流问题也与网络中的流有关，但最大流问题也与网络中的流有关，但目标目标不是使得不是使得流的总成本最小，而是寻找一个流的方案，使得流的总成本最小，而是寻找一个流的方案，使得通过通过网络的流量最大网络的流量最大。除了目标（流最大化和成本最小化。除了目标（流最大化和成本最小化）不一样外，最大流问题的特征和最小费用流问题的）不一样外，最大流问题的特征和最小费用
28、流问题的特征非常相似。特征非常相似。第23页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题例例5.25.2 某公司要从起始点某公司要从起始点vs（发点）运（发点）运送货物到目的地送货物到目的地vt（收点），其网络图（收点），其网络图如图如图5 54 4（下一张幻灯片下一张幻灯片）所示。图）所示。图中每条弧（节点中每条弧（节点i-i-节点节点j j）旁边的权）旁边的权cij表示这段运输线路的最大通过能力（容表示这段运输线路的最大通过能力（容量）。要求制定一个运输方案，使得从量）。要求制定一个运输方案，使得
29、从vs到到vt的运货量达到最大，这个问题就是寻的运货量达到最大，这个问题就是寻求网络系统的求网络系统的最大流问题最大流问题。第24页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题707080806060404030305050404070705050vsvsv1v1v2v2v3v3v5v5v4v4vtvt第25页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题例例5.25.2最大流问题的线性规最大流问题的线性规划数
30、学模型：划数学模型：（1 1）决策变量）决策变量 设设fij为通过弧（节点为通过弧（节点i-i-节点节点j j）的流量。）的流量。（2 2）目标函数）目标函数 本问题的本问题的目标是从目标是从vs流流出的总流量最大出的总流量最大。（3 3）约束条件）约束条件(转运点的净转运点的净流量为流量为0 0、弧的容量限制、弧的容量限制、非负）、非负）123141242523534142452535Max F=0()0 0s.t()0()00 vsvvsvvsvvvvsvvvvvvsvvvvsvvvtvvvvvvtvvvvijijfffffffffffffffffc第26页，共73页。第第5章章 网络网络
31、最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题例例5.25.2最大流问题电子表格模型最大流问题电子表格模型第27页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题u 最大流问题的变形最大流问题的变形主要在于：有主要在于：有多个发点多个发点（供应点）和（供应点）和多个收点多个收点（需求点）。（需求点）。u 例例5.35.3 在例在例5.25.2的基础上，增加了一个的基础上，增加了一个发点发点ps、一个收点、一个收点pt、两个转运点、两个转运点p1和
32、和p2、以及与之相连的以及与之相连的7 7条弧，如图条弧，如图5 56 6（下一下一张幻灯片张幻灯片）所示。）所示。目标是从目标是从vs和和ps两个发两个发点运出的总流量最大点运出的总流量最大。这是一个有。这是一个有2 2个发个发点（供应点）和点（供应点）和2 2个收点（需求点）的最大个收点（需求点）的最大流问题。流问题。第28页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题7070808040401010202030305050404060603030404040407070505020206060v
33、1v1v2v2v3v3v5v5v4v4vtvtp1p1pspsptptp2p2vsvs第29页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题例例5.35.3的数学模型的数学模型11123141124252353441414245253512Max F=()0()0 0()()0s.t.()0(psppsvvsvvsvvsvvvvsvpsvvvvvvsvvvvsvvptvvtpvvvvvvvtvvvvpppfffffffffffffffffffffff1412 212)0()0 0 vpsppptpvtp
34、pijijfffffc第30页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题例例5.35.3的电子表格模型的电子表格模型第31页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题最大流问题的一些实际应用最大流问题的一些实际应用：（1 1）通过配送网络的流量最大，如例）通过配送网络的流量最大，如例5.25.2和和例例5.35.3；（2 2）通过管道运输系统的油的流量最大；）通过管道运输系统的油的流量最大；（3 3）通过
35、输水系统的水的流量最大；）通过输水系统的水的流量最大；（4 4）通过交通网络的车辆的流量最大；等等。）通过交通网络的车辆的流量最大；等等。第32页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题例例5.4 5.4 计划编制问题。某市政工程公司在未来计划编制问题。某市政工程公司在未来5 58 8月月份内需完成份内需完成4 4项工程：修建一条地下通道、修建一座项工程：修建一条地下通道、修建一座人行天桥、新建一条道路及道路维修。工期和所需劳人行天桥、新建一条道路及道路维修。工期和所需劳动力见表动力见表5 51
36、1。该公司共有劳动力。该公司共有劳动力120120人，任一工程人，任一工程在一个月内的劳动力投入不能超过在一个月内的劳动力投入不能超过8080人，问公司应如人，问公司应如何分配劳动力完成所有工程，是否能按期完成？何分配劳动力完成所有工程，是否能按期完成？工程工程工期工期需要劳动力（人）需要劳动力（人）A.A.地下通道地下通道5 57 7月月100100B.B.人行天桥人行天桥6 67 7月月8080C.C.新建道路新建道路5 58 8月月200200D.D.道路维修道路维修 8 8月月8080第33页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院
37、计算分院5.3 5.3 最大流问题最大流问题u本问题除了可以用第本问题除了可以用第3 3章介绍的线性规划方法来章介绍的线性规划方法来求解（可设求解（可设xij为工程为工程i在在j月投入的劳动力）外，还月投入的劳动力）外，还可以用可以用最大流最大流的方法来求解。的方法来求解。u将工程计划用网络图将工程计划用网络图5 58 8（下一张幻灯片下一张幻灯片）表）表示。示。图中的节点图中的节点5 5、6 6、7 7、8 8分别表示分别表示5 58 8月份，月份，AiAi、BiBi、CiCi、DiDi表示工程在第表示工程在第i i个月内完成的部分。用弧表示某月完成某个月内完成的部分。用弧表示某月完成某项工
38、程的状态，弧的流量为所投入的劳动力，受到劳动力限项工程的状态，弧的流量为所投入的劳动力，受到劳动力限制（弧旁边的数字表示弧的容量，制（弧旁边的数字表示弧的容量，从从S S开始的弧，其容量为该开始的弧，其容量为该公司共有劳动力公司共有劳动力120120人人；从节点；从节点5 5、6 6、7 7、8 8开始的弧以及到节点开始的弧以及到节点A A、B B、C C、D D的弧，其容量为任一工程在一个月内的劳动力投入的弧，其容量为任一工程在一个月内的劳动力投入不能超过不能超过8080人；人；到收点到收点T T的弧，其容量为每个工程所需劳动力的弧，其容量为每个工程所需劳动力）。）。合理安排每个月各工程的劳
39、动力，在不超过现有人力的条件合理安排每个月各工程的劳动力，在不超过现有人力的条件下，尽可能保证工程按期完成，就是求图下，尽可能保证工程按期完成，就是求图5 58 8从发点到收点从发点到收点的最大流问题。的最大流问题。第34页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题S S6 67 75 5B6B6A5A58 8C5C5A6A6C6C6A7A7D8D8C8C8B7B7C7C7B BC CA AD DT T1201208080808010010080802002008080注意：增加一个起点和注意：增加
40、一个起点和一个终点，其一个终点，其容量容量是是供应供应量量和和需求量需求量第35页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题u例例5.45.4市政工程公司劳动力分配电子表格模型市政工程公司劳动力分配电子表格模型P162P162u求解结果（每个月的劳动力分配）如表求解结果（每个月的劳动力分配）如表5 52 2所示。所示。5 5月份有剩余劳动力月份有剩余劳动力2020人，人，4 4项工程恰好按期完成。项工程恰好按期完成。月份月份投入劳动力投入劳动力项目项目A A项目项目B B项目项目C C项目项目D D
41、5 5100100202080806 6120120404080807 7120120808040408 812012040408080合计合计46046010010080802002008080第36页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题最小费用最大流问题最小费用最大流问题u在实际的网络应用当中，当涉及到流的问题时，有在实际的网络应用当中，当涉及到流的问题时，有时考虑的不只是流量，还要考虑费用多少的问题。比时考虑的不只是流量，还要考虑费用多少的问题。比如一个铁路运输系统的网络流，不但要考虑网
42、络系统如一个铁路运输系统的网络流，不但要考虑网络系统的货运量最大，又要考虑总费用最小。最小费用最大的货运量最大，又要考虑总费用最小。最小费用最大流就是要解决这一类的问题。流就是要解决这一类的问题。u所谓最小费用最大流问题就是：给定一个带收点和所谓最小费用最大流问题就是：给定一个带收点和发点的网络，对每一条弧（节点发点的网络，对每一条弧（节点i-i-节点节点j j）,除了给除了给出容量出容量cij外，还给出了这条弧的单位流量的费用外，还给出了这条弧的单位流量的费用bij ，要求一个最大流要求一个最大流F F，并使得总运费用最小。，并使得总运费用最小。u最小费用最大流问题也是一个线性规划问题。最小
43、费用最大流问题也是一个线性规划问题。第37页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题例例5.55.5 某公司有一个管道网络（如图某公司有一个管道网络（如图5 51010所示，所示，下一张幻灯片下一张幻灯片），使用这个网络可以把），使用这个网络可以把石油从采地石油从采地v v1 1运送到销地运送到销地v v7 7。由于输油管道长。由于输油管道长短不一，每段管道除了有不同的流量短不一，每段管道除了有不同的流量cij限制限制外，还有不同的单位流量的费用外，还有不同的单位流量的费用bij。每段管道。每段管
44、道旁边括号内的数值意义为（旁边括号内的数值意义为（cij，bij）。如果使）。如果使用这个网络系统，从采地用这个网络系统，从采地v v1 1向销地向销地v v7 7运送石油运送石油，怎样运送才能运送最多的石油并使得总的，怎样运送才能运送最多的石油并使得总的运送费用最小？运送费用最小？第38页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题(3,2)(3,2)(6,3)(6,3)(2,8)(2,8)(1,3)(1,3)(4,4)(4,4)(2,3)(2,3)(5,7)(5,7)(2,4)(2,4)（2,52
45、,5）(3,4)(3,4)(6,6)(6,6)v1v1v7v7v6v6v5v5v4v4v3v3v2v2第39页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.3 5.3 最大流问题最大流问题解：解：用线性规划来求解此题，分为两步走。用线性规划来求解此题，分为两步走。第一步：先求出此网络系统的最大流量第一步：先求出此网络系统的最大流量F F。数学模型数学模型P164P164电子表格模型电子表格模型P165P165求得的最大流量求得的最大流量F=10F=10第二步：在最大流量第二步：在最大流量F F的所有解中，找出一个最的所有解中，找出一个
46、最小费用的解。小费用的解。数学模型数学模型P166P166电子表格模型电子表格模型P166P166求得的最小费用为求得的最小费用为145145第40页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院作业：作业：第第190页页 第第1题（最小费用流、最大流题（最小费用流、最大流）周三上机：周三上机：第第145页页 第第11题（指派问题）题（指派问题）第十二周上机以及作业第41页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.4 5.4 最短路问题最短路问题u最短路问题是网络理论中应用最
47、广泛的问题之最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如一。许多优化问题可以使用这个模型，如设备更设备更新新、管道铺设管道铺设、线路安排线路安排、厂区布局厂区布局等等u最短路问题的最普遍的应用是在最短路问题的最普遍的应用是在两个点之间寻两个点之间寻找最短路找最短路，是最小费用流问题的一种特殊类型，是最小费用流问题的一种特殊类型：源的供应量为：源的供应量为1 1、目的地（需求点）的需求、目的地（需求点）的需求量为量为1 1、转运点的净流量为、转运点的净流量为0 0、没有弧的容量、没有弧的容量限制，目标：限制，目标：通过网络到目的地的总距离最短通过网络到目的地的总距
48、离最短。第42页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.4 5.4 最短路问题最短路问题例例5.65.6 某人每天从住处某人每天从住处v1v1开车到工作地开车到工作地v7v7上班，上班，图中各弧旁的数字表示道路的长度（公里），试图中各弧旁的数字表示道路的长度（公里），试问该人应选择哪条路线，从家出发到工作地，路问该人应选择哪条路线，从家出发到工作地，路上行驶的总距离最短。上行驶的总距离最短。v1v1v2v2v3v3v4v4v5v5v6v6v7v72 29 96 68 83.53.51 14 45 52.52.53 3第43页，共
49、73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.4 5.4 最短路问题最短路问题解：解：这是一个最短路问题。其数学模型为：这是一个最短路问题。其数学模型为：（1 1）决策变量决策变量：设：设xij为弧为弧(节点节点i-i-节点节点j)j)是否是否走（走（1 1表示走，表示走，0 0表示不走）。表示不走）。（2 2）目标函数目标函数本问题的目标是总距离最短。本问题的目标是总距离最短。（3 3）约束条件约束条件(节点净流量、非负）节点净流量、非负）P169P16912132324343545465767Min z=29681 343.52.55
50、xxxxxxxxxx第44页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.4 5.4 最短路问题最短路问题例例5.65.6的最短路问题的电子表格模型的最短路问题的电子表格模型第45页，共73页。第第5章章 网络网络最优化问题最优化问题浙江大学城市学院浙江大学城市学院 计算分院计算分院5.4 5.4 最短路问题最短路问题u最短路问题的应用很广，如设最短路问题的应用很广，如设备更新、管道铺设、线路安排、备更新、管道铺设、线路安排、厂区布局等。厂区布局等。u下面举两个例子：下面举两个例子：（1 1）设备更新设备更新问题；问题；（2 2）新产
