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

1第6章网络模型26.1网络模型的应用范围和定义大量的运筹学问题都可以应用网络建模来求解：a)在墨西哥海湾上需要设计一个海面上的天然气管道网络，将各个井口链接到岸边的运输点，模型目标是最小化管道建设费用。b)在已经存在的道路网络中，求起讫点之间的最短路径.c)求山西煤矿到北京的发电厂的煤浆管道网络的最大运输量d)给一个工程项目中的各项活动确定时间表3网络模型的定义网络是由节点(node)和弧(arc)集合组成，用符号(N,A)表示，其中N表示节点的集合，A表示弧的集合。14235N={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)。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。BACDBACD5例1是北京、上海等十个城市间的铁路交通图。与此类似的还有电话线分布图、煤气管道图、航空路线图等。北京天津济南青岛武汉南京上海郑州连云港徐州6例2分别用点v1,v2,v3,v4,v5分别代表甲、乙、丙、丁、戊五支球队。若有两支球队之间比赛过，就在相应的点之间联一条线，且这条线不过其他点。如下图所示：v1v2v3v4v5可知各队之间的比赛情况如下：甲——乙、丙、丁、戊乙——甲、丙丙——甲、乙、丁丁——甲、丙、戊戊——甲、丁7例3“染色问题”储存8种化学药品，其中某些药品不能存放在同一个库房里。用v1,v2,…,v8分别代表这8种药品。规定若两种药品不能存放在一起，则其相应的点之间联一条线。如下图所示：v1v2v3v4v5v6v7v8可知需要4个库房，其中一个答案是：{v1}{v2,v4,v7}{v3,v5}{v6,v8}还有其他的答案。8从以上几个例子可见可以用由点及点与点的联线所构成的网络，去反映实际生活中，某些对象之间的某个特定的关系，通常用点代表研究的对象（如城市、球队、药品等等），用点与点的联线表示这两个对象之间有特定的关系（如两个城市间有铁路线、两个球队比赛过、两种药品不能存放在同一个库房里等）。网络是反映对象之间关系的一种工具因此，可以说，在一般情况下，网络中点的相对位置如何，点与点之间联线的长短曲直，对于反映对象之间的关系，并不是重要的，例如哥尼斯堡七桥问题。如例2，也可以用网络去反映五个球队的比赛情况，这与例3没有本质的区别。所以，图论中的图与几何图、工程图等是不同的。96.2最小生成树算法最小生成树算法是以来链接一个网络所有的节点，使得树上边的总长度最小。例如，在几个城镇之间修路，使得任意两个城镇之间都有路相连，之间可以穿过其他城镇那么最经济的道路网络设计方案就是道路里程最小。令N={1,2,…,n}是网络中节点的集合，定义：kkCkCk在第步时已经连接起来的节点集合在第步以后需要连接的节点集合10最小生成树算法步骤：第0步令第1步从中的任意一个节点i开始，令C1={i},那么，设定k=2.一般的第k步在还没有连接的节点集合中选择一个节点j*，使得j*到Ck-1中某个节点之间的弧长最小，然后将j*放在Ck-1，从中删除j*，即00,CCN0C1CNi1kC1kC**,kk-1kk-1C=C+jC=Cj11例中西部有线电视公司正在计划为5个新的居民区提供有线电视服务，下图给出了小区之间可以铺设电缆的情况以及相应的距离。确定最经济的电缆铺设方案，使得5个小区可以连接起来。2413561478351096351224356179241356148356324135614786324135614796315555迭代1迭代2迭代3迭代4C11CC22CC33CC44C13241356143535241356143510635迭代5迭代6（最小生成树）C55C可选边最小生成树算法在第6步给出了问题的解，要服务的电视网络线缆长度为1+3+4+3+5=16146.3最短路径问题6.3.1最短路应用实例RentCar公司开展了一项4年一周期的汽车更换政策，在每一年的开始，消费者都可以选择继续使用购买的汽车，也可以选择更换汽车。一辆汽车最少使用1年，最多3年，下表给出了汽车更换的费用，它取决于车辆购置时的年数以及使用年限。客户该如何更换汽车？开始购买汽车的年数给定年限的更换费用12314000540098002430062008700348007100—44900——15该问题可以描述为网络模型，节点1到5表示第1年到第5年每年的开始。与节点1(第1年)有弧相连的节点只有2,3,4,因为按照轨道汽车的使用年限为1到3年。同理，可以推断出从其他节点出发的弧。每条弧的长度等于更换费用。那么问题等价于求一条从节点1到5的最短路径。12345980054007100620087004000430048004900可以知道，最短路是1→3→5.这个解说明汽车在第1年购买，然后使用2年，在第3年开始的时候更换新的汽车，一直使用到年底。16例Smart每天开车去工作，如果找最短走，会被限速因此行程时间不是最短，如果超速会被罚款，所以最短路对smart而言不是最好选择.假设已知各个路段相应不被罚款的概率已知，如下图。他想选择一条不被警察罚款的概率最大的路径，该如何选择？123450.20.80.350.5670.90.30.25一条路径不被罚款的概率是这条路径上每一段上不被罚款的概率的乘积。例如对于1→3→5→7不被罚款的概率为0.9×0.3×0.25=0.0670.60.10.417由于不被罚款的概率为，那么取对数之后是因此，通过对数变化，这个问题可以转化为最短路问题，也就是将概率乘积转为对数概率之和。从数学角度来看，p1k的最大化等价于lgp1k的最大化，由于lgp1k≤0，所以lgp1k的最大化等价于-lgp1k的最小化112kkpppp112lglglglgkkpppp123450.69870.96910.455930.30103670.045760.522880.602060.2218510.39794求解结果表明，节点1,3,5,7是最短的路径，长度为1.1707(=lgp17)，其概率为0.0675186.3.2最短路径算法Dijkstra算法用ui表示从原点1到节点i的最短距离，定义dij(≥0)为弧(i,j)的长度，那么即可得到节点j的标号为[uj,i]=[ui+dij,i],dij≥0开始的节点标号为[0,-].在Dijkstra算法中涉及两种类型的标号：暂时的和永久的标号。对于暂时标号，如果这个节点找到更短的路径，那么标号改变，如果找不到更短的路径，标号变成永久的。常用的最短路算法有2种，Dijkstra算法和Floyd算法，Dijkstra算法可以求网络中原点到其他任意一个节点的最短路径。而Floyd算法可以求网络中任意两点之间的最短路径19算法步骤第0步对原点(节点1)给出永久的标号[0,—].令i=1.第1步(a)计算节点i有边相连的每一个节点j(j没有被永久标号)的暂时标号[ui+dij,i].如果节点j已经通过另外一个节点k被标号为[uj,k],如果ui+dijuj,那么就用标号[ui+dij,i]代替[uj,k].(b)如果所有的节点都得到了永久的标号，那么停止.否则从所有暂时标号的节点中选择具有最短距离(=ur)的标号[ur,s],令i=r，然后重复执行第i步20例下图给出了从城市1(节点1)和其他4个城市(节点2到节点5)之间可能的路线以及每条边的长度，求城市1到其他4个城市的最短路径.24315100155060302010迭代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的距离较小(u3=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的标号状态转变为永久的(u4=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有了两个可以选择的标号，并且标号对应的距离相等(u5=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这个算法的计算过程可以很容易的在网络上得以实现，如下图所示。24315100155060302010[0,-](1)[55,4](3)[100,1](1)[40,3](2)[30,1](1)[90,4](3)[90,3](2)迭代次数26从节点1到其他任何一个节点的最短路径可以通过这个节点的永久标号中的信息采用一步步回溯的办法得到，例如，节点1到节点2的最短路径可以通过下面回溯方法找到：(2)→[55,4]→(4)→[40,3]→(3)→[30,1]→(1)那么所求的最短路径是1→3→4→2，总长度55节点标号标号状态1[0,─]永久2[40+15,4]=[55,4]永久3[30,1]永久4[40,3]永久5[90,3]或[90,4]永久2732865417121225862413765习题求节点4和8之间的最短路径28Floyd算法Floyd算法比Dijkstra算法更加一般的算法，因为它可以给出网络中任意两个节点之间的最短路径。算法首先将n个节点的网络表示成一个n行n列的矩阵，矩阵中的元素(i,j)表示从节点i到节点j的距离dij，如果i,j之间没有边相连，那么相应的元素为无穷.Floyd算法的思想很直观，如下图，给定3个节点i,j,k,以及它们之间的距离，如果满足dik+dkjdij那么从i经过k到j更短.在这种情况下，用间接的路径i→k→j代替路径i→j.下面的步骤给出了这种三重操作替换应用在网络上的具体算法.ijkdikdikdij29算法步骤：第0步定义初始的距离矩阵D0和节点序列矩阵S0，如下表，对角线上用元素(-)表示不必要从自身到自身.令k=1.121121220122121211212jnjniiijinjnddddddDiddddnddd