运筹学-第11章--图与网络模型-图文

管理运筹学1第十一章图与网络模型§1图与网络的基本概念§2最短路问题§3最小生成树问题§4最大流问题§5最小费用最大流问题管理运筹学2§1图与网络的基本概念图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图11-1就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5图11-1管理运筹学3§1图与网络的基本概念当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图11-2来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图11-2管理运筹学4§1图与网络的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图11-3如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。管理运筹学5§1图与网络的基本概念无向图：由点和边构成的图，记作G=（V，E）。•有向图：由点和弧构成的图，记作D=（V，A）。•连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。•回路：若路的第一个点和最后一个点相同，则该路为回路。•赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。•网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。管理运筹学6§2最短路问题最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题求最短路有两种算法：一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路6.2.1最短路问题的网络模型管理运筹学7§2最短路问题•最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。一、求解最短路的Dijkstra算法(双标号法）步骤：1.给出点V1以标号(0,s)2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合3.如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则vs到vt的距离为lt，而从vs到vt的最短路径，则可以从kt反向追踪到起点vs而得到。如果vt未标号，则可以断言不存在从vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。4.对上述弧的集合中的每一条弧，计算sij=li+cij。在所有的sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。{(,)|,}ijijvvvIvJ管理运筹学8§2最短路问题例1求下图中v1到v6的最短路解：采用Dijkstra算法，可解得最短路径为v1v3v4v6各点的标号图如下：v23527531512v1v6v5v3v4(3,1)v23527531512V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4管理运筹学9§2最短路问题②③④⑤⑥⑦610123214675811165图6－690,0610129209,2186,1①1612,11716,3243218,32929,5【例】用Dijkstra算法求图6－6所示v1到v7的最短路及最短路长v1到v7的最短路为：p17=｛v1,v2,v3,v5,v7｝，最短路长为L17=2914管理运筹学10【例】求图6-10所示v1到各点的最短路及最短距离①②③④⑤⑥⑦⑧4526178393261216180,04522,13103,4961264,1116,36,318812248,52418,5所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。图6-10§2最短路问题管理运筹学11§2最短路问题例2电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。V1（甲地）1517624431065v2V7（乙地）v3v4v5v6管理运筹学12§2最短路问题例2最终解得：最短路径v1v3v5v6v7，每点的标号见下图（0,s）V1（甲地）1517624431065(13,3)v2(22,6)V7（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)管理运筹学13§2最短路问题例3设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备维修费如下表年份12345年初价格1111121213使用年数0-11-22-33-44-5每年维修费用5681118管理运筹学14§2最短路问题例3的解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。把所有弧的权数计算如下表：v1v2v3v4v5v6123456116223041592162230413172331417235186管理运筹学15§2最短路问题(继上页)把权数赋到图中，再用Dijkstra算法求最短路。最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和v1v4v6v1v2v3v4v5v6162230415916223041312317181723V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)管理运筹学16§2最短路问题6.2.4最短路应用举例【例】设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知4年年初购置新设备的价格分别为2.5、2.6、2.8和3.1万元。设备使用了1～4年后设备的残值分别为2、1.6、1.3和1.1万元，使用时间在1～4年内的维修保养费用分别为0.3、0.8、1.5和2.0万元。试确定一个设备更新策略，在下例两种情形下使4年的设备购置和维护总费用最小。（1）第4年年末设备一定处理掉；（2）第4年年末设备不处理。【解】画网络图。用点(1,i,…,j)表示第1年年初购置设备使用到第i年年初更新，经过若干次更新使用到第j年年初，第1年年初和第5年年初分别用①及⑤表示。使用过程用弧连接起来，弧上的权表示总费用(购置费＋维护费－残值)，如图6－16所示管理运筹学17§2最短路问题①⑤6图6－16(1,2,3)(1,4)(1,3,4)(1,2,4)(1,2,3,4)(1,2)(1,3)第一年第二年第三年第四年5.10.91.50.73.62.81.7-0.21.91.12.10.3-0.6-0.6网络图6－16说明：如图中点(1,3)表示第1年购置设备使用两年到第3年年初更新购置新设备，这时有2种更新方案，使用1年到第4年年初、使用2年到第5年年初,更新方案用弧表示，点（1,2,3）表示第1年购置设备使用一年到第二年年初又更新，使用一年到第三年初再更新，这时仍然有2种更新方案，使用1年到第4年年初和使用2年到第5年年初。管理运筹学18§2最短路问题点（1,3）和点（1,2,3）不能合并成一个点，虽然都是第三年年初购置新设备，购置费用相同，但残值不同。点(1,3)的残值等于1.6(使用了两年)，点(1,2,3)的残值等于2(使用了一年)。点（1,3）到点（1,3,4）的总费用为第三年的购置费＋第一年的维护费－设备使用两年后的残值＝2.8+0.3－1.6=1.5点（1,3）到点⑤的总费用为第三年的购置费＋第一年的维护费＋第二年的维护费－设备使用两年后的残值－第四年末的残值＝2.8+0.3+0.8－1.6－1.6=0.7。管理运筹学19§2最短路问题①⑤6图6－16(1,2,3)(1,4)(1,3,4)(1,2,4)(1,2,3,4)(1,2)(1,3)第一年第二年第三年第四年5.10.91.50.73.62.81.7-0.21.91.12.10.3-0.6-0.6（1）第四年末处理设备：求点①到点⑤的最短路。用Dijkstra算法得到最短路线为：①→(1,2)→(1,2,3)→⑤，最短路长为4。4年总费用最小的设备更新方案是：第1年购置设备使用1年，第2年更新设备使用1年后卖掉，第3年购置设备使用2年到第4年年末，4年的总费用为4万元。管理运筹学20§3最小生成树问题•树是图论中的重要概念，所谓树就是一个无圈的连通图。图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)管理运筹学21可以证明：（1）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。§3最小生成树问题管理运筹学22§3最小生成树问题给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图11-12中，(b)和(c)都是(a)的生成子图。如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在图11-12中，(c)就是(a)的生成树。最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。图11-12(a)(b)(c)管理运筹学23§3最小生成树问题一、求解最小生成树的破圈算法算法的步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。管理运筹学245v1v2v3v4v5v6843752618图6－1【例】用破圈法求图6－1的最小树。图6－4图6－4就是图6－1的最小部分树，最小树长为C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同§3最小生成树问题管理运筹学25§3最小生成树问题例4用破圈算法求图（a）中的一个最小生成树v1331728541034v7v6v5v4v2v13317285434v7v6v5v4v2v133725434v7v6v5v4v2v3v3v31