运筹学第8章网络规划

1赵明霞山西大学经济与管理学院管理运筹学——模型与方法第8章网络规划28.1图8.2最小树问题8.3最短路问题8.4最大流问题8.5最小费用流问题23图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图8-1就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5图8-1G=(V,E)点集V={v1,v2,v3,...,vm}={1,2,3,…,m}边集E={eij=(vi,vj)}={eij=(i,j)}8.1图4当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图8-2来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5图8-2•结（端）点：vi,vj•关联边，e3•点相邻(同一条边),v1,v3•边相邻(同一个端点),e1,e3环，e2多重边,e3,e4简单图：无环无多重边5图8-2次：结点的关联边数目d(v3)=4，偶点d(v4)=3，奇点d(v2)=5d(v6)=0，孤立点d(v5)=1，悬挂边链：闭链：v1v2v3v1开链：v1v2v3边不同，简单链：v3v1v2v3v4v5边不同且结点不同，初等链：v1v2v3v4v5圈：初等闭链，且至少有3个不同结点，v1v2v3v16ikjkjijiveevev,,,,,,2110ikiiikiivvvvvv1010,,,ikivv0ikivv0图8-27a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图8-3如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图8-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。8连通图：若任何两个不同的点之间，至少存在一条链，则G为连通图。若,则G’是G的子图，G是G’的母图若,则G’是G的真子图，若,则G’是G的支撑图。),(),,('''EVGEVGEEVV'',GG'EEVV'',GG'EEVV'',无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。无向图是有向图的基础图G(D)路：弧（边）的方向与链的方向一致。回路：若路的第一个点和最后一个点相同，则该路为回路。开路赋权图：对一个图的每一条边（弧）(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：赋权连通图92019/12/1510例8-3：柯尼斯堡七桥问题欧拉回路：经过每边且仅一次厄尼斯堡七桥问题、邮路问题充要条件：图中无奇点哈密尔顿回路：经过每点且仅一次货郎担问题、快递送货问题8个节目，首尾为A,H或H,A；10名演员，不连续出演。如何安排？11例8-4节目排序问题节目演员12345678910A√√√√√√B√√√C√√√D√√E√√F√√G√√√H√√√√√1213树是图论中的重要概念，所谓树就是一个无圈的连通图。图8-4中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。图8-4v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)8.2最小树问题14给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的支撑(生成)图。在图8-4中，(b)和(c)都是(a)的支撑图。如果图G的一个支撑图还是一个树，则称这个支撑图为支撑（生成）树，在图8-5中，(c)就是(a)的支撑树。最小支撑（生成）树问题就是指在一个赋权的连通的无向图G中找出一个支撑树，并使得这个支撑树的所有边的权数之和为最小。图8-5(a)(b)(c)树的基本性质1.任意两点间有且仅有一条链2.不相邻两点间添加一条边，有且仅有一个圈3.任意去掉一条边，得不连通图4.存在悬挂点5.边数+1=结点数15最小树的基本性质定理8-1：任意结点i的最小关联边（i,k）必在最小树中。定理8-2：点集V的非空子集,连结两子集的最小边（i,k）必在最小树中。16SSV171、破圈算法步骤：（1）在给定的赋权的连通图上任找一个圈。（2）在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。（3）如果所余下的图已不包含圈，则计算结束，所余下的图即为最小树，否则返回第1步。18例8-52、避圈算法步骤：（1）任找一个点S，其余各点就是。（2）在连接S与的所有边中，选择权数最小的边(i,k)；（3）将最小边(i,k)的另一个端点移入S；（4）若则停止，否则返回（2）。19SSS20例8-521最短路问题：对一个网络中的指定的两个点Vs(起点)和Vt（终点）找到一条从Vs到Vt的路，使得这条路上所有弧（边）的权数总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧（路）的权数总和被称为从Vs到Vt的距离。8.3最短路问题22适用于：每条弧（边）的赋权数wij≥0优点：能够求出某点至各点的最短路基本思想：P(j)——从始点s到j点的最短路长，称为固定标号；T(j)——从始点s到j点的最短路长上界，称为临时标号。基本步骤1、狄氏标号法（Dijkstra）23例8-624例8-7设备更新问题。某厂拟于明年购置一台设备，以后每年年初都要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个今后五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。年份i，使用年数k12345年初价格pi/万元89111419当年维护费ck/万元136112025解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v6123456191218294921013193031215214151852026把权数赋到图中，再用Dijkstra算法求最短路。v1v2v3v4v5v691218294910131930211515201218(0)(9)(12)(18)(27)(33)27适用于：每条弧的赋权数wij-∞优点：通用有效方法（直接）距离矩阵2、矩阵摹乘法nnijwW)(例8-8各点至某点的最短路求和取小28()()(1)1(1,2,,)min{}(1,2,,)kirkkirijjrjndikrindwdin从点走步到达点的最短距离1,(2,3,,)kkdWdkn1nndd1,(2,3,,1)kkddkn29\1234510342045301243205210从至15*20d例8-8（各点至5的最短路）222230d312200d412200d12351235235242350550最短路最短路长某点至各点的最短路求和取小30()()(1)1(1,2,,)min{}(1,2,,)krjkkrjriijinlrkjjnllwjn从点走步到达点的最短距离1,(2,3,,1)TTkkllWkn1,(2,3,,1)TTkkllkn31\1234510342045301243205210从至例8-8（1至各点的最短路）11012312311234012354012351最短路最短路长1=(034)Tl2=(03132)Tl3(03101)Tl4(03101)Tl各点间的最短距离32()1()(1)(1)12(,1,2,,)min{}(,1,2,,)kkijkkkijissjsndijijndddijn从点走步到达点的最短距离()111,(2,3,,)kkijkkDdDDkpDW1,(2,3,,)kkDDkplg(1)1lg2npp迭代次数例8-9（求各村间的最短距离）3310346307540266720155101465102420DW直接距离矩阵lg(71)2.6lg2p34211034671030765694702368=6620125753101310662102985320DDD3220346781030765684702346=66201247531013864210210864320DDD网络中心（r点）网络重心（r点）351()max(),(11,2,,)ijjndidn1()min()indrdi11(),(1,2,,)()min{()}niijijnhjgdjnhrhj36例8-10（1）商店建在哪个村，使各村都离他较近？（2）小学应建在哪个村，使各村小学生走路总里程最少？村庄1234567小学生人数35202530504540371234567()max()10346781010230765688347023467466201246(min)57531013768642102871086432010ijjdid（1）38123456710105140210245280350260014012010012016031001750507510015041801806003060120535025015050050150634027018090450907400320240160120800()143013009106806156901020iijgdhj（2）398.4最大流问题最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。一、最大流的数学模型例8.1某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图11-2640我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：1412232514434647234335362535573646675767471214,1,2,,6;1,2,70,1,2,,6;1,2,712ijijijmaxF=fffffffffffffffffffffffffcijfij目标函数：约束条件：41在这个线性规划模型中，其•约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；•其余的点称之为中间点，它的总流入量必须等于总流出量。•后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(v