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

7.3最短路问题问题在一个网络中，给定一个始点Vs，和一个终点Vt，求Vs到Vt的一条路，使路长最短。求解能划分阶段的，可采用动态规划方法。不能分阶段的，采用狄克斯屈方法。通过一个网络的最短路径143265720151068241082011**如果P是D中从Vs到Vt的最短路，Vi是P中的一个点，那么，从Vs沿P到Vi的路是从Vs到Vi的最短路。通过一个网络的最短路径狄克斯屈（Dijstra）方法（ωij≥0）开始节点标永久标记[0,P],其余为临时标记[T,-]找出与开始节点相邻的所有节点，为每一个设标记[L,1]，其中L值最小的节点标记右上角标上*，使之成为永久标志。L为两节点间距离，1表示始于第一节点从新的永久标志开始，找出从此节点出发可到达的所有节点，计算这些节点的最短距离（现有距离和经新的永久标志到达的距离的小的一个值），保持、新设或更改这些节点的标志为[最短距离，最短路径上前一节点标号]，比较图中所有没有*的标记（临时性标记），找出距离最短的一个节点，使之成为永久性标记。重复这一步，直到所有的节点都成为永久性标志为止。通过一个网络的最短路径kij[Di,m]Lij[Dj,k]从i-j时：如果Di+Lij≥Dj,则不改变j的标记；如果Di+LijDj，则改为[Di+Lij,i]通过一个网络的最短路径例5－5狄克斯屈方法：[35,4]143265720151068241082011[0,P][21,3][25,3][44,2][T,-][T,-][T,-][T,-][T,-][T,-][20,1][15,1][41,6]******通过一个网络的最短路径从起始点到每一点的最短距离为：节点最短距离路径2201－23151－34251－3－45351－3－4－56211－3－67411－3－6－7最短路径问题的应用例：设备更新问题某厂使用一种设备，每年年初设备科需要对该设备的更新与否作出决策。若购置新设备，就要支付购置费；如果继续使用则需要支付维修费，设备使用的年数越长，每年所需的维修费越多。现若第一年年初购置了一台新设备，问在5年内如何制定设备更新计划，以便使新设备购置费和维修费的总费用最小？已知设备在5年内各年年初的价格及设备使用不同年数的维修费如下：第i年12345价格ai1111121213使用寿命0－11－22－33－44－5b1b2b3b4b5费用bi5681118最短路径问题的应用例设备更新问题把求总费用最小问题化为最短路径问题。用点i(i=1,2,3,4,5)表示第i年买进一台新设备。增设一点6表示第五年末。从i点到i+1,……,6各画一条弧，弧（i,j）表示在第i年买进的设备一直使用到第j年年初（第j－1年年末）。求1点到6点的最短路径。路径的权数为购买和维修费用。弧（i,j）的权数为第i年的购置费ai＋从第i年使用至第j-1年末的维修费之和。从第i年使用至第j-1年末的维修费：b1+…+bj-i（使用寿命为j-i年）如：（2－4）权数为：a2+b1+b2=11＋5＋6=22具体权数计算结果如下：12345611622304159216223041317233141723518通过一个网络的最短路径例设备更新问题：使用Dijstra算法，上述问题最短路为1-3-6或1-4-6即：第1、3年年初购买设备，或第1、4年年初购买设备五年最佳总费用为53。132546162217182330594117301623413122作业题：某地7个村镇之间现有交通距离如图求：1)从村1到其余各村的最短距离？2)如要沿路架设电话线，如何使总长度最小同时又使每个村都能安装上电话？16345271211101512102516171526724最大流问题最大流问题（有向图或网络）在一定条件下，使网络系统中从开始点到结束点之间的某种物资流（交通流、信息流、资金流、水流等）的流量达到最大的问题。限制条件是每一条边的最大通过能力（流量）不等。但有多条路。最大流量求解线性规划方法标号法最大流问题网络与流：网络：给一个有向图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，0≤fij≤cij2）平衡条件，即对于中间点，流出量=流入量。可行流的流量：即发点的净输出量或收点的净输入量。最大流问题就是求一个流，使其流量达到最大。且满足：0≤fij≤cij,(vi,vj∈A),∑Fij-∑Fji=V(f)(i=s);0(i≠s,t);-v(f)(i=t)最大流问题饱和弧：若给一个可行流f=﹛fij﹜，把网络中使fij=cij的弧称为饱和弧，fij＜cij的弧称为非饱和弧。零流弧（fij=0）；非零流弧（fij＞0）设网络中有一从vs到vt到的一条链μ，则与链的方向一致的弧称为前向弧，（前向弧的全体记μ+），与链的方向相反的弧称为后向弧。（后向弧的全体记μ-）增广链：设f是一个可行流，μ是从vs到vt的一条链，若μ满足下列条件，则称之为增广链：在弧（vi，vj)∈μ+，0≤fc，在弧（vi，vj)∈μ-，0＜f≤c。截集：对网络D=（V，A，C），若点集V被剖分为两个非空集合V1和V1，使vs∈V1，vt∈V1，则把弧集（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)上，fij＜cij则给vi标号（vi，l(vi)。这里l(vi)==min[cij-fij，l(vi)]（2）若在弧（vj，vi)上，fij＞0,则给vi标号（-vi，l(vi)。这里l(vi)==min[fij，l(vi)]重复上述步骤，一旦vt被标上号，表明得到一条从vs到vt的增广链，转入调整过程。最大流问题2、调整过程：按vt及其它点的第一个标号，反向追踪找出增广链，并找出θ=min﹛cij-fij(对μ+）;fij（对μ-）﹜再令f’=﹛fij+θ(对μ+）;fij-θ（对μ-）；fij（对非增广链上的弧）﹜去掉所有的标号，对新的可行流f’重新进入标号过程。最大流问题例：用标号法求下面网络的最大可行流vsvtv2v1v4v3(3,3)(4,3)(2,2)(5,1)(1,1)(3,0)(5,3)(2,1)最大流问题例：用标号法求下面网络的最大可行流vsvtv2v1v4v3(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)最大流问题v1v2按照标号找到一条增广链：由上可知：θ=1沿增广链对可行流进行调整。vsv3vt4111最大流问题例：用标号法求下面网络的最大可行流vsvtv2v1v4v3(3,3)(4,3)(2,2)(5,2)(1,0)(3,0)(5,3)(2,2)(1,0)7.5最小费用最大流问题设一个单位流量的费用为bij，bij≥0。最小费用最大流问题即求一个最大流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’是最大流时，它也就是所求的最小费用最大流了。最小费用最大流问题由于bij≥0，所以f=0必是流量为0的最小费用流，余下的问题就是如何去寻求关于f的最小费用增广链。为此，可构造一个赋权有向图W（f），它的顶点是原网络D的顶点，而把D中的每一条弧（vi，vj）变成两个相反方向的弧（vi，vj）和（vj，vi）。定义W（f）中弧的权wij为：bij（fij＜cij）；+∞（fij=cij）wji为：-bij（fij＞0）；+∞（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)进行调整。最小费用最大流问题调整量为：θ=min﹛min[cij-fij(k-1)]（对μ+）；minfij(k-1)（对μ-）﹜令fij(k)=fij(k-1)+θ（对μ+）；fij(k-1)-θ（对μ-）；fij(k-1)（对非增广链上的弧）得到新的可行流f(k)，再对f(k)重复上述步骤。最小费用最大流问题例：求下面网络的最小费用最大流。弧旁数字为（bij，cij）。vsv2v1v3vt(4,10)(1,8)(3,10)(1,7)(2,4)(6,2)(2,5)最小费用最大流问题（1）取f(0)=0为初始可行流。（2）构造赋权有向图W（f(0)），并求出vs到vt的最短路。（3）确定与最短路相应的增广链。（4）对增广链进行调整，得到新的可行流，再构造新的赋权有向图。直到找到最小费用最大流。最小费用最大流问题W（f(0)），最短路及增广链，θ=5vsv2v1v3vt4131262最小费用最大流问题（f(1)），V（f(1)）=5v3vsv2v1vt0505005最小费用最大流问题W（f(1)），最短路及增广链，θ=2vsv2v1v3vt41312-26-1-1最小费用最大流问题（f(2），V（f(2)）=7v3vsv2v1vt2507005最小费用最大流问题vsv2v1v3vt413-126-2-1-4W(f(2))，最短路及增广链，θ=3最小费用最大流问题（f(3），V（f(3)）=10v3vsv2v1vt2837305最小费用最大流问题W（f(3)），最短路及增广链，θ=1vsv2v1v3vt4-13-12-6-2-4-3-2最小费用最大流问题（f(4），V（f(4)）=11v3vsv2v1vt3847404最小费用最大流问题W（f(4)）vsv2v1v3vt41-3-1-2623-2-4最大流量的线性规划模型例：有下列石油运输管道图。某公司欲采用这个网络图从1地向销地7运送原油，弧的容量Cij（万升/时）已给定（因管道直径的变化，Cij不完全相同）。问如何安排输送，方能使每小时运送的原油最多？163452762321256432最大流量的线性规划模型设弧（i,j）上的流量为Fij,总流量为F.目标函数：MAXF=F12+F14约束条件：流入＝流出;Fij≤Cij;Fij≥02点：F12=F23