运筹学课件-最短路、最大流、邮路

7.3最短路问题,问题在一个网络中，给定一个始点Vs，和一个终点Vt，求Vs到Vt的一条路，使路长最短。求解能划分阶段的，可采用动态规划方法。不能分阶段的，采用狄克斯屈方法。,通过一个网络的最短路径,1,4,3,2,6,5,7,20,15,10,6,8,24,10,8,20,11,*,*,如果P是D中从Vs到Vt的最短路，Vi是P中的一个点，那么，从Vs沿P到Vi的路是从Vs到Vi的最短路。,通过一个网络的最短路径,狄克斯屈（Dijstra）方法（ij0）开始节点标永久标记0,P,其余为临时标记T,-找出与开始节点相邻的所有节点，为每一个设标记L,1，其中L值最小的节点标记右上角标上*，使之成为永久标志。L为两节点间距离，1表示始于第一节点从新的永久标志开始，找出从此节点出发可到达的所有节点，计算这些节点的最短距离（现有距离和经新的永久标志到达的距离的小的一个值），保持、新设或更改这些节点的标志为最短距离，最短路径上前一节点标号，比较图中所有没有*的标记（临时性标记），找出距离最短的一个节点，使之成为永久性标记。重复这一步，直到所有的节点都成为永久性标志为止。,通过一个网络的最短路径,k,i,j,Di,m,Lij,Dj,k,从i-j时：如果Di+LijDj,则不改变j的标记；如果Di+LijDj，则改为Di+Lij,i,通过一个网络的最短路径,例55狄克斯屈方法：,35,4,1,4,3,2,6,5,7,20,15,10,6,8,24,10,8,20,11,0,P,21,3,25,3,44,2,T,-,T,-,T,-,T,-,T,-,T,-,20,1,15,1,41,6,*,*,*,*,*,*,通过一个网络的最短路径,从起始点到每一点的最短距离为：节点最短距离路径220123151342513453513456211367411367,最短路径问题的应用,例：设备更新问题某厂使用一种设备，每年年初设备科需要对该设备的更新与否作出决策。若购置新设备，就要支付购置费；如果继续使用则需要支付维修费，设备使用的年数越长，每年所需的维修费越多。现若第一年年初购置了一台新设备，问在5年内如何制定设备更新计划，以便使新设备购置费和维修费的总费用最小？已知设备在5年内各年年初的价格及设备使用不同年数的维修费如下：,最短路径问题的应用,例设备更新问题把求总费用最小问题化为最短路径问题。用点i(i=1,2,3,4,5)表示第i年买进一台新设备。增设一点6表示第五年末。从i点到i+1,6各画一条弧，弧（i,j）表示在第i年买进的设备一直使用到第j年年初（第j1年年末）。求1点到6点的最短路径。路径的权数为购买和维修费用。弧（i,j）的权数为第i年的购置费ai从第i年使用至第j-1年末的维修费之和。从第i年使用至第j-1年末的维修费：b1+bj-i（使用寿命为j-i年）如：（24）权数为：a2+b1+b2=1156=22具体权数计算结果如下：,通过一个网络的最短路径,例设备更新问题：使用Dijstra算法，上述问题最短路为1-3-6或1-4-6即：第1、3年年初购买设备，或第1、4年年初购买设备五年最佳总费用为53。,1,3,2,5,4,6,16,22,17,18,23,30,59,41,17,30,16,23,41,31,22,作业题：,某地7个村镇之间现有交通距离如图求：1)从村1到其余各村的最短距离？2)如要沿路架设电话线，如何使总长度最小同时又使每个村都能安装上电话？,1,6,3,4,5,2,7,12,11,10,15,12,10,25,16,17,15,26,7,24,最大流问题,最大流问题（有向图或网络）在一定条件下，使网络系统中从开始点到结束点之间的某种物资流（交通流、信息流、资金流、水流等）的流量达到最大的问题。限制条件是每一条边的最大通过能力（流量）不等。但有多条路。最大流量求解线性规划方法标号法,最大流问题,网络与流：网络：给一个有向图D=（V，A），在V中指定一点称为发点（记为vs)，而另一点称为收点（记为vt），其余点叫中间点，对应每一个弧（vi，vj）A，对应有一个C（vi，vj）0（或简写为cij），称为弧的容量。通常我们就把D叫做一个网络。记作D=（V，A，C）。流：定义在弧集合A上的一个函数f=f（vi，vj），并称f（vi，vj）为弧（vi，vj）上的流量，可简写为fij也可以描述成“加在网络各条弧上的一组负载量(fij)”,最大流问题,可行流可行流：满足下述条件的流f称为可行流：1）容量限制条件：对每一条（vi，vj)A，0fijcij2）平衡条件，即对于中间点，流出量=流入量。可行流的流量：即发点的净输出量或收点的净输入量。最大流问题就是求一个流，使其流量达到最大。且满足：0fijcij,(vi,vjA),Fij-Fji=V(f)(i=s);0(is,t);-v(f)(i=t),最大流问题,饱和弧：若给一个可行流f=fij，把网络中使fij=cij的弧称为饱和弧，fijcij的弧称为非饱和弧。零流弧（fij=0）；非零流弧（fij0）设网络中有一从vs到vt到的一条链，则与链的方向一致的弧称为前向弧，（前向弧的全体记+），与链的方向相反的弧称为后向弧。（后向弧的全体记-）,增广链：设f是一个可行流，是从vs到vt的一条链，若满足下列条件，则称之为增广链：在弧（vi，vj)+，0fc，在弧（vi，vj)-，0fc。截集：对网络D=（V，A，C），若点集V被剖分为两个非空集合V1和V1，使vsV1，vtV1，则把弧集（V1，V1）称为截集。截量：把截集中所有弧的容量之和称为这个截集的容量。,最大流问题,最大流问题,两个重要结论：1、任何一个可行流的流量都不会超过任一截集的容量。2、若对于一个可行流f*，网络中有一个截集（V1*，V1*），使v（f*）=C(V1*，V1*)，则f*必是最大流，而（V1*，V1*）必是所有截集中容量最小的一个，即最小截集。定理：可行流f*是最大流，当且仅当不存在关于f*的增广链。于是有如下结论：最大流量最小截量定理：任一个网络中，从vs到vt的最大流量等于分离vs，vt的最小截集的容量。,最大流问题,寻求最大流的标号法：1、标号：从vs开始，给vs标上（0，），一般地取一个标号点vi，对一切标号点vj：（1）若在弧（vi，vj)上，fijcij则给vi标号（vi，l(vi)。这里l(vi)=mincij-fij，l(vi)（2）若在弧（vj，vi)上，fij0,则给vi标号（-vi，l(vi)。这里l(vi)=minfij，l(vi)重复上述步骤，一旦vt被标上号，表明得到一条从vs到vt的增广链，转入调整过程。,最大流问题,2、调整过程：按vt及其它点的第一个标号，反向追踪找出增广链，并找出=mincij-fij(对+）;fij（对-）再令f=fij+(对+）;fij-（对-）；fij（对非增广链上的弧）去掉所有的标号，对新的可行流f重新进入标号过程。,最大流问题例：用标号法求下面网络的最大可行流,vs,vt,v2,v1,v4,v3,(3,3),(4,3),(2,2),(5,1),(1,1),(3,0),(5,3),(2,1),最大流问题例：用标号法求下面网络的最大可行流,vs,vt,v2,v1,v4,v3,(3,3),(4,3),(2,2),(5,1),(1,1),(3,0),(5,3),(2,1),（0，）,(Vs,4),(1,1),(-v1,1),(V2,1),(-v2,1),(v3,1),最大流问题,v1,v2,按照标号找到一条增广链：由上可知：=1沿增广链对可行流进行调整。,vs,v3,vt,4,1,1,1,最大流问题例：用标号法求下面网络的最大可行流,vs,vt,v2,v1,v4,v3,(3,3),(4,3),(2,2),(5,2),(1,0),(3,0),(5,3),(2,2),(1,0),7.5最小费用最大流问题,设一个单位流量的费用为bij，bij0。最小费用最大流问题即求一个最大流f，使流的总输送费用最小。当沿着一条关于可行流f的增广链，以=1调整f，得到新的可行流f，b(f)比b(f)增加值为：b(f)-b(f)=bij（f-f）-bij（f-f）=bij-bij称为这条增广链的“费用”可以证明：若f是所有可行流中费用最小者，而是关于f的所有增广链中费用最小的增广链，那么沿去调整f，得到的可行流f，就是所有可行流中的最小费用流。这样当f是最大流时，它也就是所求的最小费用最大流了。,最小费用最大流问题,由于bij0，所以f=0必是流量为0的最小费用流，余下的问题就是如何去寻求关于f的最小费用增广链。为此，可构造一个赋权有向图W（f），它的顶点是原网络D的顶点，而把D中的每一条弧（vi，vj）变成两个相反方向的弧（vi，vj）和（vj，vi）。定义W（f）中弧的权wij为：bij（fijcij）；+（fij=cij）wji为：-bij（fij0）；+（fij=0）,最小费用最大流问题,于是在网络中寻求关于f的最小费用最大流就等于在赋权有向图中，寻求从vs到vt的最短路。因此有如下算法：开始取f(0)=0,一般情况下，若在第k-1步得到最小费用流f(k-1)，则构造赋权有向图W（f(k-1)），在W（f(k-1)），中，寻求从vs到vt的最短路。若不存在最短路，则f(k-1)就是最小费用最大流；若存在最短路，则在原网络中得到相应的增广链，在增广链上对f(k-1)进行调整。,最小费用最大流问题,调整量为：=minmincij-fij(k-1)（对+）；minfij(k-1)（对-）令fij(k)=fij(k-1)+（对+）；fij(k-1)-（对-）；fij(k-1)（对非增广链上的弧）得到新的可行流f(k)，再对f(k)重复上述步骤。,最小费用最大流问题,例：求下面网络的最小费用最大流。弧旁数字为（bij，cij）。,最小费用最大流问题,（1）取f(0)=0为初始可行流。（2）构造赋权有向图W（f(0)），并求出vs到vt的最短路。（3）确定与最短路相应的增广链。（4）对增广链进行调整，得到新的可行流，再构造新的赋权有向图。直到找到最小费用最大流。,最小费用最大流问题,W（f(0)），最短路及增广链，=5,vs,v2,v1,v3,vt,4,1,3,1,2,6,2,最小费用最大流问题,（f(1)），V（f(1)）=5,最小费用最大流问题,W（f(1)），最短路及增广链，=2,vs,v2,v1,v3,vt,4,1,3,1,2,-2,6,-1,-1,最小费用最大流问题,（f(2），V（f(2)）=7,v3,vs,v2,v1,vt,2,5,0,7,0,0,5,最小费用最大流问题,vs,v2,v1,v3,vt,4,1,3,-1,2,6,-2,-1,-4,W(f(2)，最短路及增广链，=3,最小费用最大流问题,（f(3），V（f(3)）=10,v3,vs,v2,v1,vt,2,8,3,7,3,0,5,最小费用最大流问题,W（f(3)），最短路及增广链，=1,vs,v2,v1,v3,vt,4,-1,3,-1,2,-6,-2,-4,-3,-2,最小费用最大流问题,（f(4），V（f(4)）=11,v3,vs,v2,v1,vt,3,8,4,7,4,0,4,最小费用最大流问题,W（f(4)）,vs,v2,v1,v3,vt,4,1,-3,-1,-2,6,2,3,-2,-4,最大流量的线性规划模型,例：有下列石油运输管道图。某公司欲采用这个网络图从1地向销地7运送原油，弧的容量Cij（万升/时）已给定（因管道直径的变化，Cij不完全相同）。问如何安排输送，方能使每小时运送的原油最多？,最大流量的线性规划模型,设弧（i,j）上的流量为Fij,总流量为F.目标函数：MAXF=F12+F14约束条件：流入流出;FijCij;Fij02点：F12=F23+F25;4点：F14=F43+F46+F473点：F23+F43=F35+F36;5点：F25+F35F576点：F36+F46F67;7点：F47+F57+F67=F12+F14解：F12=5;F14=5;F23=2;F25=3;F43=2;F46=1;F47=2;F35=2F36=2;F57=5;F67=3最大流量F10,3,4,2,6,5,7,6,2,3,2,1,2,5,6,4,3,2,1,思考题：最小费用最大流,如果弧（i,j）上的单位流量费用为Bij(百元/万升）。图中每一条弧的权数前一位为流量限制Cij，后一位为单位费Bij。怎样运送才能使运送最多的石油并使总的费用最小？提示：先求得最大F值；再求总流量为F时使总费用最小的方案。进一步思考：求最小费用问题。如何求每小时运送6万升原油的最小费用？,3,4,2,6,5,7,6,3,2,5,3,2,2,3,1,3,2,8,5,7,6,6,4,4,3,4,2,4,1,给定一个连通图，在每边上赋予一个非负的权，要求一个圈，过每边至少一次，并使圈的总权最小。欧拉链：给定一个连通多重图G，若存在一条链，过每边一次，且仅一次，称这个圈为欧拉圈。一个图若有欧拉圈，则称为欧拉图。,7.6中国邮递员问题,中国邮递员问题,定理：连通多重图G有欧拉圈，当且仅当G中无奇点。推论：连通多重图G有欧拉链，当且仅当G恰有两个奇点。,奇偶点图上作业法,在一个有奇点的途中，要求增加一些重复边，使新图不含奇点，并且重复便的总权为最小。把新图不含奇点而增加的重复边，简称为可行方案，使总权最小的可行方案称为最优方案。问题1：可行方案如何确定？问题2：怎么判断这个方案为最优方案？,奇偶点图上作业