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

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+Lij<Dj，则改为[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(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具体权数计算结果如下：通过一个网络的最短路径例设备更新问题：使用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≤f<c，在弧（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+F25;4点：F14=F43+F46+F473点：F23+F43=F35+F36;5点：F25+F35＝F576点：F36+F46＝F67;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最大流量F＝10342657623212564321思考题：最小费用最大流如果弧（i,j）上的单位流量费用为Bij(百元/万升）。图中每一条弧的权数前一位为流量限制Cij，后一位为单位费Bij。怎样运送才能使运送最多的石油并使总的费用最小？提示：先求得最大F值；再求总流量为F时使总费用最小的方案。进一步思考：求最小费用问题。如何求每小时运送6万升原油的最小费用？3426576,32,53,22,31,32,85,76,64,43,42,41给定一个连通图，在每边上赋予一个非负的权，要求一个圈，过每边至少一次，并使圈的总权最小。欧拉链：给定一个连通多重图G，若存在一条链，过每边一次，且仅一次，称这个圈为欧拉圈。一个图若有欧拉圈，则称为欧拉图。7.6中国邮递员问题中国邮递员问题定理：连通多重图G有欧拉圈，当且仅当G中无奇点。