大学本科运筹学 教程 运筹学第八章 图与网络分析ppt课件.ppt

《大学本科运筹学 教程 运筹学第八章 图与网络分析ppt课件.ppt》由会员分享，可在线阅读，更多相关《大学本科运筹学 教程 运筹学第八章 图与网络分析ppt课件.ppt（61页珍藏版）》请在三一办公上搜索。

1、一、考虑下面给出的不完全初始单纯形表：,1、把上面的表格填写完整；2、按照上面的完整表格，写出此线性规划模型；3、写出初始基可行解和其对应的目标函数值；4、为下一次迭代确定进基变量和出基变量，说明理由，并在表格上标出主元素。5、若解得此模型对偶问题最优解之一y1 = m，试说明其经济意义。,二、求解下列运输问题，说明初始调运表中某变量检验数为负的经济意义。,三、五人翻译五种外文的速度（百个印刷符号/小时）如下表所示：,若规定每人专门负责一个语种的翻译工作，应如何指派，使总的翻译效率最高？,作业：将资金分配看作三阶段的动态过程,可分配资金S1百万元,可分配资金S2,可分配资金S3,分配U1百万元

2、,分配 u2,S4=0,分配 u3,资源分配问题模型,1、设阶段为分配过程（步骤），K=1，2，32、状态变量SK为第K步可供分配的资金数(百万元)3、决策变量UK为分配给第K各项目的资金数4、状态转移方程：SK+1=SK UK5、gK(UK)为UK资金分配给该项目所产生的收益6、fk(Sk)=maxgK + fk+1(SK+1) f4(S4)=0,基本方程,边界条件,1、f4(S4)=0 , fk(Sk)=maxgK(UK) + fk+1(SK+1)2、K=3时， S3 =0,1,2,3,4,=maxg3(U3) + f4(S4),= maxg3 (U3) , U3 =0,1,2,3,4,f

3、3(S3),可分配资金S1百万元,可分配资金S2,可分配资金S3,分配U1百万元,分配 u2,S4=0,分配 u3,2、K=3时， S3 =0,1,2,3,4 U3 =0,1,2,3,4 f3(S3) =maxg3(U3) + f4(S4) = maxg3(U3) ,4,70,70,4,3,70,70,3,2,68,68,2,1,62,62,1,0,38,38,0,4,3,2,1,0,U3,f3(S3),g3(U3),U3 S3,3、K=2时，S2 =0,1,2,3,4,B：分U2，盈利g2(U2),C：分S2 -U2，盈利f3(S3),f2(S2)=maxg2(U2) + f3(S3),3,

4、122,65+38,60+62,50+68,42+70,40+70,2,112,60+38,50+62,42+68,40+70,0,108,50+38,42+62,40+68,0,102,42+38,40+62,0,78,40+38,3、K=1时， S1 =4,甲：分U1 ，盈利g1(U1),乙+丙：分4 U1 ，盈利f2(S2),f1(S1)=maxg1(U1) + f2(S2),3,162,66+78,60+102,48+108,41+112,38+122,资金分配问题最优方案,A ：追加投资3百万元 B ：0 C ：追加投资1百万元 最大盈利162百万元,s.t. X11+ X12 +

5、X13 + X14 + X15 1 ，,X21+ X22 + X23 + X24 + X25 1,X31+ X32 + X33 + X34 + X35 1 ，,X41+ X42 + X43 + X44 + X45 1,70X11+50 X21 + 60X31 + 40X41 30 ，,70 (X11+ X12 ) +50 (X21+ X22 ) + 60 (X31+ X32 ) + 40 (X41+ X42 ) 50 ，,70 (X11+ X12 + X13 ) +50 (X21+ X22 + X23 ) + 60 (X31+ X32 + X33 ) + 40 (X41+ X42 + X43

6、) 70 ，,70 (X11+ X12 + X13 + X14 ) +50 (X21+ X22 + X23 + X24 ) + 60 (X31+ X32 + X33 + X34 ) + 40 (X41+ X42 + X43 + X44 ) 90 ，,70 (X11+ X12 + X13 + X14 + X15 ) +50 (X21+ X22 + X23 + X24 + X25 ) + 60 (X31+ X32 + X33 + X34 + X35 ) + 40 (X41+ X42 + X43 + X44 + X45 ) 110,作业:,minZ=(- cij) xij,minZ=(M - cij

7、) xij其中M是一大的常数,目标函数极大化maxZ=cij xij,第八章 图与网络分析,图论的起源,哥尼斯堡七桥问题,A,B,D,C,A,B,C,D,一笔划问题,V1,V2,V3,V5,V4,中国邮递员问题（管梅谷）,右图为一街道图。点表示街口，线表示街道。 v点处有一邮局。某邮递员从邮局v出发送邮件，需每条街至少经过一次，最后回到邮局。问他应怎样选择路线，才能使走的路程最短？,v,图的基本概念,图: 反映现象之间关系的工具,由点和点间连线组成。如四国单循环制足球邀请赛，以图表示赛制,V1,V2,V3,V4,例:,（V1）,张,林（V2）,孙（V3）,（V4）,李,吴（V6）,王（V5）,

8、郑（V7）,（V1）,张,孙（V2）,林（V3）,（V4）,李,吴（V6）,王（V5）,郑（V7）,若以图表示比赛结果,V1,V2,V3,V4,（V1）,张,王（V2）,孙（V3）,（V4）,李,吴（V6）,林（V5）,郑（V7）,无向图,两点间不带箭头的联线称边 边的集合记为E 点的集合记为V一个由点及边构成的图，称为无向图，记为G=(V, E ),V1,V2,V3,V4,有向图,两点间带箭头的联线称弧 弧的集合记为A一个由点及弧构成的图，称为有向图，记为D=(V, A ),V1,V2,V3,V4,点的次,以点v为端点的边的个数称为点v的次,次为1的点 悬挂点,次为0的点 孤立点,天津,南京

9、,常州,上海,杭州,郑州,连云港,济南,徐州,台北,链和圈,链中，若vi1=vik ，则称此链为一个圈。,一个点边交错的序列(vi1,ei1,vi2 ,ei1, vik-1,eik-1,vik )称为一条联结vi1和vik链。,V1,V2,V3,V5,V4,e1,e3,e2,e4,e5,e6,e7,连通图,图G=(V, E )中，若任何两点之间，至少有一条链，则称G为连通图，否则为不连通图。,路和回路,在有向图中，若点弧交错形成的链中弧方向均相同，则为一条路。有向图中若点弧交错形成的圈中弧方向均相同，则为一条回路。,支撑子图,给定图G=(V, E )，若有图G=(V, E )，使 V = V,

10、 E E ，则G称G是的一个支撑子图。,树,一个无圈的连通图为树。树的性质如下：,必有次为1 的点，称为树叶。树是无回路的连通图，所以任意两点之间有且仅有一条通路，任意去掉一个树枝，树被分成不连通图。,树,树的任意两个顶点间加一条边，构成一个回路，不再成为树。一个连通图有很多树，这些树都是原连通图的部分图，即包括了原连通图的所有顶点。,支撑树,若图T=(V, E )是图G=(V, E )的支撑子图，且G是一个树，则称T是G的一个支撑树。,最小支撑树,在图G=(V, E )中，对每条边 vi, vj 相应给一个数wij，则G为赋权图， wij称为边 vi, vj 上的权。权可表示距离、时间、费用

11、等。,最小支撑树,若T =(V, E )是图G=(V, E )的一个支撑树，则E中所有边的权之和为支撑树T的权。若支撑树T的权 w（ T）是G的所有支撑树的权中最小者，则称T是G的最小支撑树（最小树）。,w12,w25,w23,w34,w45,w15,V1,V2,V3,V5,V4,2,5,4,4,5,3,v1,v2,v3,v4,2,4,3,v1,v2,v3,v4,最小支撑树的避圈法,w（ T）=9,最小支撑树的破圈法,2,5,4,4,5,3,v1,v2,v3,v4,2,5,4,4,5,3,v1,v2,v3,v4,w（ T）=9,例：某大学准备对所属的7个学院办公室计算机联网，可能连通的途径如图

12、，请设计一个铺线方法既能连通7个学院办公室，又使总的线路长度最短。,1,2,3,3,3,7,10,4,w（ T）=19,最短路问题,v1,v8,v7,v6,v5,v4,v3,v2,6,3,4,10,1,4,3,6,6,1,2,2,4,10,v1 6,v1 3,v1 1,v4 11,v5 9,v3 5,v2 6,v510,v5 12,Dijkstra 标号法,使用两种标号给图中每一点vi标号：T标号（Temporary label），P标号（Permanent label）。给vi点一个P标号时，表示从始点vs到vi点的最短路权，此标号不再改变；给vi点一个T标号时，表示从vs到vi点的最短路权

13、的上界，是一种临时标号，没有得到P标号的点都是T标号。计算的每一步就是把某一点的T标号改为P标号，当所有点都得到P标号时，计算结束。,Dijkstra 标号法步骤,1、给始点vs以P标号， P (vs)=0，其余各点给T标号， T（vi）= 2、若vi点为刚得到P标号的点，考虑与vi相邻的另一顶点vj ，且vj为T标号。对vj的T标号进行如下更改： T（ vj ）= min T（vj）, P (vi)+Lij 3、比较所有具有T标号的点，把最小者改为P标号若全部点均为P标号则停止，否则转回第2步。,无向图的Dijkstra 标号法,v1,v9,v8,v7,v6,v5,v4,v3,v2,6,3,

14、3,4,2,10,1,4,3,6,6,2,1,2,2,6,5,3,7,11,10,8,1,9,12,6,11,用最短路解设备更新问题,16,18,22,41,30,22,30,16,59,31,23,17,41,23,17,V1，0,V1，16,V1，22,V1，41,V1，30,V1，59,V2，57,V3，53,V4，53,16,18,22,41,30,22,30,16,59,31,23,17,41,23,17,V1，0,V1，16,V1，22,V1，41,V1，30,V1，59,V2，57,V3，53,V4，53,网络最大流问题,流量,容量,基本概念,1、网络在有向连通图D=(V, A

15、)中， D的每条弧上有非负数的权Cij（弧的容量），且存在一个发点Vs和一个收点Vt ，则称此D为网络。 记为： D=(V, A , C ),vs,v3,v4,v2,v1,vt,2,4,1,1,5,3,2,5,3,2、流,在网络D=(V, A , C )中，对任一弧（vi, vj ）有流量fij，称集合f=fij为网络上的一个流。,vs,v3,v4,v2,v1,vt,（4，3）,（3，3）,（5，1）,（1，1）,（3，0）,（2，2）,（5，3）,（2，1）,Cij,（1，1）,2、流,如：,vs,v3,v4,v2,v1,vt,3,3,1,1,0,2,3,1,1,3、可行流,vs,v3,v4

16、,v2,v1,vt,（4，3）,（3，3）,（5，1）,（1，1）,（3，0）,（2，2）,（5，3）,（2，1）,（1，1）,3、可行流,满足下列条件的流称为可行流。（1）容量限制条件：0 fij Cij（2）平衡条件：对于中间点： 流入的流量=流出的流量对于发点Vs和收点Vt ： Vs的流出量= Vt的流入量,对于一个网络，可行流总存在，如所有fij =0，就是一可行流，v(f)=0。,vs,v3,v4,v2,v1,vt,（4，0）,（3，0）,（5，0）,（1，1）,（3，0）,（2，0）,（5，0）,（2，0）,（1，1）,4、最大流,网络中，从Vs到Vt流量最大的可行流为该网络的最大

17、流。,网络最大流问题,应用范围交通运输网络中，存在人流、车流、货物流，供水供气网络中存在水流、气流，通讯系统中有信息流。最大流问题就是在一定条件下，使网络系统中的某种流的流量达到最大。,有增广链：,vs,v4,v2,v2,vt,（4，3）,（3，2）,（5，2）,（1，1）,（5，3）,（2，1）,vs,v3,v1,vt,（4，2）,（3，2）,（1，1）,（2，1）,v3,（3，3）,（2，2）,（1，0）,5、增广链,在可行流中，,vs,v3,v4,v2,v1,vt,（4，3）,（3，3）,（5，1）,（1，1）,（3，0）,（2，2）,（5，3）,（2，1）,（1，1）,fij = Ci

18、j的弧为饱和弧fij Cij的弧为非饱和弧fij = 0的弧为零流弧fij 0的弧为非零流弧,5、增广链,若是从Vs到Vt的一条链， 弧的方向与链的方向（ VsVt ）一致，称前向弧； 弧的方向与链的方向（ VsVt ）相反，称后向弧；,在可行流f中，是从Vs到Vt的一条链，若满足对于前向弧，有0fij Cij（前向弧为非饱和弧）对于后向弧，有0 fij Cij（后向弧为非零流弧）则称是关于f的一条增广链。,最大流算法的基本思想,增广链定理：一个可行流f是最大流的充分必要条件是没有关于f的增广链。寻找最大流时，从任一可行流开始，寻找这个可行流的一条增广链，增加原可行流的流量，得到一较大的可行流

19、。再找新可行流的增广链，如此继续下去，直到找不到增广链，这时的可行流就是最大流。,最大流的标号法标号寻找增广链,vs,v3,v4,v2,v1,vt,（4，3）,（3，3）,（5，1）,（1，1）,（3，0）,（2，2）,（5，3）,（2，1）,（1，1）,（0，+）,（ vs ，4）,（ -v2 ，1）,（ -v1 ，1）,（ v3 ，1）,（2，2）,（1，0）,（1，0）,（5，2）,来源的点,可调整的量,（ vs ，3）,调整量,调整,最大流标号法步骤,用标号法找增广链,沿调整f ，得f,前向弧： fij= fij +后向弧： fij= fij 非增广链上的弧： fij不变,f是否存在增广链,找到最大流,No,Yes,