数模最短路与最优问题课件.ppt

1、1.图论问题的起源图论问题的起源 18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”SNAB七桥问题的分析 七桥问题看起来不难，很多人都想试一试，但没有人找到答案.后来有人写信告诉了当时的著名数学家欧拉.千百人的失败使欧拉猜想,也许那样的走法根本不可能.1876年,他证明了自己的猜想.Euler把南北两岸和四个岛抽象成四个点,将连接这些陆地的桥用连接相应两点的一条线来表示,就得到如下一个简图:SNAB欧拉的结论欧拉的结论 欧拉指出欧拉指出:一个线图中存在通过每边一

2、次仅一次一个线图中存在通过每边一次仅一次回到出发点的路线的充要条件是回到出发点的路线的充要条件是:1)图是连通的图是连通的,即任意两点可由图中的一些边连接即任意两点可由图中的一些边连接起来起来;2)与图中每一顶点相连的边必须是偶数与图中每一顶点相连的边必须是偶数.由此得出结论由此得出结论:七桥问题无解七桥问题无解.欧拉由七桥问题所引发的研究论文是图论的开篇欧拉由七桥问题所引发的研究论文是图论的开篇之作之作,因此称欧拉为图论之父因此称欧拉为图论之父.4.图的作用图的作用 图是一种表示工具.改变问题的描述方式,往往是创造性的启发式解决问题的手段.一种描述方式就好比我们站在一个位置和角度观察目标,有

3、的东西被遮挡住了,但如果换一个位置和角度,原来隐藏着的东西就可能被发现.采用一种新的描述方式,可能会产生新思想.图论中的图提供了一种直观,清晰表达已知信息的方式.它有时就像小学数学应用题中的线段图一样,能使我们用语言描述时未显示的或不易观察到的特征、关系,直观地呈现在我们面前,帮助我们分析和思考问题,激发我们的灵感.5.图的广泛应用图的广泛应用 图的应用是非常广泛的图的应用是非常广泛的,在工农业生产、交通在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络运输、通讯和电力领域经常都能看到许多网络,如河道网、灌溉网、管道网、公路网、铁路网、如河道网、灌溉网、管道网、公路网、铁路网、电话线网

4、、计算机通讯网、输电线网等等电话线网、计算机通讯网、输电线网等等.还有还有许多看不见的网络许多看不见的网络,如各种关系网如各种关系网,像状态转移关像状态转移关系、事物的相互冲突关系、工序的时间先后次序系、事物的相互冲突关系、工序的时间先后次序关系等等关系等等,这些网络都可以归结为图论的研究对这些网络都可以归结为图论的研究对象象图图.其中存在大量的网络优化问题需要我其中存在大量的网络优化问题需要我们解决们解决.还有象生产计划、投资计划、设备更新还有象生产计划、投资计划、设备更新等问题也可以转化为网络优化的问题等问题也可以转化为网络优化的问题.6.基本的网络优化问题 基本的网络优化问题有:最短路径

5、问题、最小生成树问题、最大流问题和最小费用问题.图论作为数学的一个分支,已经有有效的算法来解决这些问题.当然这当中的有些问题也可以建立线性规划的模型,但有时若变量特别多,约束也特别多,用线性规划的方法求解效率不高甚至不能在可忍受的时间内解决.而根据这些问题的特点,采用网络分析的方法去求解可能会非常有效.例如,在1978年,美国财政部的税务分析部门在对卡特尔税制改革做评估的过程中,就有一个100,000个约束以上,25,000,000个变量的问题,若用普通的线性规划求解,预计要花7个月的时间.他们利用网络分析的方法,将其分解成6个子问题,利用特殊的网络计算机程序,花了大约7个小时问题就得到了解决

6、.数学建模与数学实验数学建模与数学实验主讲：陈六新最短路径与最优匹配问题最短路径与最优匹配问题实验目的实验目的实验内容实验内容2会用会用MATLAB软件求最短路与最优匹配软件求最短路与最优匹配1了解最短路与最优匹配的算法及其应用了解最短路与最优匹配的算法及其应用1图图 论论 的的 基基 本本 概概 念念2最最 短短 路路 问问 题题 及及 其其 算算 法法3最最 短短 路路 的的 应应 用用5建模案例：最优截断切割问题建模案例：最优截断切割问题6实验作业实验作业4最优匹配及算法最优匹配及算法 图图 论论 的的 基基 本本 概概 念念一、一、图图 的的 概概 念念1 1图的定义图的定义2 2顶点

7、的次数顶点的次数 3 3子图子图二、二、图图 的的 矩矩 阵阵 表表 示示1 1 关联矩阵关联矩阵2 2 邻接矩阵邻接矩阵返回返回定义定义有序三元组G=(V,E,)称为一个图图,如果：图的定义图的定义定义定义定义定义规定用记号和分别表示图的顶点数和边数.返回返回顶点的次数顶点的次数4()4dv5)(3)(2)(444vdvdvd例例 在一次聚会中，认识奇数个人的人数一定是偶数.返回返回子图子图返回返回关联矩阵关联矩阵注：假设图为无向简单图返回返回邻接矩阵邻接矩阵注：假设图为简单无向图无向赋权图的邻接矩阵可类似定义返回返回最最 短短 路路 问问 题题 及及 其其 算算 法法一、一、基基 本本 概

8、概 念念二、固二、固 定定 起起 点点 的的 最最 短短 路路三、每三、每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路返回返回基基 本本 概概 念念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路径4521141vevevPvv定义定义（）任意两点均有路径的图称为连通图连通图（）起点与终点重合的路径称为圈圈（）连通而无圈的图称为树树返回返回固固 定定 起起 点点 的的 最最 短短 路路最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此,

9、可采用树生长的过程来求指定顶点到其余顶点的最短路62341587算法步骤：算法步骤：（4）若S，转 2，否则，停止.TO MATLAB(road1)03064093021509701608120Wl uW u v()(,)1 2 34 5 6 7 8返回返回uuuuuuuu每每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路1 1求距离矩阵的方法求距离矩阵的方法2 2求路径矩阵的方法求路径矩阵的方法3 3查找最短路路径的方法查找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（三）算法步骤（三）算法步骤返回返回算法的基本思想算法的基本思想返回返回nnnnnnnnnnnnnnddd

10、ddddddddddddddddddddddddddddddddddddddddddddddD654321666656463626155655545352514464544434241336353433323122625242322211161514131211算法原理算法原理 求距离矩阵的方法求距离矩阵的方法返回返回算法原理算法原理 求路径矩阵的方法求路径矩阵的方法)()0()0(ijrR,jrij)0(每求得一个 D(k)时，按下列方式产生相应的新的 R(k)否则若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距离矩阵的同时可建立路径矩阵R 即当k被插入任何两

11、点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径)(D)(R返回返回)(Rvi j算法原理算法原理 查找最短路路径的方法查找最短路路径的方法若1)(prij，则点 p1是点 i 到点 j 的最短路的中间点.pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21,12返回返回算法步骤算法步骤例例 求下图中加权图的任意两点间的距离与路径 TOMATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD951d，故从 v5到 v1的最短路为51

12、r所以从 v5到 v1的最短路径为：1435.返回返回一、一、可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、选选 址址 问问 题题1 中心问题中心问题2 重心问题重心问题返回返回可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题返回返回 选址问题选址问题-中心问题中心问题 TO MATLAB(road3(floyd)0753970246520243420696460D05.15.55.86475.10475.45.25.55.54032475.8730571065.42502545.24720375.5710530DS(v1)=10,S(v2)=7,S(

13、v3)=6,S(v4)=10,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处.返回返回 选址问题选址问题-重心问题重心问题返回返回匹配匹配 匹配问题是运筹学的重要问题之一,也是图论研究的重点内容,它提供了解决“人员分配问题”和“最优分配问题”一种新的思想.定义定义1.设G=是无环图,ME(G),M,若M中任意两条边都不相邻,则称M是图是图G的一个匹配的一个匹配.若对图G的任何匹配M,均有M|M|,矛盾.()若M不是G的最大匹配,则存在匹配M,使得|M|M|,作H=MM,由定理1,H的任意边导出子图Q是下列两种情况之一:(1)交错偶圈:Q中每个结点度数为

14、2.(2)交错路.Q中除端点外,其余结点度数均为2.因为|M|M|,故|E(H)M|E(H)M|,因而H中必有一条起始于M且终止于M的连通分支P,故P是M可增广路,矛盾,所以命题正确.定义:NG(S):设S是图G的任意顶点子集,G中与S的顶点邻接的所有顶点的集合,称为S的邻集,记做NG(S).定理定理3(Hall定理,1935)设G是有二部划分(V1,V2)的二分图,则G含有饱和V1的每个顶点的匹配M的充要条件充要条件是,对SV1,有N(S)S.证明证明:()对SV1,匹配M将S中的每个顶点与N(S)中的顶点配对,所以N(S)S.()当对SV1,有N(S)S时.可按下述方法作出饱和V1的匹配M

15、.先作一初始匹配M1,若已经饱和V1,定理得证.否则,V1中至少有一非饱和点x1,检查以x1为起点,终点在V2中的交错路.考虑下面两种情形:(1)不存在任何一条交错路可以到达V2的非饱和点.此时从X1开始的一切交错路的终点还是在V1中.故存在AV1,使得N(A)M1,因此,重复该过程就可以找到饱和V1的全部顶点的匹配M.推论推论1 具有二部划分(V1,V2)的二分图G有完美匹配 V1=V2,且对SV1(或V2),有N(S)S.证明:必要性必要性.若二分图G有完美匹配,由定理3有V2=N(V1)V1,即V2V1,同理V1V2,因此V1=V2.充分性充分性:因为对SV1,有N(S)S,由定理1,G

16、中存在饱和V1的每个顶点匹配M,又G是二分图,故匹配M的每一边的两个端点分别属于V1和V2,据V1=V2即知M饱和V2,所以M为完美匹配.推论推论2.设G是k(0)正则二分图,则G有完美匹配.证明:因为G是二部划分(V1,V2)的k正则二分图,故 kV1=E(G)=kV2 又k0,所以V1=V2.任取SV1,并用E1和E2分别表示G中与S和N(S)中关联的边集,则E1E2,则 kN(S)=E2E1=kS即N(S)S,SV1,由定理3可知,G有饱和V1的匹配M,再据V1=V2和推论1即知M是完美匹配.推论推论3.设G是二部划分(V1,V2)的简单二分图,且V1=V2=n,若(G)n/2,则G有完

17、美匹配.证明:SV1,(1)若S中至少有两个顶点,由(G)n/2可知N(S)n/2+n/2=n=V1S(2)若S中只有一个顶点,由(G)n/2可知N(S)n/2,所以 N(S)1S=1.综上,对SV1,均有N(S)S,所以G中有完美匹配.定理定理4.G有完美匹配O(G-S)S,SV(G),其中O(G-S)是G-S的奇数阶连通分支数目.(不证)例1.有n张纸牌,每张纸牌的正反两面都写上1,2,n的某一个数.证明:如果每个数字恰好出现两次,则这些纸牌一定可以这样摊开,使朝上的面中1,2,n都出现.证明证明:作一个二分图G=,其中V1=1,2,n,V2=y1,y2,yn表示这n张纸牌.i与yi之间连

18、接的边数等于数i在纸牌yj中出现的次数,这样得到的图G是一个2-正则二分图,因此图G中有完美匹配,设为M=1yi1,2yi2,nyin 则只要把纸牌yi1中的1朝上,yi2中的2朝上,yin的n朝上,这样摊开,这样摊开的纸牌就能使上面中1,2,n都出现.例例2.某工厂生产由6种不同颜色的纱布织成的双色布,由该厂所生产的双色布中,每一种颜色至少和其他三种颜色搭配.证明可以挑选出三种不同的双色布,它们含有所有的6种颜色.证明证明:构造图G=,其中V=v1,v2,v3,v4,v5,v6表示6种颜色,工厂生产出一种颜色vi与vj搭配而成的双色布边vi,vjE(G).由题意知,G为简单图,且每个结点的度

19、数至少为3,下证G中含有一个完美匹配.今设v1,v2E(G),由于d(v3)3,所以存在一个不同于v1和v2的顶点vi(4i6),使v3,viE(G),不妨设vi=4,即v3,v4E(G).如果边v5,v6E(G),由于d(v5)3,v1,v2,v3,v4中至少有3个顶点与v5相邻,即v5与边v1,v2,v3,v4中的每一边的某一个端点相邻,不妨设v1,v5E(G)和v3,v5E(G).对于顶点v6,同样与v1,v2,v3,v4中至少3个顶点相邻,即在v2和v4中至少有一个顶点与v6相邻.如果v2,v6E(G),则边v1,v5,v3,v4,v2,v6是G的一个完美匹配;如果v4,v6E(G),

20、则v1,v5,v3,v5,v4,v6是G的一个完美匹配.综上所述,G总存在完美匹配,完美匹配中的三条边所对应的三种双色布即为所求.最大匹配的生成算法-匈牙利算法定义定义1.根在x的M交错子图:设M是图G的匹配，x是G中非M饱和点。G中由起点为x的M交错路所能连接的顶点集所导出的G的导出子图称为根在称为根在x的的M交错子图交错子图.定理定理1.设M是具有二部划分(V1,V2)的二分图G的匹配,xV1是非M饱和点,H是G中根在x的M交错子图的顶点集S=HV1,T=HV2,则:(1)TNG(S);(2)下述三条等价:(a)G中不存在以x为端点的M可增广路;(b)x是H中唯一的非M饱和点;(c)T=N

21、G(S),且T=S-1.证明:(1)yT,则G中存在以x和y为端点的M交错路P.令uNp(y),由于G是二分图且yTV2,所以uHV1=S,即yNG(S),因而T NG(S),.(2)(a)(b)设y是H中异于x的非M饱和点,则G中存在以x和y为端点的M交错路P。P是G中以x为端点的M可增广路,与(a)矛盾.(b)(c)任取yNG(S)V2,则存在uS=H V1和边eE(G)使G(e)=u,y.若u=x,显然有yT.若ux,则G中存在以x和u为端点的交错路P.因为x是唯一非M饱和点,所以u为M饱和点.若P不含y,则eM.由H的定义知,y HV2=T,所以NG(S)T,再由(1),T=NG(S)

22、.显然显然y T(交错路中不可能含有两个非交错路中不可能含有两个非M饱和点饱和点),与与T=NG(S)矛盾矛盾.若若y S,则显然有则显然有T=S-2.矛盾矛盾.所以所以G中不存在以中不存在以x为端点的为端点的M可增广路可增广路.(3)(c)(a)反设反设G中存在以中存在以x为端点的为端点的M可增广可增广路路,则则G中至少还存在一个异于中至少还存在一个异于x的非的非M饱和点饱和点y,若若y S,则则y T NG(S),匈牙利算法基本思想基本思想:设G是具有二部划分(V1,V2)的二分图,从图G的任意匹配M开始.若M饱和V1,则M是G的匹配.若M不能饱和V1,则在V1中选择一个非M饱和点x,若G

23、中存在以x为起点的M可增广路P,则M=MP就是比M更大的匹配,利用M代替M,并重复这个过程.若G中不存在以x为起点的M可增广路,则令H是根在x的M交错子图的顶点集,并令S=HV1,T=HV2,由定理1,T=NG(S),且G中不存在以x为起点的M可增广路,此时称x为检验过的非M饱和点.对V1中其它未检验过的非M饱和点重复该过程,直到V1中的所有非M饱和点全部检验过为止.当整个过程结束时,由于G中不存在M可增广路,从而M为G的最大匹配.匈牙利算法步骤匈牙利算法步骤:设设G是具有二部划分是具有二部划分(V1,V2)的二分图的二分图.(1)任给初始匹配任给初始匹配M;(2)若若M饱和饱和V1则结束则结

24、束.否则转否则转(3);(3)在在V1中找一非中找一非M饱和点饱和点x,置置S=x,T=;(4)若若N(S)=T,则停止则停止,否则任选一点否则任选一点y N(S)-T;(5)若若y为为M饱和点转饱和点转(6),否则作求一条从否则作求一条从x到到y的的M可增广路可增广路P,置置M=M P,转转(2)(6)由于由于y是是M饱和点饱和点,故故M中有一边中有一边y,u,置置S=S u,T=T y,转转(4).例1 如图G所示，V1=x1,x2,x3,x4,x5，V2=y1,y2,y3,y4,y5，试求图G的最大匹配。x1,x2 x3 x4 x5y1 y2 y3 y4 y5图图ax1 x2 x3 x4

25、 x5y1 y2 y3 y4 y5图图bx1 x2 x3 x4 x5y1 y2 y3 y4 y5解：任取初始匹配M=x2y2,x3y3,x5y5，如图(a)中虚线所示.解题过程如下表:MxSTN(S)y N(S)-Ty,u MPx2y2,x3y3,x5y5x1x1y2,y3y2饱和饱和y2,x2x1,x2y2y1,y2,y3,y4,y5y1非饱和非饱和(x1y2x2y1)x1y2,x2y1,x3y3 x5y5x4x4y2,x3y2饱和饱和y2,x1x4,x1y2y2,y3y3饱和饱和y3,x3x4,x1,x3y2,y3y2,y3N(S)=T,停止停止因此,M=x1y2,x2y1,x3y3,x5

26、y5即为图G的最大匹配,如图(b)虚线所示.匈牙利算法的时间复杂度分析匈牙利算法的时间复杂度分析:设二分图设二分图G有有n个个结点结点,m条边条边,利用匈牙利算法求利用匈牙利算法求G的最大匹配时的最大匹配时,初始匹配可为空初始匹配可为空,因此算法最多可找因此算法最多可找n条可增广条可增广路路,每找一条可增广路每找一条可增广路,最多比较m条边,从而算法的时间复杂度为O(mn),故匈牙利算法为有效算法.最优匹配最优匹配定义定义1.最优匹配最优匹配:在加权图中求一个总权最大的完在加权图中求一个总权最大的完美匹配美匹配,这种匹配这种匹配称为最优匹配称为最优匹配.定义定义2.已知已知G是具有二部划分是具

27、有二部划分(V1,V2)的完全加权二的完全加权二分图分图,映射映射l:V(G)R,满足对满足对G的每条边的每条边e=x,y,均均有有l(x)+l(y)(x,y),其中其中(x,y)表示边表示边x,y的的权权,则称则称l为为G的可行顶标的可行顶标.令令El=x,y x,y E(G),l(x)+l(y)=(x,y),Gl为以为以El为边集的为边集的G的生成子图的生成子图,则称则称Gl为为l等子图等子图.说明说明:可行顶标总可行顶标总是存在的是存在的,例如例如:212,0)(),(maxVyylVyxxlVy定理定理1.设设l是是G的可行顶标的可行顶标.若若l等子图等子图Gl有完美匹配有完美匹配M,

28、则则M是是G的最优匹配的最优匹配.基于定理基于定理1的在一个加权二分图的在一个加权二分图(Km,n,)中求最优中求最优匹配的有效算法匹配的有效算法Kuhn-munkres算法算法:(1)从任意可行顶标从任意可行顶标(如平凡标号如平凡标号)l开始开始,确定确定l等子图等子图Gl,并且在并且在Gl中选取匹配中选取匹配M.若若M饱和饱和V1,则则M是完美匹是完美匹配配,也即也即M是最优匹配是最优匹配,算法终止算法终止,否则转入否则转入(2)步步.(2)匈牙利算法终止于匈牙利算法终止于S V1,T V2且使且使NGl(S)=T,计计算算 ,确定新的可行顶标确定新的可行顶标l,并以并以l替代替代l,以以

29、Gl替代替代Gl转入转入(1)步步.la例1.已知完全二分图k5,5,其中V1=x1,x2,x3,x4,x5,V2=y1,y2,y3,y4,y5,且k5,5的权矩阵为A,求k5,5的最优匹配.3554122022244100110012133A实验作业实验作业 生产策略问题生产策略问题：现代化生产过程中，生产部门面临的突出问题之一，便是如何选取合理的生产率.生产率过高，导致产品大量积压，使流动资金不能及时回笼；生产率过低，产品不能满足市场需要，使生产部门失去获利的机会.可见，生产部门在生产过程中必须时刻注意市场需求的变化，以便适时调整生产率，获取最大收益.某生产厂家年初要制定生产策略，已预知其产品在年初的需求量为a=6万单位，并以b=1万单位/月速度递增.若生产产品过剩，则需付单位产品单位时间（月）的库存保管费C2=0.2元；若产品短缺，则单位产品单位时间的短期损失费C3=0.4元.假定生产率每调整一次带有固定的调整费C1=1万元，问：工厂应如何制定当年的生产策略，使工厂的总损失最小？返回返回