数学建模提高班专题六网络优化模型及案例分析资料

1、会计学1数学建模提高班专题六网络优化模型及数学建模提高班专题六网络优化模型及案例分析资料案例分析资料3农夫过河农夫过河摆渡人F狼W羊G菜C4 南岸状态： 16种，其中WG,GC,WGC，从而FC,FW,F为不允许状态，FWGCFWGFWCFGCFGOCGWWC10个允许状态：农夫过河农夫过河5FWGCFWG FWC FGCFGOCGWWC寻求图中从顶点“FWGC”到顶点“O”的最短路径，这样的路径有几条？求出最优的渡河方案。语言描述时未显示的关系跃然纸上农夫过河农夫过河6FWGCFWG FWC FGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC农夫过河农夫过河78910 S N

2、G M R P李春兰郑文国姚南陈奇峰王润惠邹文燕万华李祖军黄大度史武军刘昆欧阳金郭志伟陈奇峰刘云刘元元黄大度董舟邹鑫赵云王凯李白彤甄军李欣陈俊于洪化范文李出荣张惠赵云曹林军胡志强张敏陈修建欧阳金李晓李白彤万华曾光伟张星夏雯邵桂芳王学权单富民董舟杨欣吴军查小辉王坚程静波邹文燕卫迎新赵小民息志强陈修建邹鑫刘元兵杨成宝邱吉洲许茂陈俊周清武樊雪峰刘伟甄军姜永东1112SNGRPM完成上述表示课程冲突关系的线图直观、清晰地表达已知信息的方式1314v1v2v5v6v7v4v3abjkcghidfe150101000101111001000101100101010101001101010001010765

3、43217654321v1v2v5v6v7v4v3abjkcghidfe1617固固 定定 起起 点点 的的 最最 短短 路路最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路1920算法步骤：算法步骤：（4） 若S ，转 2，否则，停止.（2）更新l v( )、z v( )： vSVS,若l v( )l uW u v( )( , ) 则令l v( )=l uW u v( )( , ),z v( )= u21 TO MATLAB(road1)2223 1

4、2 34 5 6 7 8uuuuuuuu24每每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路(二二)算算法法原原理理1求距离矩阵的方法求距离矩阵的方法2求路径矩阵的方法求路径矩阵的方法3查找最短路路径的方法查找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（三）算法步骤（三）算法步骤25算法的基本思想算法的基本思想26算法原理算法原理 求距离矩阵的方法求距离矩阵的方法27算法原理算法原理 求路径矩阵的方法求路径矩阵的方法)()0()0(ijrR, jrij)0(每求得一个 D(k)时，按下列方式产生相应的新的 R(k)否则若)1()1()1()1()(kkjkikkijki

5、jkijdddrkr在建立距离矩阵的同时可建立路径矩阵R 即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径)(D)(R)(Rv28i j算法原理算法原理 查找最短路路径的方法查找最短路路径的方法若1)(prij，则点 p1是点 i 到点 j 的最短路的中间点.pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21, 1229算法步骤算法步骤Floyd 算法：算法：求任意两点间的最短路(2) 更新 d(i,j), r(i,j)对所有 i,j，若 d(i,k)+d(k,j)=1; 24!For city i

6、, except the base (city 1); 25for(cities(i) | i #gt# 1 : 26! It must be entered; 27 sum(cities(j)| j #ne# i: x(j,i)=1; 28! level(j)=levle(i)+1, if we link j and i;70 29 for(cities(j)| j #gt# 1 #and# j #ne# i : 30 level(j) = level(i) + x(i,j) 31 - (n-2)*(1-x(i,j) + (n-3)*x(j,i); 32 ); 33! The level o

7、f city is at least 1 but no more n-1, 34 and is 1 if it links to base (city 1); 35 bnd(1,level(i),999999); 36 level(i)=n-1-(n-2)*x(1,i); 37 ); 38! Make the xs 0/1; 39for(link : bin(x); END71利用水平变量利用水平变量(level)来保证所选的边不构成圈来保证所选的边不构成圈.Global optimal solution found at iteration: 34Objective value: 60.00

8、000 Variable Value Reduced Cost X( 1, 2) 1.000000 8.000000 X( 1, 3) 1.000000 5.000000 X( 3, 4) 1.000000 7.000000 X( 3, 7) 1.000000 7.000000 X( 4, 5) 1.000000 3.000000 X( 5, 8) 1.000000 6.000000 X( 7, 9) 1.000000 6.000000 X( 9, 6) 1.000000 8.000000 X( 9, 10) 1.000000 10.0000072连接这连接这10个城镇的最小距离为个城镇的最小距离为60公里，其连接情况如下公里，其连接情况如下.SV地区的最优连线地区的最优连线7375767778辐射杂交细胞798081828384858687888990919495算法的基本思想算法的基本思想96算法原理算法原理 求距离矩阵