运筹学网络最优化问题.pptx

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