网络优化-第5章-最短路问题课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,网,络,优,化,Network Optimization,http:/ 最短路问题,(Shortest Path Problem),1,网 络 优 化 Network Optimizatio,许多实际问题都可以转化为最短路问题,其有效算法经常在其它网络优化问题中作为子算法调用,S,T,最短路问题,的例子和意义,2,许多实际问题都可以转化为最短路问题 其有效算法经常在其它,例5.1（Single-level Uncapacitated Lotsizing）,某工厂生产某种产品用以满足市场需求,且已知在时段,t,中的市场需求为,d,t,.在某时段,t,如果开工生产,则生产开工所需的生产准备费为,s,t,单件产品的生产费为,c,t,.在某时段,t,期末,如果有产品库存,单件产品的库存费为,h,t,.假设初始库存为0,不考虑能力限制,工厂应如何安排生产,可以保证按时满足生产,且使总费用最小?（Wagner Whitin，1958）,最短路问题的例子-,单产品、无能力限制的批量问题,假设在时段,t,产品的生产量为,x,t,期末产品的库存为,I,t,(,I,0,=0);用二进制变量,y,t,表示在时段,t,工厂是否进行生产准备.,假设费用均非负，则在最优解中 ，即,可以证明：一定存在满足条件 的最优解.,可以只考虑,3,例5.1（Single-level Uncapacitat,单产品、无能力限制的批量问题,记,w,ij,为第,i,时段生产量为 时所导致的费用,(,包括生产准备费、生产费和库存费,),即,其中,网络：从所有节点,i,到,j,(,i,),连一条弧,弧上的权为,w,i,j-,1,如T=4时：,1,2,3,4,5,w,11,w,33,w,22,w,44,w,34,w,23,w,12,w,13,w,24,w,14,4,单产品、无能力限制的批量问题记wij为第i时段生产量为,例5.3 计划评审技术,即PERT(Project Evaluation&Review Technique),又称网络计划技术或统筹法),大型复杂工程项目(Project)往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求,每一子项目需要一定的时间完成.PERT网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路(关键路线).工程上所谓的关键路线法(CPM:Critical Path Method)基本上也是计划评审技术的一部分.,项目网络不含圈,其最长路问题和最短路问题都是可解的.,(开始)A,F(结束),5,6,6,7,4,4,5,1,3,B,E,D,C,5,例5.3 计划评审技术,即PERT(Project Eva,最短路问题,给定有向网络,N,，弧（,i,，,j,）对应的权又称为,弧长,（或,费用,）.,对于其中的两个顶点,s,，,t,，以,s,为起点和,t,为终点的有向路称为,s-t,有向路,，其所经过的所有弧上的权（或弧长、费用）之和称为该有向路的权（或弧长、费用）.,所有,s-t,有向路中权(或弧长、费用)最小的一条称为,s-t,最短路,.,对于有向网络中的一个圈，定义它的权为圈上所有前向弧上的权的和,减去圈上所有反向弧上的权,.,权为正的圈称为,正圈,;,权为负的圈称为,负圈,;,权为,0,的圈称为,零圈,.,对一个有向圈，,它的权就是圈上所有弧上的权的和,.,本章的圈一般都是指有向圈,我们直接将正有向圈简称为“,正圈,”，,负有向圈简称为“,负圈,”，,零有向圈简称为“,零圈,”,而“,无圈,”指的是不存在有向圈,.,s,t,6,最短路问题给定有向网络N，弧（i，j）对应的权又称为弧长（或,无向网络,上的最短路问题一般可以转化为有向网络上的问题,.,如果所有弧上的权全为非负（或非正）数，只需将无向图的一条边代之以两条对称的有向弧即可,.,如果弧上的权有负有正，一般来说问题要复杂得多。,最短路问题 两点说明,最长路问题,可以转化为最短路问题，把弧上的费用反号即可,.,必须指出：目前为止，一切最短路算法都只对不含负有向圈的网络有效,.,对于含负有向圈的网络，最短路问题是,NP,困难的,.,因此，本章中除非特别说明，一律假定网络不包含负有向圈,.,7,无向网络上的最短路问题一般可以转化为有向网络上的问题.最短路,x,ij,表示弧（,i,，,j,）是否位于,s-t,路上：当,x,ij,=1时，表示弧（,i,，,j,）位于,s-t,路上，当,x,ij,=0时，表示弧（,i,，,j,）不在,s-t,路上.,关联矩阵是全么模矩阵，因此0-1变量可以松弛为区间0,1中的实数,不含负圈,，变量直接松弛为所有非负实数,思考：为什么,x,ij,可以不限定为0，1？,最短路问题的数学描述,8,xij表示弧（i，j）是否位于s-t路上：当xij=1时，,5.2.1 Bellman方程,对偶问题为,根据互补松弛条件,当,x,和,u,分别为原问题和对偶问题的最优解时:,9,5.2.1 Bellman方程 对偶问题为 根据互补松弛条件,Bellman方程,当某弧,(i,j),位于最短路上时，,即变量,x,ij,0,时,一定有,如果,u,为对偶问题最优解,易知,u+c,(,c,为任意实数,),仍为最优解,.,不妨令,u,s,=,0,，则,u,的具体数值就可以唯一确定了,.,Bellman方程(最短路方程、动态规划基本方程),相当于对节点,j,赋予的一个实数值,u,j,（通常称为,“标号”），在,u,s,=,0,时表示的正好是节点,s,到节点,j,的最短路的长度,.,一般情况下直接求解最短路方程是相当困难的.,10,Bellman方程当某弧(i,j)位于最短路上时，即变量x,定理,5.1,对于只含正有向圈的连通有向网络，从起点,s,到任一顶点,j,都存在最短路，它们构成以起点,s,为根的树形图（称为,最短路树,（,Tree of Shortest Paths,）或,最短路树形图,（,Shortest Path Arborescence,），最短路的长度可以由,Bellman,方程唯一确定,.,前一部分实际上是,Bellman,最优化原理的直接结果；,后一部分中,Bellman,方程解的唯一性可以用反证法证明（略）,最短路树（树形图）,A,F,5,6,6,7,4,4,5,1,3,B,E,D,C,11,定理5.1 对于只含正有向圈的连通有向网络，从起点s到任一顶,如果将定理中的条件“只含正有向圈”改为“不含负有向圈”：,上述最短路仍然存在；,Bellman方程的解的唯一性可能不成立.,起点,s,到顶点的最短路长度分别是,u,s,=,u,1,=,0,，,u,2,=10,，,u,3,=11,但此时只要,u,3,=,u,2,+1,11(,u,s,=,u,1,=,0),就可以满足,Bellman,方程,.,如,u,s,=,u,1,=,0,，,u,2,=8,，,u,3,=9 等,最短路树（树形图）,1,2,3,10,1,-1,s,对于一般的网络，Bellman方程只是最短路长度必须满足的,必要条件,，而不是充分条件；,对于只含正有向圈(或无圈)的连通有向网络，它才是,充要条件,.,12,如果将定理中的条件“只含正有向圈”改为“不含负有向圈”：起点,最短路算法-,如果采用邻接表表示法，可首先计算各节点的入度；,然后找入度为零者编号；,去掉已编号节点及相关弧，同时修改相邻节点入度（只需扫描该去掉的节点的出弧）；,依次类推。,如果采用邻接矩阵表示法，可首先计算各节点的入度；,然后找入度为零者编号；,去掉已编号节点及相关弧，同时修改相邻节点入度（只需扫描该去掉的节点的对应行）；,依次类推。,5.2.2 无圈网络,引理5.1(拓扑排序,Topological Ordering)设有向图,D,不含有向圈,则,D,的顶点总可以重新编号,使得 .,该算法自然可以用来判断有向图是否无圈图.,13,最短路算法-如果采用邻接表表示法，可首先计算各节点的入度；,最短路算法-,当网络是无圈时，这一最短路算法的复杂度为,5.2.2 无圈网络,当采用递推计算求解上述方程时,每个顶点和每条弧均被考虑一次.,这是求解最短路问题可能达到的最小的复杂度,因为任何算法都至少必须对每条弧考虑一次,14,最短路算法-当网络是无圈时，这一最短路算法的复杂度为 5.,最短路算法 例,例5.4 计算如下网络(图5.4(,a,)中从节点A到所有其它节点的最短路.,E,A,B,C,D,1,-2,5,-1,-1,3,4,1,A,B,C,D,1,-1,1,E,-2,E,-2,1,3,5,4,1,5,-1,3,4,1,2,计算过程,:,=0,=min0+1=1,=min0+(-1)=-1,=min0+5,1+(-2),-1+3=-1,=min-1+1,-1+4=0.,15,最短路算法 例例5.4 计算如下网络(图5.4(a),最短路算法-,算法通过不断修改这些标号，进行迭代计算.当算法结束时，距离标号表示的是从起点到该顶点的最短路长度.,基本思想：对于,V,中每一个顶点,j,，赋予两个数值（通常称为“标号”）：,一个是距离标号,u,j,，记录的是从起点到该顶点的最短路长度的上界；,另一个是前趋标号,pred,（,j,），记录的是当起点,s,到该顶点,j,的一条路长取到该上界时，该条路中顶点,j,前面的那个直接前趋（节点）.,迭代进行计算的过程中，所有顶点实际上被分成了两类：,一类是离起点,s,较近的顶点，它们的距离标号表示的是从点,s,到该顶点的最短路长度，因此其标号不会在以后的迭代中再被改变（称为永久标号）；,一类是离起点,s,较远的顶点，它们的距离标号表示的只是从点到该顶点的最短路长度的上界，因此其标号还可能会在以后的迭代中再被改变（称为临时标号）.,5.2.3,正费用网络(Dijkstra,1959),16,最短路算法-算法通过不断修改这些标号，进行迭代计算.当算,正费用网络（Dijkstra算法）,STEP1.,如果,S=V,则,u,j,为节点,s,到节点,j,的最短路路长,(,最短路可以通过数组,pred,所记录的信息反向追踪获得,),结束,.,否则继续,STEP2.,STEP0.(,初始化)令,S,=,，=,V,，；对,V,中的顶点,j(j,s),令初始距离标号 .,STEP2.,从 中找到距离标号最小的节点,i,，把它从 删除，加入,S,.,对于所有从,i,出发的弧,若 ，则令,.,转,STEP1.,17,正费用网络（Dijkstra算法）STEP1.如果S=V,正费用网络（Dijkstra算法）,归纳法.算法开始时结论成立.设直到迭代的第,k,步，上述结论(1)(2)成立.,pred(j),pred(i),i,j,s,P1,P2,S,中具有最小标号的顶点,i,可以移入,S,中，这不会破坏结论（1）.,引理,5.2,在上述,Dijkstra,算法中,（,1,）对于,S,中的任一顶点,j,，其距离标号,u,j,是从起点,s,到该顶点,j,的最短路路长；,（2）对于 中的任一顶点,j,，其距离标号,u,j,是从起点,s,出发，只经过,S,中的顶点到达顶点,j,的最短路路长.,对于 中的其它顶点,k,，修改标号，不会破坏结论（,2,）,.,18,正费用网络（Dijkstra算法）归纳法.算法开始时结论成,Dijkstra算法-计算复杂性分析,对于节点寻找过程，第一次循环时需要,n,次比较操作，第二次循环时需要,n,-1,次比较操作，依次类推.因此，节点寻找过程的复杂度为,综上所述，该算法的复杂度为,该,算法的主要计算量在于STEP2循环（最多执行,n,次），它包括两个过程：节点寻找过程（从 中找到距离标号最小的节点,i,）和距离修改过程（修改与节点,i,相邻的节点的距离标号）.,对于距离修改过程，注意到一个顶点只有当它与顶点,i,相邻时，其标号才可能变更，才需要修改标号.每次循