数模专题图论模型PPT学习教案

1、会计学1数模专题图论模型数模专题图论模型 1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线. 2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.第1页/共91页公路边的数字为该路段的公里数.第2页/共91页2) 问题分析：本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线. 将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条再回到点O，使得总权（路程或时间）最小.公路的长度（或行驶时间）看

2、作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次第3页/共91页 如第一问是三个旅行售货员问题，第二问是四本题是旅行售货员问题的延伸多旅行售货员问题. 本题所求的分组巡视的最佳路线，也就是m条众所周知，旅行售货员问题属于NP完全问题，显然本问题更应属于NP完全问题. 有鉴于此，经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.个旅行售货员问题.即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来

3、求得近似最优解.第4页/共91页第5页/共91页第6页/共91页第7页/共91页第8页/共91页第9页/共91页第10页/共91页第11页/共91页问题转化为在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次再回回到点O ,使得总权(路程或时时间)最小,即最佳旅行售货员问题.第12页/共91页最佳旅行售货员问题是NP完全问题,采用一种近似算法求其一个近似最优解，来代替最优解.算法一 求加权图的最佳旅行售货员回路近似算法: 1) 用图论软件包求出G中任意两个顶点间的最短路, 构造出完全图),(,),(),(yxEyxEVG);,(minyxdG2) 输入图 的一个初始H圈；G3) 用对

4、角线完全算法（见3）产生一个初始圈;4) 随机搜索出 中若干个H圈，例如2000个；G5) 对第2)，3)，4)步所得的每个H圈，用二边逐次修正法进行优化，得到近似最优H圈；6) 在第5)步求出的所有H圈中，找出权最小的一个, 此即要找的最优H圈的近似解.因二边逐次修正法的结果与初始圈有关,故本算法第2)，3)，4)步分别用三种方法产生初始圈，以保证能得到较优的计算结果.第13页/共91页 问题一 若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线. 此问题是多个售货员的最佳旅行售货员问题.4)min)(1niiC第14页/共91页 此问题包含两方面：a)对顶点分组, b)在每组中求(单

5、个售货员)最佳旅行售货员回路. 因单个售货员的最佳旅行售货员回路问题不存存在多项式时间内的精确算法.故多也不第15页/共91页 而图中节点数较多，为53个，我们只能去寻求一种较合理的划分准则，对图1进行粗步划分后,求出各部分的近似最佳旅行售货员回路的权,再进一进一步进行调整，使得各部分满足均衡性条件3). 从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路. 故用软件包求出O点到其余顶点的最短路. 这些最短路构成一棵O为树根的树.将从O点出发的树枝称为干枝.第16页/共91页从O点出发到其它点共有6条干枝，它们的名称分别为，. 在分组时应遵从准则： 准则1 尽量使同一干枝上及其分枝上的

6、点分在同一组.准则2 应将相邻的干枝上的点分在同一组； 准则3 尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到两种分组形式如下：分组1:（，），（，），（，）分组2:（，），（，），（，）分组1极不均衡,故考虑分组2.第17页/共91页分组2:(,),(,),(,) 对分组2中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路线. 在每个子图所构造的完全图中,取一个尽量包含上图中树上的边的H圈作为其第2)步输入的初始圈.第18页/共91页分组2的近似解 第19页/共91页因为该分组的均衡度54.2%9 .2415 .1259 .241)(max)()(3 , 2 , 121

7、0iiCCC.所以此分法的均衡性很差. 为改善均衡性，将第组中的顶点C,2,3,D,4分给第组（顶点2为这两组的公共点），重新分分组后的近似最优解见表2.第20页/共91页第21页/共91页%.69.114 .2161 .1914 .216)(max)()(3 , 2 , 1130iiCCC因该分组的均衡度 所以这种分法的均衡性较好. 问题二 当巡视人员在各乡（镇）、村的停留停留时间一定,汽车的行驶速度一定,要在24小时内完成巡视,至少要分几组及最佳旅行的巡视路线.第22页/共91页 由于T=2小时,t=1小时,V=35公里/小时,需访问的乡镇共有17个，村共有35个. 计算出在乡(镇)及村的

8、总停留时间为17 2+35=69小时，要在24小时内完成巡回，若不考虑行走时间，有: 69/i24(i为分的组数). 得i最小为4，故至少要分4组. 由于该网络的乡(镇)、村分布较为均匀,故有可能找出停留时间尽量均衡的分组,当分4组时各组停停留时间大约为69/4=17.25小时，则每组分配在路路途上的时间大约为24-17.25=6.75小时.而前面讨论过,分三组时有个总路程599.8公里的巡视路线，分4组时的总路程不会比599.8公里大太多,不妨以599.8公里来计算.路上约用599.8/35=17小时,若平均分配给4个组,每个组约需17/4=4.25小时6.75小小时,故分成4组是可能办到的

9、.第23页/共91页 现在尝试将顶点分为4组.分组的原则：除遵从前面准则1、2、3外，还应遵从以下准则：准则4 尽量使各组的停留时间相等. 用上述原则在下图上将图分为4组，同时计算各组的停留时间,然后用算法一算出各组的近似最最佳旅行售货员巡回，得出路线长度及行走时间,从而得出完成巡视的近似最佳时间. 用算法一计计算时，初始圈的输入与分三组时同样处理.这4组的近似最优解见表3.第24页/共91页第25页/共91页表3符号说明：加有底纹的表示前面经过并停留过,此次只经过不停留;加框的表示此点只经过不停留. 可看出,表3分组的均衡度很好,且完全满足24小时完成巡视的要求. 该分组实际均衡度 4.62

10、% 74.2269.2174.220第26页/共91页称G = ( X, Y, E )为二部图. 如果X中的每个点都与Y中的每个点邻接, 则称G = ( X, Y, E )为完备二部图. 若 F：E R +, 则称G = ( X, Y, E, F )为二部赋权图. 定义1 设X , Y都是非空有限顶点集, 且X Y = ,YyXxxyE, 的一个匹配。的一个匹配。是是中均不邻接，则称中均不邻接，则称边在边在中任意两条中任意两条若若设图设图定义定义GMGMEM,EV,G 2 第27页/共91页定义3 若匹配M的某条边与点v关联, 则称M饱和点v, 并且称v是M的饱和点, 否则称v是M的非饱和点.

11、 定义4 设M是图G的一个匹配, 如果G的每一个点都是M的饱和点, 则称M是完美匹配；如果G中没有另外的匹配M0, 使 | M0 | M |, 则称M是最大匹配. 每个完美匹配都是最大匹配, 反之不一定成立. 二部图的匹配及其应用第28页/共91页例16： 判断下图的匹配最大匹配非完美匹配完美匹配二部图的匹配及其应用第29页/共91页定义5 设M是图G的的一个匹配, 其边在EM和M 中交错出现的路, 称为G的一条M交错路. 起点和终点都不是M的饱和点的M 交错路, 称为M 增广路. 定理1 G的一个匹配M是最大匹配的充要条件是G不包含M 增广路. 二部图的匹配及其应用第30页/共91页定理2

12、设G = ( X, Y, E )为二部图, 则 G存在饱和X的每个点的匹配的充要条件是对任意S ,有 | N (S ) | | S | .其中, N (S ) = v | uS, v与u相邻. G存在完美匹配的充要条件是对任意S 或S 有 | N (S ) | | S | . X XY二部图的匹配及其应用第31页/共91页工作安排问题之一 给n个工作人员x1, x2, , xn安排n项工作y1, y2, , yn. n个工作人员中每个人能胜任一项或几项工作, 但并不是所有工作人员都能从事任何一项工作. 比如x1能做y1, y2工作, x2能做y2, y3, y4工作等. 这样便提出一个问题,

13、对所有的工作人员能不能都分配一件他所能胜任的工作？ 二部图的匹配及其应用第32页/共91页 我们构造一个二部图G = ( X, Y, E ), 这里X = x1, x2, , xn,Y = y1, y2, , yn, 并且当且仅当工作人员xi胜任工作yj时, xi与yj才相邻. 于是, 问题转化为求二部图的一个完美匹配. 因为 |X|=|Y|, 所以完美匹配即为最大匹配. 二部图的匹配及其应用第33页/共91页1x2x3x4x5x1y2y3y4y5y求下图完美匹配Hungarian算法： 时终止。时终止。STSN 二部图的匹配及其应用第34页/共91页匈牙利算法： 解 取初始匹配M0 =x2

14、y2 , x3 y3 , x5 y5 给X中M0的两个非饱和点x1,x4都给以标号0和标记* (如下图所示). 00*二部图的匹配及其应用第35页/共91页00 去掉x1的标记*, 将与x1邻接的两个点y2, y3都给以标号1. 因为y2, y3都是M0的两个饱和点,所以将它们在M0中邻接的两个点x2, x3都给以相应的标号和标记*. *11*23*二部图的匹配及其应用第36页/共91页00*11*23* 去掉x2的标记*, 将与x2邻接且尚未给标号的三个点y1, y4, y5都给以标号2. 222二部图的匹配及其应用第37页/共91页00*1123*222 因为y1是M0的非饱和点, 逆向返

15、回, 直到x1为0为止.于是得到M0的增广路x1 y2x2 y1, 记P = x1 y2 , y2x2 , x2 y1. 取M1 = M0P = x1 y2 , x2 y1 , x3 y3 , x5 y5, 则M1是比M多一边的匹配. 二部图的匹配及其应用第38页/共91页0* 再给X中M1的非饱和点x4给以标号0和标记*, 然后去掉x4的标记*, 将与x4邻接的两个点y2, y3都给以标号4. 44二部图的匹配及其应用第39页/共91页044 因为y2, y3都是M1的两个饱和点, 所以将它们在M1中邻接的两个点x1, x3都给以相应的标号和标记*.*23二部图的匹配及其应用第40页/共91

16、页044*23 去掉x1的标记*, 因为与x1邻接的两个点y2, y3都有标号4, 所以去掉x3的标记*. 而与x3邻接的两个点y2, y3也都有标号4, 此时X中所有有标号的点都已去掉了标记*(如下图所示), 因此M1是G的最大匹配.没有完美匹配。 二部图的匹配及其应用第41页/共91页注意到S=x1,x3,x4时，N(S)=y1,y3, ,N SS 所以没有完美匹配。二部图的匹配及其应用第42页/共91页定义6 设G = ( X, Y, E , F )为完备的二部赋权图, 若L：X Y R + 满足：对任意xX, yY , L (x) + L ( y ) F (x y), 则称L为G的一个

17、可行点标记, 记相应的生成子图为GL = ( X, Y, EL , F ), 这里EL = x yE | L ( x ) + L ( y ) = F (x y). 定理3 设L是完备的二部赋权图G = ( X, Y, E , F )的可行点标记, 若M *是GL的完美匹配, 则M *是G的最佳匹配. (权数最大的匹配) 二部图的匹配及其应用第43页/共91页工作安排问题之二 给n个工作人员x1, x2, , xn安排n项工作y1, y2, , yn. 如果每个工作人员工作效率不同, 要求工作分配的同时考虑总效率最高. 二部图的匹配及其应用第44页/共91页 我们构造一个二部赋权图G = ( X

18、, Y, E , F ), 这里X = x1, x2, , xn,Y = y1, y2, , yn, F(xi yj )为工作人员xi胜任工作yj时的工作效率. 则问题转化为：求二部赋权图G的最佳匹配. 在求G 的最佳匹配时, 总可以假设G为完备二部赋权图.若xi与yj不相邻, 可令F(xi yj )=0. 同样地, 还可虚设点x或y,使|X|=|Y|.如此就将G 转化为完备二部赋权图,而且不会影响结果. 二部图的匹配及其应用第45页/共91页引例：车辆调度问题1234567813025183227192226229311918212030193282930191922232642930192

19、42519182152120181716141618车地点第46页/共91页MATLAB程序Kuhn-munkras算法function sumw=kuhngong(A)n=size(A,1); w=A; l=zeros(n,2);for i=1:n for j=1:n if l(i,1)temp al=temp; end, end, end, end 第48页/共91页 for i=1:n if FLAG_S(i) l(i,1)=l(i,1)-al; end, end for j=1:n if FLAG_T(j) l(j,2)=l(j,2)+al; end, end FLAG_AGL=zer

20、os(n,n); for i=1:n for j=1:n if l(i,1)+l(j,2)=w(i,j) FLAG_AGL(i,j)=i; end, end, end, end for x=1:n for y=1:n if (FLAG_S(x)&(FLAG_T(y) &(FLAG_AGL(x,y)=x) f(y,2)=x; if M(y,2) %1start for z=1:n if (FLAG_AGL(z,y)=z) &(M(y,2)=z) FLAG_S(z)=1; FLAG_T(y)=1; f(z,1)=y; FLAG4=1; break; end, end else %1end stop

21、=0; searched=zeros(n,2); while stop for i=1:n if (f(y,2)=i) M(y,2)=i;M(i,1)=i; if i=u stop=1; break; end for k=1:n if (f(i,1)=k) M(k,2)=0; y=k; break; end, end if stop=0 break end, end, end, end MATLAB程序Kuhn-munkras算法（续）第49页/共91页引例的求解：车辆调度问题第50页/共91页引例的求解：车辆调度问题第51页/共91页引例的求解：车辆调度问题第52页/共91页 在加权二部图G

22、中，设顶点xi与顶点yj之间的边权为aij,引入0-1决策变量zj,当匹配含边(xi,yj)时,zij=1,否则zij=0.因此，相应的线性规划模型为 1111min1,1,2,(1,1,2, ,()01,1,2, .mnijijijnijjnijiija zzin Xzjn Yjn； s.t.， 部中每个点只与一条匹配边关联) 部中每个点只与一条匹配边关联 z或 第53页/共91页例（指派问题）设有n个人, 计划作n项工作, 第i个人做第j项工作的收益如下表, 现求一种工作分配方式，使得每个人完成一项工作，且使总收益最大.第54页/共91页络流理论”，是网络应用的重要组成部分。第55页/共9

23、1页第56页/共91页sbacdt3,35,43,34,45,12,03,35,41,11x2x4v1v1y3vs3y2y6,15,12,21,12,23,23,05,34,01,01,02,16,04,46,43,1第57页/共91页第58页/共91页1x2x4v1v1y3vs3y2y6,15,12,21,12,23,23,05,34,01,01,02,16,04,46,43,1图1第59页/共91页第60页/共91页3v3y3,21x1v1y6,15,12x4vs2y2,21,12,23,05,34,01,01,02,16,04,46,43,1s,2,4t,0,0图2, 6第61页/共91页第62页/共91页第63页/共91页第64页/共91页第65页/共91页第66页/共91页第67页/共91页第68页/共91页第69页/共91页第70页/共91页sbacdt353452351图3第71页/共91页sbacdt3,05,03,04