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

《运筹学课件-最短路、最大流、邮路.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、7.3最短路问题问题在一个网络中，给定一个始点Vs，和一个终点Vt，求Vs到Vt的一条路，使路长最短。求解能划分阶段的，可采用动态规划方法。不能分阶段的，采用狄克斯屈方法。通过一个网络的最短路径143265720151068241082011**如果P是D中从Vs到Vt的最短路，Vi是P中的一个点，那么，从Vs沿P到Vi的路是从Vs到Vi的最短路。通过一个网络的最短路径狄克斯屈（Dijstra）方法（ωij≥0）开始节点标永久标记[0,P],其余为临时标记[T,-]找出与开始节点相邻的所有节点，为每一个

2、设标记[L,1]，其中L值最小的节点标记右上角标上*，使之成为永久标志。L为两节点间距离，1表示始于第一节点从新的永久标志开始，找出从此节点出发可到达的所有节点，计算这些节点的最短距离（现有距离和经新的永久标志到达的距离的小的一个值），保持、新设或更改这些节点的标志为[最短距离，最短路径上前一节点标号]，比较图中所有没有*的标记（临时性标记），找出距离最短的一个节点，使之成为永久性标记。重复这一步，直到所有的节点都成为永久性标志为止。通过一个网络的最短路径kij[Di,m]Lij[Dj,k]从i-j时：

3、如果Di+Lij≥Dj,则不改变j的标记；如果Di+Lij

4、6－7最短路径问题的应用例：设备更新问题某厂使用一种设备，每年年初设备科需要对该设备的更新与否作出决策。若购置新设备，就要支付购置费；如果继续使用则需要支付维修费，设备使用的年数越长，每年所需的维修费越多。现若第一年年初购置了一台新设备，问在5年内如何制定设备更新计划，以便使新设备购置费和维修费的总费用最小？已知设备在5年内各年年初的价格及设备使用不同年数的维修费如下：最短路径问题的应用例设备更新问题把求总费用最小问题化为最短路径问题。用点i(i=1,2,3,4,5)表示第i年买进一台新设备。增设一点6

5、表示第五年末。从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、-6即：第1、3年年初购买设备，或第1、4年年初购买设备五年最佳总费用为53。132546162217182330594117301623413122作业题：某地7个村镇之间现有交通距离如图求：1)从村1到其余各村的最短距离？2)如要沿路架设电话线，如何使总长度最小同时又使每个村都能安装上电话？16345271211101512102516171526724最大流问题最大流问题（有向图或网络）在一定条件下，使网络系统中从开始点到结束点之间的某种物资流（交通流、信息流、资金流、水流等）的流量达到最大的问题

7、。限制条件是每一条边的最大通过能力（流量）不等。但有多条路。最大流量求解线性规划方法标号法最大流问题网络与流：网络：给一个有向图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也可以描述成“加

8、在网络各条弧上的一组负载量(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)最大流问题饱和弧：若给一个可