第5章-网络最优化问题课件.ppt

1、实用运筹学运用Excel建模和求解第第5 5章章网络最优化问题网络最优化问题本章内容要点网络最优化问题的基本概念网络最优化问题的基本概念网络最优化问题的四种主要网络最优化问题的四种主要类型：类型：最小费用流最小费用流、最大流最大流、最短路最短路、最小支撑树最小支撑树各种网络最优化问题的建模各种网络最优化问题的建模与应用与应用本章节内容5.1 5.1 网络最优化问题基本概念网络最优化问题基本概念5.2 5.2 最小费用流问题最小费用流问题5.3 5.3 最大流问题最大流问题5.4 5.4 最短路问题最短路问题5.5 5.5 最小支撑树问题最小支撑树问题5.6 5.6 货郎担问题和中国邮路问题货郎

2、担问题和中国邮路问题本章主要内容框架图点连 线（边 或 弧）基 本 概 念权（赋 权 图）网 络 图最 小 费 用 流 问 题最 大 流 问 题网 络 最 优 化 问 题主 要 类 型最 短 路 问 题最 小 支 撑 树 问 题货 郎 担 问 题 和 中 国 邮 路 问 题节 点（供 应 点、转 运 点、需 求 点）净 流 量建 模 和 求 解数 学 模 型电 子 表 格 模 型图论的起源和发展 1736年，欧拉的哥尼斯堡七桥问题BACD图论的起源和发展 1847年，基尔霍夫年，基尔霍夫，电网络，树，电网络，树”；1852年，年，四色猜想四色猜想；1964年，华罗庚，年，华罗庚，统筹方法平话统

3、筹方法平话。1857年，凯莱年，凯莱，同分异构，同分异构，“树树”；1956年，杜邦公司，年，杜邦公司，CPM，关键路线法；，关键路线法；1958年，美国海军部，年，美国海军部，PERT，计划评审技术；，计划评审技术；1962年，管梅谷，年，管梅谷，中国邮路问题中国邮路问题；1859年，哈密顿，年，哈密顿，哈密顿回路哈密顿回路 ；几个例子几个例子例例1 是北京、上海等是北京、上海等十个城市间的铁路交十个城市间的铁路交通图。与此类似的还通图。与此类似的还有电话线分布图、煤有电话线分布图、煤气管道图、航空路线气管道图、航空路线图等。图等。北京北京天津天津济南济南青岛青岛武汉武汉南京南京上海上海郑州

4、郑州连云港连云港徐州徐州例2旅行商问题/货郎（担）问题(TSP-Traveling Salesman Problem)一名推销员准备前往若干城市推销产品.如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.例3 稳定婚配 假设有n个男人和n个女人,每人都希望从n个异性中选择一位自己的配偶.假设每人都对n个异性根据自己的偏好进行了排序,以此作为选择配偶的基础.当给定一种婚配方案(即给每人指定一个配偶)后,如果存在一个男人和一个女人不是互为配偶,但该男人喜欢该女人胜过其配偶,且该女人喜欢该男人也胜过其配偶,则该婚

5、配方案称为不稳定的.安排稳定的婚配方案的问题称为稳定婚配问题。5.1 网络最优化问题基本概念u网络在各种实际背景问题中以各种各样的形式存网络在各种实际背景问题中以各种各样的形式存在。交通、电子和通讯网络遍及我们日常生活的在。交通、电子和通讯网络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中各个方面，网络规划也广泛用于解决不同领域中的各种问题，如生产、分配、项目计划、厂址选的各种问题，如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。择、资源管理和财务策划等等。u网络规划为描述系统各组成部分之间的关系提供网络规划为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的帮

6、助，广泛应用于了非常有效的直观和概念上的帮助，广泛应用于科学、社会和经济活动的各个领域中。科学、社会和经济活动的各个领域中。u近些年来，运筹学（管理科学）中一个振奋人心近些年来，运筹学（管理科学）中一个振奋人心的发展是它的的发展是它的网络最优化问题的方法论网络最优化问题的方法论和和应用方应用方面面都取得了不同寻常的飞速发展都取得了不同寻常的飞速发展。5.1 网络最优化问题基本概念u许多研究的对象往往可以用一个许多研究的对象往往可以用一个图图表示，研究的表示，研究的目的归结为图的极值问题。目的归结为图的极值问题。u运筹学中研究的图具有下列特征：运筹学中研究的图具有下列特征：(1)(1)用用点点表

7、示研究对象，用表示研究对象，用连线连线（不带箭头的（不带箭头的边边或或带箭头的带箭头的弧弧）表示对象之间某种关系；）表示对象之间某种关系；(2)(2)强调点与点之间的关联关系，不讲究图的比例强调点与点之间的关联关系，不讲究图的比例大小与形状；大小与形状；(3)(3)每条边上都赋有一个权，其图称为每条边上都赋有一个权，其图称为赋权图赋权图。实。实际中权可以代表两点之间的距离、费用、利润、时际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义；间、容量等不同的含义；(4)(4)建立一个建立一个网络模型网络模型，求最大值或最小值。，求最大值或最小值。5.1 网络最优化问题基本概念v1v3

8、v5v2v4v68736548521对于该网络图，可以提出许多极值问题对于该网络图，可以提出许多极值问题 5.1 网络最优化问题基本概念（1 1）将某个点）将某个点vi的物资或信息送到另一的物资或信息送到另一个点个点vj，使得运送总成本最小。这属于，使得运送总成本最小。这属于最小费用流最小费用流问题。问题。（2 2）将某个点）将某个点vi的物资或信息送到另一的物资或信息送到另一个点个点vj，使得总流量最大。这属于，使得总流量最大。这属于最大最大流流问题。问题。（3 3）从某个点）从某个点vi出发到达另一个点出发到达另一个点vj，怎样安排路线使得总距离最短或总费用怎样安排路线使得总距离最短或总费

9、用最小。这属于最小。这属于最短路最短路问题。问题。5.1 网络最优化问题基本概念（4 4）点）点vi表示自来水厂及用户，表示自来水厂及用户，vi与与vj之间的边表示两点间可以铺设管道，权为之间的边表示两点间可以铺设管道，权为vi与与vj间间铺设管道的距离或费用，极值问题是如何铺设管道，将自来水送到其他铺设管道的距离或费用，极值问题是如何铺设管道，将自来水送到其他5 5个用户并且个用户并且使总的费用最小。这属于使总的费用最小。这属于最小支撑树最小支撑树问题。问题。(5)(5)售货员从某个点售货员从某个点vi出发走过出发走过其他所有点其他所有点后回到原点后回到原点vi，如何安排路线使总路程最短。，

10、如何安排路线使总路程最短。这属于这属于货郎担问题货郎担问题或旅行售货员问题。或旅行售货员问题。（6 6）邮递员从邮局）邮递员从邮局vi出发要经过出发要经过每一条边每一条边将邮件送到用户手中，最后回到邮局将邮件送到用户手中，最后回到邮局vi，如何，如何安排路线使总路程最短。这属于安排路线使总路程最短。这属于中国邮递员问题中国邮递员问题。5.1 网络最优化问题基本概念网络最优化问题类型网络最优化问题类型主要包括：主要包括：（1 1）最小费用流问题；）最小费用流问题；（2 2）最大流问题；）最大流问题；（3 3）最短路问题；）最短路问题；（4 4）最小支撑树问题；）最小支撑树问题；（5 5）货郎担问

11、题和中国邮路问题，等等）货郎担问题和中国邮路问题，等等5.2 最小费用流问题u最小费用流问题的模型在网络最优化中扮演着重要的角色，因为它的适用性最小费用流问题的模型在网络最优化中扮演着重要的角色，因为它的适用性很广，并且求解方法容易。通常很广，并且求解方法容易。通常最小费用流问题用于最优化货物从供应点到最小费用流问题用于最优化货物从供应点到需求点的网络。目标是在通过网络配送货物时，以最小的成本满足需求，一需求点的网络。目标是在通过网络配送货物时，以最小的成本满足需求，一种典型的应用就是使得配送网络的运营最优种典型的应用就是使得配送网络的运营最优。u最小费用流问题的最小费用流问题的特殊类型特殊类

12、型包括包括运输问题运输问题和和指派问题指派问题，以及在下面将要提到，以及在下面将要提到的两种重要类型：的两种重要类型：最大流问题最大流问题和和最短路问题最短路问题。5.2 最小费用流问题例例5.1 5.1 某公司有两个工厂生产产品，这些产品需要运某公司有两个工厂生产产品，这些产品需要运送到两个仓库中。其配送网络图如图送到两个仓库中。其配送网络图如图5-25-2所示。目标所示。目标是确定一个是确定一个运输方案运输方案（即每条路线运送多少单位的产（即每条路线运送多少单位的产品），使通过配送网络的品），使通过配送网络的总运输成本最小总运输成本最小。（5050，400400）（5050，200200）

13、（5050，400400）（5050，300300）F1F1F2F2DCDCW2W2W1W18080707060609090（无限制，（无限制，700700）（无限制，（无限制，900900）5.2 最小费用流问题最小费用流问题的三个基本概念：最小费用流问题的三个基本概念：1 1、最小费用流问题的构成（、最小费用流问题的构成（网络表示网络表示）（1 1）节点节点：包括供应点、需求点和转运：包括供应点、需求点和转运点；点；（2 2）弧弧：可行的运输线路（节点：可行的运输线路（节点i-i-节点节点j j），经常有最大流量（容量）的限制。），经常有最大流量（容量）的限制。5.2 最小费用流问题2 2

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

15、流量成正比；（和流量成正比；（目标是线性的目标是线性的）（7 7）最小费用流问题的目标在满足给定需求条件下，使得通）最小费用流问题的目标在满足给定需求条件下，使得通过网络供应的过网络供应的总成本最小总成本最小（或总利润最大）。（或总利润最大）。5.2 最小费用流问题3 3、最小费用流问题的解的特征、最小费用流问题的解的特征（1 1）具有可行解具有可行解的特征：在以上的假设下，当的特征：在以上的假设下，当且仅当且仅当供应点所提供的流量总和供应点所提供的流量总和等于等于需求点所需求点所需要的流量总和需要的流量总和时（即平衡条件），最小费用时（即平衡条件），最小费用流问题有可行解；流问题有可行解；（

16、2 2）具有整数解具有整数解的特征：只要其所有的的特征：只要其所有的供应供应、需求需求和和弧的容量弧的容量都是都是整数整数值，那么任何最小费值，那么任何最小费用流问题的可行解就一定有所有流量都是用流问题的可行解就一定有所有流量都是整数整数的最优解的最优解（与运输问题和指派问题的解一样）。（与运输问题和指派问题的解一样）。因此，没有必要加上所有决策变量都是整数的因此，没有必要加上所有决策变量都是整数的约束条件。约束条件。5.2 最小费用流问题最小费用流问题的最小费用流问题的数学模型数学模型为：为：（1 1）决策变量：设）决策变量：设fij为通过弧（节点为通过弧（节点i-i-节点节点j j）的）的

17、流量。流量。（2 2）目标是通过网络供应的总成本最小。）目标是通过网络供应的总成本最小。（3 3）约束条件）约束条件 所有所有供应点供应点：净流量（总流出总流入）为：净流量（总流出总流入）为正正；所有所有转运点转运点：净流量为：净流量为零零；所有所有需求点需求点：净流量为：净流量为负负；所有弧的流量所有弧的流量fij受到弧的受到弧的容量限制容量限制；所有弧的流量所有弧的流量fij非负非负。5.2 最小费用流问题例例5.15.1最小费用流问题的最小费用流问题的数学模型数学模型为：为：（1 1）决策变量：设）决策变量：设fij为通过弧为通过弧(节点节点i-节点节点j)的流的流量。量。（2 2）目标

18、函数）目标函数 本问题的目标是总运输成本最小本问题的目标是总运输成本最小11112222Min z=700300200 400900400FWFDCDCWFDCFWDCWffffff5.2 最小费用流问题（3 3）约束条件）约束条件(节点节点净流量、弧的容量限净流量、弧的容量限制、非负）制、非负）供应点供应点 F1:F1:供应点供应点 F2:F2:转运点转运点 DC:DC:需求点需求点 W1:W1:需求点需求点 W2:W2:弧的容量限制：弧的容量限制：非负：非负：1111222211122212121112221Min z=700300200 400900400=80+=70 ()0s.t.=

19、60 90,FWFDCDC WFDCFWDC WFWFDCFDCFWDC WDC WFDCFDCFWDC WDC WFWFDCfffffffffffffffffff21211112222,50,0FDCDC WDC WFWFDCDC WFDCFWDC Wfffffffff5.2 最小费用流问题 例例5.15.1的的电子表格模型电子表格模型：列出了网络中的弧和各弧所对应的容量、：列出了网络中的弧和各弧所对应的容量、单位成本。决策变量为通过弧的流量。目标是计算流量的总成本。单位成本。决策变量为通过弧的流量。目标是计算流量的总成本。每个节点的净流量为约束条件。供应点的净流量为正，需求点的每个节点的净

20、流量为约束条件。供应点的净流量为正，需求点的净流量为负，而转运点的净流量为净流量为负，而转运点的净流量为0 0。这里用了一个这里用了一个窍门窍门：用两个：用两个SUMIFSUMIF函数的差来计算每个节点的净函数的差来计算每个节点的净流量，这样流量，这样快捷快捷且且不容易犯错不容易犯错。5.2 最小费用流问题u大规模的最小费用流问题的求解一般采用大规模的最小费用流问题的求解一般采用“网络单纯法网络单纯法（The Network The Network Simplex MethodSimplex Method）”。现在，许多公司都使用网络单纯法来解决他们的最小。现在，许多公司都使用网络单纯法来解决

21、他们的最小费用流问题。有些问题是非常庞大的，有着数万个节点和弧。有时，弧的数费用流问题。有些问题是非常庞大的，有着数万个节点和弧。有时，弧的数量甚至可能会多得多，达到几百万条。量甚至可能会多得多，达到几百万条。u但但ExcelExcel学生版（非专业版）学生版（非专业版）的的“规划求解规划求解”中没有网络单纯法中没有网络单纯法，但其他的，但其他的线性规划的商业软件包通常都有这种方法。线性规划的商业软件包通常都有这种方法。5.2 最小费用流问题最小费用流问题有五种重要的特殊类型：最小费用流问题有五种重要的特殊类型：（1 1）运输问题运输问题：有出发地：有出发地(供应点供应点-供应量供应量)和目的

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

23、的容量，有转运点，但没有弧的容量限制限制(或有容量限制或有容量限制)，目标是总流量费用最小（或，目标是总流量费用最小（或总利润最大）。总利润最大）。5.2 最小费用流问题最小费用流问题有五种重要的特殊类型最小费用流问题有五种重要的特殊类型(续续)：（4 4）最大流问题最大流问题：有供应点、需求点、转运点、弧的容量限制，但：有供应点、需求点、转运点、弧的容量限制，但没有供应量和没有供应量和需求量的限制需求量的限制，目标是通过网络到目的地的总流量最大。，目标是通过网络到目的地的总流量最大。（5 5）最短路问题最短路问题：有供应点：有供应点(供应量为供应量为1)1)、需求点、需求点(需求量为需求量为

24、1)1)、转运点、转运点、没有没有弧的容量限制弧的容量限制，目标是通过网络到目的地的总距离最短。，目标是通过网络到目的地的总距离最短。5.3 最大流问题u在许多实际的网络系统中都存在着流量和最大流在许多实际的网络系统中都存在着流量和最大流问题。例如问题。例如铁路运输系统中的车辆流铁路运输系统中的车辆流，城市给排城市给排水系统的水流问题水系统的水流问题等。而网络系统最大流问题是等。而网络系统最大流问题是图与网络流理论中十分重要的最优化问题，它对图与网络流理论中十分重要的最优化问题，它对于解决生产中的实际问题起着十分重要的作用。于解决生产中的实际问题起着十分重要的作用。u最大流问题也与网络中的流有

25、关，但最大流问题也与网络中的流有关，但目标目标不是使不是使得流的总成本最小，而是寻找一个流的方案，使得流的总成本最小，而是寻找一个流的方案，使得得通过网络的总流量最大通过网络的总流量最大。除了目标（流最大化。除了目标（流最大化和成本最小化）不一样外，最大流问题的特征和和成本最小化）不一样外，最大流问题的特征和最小费用流问题的特征非常相似。最小费用流问题的特征非常相似。5.3 最大流问题例例5.25.2 某公司要从起始点某公司要从起始点vs（发点）运（发点）运送货物到目的地送货物到目的地vt（收点），其网络图（收点），其网络图如图如图5-45-4（下一张幻灯片下一张幻灯片）所示。图中）所示。图中

26、每条弧（节点每条弧（节点i-i-节点节点j j）旁边的权）旁边的权cij表表示这段运输线路的最大通过能力（容示这段运输线路的最大通过能力（容量）。要求制定一个运输方案，使得从量）。要求制定一个运输方案，使得从vs到到vt的运货量达到最大，这个问题就的运货量达到最大，这个问题就是寻求网络系统的是寻求网络系统的最大流问题最大流问题。5.3 最大流问题707080806060404030305050404070705050vsvsv1v1v2v2v3v3v5v5v4v4vtvt5.3 最大流问题例例5.25.2最大流问题的线性最大流问题的线性规划数学模型：规划数学模型：（1 1）决策变量）决策变量

27、设设fij为通过弧（节点为通过弧（节点i-i-节点节点j j）的流量。）的流量。（2 2）目标函数）目标函数 本问题的本问题的目标是从目标是从vs流出的总流量最大流出的总流量最大。（3 3）约束条件）约束条件(转运点的转运点的净流量为净流量为0 0、弧的容量限、弧的容量限制、非负）制、非负）123141242523534142452535Max F=0()0 0s.t()0()00 vsvvsvvsvvvvsvvvvvvsvvvvsvvvtvvvvvvtvvvvijijfffffffffffffffffc5.3 最大流问题例例5.25.2最大流问题电子表格模型最大流问题电子表格模型5.3 最大

28、流问题u最大流问题的变形最大流问题的变形主要在于：有主要在于：有多个发多个发点点（供应点）和（供应点）和多个收点多个收点（需求点）。（需求点）。u例例5.35.3 在例在例5.25.2的基础上，增加了一个的基础上，增加了一个发点发点ps、一个收点、一个收点pt、两个转运点、两个转运点p1和和p2、以及与之相连的以及与之相连的7 7条弧，如图条弧，如图5-65-6（下一下一张幻灯片张幻灯片）所示。）所示。目标是从目标是从vs和和ps两个发两个发点运出的总流量最大点运出的总流量最大。这是一个有。这是一个有2 2个发个发点（供应点）和点（供应点）和2 2个收点（需求点）的最个收点（需求点）的最大流问

29、题。大流问题。5.3 最大流问题7070808040401010202030305050404060603030404040407070505020206060v1v1v2v2v3v3v5v5v4v4vtvtp1p1pspsptptp2p2vsvs5.3 最大流问题例例5.35.3的数学模型的数学模型11123141124252353441414245253512Max F=()0()0 0()()0s.t.()0(psppsvvsvvsvvsvvvvsvpsvvvvvvsvvvvsvvptvvtpvvvvvvvtvvvvpppfffffffffffffffffffffff1412 212)0

30、()0 0 vpsppptpvtppijijfffffc5.3 最大流问题例例5.35.3的电子表格模型的电子表格模型5.3 最大流问题最大流问题的一些实际应用最大流问题的一些实际应用：（1 1）通过配送网络的流量最大，如例）通过配送网络的流量最大，如例5.25.2和例和例5.35.3；（2 2）通过管道运输系统的油的流量最大；）通过管道运输系统的油的流量最大；（3 3）通过输水系统的水的流量最大；）通过输水系统的水的流量最大；（4 4）通过交通网络的车辆的流量最大；等等。）通过交通网络的车辆的流量最大；等等。5.3 最大流问题例例5.4 5.4 计划编制问题。某市政工程公司在未来计划编制问题

31、。某市政工程公司在未来5 58 8月月份内需完成份内需完成4 4项工程：修建一条地下通道、修建一座项工程：修建一条地下通道、修建一座人行天桥、新建一条道路及道路维修。工期和所需劳人行天桥、新建一条道路及道路维修。工期和所需劳动力见表动力见表5-15-1。该公司共有劳动力。该公司共有劳动力120120人，任一工程在人，任一工程在一个月内的劳动力投入不能超过一个月内的劳动力投入不能超过8080人，问公司应如何人，问公司应如何分配劳动力完成所有工程，是否能按期完成？分配劳动力完成所有工程，是否能按期完成？工程工程工期工期需要劳动力（人）需要劳动力（人）A.A.地下通道地下通道5 57 7月月1001

32、00B.B.人行天桥人行天桥6 67 7月月8080C.C.新建道路新建道路5 58 8月月200200D.D.道路维修道路维修 8 8月月80805.3 最大流问题u本问题除了可以用第本问题除了可以用第3 3章介绍的线性规划方法来求解（可章介绍的线性规划方法来求解（可设设xij为工程为工程i在在j月投入的劳动力）外，还可以用月投入的劳动力）外，还可以用最大流最大流的方的方法来求解。法来求解。u将工程计划用网络图将工程计划用网络图5-85-8（下一张幻灯片下一张幻灯片）表示。图中的）表示。图中的节点节点5 5、6 6、7 7、8 8分别表示分别表示5 58 8月份，月份，AiAi、BiBi、C

33、iCi、DiDi表示表示工程在第工程在第i i个月内完成的部分。用弧表示某月完成某项工程个月内完成的部分。用弧表示某月完成某项工程的状态，弧的流量为所投入的劳动力，受到劳动力限制的状态，弧的流量为所投入的劳动力，受到劳动力限制（弧旁边的数字表示弧的容量，（弧旁边的数字表示弧的容量，从从S S开始的弧，其容量为该开始的弧，其容量为该公司共有劳动力公司共有劳动力120120人人；从节点；从节点5 5、6 6、7 7、8 8开始的弧以及到开始的弧以及到节点节点A A、B B、C C、D D的弧，其容量为任一工程在一个月内的劳的弧，其容量为任一工程在一个月内的劳动力投入不能超过动力投入不能超过8080

34、人；人；到收点到收点T T的弧，其容量为每个工程的弧，其容量为每个工程所需劳动力所需劳动力）。合理安排每个月各工程的劳动力，在不超）。合理安排每个月各工程的劳动力，在不超过现有人力的条件下，尽可能保证工程按期完成，就是求过现有人力的条件下，尽可能保证工程按期完成，就是求图图5-85-8从发点到收点的最大流问题。从发点到收点的最大流问题。5.3 最大流问题S S6 67 75 5B6B6A5A58 8C5C5A6A6C6C6A7A7D8D8C8C8B7B7C7C7B BC CA AD DT T1201208080808010010080802002008080注意：增加一个起点注意：增加一个起点

35、S和一个终点和一个终点T，其，其容量容量是是供应量供应量和和需求量需求量5.3 最大流问题u例例5.45.4市政工程公司劳动力分配电子表格模型市政工程公司劳动力分配电子表格模型P162P162u求解结果（每个月的劳动力分配）如表求解结果（每个月的劳动力分配）如表5-25-2所示。所示。5 5月份有剩余劳动力月份有剩余劳动力2020人，人，4 4项工程恰好按期完成。项工程恰好按期完成。月份月份投入劳动力投入劳动力项目项目A A项目项目B B项目项目C C项目项目D D5 5100100202080806 6120120808040407 7120120404080808 812012040408

36、080合计合计460460100100808020020080805.3 最大流问题（补充）u例例5.45.4（补充补充）市政工程公司劳动力分配市政工程公司劳动力分配简化版简化版。在在P161的工程计划网络图中，可以去掉中间的节点的工程计划网络图中，可以去掉中间的节点A5D8（共（共10个节点）个节点），直接将代表月份的节点（，直接将代表月份的节点（5、6、7、8）指向相应的工程节点（）指向相应的工程节点（A、B、C、D），其容量为任一工程在一个月内的劳动力投入不能超过），其容量为任一工程在一个月内的劳动力投入不能超过80人。人。S S6 67 75 58 8B BC CA AD DT T12

37、0120100100808020020080808080注意：增加一个起点注意：增加一个起点S和一个终点和一个终点T，其，其容量容量是是供应量供应量和和需求量需求量5.3 最大流问题（补充）u例例5.4 5.4（补充补充）市政工程公司劳动力分配市政工程公司劳动力分配简化版简化版。u此时对应的电子表格模型也做相应的简化。此时对应的电子表格模型也做相应的简化。u求得求得另外一个另外一个结果（每个月的劳动力分配）如下表所结果（每个月的劳动力分配）如下表所示。示。6 6月份有剩余劳动力月份有剩余劳动力2020人，人，4 4项工程恰好按期完成。项工程恰好按期完成。月份月份投入劳动力投入劳动力项目项目A

38、A项目项目B B项目项目C C项目项目D D5 5120120404080806 6100100606040407 7120120404080808 812012040408080合计合计460460100100808020020080805.3 最大流问题（补充）u补充：补充：用用最大流最大流的方法来求解的方法来求解4 4个个实际问题：实际问题：（1 1）某公司有某公司有3 3个仓库和个仓库和4 4个零售店，各仓库可提供的个零售店，各仓库可提供的货量及零售店的最大零售量如下表所示，货量及零售店的最大零售量如下表所示，打圈打圈的表示公的表示公司指定该店可向相应的仓库取货。现在要求作一个调运司指

39、定该店可向相应的仓库取货。现在要求作一个调运方案，使得各店从各仓库得到的总货量最多。方案，使得各店从各仓库得到的总货量最多。（答案：最大总货量为（答案：最大总货量为41,441,4个零售店都能满足）个零售店都能满足）零售店零售店B1B1B2B2B3B3B4B4存货量存货量仓库仓库A1A1o oo o2020仓库仓库A2A2o oo o1212仓库仓库A3A3o oo o1212最大零售量最大零售量14149 98 810105.3 最大流问题（补充）u补充：补充：用用最大流最大流的方法来求解的方法来求解4 4个个实际问题：实际问题：（2 2）某产品从仓库运往市场销售，已知各仓库的可供某产品从仓

40、库运往市场销售，已知各仓库的可供量、各市场的需求量及从仓库到市场的运输能力如下量、各市场的需求量及从仓库到市场的运输能力如下表所示（表示无路）。试求从仓库可运往市场的最表所示（表示无路）。试求从仓库可运往市场的最大流量，各市场需求能否满足？大流量，各市场需求能否满足？（答案：最大流量为（答案：最大流量为110110，市场，市场B3B3只满足只满足5050，其他市场都满足），其他市场都满足）市场市场B1B1B2B2B3B3B4B4可供量可供量仓库仓库A1A13030101040402020仓库仓库A2A2101050502020仓库仓库A3A32020101040405 5100100需求量需求

41、量20202020606020205.3 最大流问题（补充）u补充：补充：用用最大流最大流的方法来求解的方法来求解4 4个个实际问题：实际问题：（3 3）某单位招收懂俄、英、日、德、法文的翻译各某单位招收懂俄、英、日、德、法文的翻译各1 1人，现有人，现有5 5人应聘，已知乙懂俄文，甲、乙、丙、丁人应聘，已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这文，问这5 5个人是否都能得到聘书？最多几个得到招个人是否都能得到聘书？最多几个得到招聘，招聘后每人从事哪一方面的翻译任务？聘，招聘后每人从事哪一方面的翻译任务？（4

42、 4人）人）（4 4）已知有已知有6 6台机床台机床AiAi，6 6种零件种零件BiBi。机床。机床A1A1可加工可加工零件零件B1B1；A2A2可加工零件可加工零件B1B1、B2 B2；A3A3可加工零件可加工零件B1B1、B2B2、B3B3；A4A4可加工零件可加工零件B2B2；A5A5可加工零件可加工零件B2B2、B3B3、B4B4；A6A6可加工零件可加工零件B2B2、B5B5、B6B6。现在要求制定一个加工方。现在要求制定一个加工方案，使一台机床只加工一种零件，一种零件只在一台案，使一台机床只加工一种零件，一种零件只在一台机床上加工，要求尽可能多地安排零件的加工。请把机床上加工，要求

43、尽可能多地安排零件的加工。请把这个问题转化为求网络最大流的问题，求出能满足上这个问题转化为求网络最大流的问题，求出能满足上述条件的加工方案。述条件的加工方案。（答案：最大流为（答案：最大流为5 5）5.3 最大流问题最小费用最大流问题最小费用最大流问题u在实际的网络应用当中，当涉及到流的问题时，有在实际的网络应用当中，当涉及到流的问题时，有时考虑的不只是时考虑的不只是流量流量，还要考虑，还要考虑费用费用多少的问题。比多少的问题。比如一个铁路运输系统的网络流，不但要考虑网络系统如一个铁路运输系统的网络流，不但要考虑网络系统的货运量最大，还要考虑总费用最小。最小费用最大的货运量最大，还要考虑总费用

44、最小。最小费用最大流就是要解决这一类的问题。流就是要解决这一类的问题。u所谓最小费用最大流问题就是：给定一个带收点和所谓最小费用最大流问题就是：给定一个带收点和发点的网络，对每一条弧（节点发点的网络，对每一条弧（节点i-i-节点节点j j）,除了给除了给出容量出容量cij外，还给出了这条弧的单位流量的费用外，还给出了这条弧的单位流量的费用bij ，要求一个最大流要求一个最大流F F，并使得总运费用最小。，并使得总运费用最小。u最小费用最大流问题也是一个线性规划问题。最小费用最大流问题也是一个线性规划问题。5.3 最大流问题例例5.55.5 某公司有一个管道网络（如图某公司有一个管道网络（如图5

45、-105-10所所示，示，下一张幻灯片下一张幻灯片），使用这个网络可以把），使用这个网络可以把石油从采地石油从采地v v1 1运送到销地运送到销地v v7 7。由于输油管道。由于输油管道长短不一，每段管道除了有不同的长短不一，每段管道除了有不同的流量流量cij限限制外，还有不同的单位流量的制外，还有不同的单位流量的费用费用bij。每段。每段管道旁边括号内的数值意义为（管道旁边括号内的数值意义为（cij，bij）。）。如果使用这个网络系统，从采地如果使用这个网络系统，从采地v v1 1向销地向销地v v7 7运送石油，怎样运送才能运送最多的石油并运送石油，怎样运送才能运送最多的石油并使得总的运送

46、费用最小？使得总的运送费用最小？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,5）(3,4)(3,4)(6,6)(6,6)v1v1v7v7v6v6v5v5v4v4v3v3v2v25.3 最大流问题解：解：用线性规划来求解此题，分为用线性规划来求解此题，分为两步两步走。走。第一步第一步：先求出此网络系统的：先求出此网络系统的最大流量最大流量F F。数学模型数学模型P164P164电子表格模型电子表格模型P165P165求得的最大流量求得的最大流量F=10

47、F=10第二步第二步：在最大流量：在最大流量F F的所有解中，找出一个的所有解中，找出一个最最小费用小费用的解。的解。数学模型数学模型P166P166电子表格模型电子表格模型P166P166求得的最小费用为求得的最小费用为1451455.4 最短路问题u最短路问题是网络理论中应用最广泛的问最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，题之一。许多优化问题可以使用这个模型，如如设备更新设备更新、管道铺设管道铺设、线路安排线路安排、厂区布厂区布局局等等u最短路问题的最普遍的应用是在最短路问题的最普遍的应用是在两个点之两个点之间寻找最短路间寻找最短路，是最小费用流问题的一

48、种特，是最小费用流问题的一种特殊类型：源的供应量为殊类型：源的供应量为1 1、目的地（需求点）、目的地（需求点）的需求量为的需求量为1 1、转运点的净流量为、转运点的净流量为0 0、没有、没有弧的容量限制，目标：弧的容量限制，目标：通过网络到目的地的通过网络到目的地的总距离最短总距离最短。5.4 最短路问题例例5.65.6 某人每天从住处某人每天从住处v1v1开车到工作地开车到工作地v7v7上上班，图中各弧旁的数字表示道路的长度（公班，图中各弧旁的数字表示道路的长度（公里），试问该人应选择哪条路线，从家出发里），试问该人应选择哪条路线，从家出发到工作地，路上行驶的总距离最短。到工作地，路上行驶

49、的总距离最短。v1v1v2v2v3v3v4v4v5v5v6v6v7v72 29 96 68 83.53.51 14 45 52.52.53 35.4 最短路问题解：解：这是一个最短路问题。其数学模型为：这是一个最短路问题。其数学模型为：（1 1）决策变量决策变量：设：设xij为弧为弧(节点节点i-i-节点节点j)j)是是否走（否走（1 1表示走，表示走，0 0表示不走）。表示不走）。（2 2）目标函数目标函数本问题的目标是总距离最短本问题的目标是总距离最短（3 3）约束条件约束条件(节点净流量、非负）节点净流量、非负）P169P16912132324343545465767Min z=2968

50、1 343.52.55xxxxxxxxxx5.4 最短路问题例例5.65.6的最短路问题的电子表格模型的最短路问题的电子表格模型5.4 最短路问题u最短路问题的应用很广，如设备最短路问题的应用很广，如设备更新、管道铺设、线路安排、厂区更新、管道铺设、线路安排、厂区布局、选址（布局、选址（如如P194P194的习题的习题9 9、P198P198的习题的习题1919）等。）等。u下面举两个例子：下面举两个例子：（1 1）设备更新设备更新问题；问题；（2 2）新产品开发时间新产品开发时间问题。问题。5.4 最短路问题u例例5.7 5.7 设备更新问题设备更新问题。某工厂的某台机器可连。某工厂的某台机