运筹学第11章图与网络模型ppt课件.ppt

1,第十一章图与网络模型,1图与网络的基本概念2最短路问题3最小生成树问题4最大流问题5最小费用最大流问题,2,1图与网络的基本概念,图论中图是由点和边构成，可以反映一些对象之间的关系。 例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图11-1就是一个表示这种关系的图。,3,1图与网络的基本概念,当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图11-2来表示，可见图论中的图与几何图、工程图是不一样的。,4,1图与网络的基本概念,如果我们把上面例子中的“相互认识”关系改为“认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。,5,1图与网络的基本概念,无向图： 由点和边构成的图，记作G=（V，E）。有向图： 由点和弧构成的图，记作D=（V，A）。连通图： 对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。回路： 若路的第一个点和最后一个点相同，则该路为回路。赋权图： 对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络： 在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。,6,2最短路问题,最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题,求最短路有两种算法： 一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法 另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。,最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路,6.2.1最短路问题的网络模型,7,2最短路问题,最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。一、求解最短路的Dijkstra算法(双标号法）步骤：1.给出点V1以标号(0,s)2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合3. 如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则 vs到vt的距离为lt，而从 vs到vt的最短路径，则可以从kt 反向追踪到起点vs 而得到。如果vt 未标号，则可以断言不存在从 vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。4. 对上述弧的集合中的每一条弧，计算 sij=li+cij 。在所有的 sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。,8,2最短路问题,例1 求下图中v1到v6的最短路解：采用Dijkstra算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下：,9,2最短路问题,6,10,12,3,2,14,6,7,5,8,11,16,5,图66,9,0,0,6,10,12,9,20,9,2,18,6,1,16,12,1,17,16,3,24,32,18,3,29,29,5,【例】用Dijkstra算法求图66 所示v1到v7的最短路及最短路长,v1 到v7的最短路为：p17=v1, v2, v3, v5, v7，最短路长为L17=29,14,10,【例】求图6-10所示v1到各点的最短路及最短距离,0,0,4,5,2,2,1,3,10,3,4,9,6,12,6,4,1,11,6,3,6,3,18,8,12,24,8,5,24,18,5,所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。,图6-10,2最短路问题,11,2最短路问题,例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。 解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。,12,2最短路问题,例2最终解得：最短路径v1 v3 v5 v6 v7，每点的标号见下图,（0,s） V1 （甲地）,15,17,6,2,4,4,3,10,6,5,(13,3) v2,(22,6)V7 （乙地）,V5(14,3),V6(16,5),V3(10,1),V4(18,5),13,2最短路问题,例3 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。 已知：设备每年年初的价格表 设备维修费如下表,14,2最短路问题,例3的解： 将问题转化为最短路问题，如下图： 用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。把所有弧的权数计算如下表：,15,2最短路问题,(继上页) 把权数赋到图中，再用Dijkstra算法求最短路。 最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1 v3 v6和 v1 v4 v6,16,2最短路问题,6.2.4 最短路应用举例,【例】设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知4年年初购置新设备的价格分别为2.5、2.6、2.8和3.1万元。设备使用了14年后设备的残值分别为2、1.6、1.3和1.1万元，使用时间在14年内的维修保养费用分别为0.3、0.8、1.5和2.0万元。试确定一个设备更新策略，在下例两种情形下使4年的设备购置和维护总费用最小。（1）第4年年末设备一定处理掉；（2）第4年年末设备不处理。,【解】画网络图。用点(1,i,j)表示第1年年初购置设备使用到第i年年初更新，经过若干次更新使用到第j年年初，第1年年初和第5年年初分别用及表示。使用过程用弧连接起来，弧上的权表示总费用(购置费维护费残值)，如图616所示,17,2最短路问题,6,图616,(1,2,3),(1,4),(1,3,4),(1,2,4),(1,2,3,4),(1,2),(1,3),第一年,第二年,第三年,第四年,5.1,0.9,1.5,0.7,3.6,2.8,1.7,-0.2,1.9,1.1,2.1,0.3,-0.6,-0.6,网络图616说明：如图中点(1,3)表示第1年购置设备使用两年到第3年年初更新购置新设备，这时有2种更新方案，使用1年到第4年年初、使用2年到第5年年初,更新方案用弧表示，点（1,2,3）表示第1年购置设备使用一年到第二年年初又更新，使用一年到第三年初再更新，这时仍然有2种更新方案，使用1年到第4年年初和使用2年到第5年年初。,18,2最短路问题,点（1,3）和点（1,2,3）不能合并成一个点，虽然都是第三年年初购置新设备，购置费用相同，但残值不同。点(1,3)的残值等于1.6(使用了两年)，点(1,2,3)的残值等于2(使用了一年)。点（1,3）到点（1,3,4）的总费用为第三年的购置费第一年的维护费设备使用两年后的残值2.8+0.31.6=1.5点（1,3）到点的总费用为第三年的购置费第一年的维护费第二年的维护费设备使用两年后的残值第四年末的残值2.8+0.3+0.81.61.6=0.7。,19,2最短路问题,6,图616,(1,2,3),(1,4),(1,3,4),(1,2,4),(1,2,3,4),(1,2),(1,3),第一年,第二年,第三年,第四年,5.1,0.9,1.5,0.7,3.6,2.8,1.7,-0.2,1.9,1.1,2.1,0.3,-0.6,-0.6,（1）第四年末处理设备：求点到点的最短路。用Dijkstra算法得到最短路线为：(1,2)(1,2,3)，最短路长为4。 4年总费用最小的设备更新方案是：第1年购置设备使用1年，第2年更新设备使用1年后卖掉，第3年购置设备使用2年到第4年年末，4年的总费用为4万元。,20,3最小生成树问题,树是图论中的重要概念，所谓树就是一个无圈的连通图。,图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树， (c)因为不连通所以也不是树。,21,可以证明：（1）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。,3最小生成树问题,22,3最小生成树问题,给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图11-12中，(b)和(c)都是(a)的生成子图。 如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在图11-12中，(c)就是(a)的生成树。 最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。,(a),(b),(c),23,3最小生成树问题,一、求解最小生成树的破圈算法算法的步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。,24,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图61,【例】用破圈法求图61的最小树。,图64,图64就是图61的最小部分树，最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同,3最小生成树问题,25,3最小生成树问题,例4 用破圈算法求图（a）中的一个最小生成树,图11-13,26,加边法：取图G的n个孤立点v1，v2， vn作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）,v1,v2,v3,v4,v5,v6,图65,在图65中，如果添加边v1, v2就形成圈v1, v2, v4，这时就应避开添加边v1, v2，添加下一条最短边v3, v6。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等,Min C(T)=15,3最小生成树问题,27,3最小生成树问题,例5、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。,解：此问题实际上是求图11-14的最小生成树，这在例4中已经求得，也即按照图11-13的(f)设计，可使此网络的总的线路长度为最短，为19百米。 “管理运筹学软件”有专门的子程序可以解决最小生成树问题。,28,4最大流问题,6.3.1 基本概念,8,14,5,6,3,3,8,10,7,6,3,图618,4,图618所示的网络图中定义了一个发点v1，称为源(source，supply node），定义了一个收点v7，称为汇（sink，demand node），其余点v2，v3，v6为中间点，称为转运点(transshipment nodes)。如果有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的容量(capacity)。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。,29,4最大流问题,设cij为弧（i，j）的容量，fij为弧（i，j）的流量。容量是弧（i，j）单位时间内的最大通过能力，流量是弧（i，j）单位时间内的实际通过量，流量的集合f=fij称为网络的流。发点到收点的总流量记为v=val(f)，v也是网络的流量。,图618最大流问题的线性规划数学模型为,30,4最大流问题,满足下例3个条件的流fij 的集合 f = fij 称为可行流,发点vs流出的总流量等于流入收点vt的总流量,31,4最大流问题,链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。,前向弧：与链的方向相同的弧称为前向弧。,后向弧：与链的方向相反的弧称为后向弧。,增广链: 设 f 是一个可行流，如果存在一条从vs到vt的链，满足：,1.所有前向弧上fijCij,2.所有后向弧上fij0,则该链称为增广链,容量,流量,32,4最大流问题,步骤如下：,第二步：对点进行标号找一条增广链。（1）发点标号（）（2）选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查： A如果弧的方向向前（前向弧）并且有fij0，则vj标号: jfji当收点已得到标号时，说明已找到增广链，依据vi 的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。,第一步： 找出第一个可行流，例如所有弧的流量fij =0,6.3.2 Ford-Fulkerson标号算法,33,4最大流问题,第三步：调整流量（1）求增广链上点vi 的标号的最小值，得到调整量,（2）调整流量,得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止,【定理6.1】 可行流f是最大流的充分必要条件是不存在发点到收点的增广链,34,4最大流问题,8,14,5,6,3,3,8,10,7,6,3,图619,(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),【例】求图618发点v1到收点v7的最大流及最大流量,【解】给定初始可行流，见图6-19,35,4最大流问题,8,14,5,6,3,3,8,10,7,6,3,图620(b),(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),2,3,3,7,第一轮标号：,c12f12,v2标号2,增广链(1,2)，(3,2)，(3,4)，(4,7) ,+=(1,2)，(3,4)，(4,7),=(3，2)，调整量为增广链上点标号的最小值min，2，3，3，72,36,4最大流问题,8,14,5,6,3,3,8,10,7,6,3,图621,(10),(8),(1),(6),(3),(7),(2),(6),(1),4,(5),(1),(7),调整后的可行流：,37,4最大流问题,8,14,5,6,3,3,8,10,7,6,3,图622,(10),(8),(1),(6),(3),(7),(2),(6),(1),4,(5),(1),(7),4,4,1,5,第二轮标号：,增广链(1,3)，(3,4)，(4,7) ，调整量为 min，4，1，51,38,4最大流问题,8,14,5,6,3,3,8,10,7,6,3,图623,(11),(8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),调整后得到可行流：,39,4最大流问题,8,14,5,6,3,3,8,10,7,6,3,图622,(11),(8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),3,1,4,第三轮标号：,增广链(1,3)，(3,6)，(6,4)，(4,7) ，调整量为 min，3，1，2，41,2,40,4最大流问题,8,14,5,6,3,3,8,10,7,6,3,图625,(12),(8),(1),(6),(3),(8),(3),(6),(2),4,(7),(1),(7),调整后得到可行流：,41,4最大流问题,8,14,5,6,3,3,8,10,7,6,3,图622,(12),(8),(1),(6),(3),(8),(3),(6),(2),4,(7),(1),(7),2,第四轮标号：,v7得不到标号，不存在v1到 v7的增广链，图6-22所示的可行流是最大流，最大流量为 vf12+f138+12=20,4,42,4最大流问题,无向图最大流标号算法,无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已标号另一端vj未标号的边只要满足 Cijfij0 则vj就可标号（Cijfij）,【例】求下图v1到则v7标的最大流,7,(10),(6),(10),(8),(2),(3),(7),(6),(5),(13),(0),(13),2,3,9,9,3,43,4最大流问题,3,7,7,1,V=29,10,5,6,6,1,44,4最大流问题,截集 将图G（V，E）的点集分割成两部分,称为一个截集，截集中所有弧的容量之和称为截集的截量。,下图所示的截集为,45,4最大流问题,又如下图所示的截集为,上图所示的截集为,所有截量中此截量最小且等于最大流量，此截集称为最小截集。,【定理】最大流量等于最小截集的截量。,46,4最大流问题,最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。一、最大流的数学模型 例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？,v5,47,4最大流问题,我们可以为此例题建立线性规划数学模型： 设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：,48,4最大流问题,在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0fij cij。我们把满足守恒条件及流量可行条件的一组网络流 fij称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。 我们把例6的数据代入以上线性规划模型，用“管理运筹学软件”，马上得到以下的结果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最优值（最大流量）=10。,49,4最大流问题,二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图: (a)和(b)、(c)和(d)的意义相同。 用以上方法对例6的图的容量标号作改进，得下图,vi,vj,vi,vj,cij,0,（a）,（b）,cij,cij,vi,vj,（cji）,（c）,vi,vj,cij,cji,（d）,50,4最大流问题,求最大流的基本算法（1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。（3）在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的逆流容量pf，返回步骤（1）。 用此方法对例6求解： 第一次迭代：选择路为v1 v4 v7 。弧（ v4 , v7 ）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：,51,4最大流问题,第二次迭代：选择路为v1 v2 v5 v7 。弧（ v2 , v5 ）的顺流容量为3，决定了pf=3，改进的网络流量图如下图： 第三次迭代：选择路为v1 v4 v6 v7 。弧（ v4 , v6 ）的顺流容量为1，决定了pf=1，改进的网络流量图如下图：,52,第四次迭代：选择路为v1 v4 v3 v6 v7 。弧（ v3 , v6 ）的顺流容量为2，决定了pf=2，改进的网络流量图如下图： 第五次迭代：选择路为v1 v2 v3 v5 v7 。弧（ v2 , v3 ）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：,4最大流问题,53,经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。 最大流量图如下图：,4最大流问题,“管理运筹学软件”中还有专门的子程序用于解决最大流问题。,54,4最大流问题,最大流应用举例,【例6.12】某公司需要招聘5个专业的毕业生各一个，通过本人报名和筛选，公司最后认为有6人都达到录取条件。这6人所学专业见表6-10,表中打“”表示该生所学专业。公司应招聘哪几位毕业生，如何分配他们的工作,表6-10,55,4最大流问题,A,B,C,D,E,s,t,(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),图632,【解】画出一个图，虚设一个发点和一收点，每条弧上的容量等于1，问题为求发点到收点的最大流，求解结果之一见图632。公司录取第26号毕业生，安排的工作依次为管理信息、企业管理、市场营销、工程管理和计算机。,56,4最大流问题,【例】某市政工程公司在未来58月份内需完成4项工程：A.修建一条地下通道、B.修建一座人行天桥、C.新建一条道路及D.道路维修。工期和所需劳动力见表6-11。该公司共有劳动力120人，任一项工程在一个月内的劳动力投入不能超过80人，问公司如何分配劳动力完成所有工程，是否能按期完成,表6-12,【解】将工程计划用网络图633表示。设点v5、v6、v7、v8分别表示58月份，Ai、Bi 、Ci 、Di表示工程在第i个月内完成的部分，用弧表示某月完成某项工程的状态，弧的容量为劳动力限制。就是求图633从发点到收点的最大流问题。,57,4最大流问题,A5,B6,C7,D8,s,t,图633,A6,C5,A7,C6,B7,C8,A,B,C,D,120,120,120,120,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,100,80,200,80,(100),(120),(120),(120),(20),(80),(40),(80),(0),(40),(80),(0),(40),(80),(20),(80),(80),(40),(80),(80),(40),(0),(40),(80),(100),(80),(200),(80),58,4最大流问题,标号算法求解得到图633，括号内的数字为弧的流量。每个月的劳动力分配见表6-13。5月份有剩余劳动力20人，4项工程恰好按期完成,表6-13,59,5最小费用最大流问题,最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi,vj），除了给出容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总运送费用最小。一、最小费用最大流的数学模型 例7 由于输油管道的长短不一，所以在例6中每段管道（ vi,vj ）除了有不同的流量限制cij外，还有不同的单位流量的费用bij ，cij的单位为万加仑/小时， bij的单位为百元/万加仑。如图。从采地 v1向销地 v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。,(6,6),(3,4),(5,7),(2,5),(2,4),（2,3）,(4,4),(1,3),(2,8),（3,2）,v1,v2,v5,v7,v4,v3,v6,(6,3),60,5最小费用最大流问题,这个最小费用最大流问题也是一个线性规划的问题。 解：我们用线性规划来求解此题，可以分两步走。 第一步，先求出此网络图中的最大流量F，这已在例6中建立了线性规划的模型，通过管理运筹学软件已经获得结果。 第二步，在最大流量F的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下： 仍然设弧（vi,vj）上的流量为fij，这时已知网络中最大流量为F，只要在例6的约束条件上，再加上总流量必须等于F的约束条件：f12=f14=F,即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用 。 由此得到线性规划模型如下：,61,5最小费用最大流问题,62,5最小费用最大流问题,用管理运筹学软件，可求得如下结果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最优值(最小费用)=145。对照前面例6的结果，可对最小费用最大流的概念有一个深刻的理解。 如果我们把例7的问题改为：每小时运送6万加仑的石油从采地v1到销地v7最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij的网络中，求一个给定值f的流量的最小费用，这个给定值f的流量应小于等于最大流量F，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可。在例6中只要把f12+f14=F改为f12+f14=f=6得到了最小费用流的线性规划的模型了。,63,5最小费用最大流问题,二、最小费用最大流的网络图解法对网络上弧（vi,vj）的（cij,bij）的表示作如下改动，用(b)来表示(a)。用上述方法对例7中的图形进行改进，得图如下页：,vi,vj,vi,vj,（cij,bij ）,（0,-bij ）,（a）,（b）,（cij,bij ）,（cij,bij ）,vi,vj,（cji,bji ）,（cij,bij ）,vi,vj,（cji,bji ）,（0,-bji),（0,-bji),（c）,（d）,64,5最小费用最大流问题,求最小费用最大流的基本算法 在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样，不同的只是在步骤（1）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。,65,5最小费用最大流问题,用上述方法对例7求解： 第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后总流量为1，总费用10。,v5,66,5最小费用最大流问题,第二次迭代：找到最短路v1 v4 v7。第二次迭代后总流量为3，总费用32。,67,5最小费用最大流问题,第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后总流量为5，总费用56。,68,5最小费用最大流问题,第四次迭代：找到最短路v1 v4 v3 v5 v7 。第四次迭代后总流量为6，总费用72。,69,5最小费用最大流问题,第五次迭代：找到最短路v1 v2 v5 v7 。第五次迭代后总流量为9，总费用123。,70,5最小费用最大流问题,第六次迭代：找到最短路v1 v2 v3 v5 v7 。第六次迭代后总流量为10，总费用145。已经找不到从v1到v7的每条弧容量都大于零的路了，故已求得最小费用最大流了。,71,5最小费用最大流问题,如果对例7求一个最小费用流的问题：每小时运送6万加仑石油从v1到v7的最小费用是多少，或者每小时运送7万加仑呢？我们可以从第四次迭代及图11-32即可得到运送6万加仑最小费用72百元，其运送方式通过比较图11-28及图11-32即得图11-36所示。 至于每小时运送7万加仑，我们可以在图11-36的基础上，再按第五次迭代所选的最短路运送1万加仑即得最小费用：72+1*17=89百元，其运送方式如图11-37所示。,72,5最小费用最大流问题,注：“管理运筹学软件”有专门的子程序用于解决这类问题。,