运筹学导论第八版6网络模型

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第,6,章 网络模型,2,6.1,网络模型的应用范围和定义,大量的运筹学问题都可以应用网络建模来求解：,在墨西哥海湾上需要设计一个海面上的天然气管道网络，将各个井口链接到岸边的运输点，模型目标是最小化管道建设费用。,在已经存在的道路网络中，求起讫点之间的最短路径,.,求山西煤矿到北京的发电厂的煤浆管道网络的最大运输量,给一个工程项目中的各项活动确定时间表,3,网络模型的定义,网络是由节点,(node),和弧,(arc),集合组成，用符号,(N,A),表示，其中,N,表示节点的集合，,A,表示弧的集合。,1,4,2,3,5,N=1,，,2,，,3,，,4,，,5,A=(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5),如果一条弧上的其中一个方向的流量是正数，相反方向就是为零，该弧是,有向的,(,directed,),，如果所有弧上的容量都是有向的，则网络是有向网络。将两点之间链接起来，并经过其他的一些节点的这一些列弧，称之为路径,(path),如果经过路径又能回到自身，则这些路径称之为,圈,(Loop),如果网络中没有圈，网络就是树,(tree),如果该树包括了图上所有的节点，则是生成树。,4,欧拉,(Euler),在,1736,年发表图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个小岛，河上有七座桥，参见图,5.1(a),。,当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。,B,A,C,D,B,A,C,D,5,例,1,是北京、上海等十个城市间的铁路交通图。与此类似的还有电话线分布图、煤气管道图、航空路线图等。,北京,天津,济南,青岛,武汉,南京,上海,郑州,连云港,徐州,6,例,2,分别用点,v,1,v,2,v,3,v,4,v,5,分别代表甲、乙、丙、丁、戊五支球队。若有两支球队之间比赛过，就在相应的点之间联一条线，且这条线不过其他点。如下图所示：,v,1,v,2,v,3,v,4,v,5,可知各队之间的比赛情况如下：,甲,乙、丙、丁、戊,乙,甲、丙,丙,甲、乙、丁,丁,甲、丙、戊,戊,甲、丁,7,例,3 “,染色问题”,储存,8,种化学药品，其中某些药品不能存放在同一个库房里。用,v,1,v,2,v,8,分别代表这,8,种药品。规定若两种药品不能存放在一起，则其相应的点之间联一条线。如下图所示：,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,可知需要,4,个库房，其中一个答案是：,v,1,v,2,v,4,v,7,v,3,v,5,v,6,v,8,还有其他的答案。,8,从以上几个例子可见,可以用由点及点与点的联线所构成的网络，去反映实际生活中，某些对象之间的某个特定的关系，通常用点代表研究的对象（如城市、球队、药品等等），用点与点的联线表示这两个对象之间有特定的关系（如两个城市间有铁路线、两个球队比赛过、两种药品不能存放在同一个库房里等）。,网络是反映对象之间关系的一种工具,因此，可以说，在一般情况下，网络中点的相对位置如何，点与点之间联线的长短曲直，对于反映对象之间的关系，并不是重要的，例如哥尼斯堡七桥问题。,如例,2,，也可以用网络去反映五个球队的比赛情况，这与例,3,没有本质的区别。所以，图论中的图与几何图、工程图等是不同的。,9,6.2,最小生成树算法,最小生成树算法是以来链接一个网络所有的节点，使得树上边的总长度最小。例如，在几个城镇之间修路，使得任意两个城镇之间都有路相连，之间可以穿过其他城镇那么最经济的道路网络设计方案就是道路里程最小。,令,N=1,2,n,是网络中节点的集合，定义：,10,最小生成树算法步骤：,第,0,步,令,第,1,步,从 中的任意一个节点,i,开始，令,C,1,=,i,那么,，设定,k,=2.,一般的第,k,步,在还没有连接的节点集合 中选择一个节点,j,*,，使得,j,*,到,C,k-1,中某个节点之间的弧长最小，然后将,j,*,放在,C,k-1,，从 中删除,j,*,，即,11,例,中西部有线电视公司正在计划为,5,个新的居民区提供有线电视服务，下图给出了小区之间可以铺设电缆的情况以及相应的距离。确定最经济的电缆铺设方案，使得,5,个小区可以连接起来。,2,4,1,3,5,6,1,4,7,8,3,5,10,9,6,3,5,12,2,4,3,5,6,1,7,9,2,4,1,3,5,6,1,4,8,3,5,6,3,2,4,1,3,5,6,1,4,7,8,6,3,2,4,1,3,5,6,1,4,7,9,6,3,1,5,5,5,5,迭代,1,迭代,2,迭代,3,迭代,4,C,1,C,2,C,3,C,4,13,2,4,1,3,5,6,1,4,3,5,3,5,2,4,1,3,5,6,1,4,3,5,10,6,3,5,迭代,5,迭代,6,（最小生成树）,C,5,可选边,最小生成树算法在第,6,步给出了问题的解，要服务的电视网络线缆长度为,1+3+4+3+5=16,14,6.3,最短路径问题,6.3.1,最短路应用实例,RentCar,公司开展了一项,4,年一周期的汽车更换政策，在每一年的开始，消费者都可以选择继续使用购买的汽车，也可以选择更换汽车。一辆汽车最少使用,1,年，最多,3,年，下表给出了汽车更换的费用，它取决于车辆购置时的年数以及使用年限。客户该如何更换汽车？,开始购买汽车的年数,给定年限的更换费用,1,2,3,1,4000,5400,9800,2,4300,6200,8700,3,4800,7100,4,4900,15,该问题可以描述为网络模型，节点,1,到,5,表示第,1,年到第,5,年每年的开始。,与节点,1(,第,1,年,),有弧相连的节点只有,2,3,4,因为按照轨道汽车的使用年限为,1,到,3,年。同理，可以推断出从其他节点出发的弧。每条弧的长度等于更换费用。那么问题等价于求一条从节点,1,到,5,的最短路径。,1,2,3,4,5,9800,5400,7100,6200,8700,4000,4300,4800,4900,可以知道，最短路是,1,3,5.,这个解说明汽车在第,1,年购买，然后使用,2,年，在第,3,年开始的时候更换新的汽车，一直使用到年底。,16,例,Smart,每天开车去工作，如果找最短走，会被限速因此行程时间不是最短，如果超速会被罚款，所以最短路对,smart,而言不是最好选择,.,假设已知各个路段相应不被罚款的概率已知，如下图。他想选择一条不被警察罚款的概率最大的路径，该如何选择？,1,2,3,4,5,0.2,0.8,0.35,0.5,6,7,0.9,0.3,0.25,一条路径不被罚款的概率是这条路径上每一段上不被罚款的概率的乘积。例如对于,1,3,57,不被罚款的概率为,0.90.30.25=0.067,0.6,0.1,0.4,17,由于不被罚款的概率为 ，那么取对数之后是,因此，通过对数变化，这个问题可以转化为最短路问题，也就是将概率乘积转为对数概率之和。,从数学角度来看，,p,1k,的最大化等价于,lg,p,1k,的最大化，由于,lg,p,1k,0,，所以,lg,p,1k,的最大化等价于,-lg,p,1k,的最小化,1,2,3,4,5,0.6987,0.9691,0.45593,0.30103,6,7,0.04576,0.52288,0.60206,0.22185,1,0.39794,求解结果表明，节点,1,3,5,7,是最短的路径，长度为,1.1707(=lg,p,17,),，其概率为,0.0675,18,6.3.2,最短路径算法,Dijkstra,算法,用,u,i,表示从原点,1,到节点,i,的最短距离，定义,d,ij,(0),为弧,(,i,j,),的长度，那么即可得到节点,j,的标号为,u,j,i,=,u,i,+d,ij,i,d,ij,0,开始的节点标号为,0,-.,在,Dijkstra,算法中涉及两种类型的标号：暂时的和永久的标号。对于暂时标号，如果这个节点找到更短的路径，那么标号改变，如果找不到更短的路径，标号变成永久的。,常用的最短路算法有,2,种，,Dijkstra,算法和,Floyd,算法，,Dijkstra,算法可以求网络中原点到其他任意一个节点的最短路径。而,Floyd,算法可以求网络中任意两点之间的最短路径,19,算法步骤,第,0,步 对原点,(,节点,1),给出永久的标号,0,.,令,i,=1.,第,1,步,(,a,),计算节点,i,有边相连的每一个节点,j,(,j,没有被永久标号,),的暂时标号,u,i,+d,ij,i,.,如果节点,j,已经通过另外一个节点,k,被标号为,u,j,k,如果,u,i,+d,ij,u,j,那么就用标号,u,i,+d,ij,i,代替,u,j,k,.,(,b,),如果所有的节点都得到了永久的标号，那么停止,.,否则从所有暂时标号的节点中选择具有最短距离,(=,u,r,),的标号,u,r,s,令,i,=,r,，然后重复执行第,i,步,20,例,下图给出了从城市,1(,节点,1),和其他,4,个城市,(,节点,2,到节点,5),之间可能的路线以及每条边的长度，求城市,1,到其他,4,个城市的最短路径,.,2,4,3,1,5,100,15,50,60,30,20,10,迭代,0,给出节点,1,分配永久标号,0,.,21,迭代,0,给出节点,1,分配永久标号,0,.,迭代,1,节点,1(,永久标号节点,),可以直接到达节点,2,和,3,，那么下表给出了节点新的标号,(,暂时的和永久的,),：,节点,标号,标号状态,1,0,永久,2,0+100,1,=100,1,暂时,3,0+30,1,=30,1,暂时,上表中有两个暂时的标号,100,1,和,30,1,，节点,3,的距离较小,(u,3,=30).,因此，把节点,3,的标号状态变成永久的。,22,迭代,2,节点,3,可以直接到达节点,4,和,5,，那么下表给出了各个节点新的标号,(,暂时的和永久的,),为：,节点,标号,标号状态,1,0,永久,2,100,1,暂时,3,30,1,永久,4,30+10,3,=40,3,暂时,5,30+60,3,=90,3,暂时,将暂时标号为,40,3,的节点,4,的标号状态转变为永久的,(,u,4,=40),23,迭代,3,节点,4,可以直接到达节点,2,和,5,，那么新的标号为：,节点,标号,标号状态,1,0,永久,2,40+15,4,=55,4,暂时,3,30,1,永久,4,40,3,永久,5,90,3,或,40+50,3,=90,4,暂时,对于节点,2,，在迭代,1,得到的暂时标号为,100,1,而此时通过节点,4,找到了一条更短的路径，所以将节点,2,的标号更改为,55,4.,同样在这次迭代后，节点,5,有了两个可以选择的标号，并且标号对应的距离相等,(,u,5,=40).,通过比较，这一次迭代选择节点,2,，并将节点,2,的标号变成永久的。,24,迭代,4,此时节点,2,只可以到达节点,3,，然而节点,3,已经是永久性标号了，不能给予重新标号了。所以这一代迭代的标号除了将节点,2,的标号变为永久的以外，其他的与迭代,3,的标号相同。这样节点,5,是仅有的暂时标号，又因为节点,5,没有子节点，所以节点,5,的标号自动变成永久的。整个过程结束。,节点,标号,标号状态,1,0,永久,2,40+15,4,=55,4,永久,3,30,1,永久,4,40,3,永久,5,90,3,或,90,4,永久,25,这个算法的计算过程可以很容易的在网络