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

《运筹学导论第八版6网络模型ijhx.pptx》由会员分享，可在线阅读，更多相关《运筹学导论第八版6网络模型ijhx.pptx（40页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1第6章 网络模型26.1 网络模型的应用范围和定义大量的运筹学问题都可以应用网络建模来求解：a)在墨西哥海湾上需要设计一个海面上的天然气管道网络，将各个井口链接到岸边的运输点，模型目标是最小化管道建设费用。b)在已经存在的道路网络中，求起讫点之间的最短路径.c)求山西煤矿到北京的发电厂的煤浆管道网络的最大运输量d)给一个工程项目中的各项活动确定时间表3网络模型的定义网络模型的定义网络是由节点(node)和弧(arc)集合组成，用符号(N,A)表示，其中N表示节点的集合，A表示弧的集合。14235N=1，2，3，4，5A=(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),

2、(4,2),(4,5)如果一条弧上的其中一个方向的流量是正数，相反方向就是为零，该弧是有向的有向的(directed)，如果所有弧上的容量都是有向的，则网络是有向网络。将两点之间链接起来，并经过其他的一些节点的这一些列弧，称之为路径(path),如果经过路径又能回到自身，则这些路径称之为圈圈(Loop),如果网络中没有圈，网络就是树(tree),如果该树包括了图上所有的节点，则是生成树。4欧拉(Euler)在1736 年发表图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问题。哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个小岛，河上有七座桥，参见图 5.1(a)。当时那里的居民热衷于这样的问题：

3、一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。BACDBACD5例例1 1 是北京、上海等十个是北京、上海等十个城市间的铁路交通图。城市间的铁路交通图。与此类似的还有电话与此类似的还有电话线分布图、煤气管道线分布图、煤气管道图、航空路线图等。图、航空路线图等。北京北京天津天津济南济南青岛青岛武汉武汉南京南京上海上海郑州郑州连云港连云港徐州徐州6例例2 2 分别用点分别用点v v1 1,v,v2 2,v,v3 3,v,v4 4,v,v5 5分别代表甲、乙、分别代表甲、乙、丙、丁、戊五支球队。若有两支球队之间比赛丙、丁、戊五支球队。若有两支球队之间比赛过，就在相应的点之间联一条线，

4、且这条线不过，就在相应的点之间联一条线，且这条线不过其他点。如下图所示：过其他点。如下图所示：v1v2v3v4v5可知各队之间的比赛情况如下：可知各队之间的比赛情况如下：甲甲 乙、丙、丁、戊乙、丙、丁、戊乙乙 甲、丙甲、丙丙丙 甲、乙、丁甲、乙、丁丁丁 甲、丙、戊甲、丙、戊戊戊 甲、丁甲、丁7例例3 “染色问题染色问题”储存储存8种化学药品，其中某些药品不能种化学药品，其中某些药品不能存放在同一个库房里。存放在同一个库房里。用用v1,v2,v8分别代分别代表这表这8种药品。规定若两种药品不能存放在种药品。规定若两种药品不能存放在一起，则其相应的点之间联一条线。如下一起，则其相应的点之间联一条线

5、。如下图所示：图所示：v1v2v3v4v5v6v7v8可知需要可知需要4个库房，个库房，其中一个答案是：其中一个答案是：v1 v2,v4,v7 v3,v5 v6,v8 还有其他的答案。还有其他的答案。8从以上几个例子可见可以用由点及点与点的联线所构成的网络，去反映实际生活中，某些对象之间的某个特定的关系，通常用点代表研究的对象（如城市、球队、药品等等），用点与点的联线表示这两个对象之间有特定的关系（如两个城市间有铁路线、两个球队比赛过、两种药品不能存放在同一个库房里等）。网络是反映对象之间关系的一种工具因此，可以说，在一般情况下，网络中点的相对位置如何，点与点之间联线的长短曲直，对于反映对象之

6、间的关系，并不是重要的，例如哥尼斯堡七桥问题。如例2，也可以用网络去反映五个球队的比赛情况，这与例3没有本质的区别。所以，图论中的图与几何图、工程图等是不同的。96.2 最小生成树算法最小生成树算法是以来链接一个网络所有的节点，使得树上边的总长度最小。例如，在几个城镇之间修路，使得任意两个城镇之间都有路相连，之间可以穿过其他城镇那么最经济的道路网络设计方案就是道路里程最小。令N=1,2,n是网络中节点的集合，定义：10最小生成树算法步骤：第第0步步 令第第1步步 从 中的任意一个节点i开始，令C1=i,那么 ，设定 k=2.一般的第一般的第k步步 在还没有连接的节点集合 中选择一个节点 j*，

7、使得j*到Ck-1中某个节点之间的弧长最小，然后将 j*放在Ck-1，从 中删除 j*，即11例例中西部有线电视公司正在计划为5个新的居民区提供有线电视服务，下图给出了小区之间可以铺设电缆的情况以及相应的距离。确定最经济的电缆铺设方案，使得5个小区可以连接起来。2413561478351096351224356179241356148356324135614786324135614796315555迭代1迭代2迭代3迭代4C1C2C3C413241356143535241356143510635迭代5迭代6（最小生成树）C5可选边最小生成树算法在第6步给出了问题的解，要服务的电视网络线缆长度为

8、1+3+4+3+5=16146.3 最短路径问题6.3.1 最短路应用实例RentCar公司开展了一项4年一周期的汽车更换政策，在每一年的开始，消费者都可以选择继续使用购买的汽车，也可以选择更换汽车。一辆汽车最少使用1年，最多3年，下表给出了汽车更换的费用，它取决于车辆购置时的年数以及使用年限。客户该如何更换汽车？开始购买汽车的年数给定年限的更换费用123140005400980024300620087003480071004490015该问题可以描述为网络模型，节点1到5表示第1年到第5年每年的开始。与节点1(第1年)有弧相连的节点只有2,3,4,因为按照轨道汽车的使用年限为1到3年。同理，

9、可以推断出从其他节点出发的弧。每条弧的长度等于更换费用。那么问题等价于求一条从节点1到5的最短路径。12345980054007100620087004000430048004900可以知道，最短路是135.这个解说明汽车在第1年购买，然后使用2年，在第3年开始的时候更换新的汽车，一直使用到年底。16例例 Smart每天开车去工作，如果找最短走，会被限速因此行程时间不是最短，如果超速会被罚款，所以最短路对smart而言不是最好选择.假设已知各个路段相应不被罚款的概率已知，如下图。他想选择一条不被警察罚款的概率最大的路径，该如何选择？123450.20.80.350.5670.90.30.25一

10、条路径不被罚款的概率是这条路径上每一段上不被罚款的概率的乘积。例如对于1357不被罚款的概率为0.90.30.25=0.0670.60.10.417由于不被罚款的概率为 ，那么取对数之后是 因此，通过对数变化，这个问题可以转化为最短路问题，也就是将概率乘积转为对数概率之和。从数学角度来看，p1k的最大化等价于lgp1k的最大化，由于lgp1k0，所以lgp1k的最大化等价于-lgp1k的最小化123450.69870.96910.455930.30103670.045760.522880.602060.2218510.39794求解结果表明，节点1,3,5,7是最短的路径，长度为1.1707(

11、=lgp17)，其概率为0.0675186.3.2 最短路径算法Dijkstra算法算法用 ui 表示从原点1到节点 i 的最短距离，定义 dij(0)为弧(i,j)的长度，那么即可得到节点 j 的标号为uj,i=ui+dij,i,dij0开始的节点标号为0,-.在Dijkstra算法中涉及两种类型的标号：暂时的和永久的标号。对于暂时标号，如果这个节点找到更短的路径，那么标号改变，如果找不到更短的路径，标号变成永久的。常用的最短路算法有2种，Dijkstra算法和Floyd算法，Dijkstra算法可以求网络中原点到其他任意一个节点的最短路径。而Floyd算法可以求网络中任意两点之间的最短路径

12、19算法步骤第0步 对原点(节点1)给出永久的标号 0,.令i=1.第1步 (a)计算节点 i 有边相连的每一个节点j(j没有被永久标号)的暂时标号ui+dij,i.如果节点j已经通过另外一个节点 k被标号为uj,k,如果ui+dij uj,那么就用标号ui+dij,i代替uj,k.(b)如果所有的节点都得到了永久的标号，那么停止.否则从所有暂时标号的节点中选择具有最短距离(=ur)的标号ur,s,令 i=r，然后重复执行第 i 步20例下图给出了从城市1(节点1)和其他4个城市(节点2到节点5)之间可能的路线以及每条边的长度，求城市1到其他4个城市的最短路径.2431510015506030

13、2010迭代迭代0 给出节点1分配永久标号0,.21迭代迭代0 给出节点1分配永久标号0,.迭代迭代1 节点1(永久标号节点)可以直接到达节点2和3，那么下表给出了节点新的标号(暂时的和永久的)：节点标号标号状态10,永久永久20+100,1=100,1暂时30+30,1=30,1暂时上表中有两个暂时的标号100,1和30,1，节点3的距离较小(u3=30).因此，把节点3的标号状态变成永久的。22迭代迭代2 节点3可以直接到达节点4和5，那么下表给出了各个节点新的标号(暂时的和永久的)为：节点标号标号状态10,永久永久2100,1暂时330,1永久永久430+10,3=40,3暂时530+6

14、0,3=90,3暂时将暂时标号为40,3的节点4的标号状态转变为永久的(u4=40)23迭代迭代3 节点4可以直接到达节点2和5，那么新的标号为：节点标号标号状态10,永久永久240+15,4=55,4暂时330,1永久440,3永久永久590,3或 40+50,3=90,4暂时对于节点2，在迭代1得到的暂时标号为100,1,而此时通过节点4找到了一条更短的路径，所以将节点2的标号更改为55,4.同样在这次迭代后，节点5有了两个可以选择的标号，并且标号对应的距离相等(u5=40).通过比较，这一次迭代选择节点2，并将节点2的标号变成永久的。24迭代迭代4 此时节点2只可以到达节点3，然而节点3

15、已经是永久性标号了，不能给予重新标号了。所以这一代迭代的标号除了将节点2的标号变为永久的以外，其他的与迭代3的标号相同。这样节点5是仅有的暂时标号，又因为节点5没有子节点，所以节点5的标号自动变成永久的。整个过程结束。节点标号标号状态10,永久永久240+15,4=55,4永久永久330,1永久440,3永久永久590,3或90,4永久25这个算法的计算过程可以很容易的在网络上得以实现，如下图所示。243151001550603020100,-(1)55,4(3)100,1(1)40,3(2)30,1(1)90,4(3)90,3(2)迭代次数26从节点1到其他任何一个节点的最短路径可以通过这个

16、节点的永久标号中的信息采用一步步回溯的办法得到，例如，节点1到节点2的最短路径可以通过下面回溯方法找到：(2)55,4(4)40,3(3)30,1(1)那么所求的最短路径是1342，总长度55节点标号标号状态10,永久永久240+15,4=55,4永久330,1永久440,3永久永久590,3或90,4永久2732865417121225862413765习题习题求节点4和8之间的最短路径28Floyd算法算法Floyd算法比Dijkstra算法更加一般的算法，因为它可以给出网络中任意两个节点之间的最短路径。算法首先将n个节点的网络表示成一个n行n列的矩阵，矩阵中的元素(i,j)表示从节点i到

17、节点 j 的距离 dij，如果i,j之间没有边相连，那么相应的元素为无穷.Floyd算法的思想很直观，如下图，给定3个节点i,j,k,以及它们之间的距离，如果满足 dik+dkjdij那么从i经过k到j更短.在这种情况下，用间接的路径ikj代替路径ij.下面的步骤给出了这种三重操作替换应用在网络上的具体算法.ijkdikdikdij29算法步骤算法步骤：第第0步步 定义初始的距离矩阵D0和节点序列矩阵S0，如下表，对角线上用元素(-)表示不必要从自身到自身.令k=1.30算法步骤算法步骤：一般的第一般的第 k 步步 令第 k 行和第 k 列为枢轴行和枢轴列.对于矩阵 Dk-1 中的每一个元素

18、dij 做三重操作.如果满足条件：dik+dkjdij (ik,jk,ij)那么进行下面的转化：(a)用dik+dkj代替矩阵 Dk-1中的元素 dij，从而得到矩阵Dk (b)用k代替矩阵Sk-1中的元素sij，从而得到矩阵Sk.令k=k+1.如果k=n+1,停止；否则重复第k步.31经过n步之后，我们可以从矩阵Dn和Sn中按照下面的规则得到节点i和节点j之间的最短路径：(1)在矩阵Dn中，dij表示节点i与节点j之间的最短路径长度.(2)在矩阵Sn中，可以确定中间节点k=sij(根据得到的路径ikj).如果sik=k并且skj=j，停止，因为路径中所有的中间节点都找到了.否则，在节点 i

19、与节点 k 之间，节点k与节点j之间重复上面的程序.32下图给出了算法第k步对矩阵Dk-1的转化过程，其中 k 行和 k 列是当前的枢轴行和枢轴列.第i行表示第1,2,k-1行中的任意一个，第p行表示第k+1，k+2,n行中的任意一个，第j列表示第1,2,k-1行中的任意一个，第q列表示第k+1，k+2,n 列中的任意一个.三重操作可以按照下面的方法执行：如果枢轴行和枢轴列上的元素(图中正方形中的元素)之和小于相交元素(图中圆形中的元素)的值，那么用这个和代替交叉元素的值就可以使最短距离得到优化.dijdiqdpjdpqdikdpkdkjdkq枢轴行k行i行p列 j列 q枢轴列k33例下图给出

20、的网络，求任意两点之间的饿最短路径.图中弧上给出了相应节点间的距离.弧(3,5)是有向的，因此不允许从节点5到节点3，其他边是双向的.123453510615412345131023531061545645434迭代迭代0 矩阵D0和S0代表初始的网络.除了d53=外(因为不允许从节点5到节点3)，D0是对称的.123451310235310615456454123451234521345312454123551234D0S0迭代迭代1 令k=1.D0矩阵中的红色字体的第1行和第1列为枢轴行和枢轴列，其中应用三重操作可以改进的元素是d23和d32(图中用深色阴影表示).然后根据下面的方法，从D

21、0和和S0得到D1和S1：(1)用d21+d13=3+10=13代替d23，并令s23=1(2)用d31+d12=10+3=13代替d32，并令s32=1351234513102313531013615456454123451234521145311454123551234D1S1迭代迭代2 令k=2.D1矩阵中的红色字体的第1行和第1列为枢轴行和枢轴列，其中应用三重操作可以改进的元素是d14和d41(图中橙色部分).然后根据下面的方法，从D0和和S0得到D1和S1：(1)用d12+d24=3+5=8代替d14，并令s14=1(2)用d42+d21=3+5=8代替d41，并令s41=13612

22、3451310823135310136154856454123451232521145311454223551234D2S2迭代迭代3 令k=3.D2矩阵中的红色字体的第3行和第3列为枢轴行和枢轴列，其中应用三重操作可以改进的元素是d14和d41(图中橙色部分).然后根据下面的方法，从D0和和S0得到D1和S1：(1)用d12+d24=3+5=8代替d14，并令s14=1(2)用d42+d21=3+5=8代替d41，并令s41=137123451310823135310136154856454123451232321143311454223551234D3S3迭代迭代4 令k=4.D3矩阵中的

23、红色字体的第4行和第4列为枢轴行和枢轴列.应用三重操作可以得到矩阵D4和和S4：12345131081223115931011610485645129104123451232421444314444223554444D4S438迭代迭代5 令k=5.D4矩阵中的第5行和第5列为枢轴行和枢轴列.应用三重操作发现没有可以改进的元素了最后得到的矩阵D4中可以得到节点1和5之间的最短路径长度是d15=12.下面通过S4确定这条最短路径，注意到对于一个路段(i,j),如果sij=j，那么从i有弧直接连接到j；否则，i和j之间经过至少一个中间节点。在S4中，因为s15=45，可以知道路径应该经过节点4到达节点5，即145；又因为s14=24所以(1,4)也不是直接连接，应该用路径124代替，因此路径145变为1245.此时s12=2，s24=4，s45=5，所以这条最短路径就是1245.39习题求下图的任意两点之间的最短路径。24513422231084612540