《大学本科运筹学教程运筹学第八章图与网络分析ppt课件》由会员分享，可在线阅读，更多相关《大学本科运筹学教程运筹学第八章图与网络分析ppt课件（61页珍藏版）》请在金锄头文库上搜索。
1、一、考虑下面给出的不完全初始单纯形表：C63025000cBxBbX1X2X3X4X5X640310100500210102021-10011、把上面的表格填写完整；2、按照上面的完整表格，写出此线性规划模型；3、写出初始基可行解和其对应的目标函数值；4、为下一次迭代确定进基变量和出基变量，说明理由，并在表格上标出主元素。5、若解得此模型对偶问题最优解之一y1=m，试说明其经济意义。二、求解下列运输问题，说明初始调运表中某变量检验数为负的经济意义。销地产地B1B2B3B4产量A1A283741642088A3571062销量5526三、五人翻译五种外文的速度（百个印刷符号/小时）如下表所示：语
2、种人英俄日德法甲乙98456981056丙97358丁48695戊653108若规定每人专门负责一个语种的翻译工作，应如何指派，使总的翻译效率最高？作业：将资金分配看作三阶段的动态过程作业：将资金分配看作三阶段的动态过程1(项目项目A)2 (项目项目B)3 (项目项目C)可分配可分配资金资金S1百万元百万元可分配可分配资金资金S2可分配可分配资金资金S3分配分配U1百百万元万元分配分配 u2S4=0分配分配 u3资源分配问题模型资源分配问题模型1、设阶段为分配过程（步骤），、设阶段为分配过程（步骤），K=1，2，32、状态变量状态变量SK为第为第K步可供分配的资金数步可供分配的资金数(百万元百
3、万元)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 f3(S3)1(项目项目A)2 (项目项目B)3 (项目
4、项目C)可分配可分配资金资金S1百万元百万元可分配可分配资金资金S2可分配可分配资金资金S3分配分配U1百百万元万元分配分配 u2S4=0分配分配 u32、K=3时，时， S3 =0,1,2,3,4 U3 =0,1,2,3,4 f3(S3) =maxg3(U3) + f4(S4) = maxg3(U3) 47070437070326868216262103838043210U3f3(S3)g3(U3) U3 S301234A3841486066B4042506065C38626870703、K=2时，时，S2 =0,1,2,3,4 B：分：分U2，盈利盈利g2(U2) C：分：分S2 -U2，
5、盈利盈利f3(S3) f2(S2)=maxg2(U2) + f3(S3)312265+3860+6250+6842+7040+70211260+3850+6242+6840+70010850+3842+6240+68010242+3840+6207840+384321043210U2f2(S2)g2(U2) + f3(S3) U2 S2 S3f3(S3)U30380162126823703470401234A3841486066B4042506065C38626870703、K=1时，时，S1 =4甲：分甲：分U1 ，盈利盈利g1(U1) 乙乙+丙：分丙：分4 U1 ，盈利盈利f2(S2) f
6、1(S1)=maxg1(U1) + f2(S2)316266+7860+10248+10841+11238+122443210U1f1(S1)g1(U1) + f2(S2) U1 S1 S3f3(S3)U307801102021080311224122301234A3841486066B4042506065C3862687070资金分配问题最优方案资金分配问题最优方案A ：追加投资追加投资3百万元百万元 B ：0 C ：追加投资追加投资1百万元百万元 最大盈利最大盈利162百万元百万元s.t. X11+ X12 + X13 + X14 + X15 1 ， X21+ X22 + X23 + X2
7、4 + X25 1X31+ X32 + X33 + X34 + X35 1 ， 设设xij=1 第第i电厂在第电厂在第j年投资年投资0 第第i电厂在第电厂在第j年不投资年不投资X41+ X42 + X43 + X44 + X45 170X11+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
8、 + X43 ) 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 作业作业:9468585910697358486951
9、053681642525104137526241505742minZ=(- cij) xijminZ=(M - cij) xij其中其中M是一大的是一大的常数常数 目标函数极大化目标函数极大化maxZ=cij xij0310234003115406020303530第八章第八章 图与网络分析图与网络分析图论的起源图论的起源哥尼斯堡七桥问题ABDCABCD一笔划问题一笔划问题V1V2V3V5V4中国邮递员问题（管梅谷）中国邮递员问题（管梅谷）右图为一街道图。点表右图为一街道图。点表示街口，线表示街道。示街口，线表示街道。 v点处有一邮局。某邮点处有一邮局。某邮递员从邮局递员从邮局v出发送邮出发送
10、邮件，需每条街至少经件，需每条街至少经过一次，最后回到邮过一次，最后回到邮局。问他应怎样选择局。问他应怎样选择路线，才能使走的路路线，才能使走的路程最短？程最短？v图图的基本概念的基本概念图图: 反映现象之间关系的工具反映现象之间关系的工具,由点和点间由点和点间连线组成。连线组成。如四国单循环制足球邀请赛，以图表示赛制如四国单循环制足球邀请赛，以图表示赛制V1V2V3V4例例:（V1）张张林（林（V2）孙（孙（V3）（V4）李李吴（吴（V6）王（王（V5）郑（郑（V7）（V1）张张孙（孙（V2）林（林（V3）（V4）李李吴（吴（V6）王（王（V5）郑（郑（V7）若以图表示比赛结果若以图表示比赛
11、结果V1V2V3V4（V1）张张王（王（V2）孙（孙（V3）（V4）李李吴（吴（V6）林（林（V5）郑（郑（V7）无向图无向图两点间不带箭头的联线两点间不带箭头的联线称称边边 边的集合记为边的集合记为E 点的集合记为点的集合记为V一个由点及边构成的图，一个由点及边构成的图，称为称为无向图无向图，记为，记为G=(V, E )V1V2V3V4有向图有向图两点间带箭头的联线称两点间带箭头的联线称弧弧 弧的集合记为弧的集合记为A一个由点及弧构成的图，一个由点及弧构成的图，称为称为有向图有向图，记为，记为D=(V, A )V1V2V3V4点的次点的次以点以点v为端点的边的个为端点的边的个数称为数称为点点
12、v的次的次次为次为1的点的点 悬挂点悬挂点 次为次为0的点的点 孤立点孤立点天津天津南京南京常州常州上海上海杭州杭州郑州郑州连云港连云港济南济南徐州徐州台北台北链和圈链和圈链中，若链中，若vi1=vik ，则称此链为一个则称此链为一个圈。圈。一个点边交错的序列一个点边交错的序列(vi1,ei1,vi2 ,ei1, vik-1,eik-1,vik )称为称为一条联结一条联结vi1和和vik链。链。V1V2V3V5V4e1e3e2e4e5e6e7连通图连通图图图G=(V, E )中，若任何两点之间，至少中，若任何两点之间，至少有一条链，则称有一条链，则称G为为连通图连通图，否则为，否则为不不连通图
13、连通图。路和回路在有向图中，若点弧交错形成的链中弧在有向图中，若点弧交错形成的链中弧方向均相同，则为一条方向均相同，则为一条路路。有向图中若点弧交错形成的圈中弧方向有向图中若点弧交错形成的圈中弧方向均相同，则为一条均相同，则为一条回路回路。v7v6v5v4v3v26341014366122410v8v1支撑子图给定图给定图G=(V, E )，若有图若有图G=(V, E )，使使 V = V, E E ，则，则G称称G是的一个是的一个支撑子图支撑子图。V1V2V3V5V4e1e3e2e4e5e6e7V1V2V3V5V4e1e3e2e5e6树树一个无圈的连通图为一个无圈的连通图为树树。树的性质如下
14、：。树的性质如下：必有次为必有次为1 的点，称的点，称为为树叶树叶。树是无回路的连通图，树是无回路的连通图，所以任意两点之间有所以任意两点之间有且仅有一条通路，任且仅有一条通路，任意去掉一个树枝，树意去掉一个树枝，树被分成不连通图。被分成不连通图。天津天津南京南京常州常州上海上海郑州郑州连云港连云港济南济南徐州徐州树树树的任意两个顶点树的任意两个顶点间加一条边，构成间加一条边，构成一个回路，不再成一个回路，不再成为树。为树。一个连通图有很多一个连通图有很多树，这些树都是原树，这些树都是原连通图的部分图，连通图的部分图，即包括了原连通图即包括了原连通图的所有顶点。的所有顶点。天津天津南京南京常州
15、常州上海上海郑州郑州连云港连云港济南济南徐州徐州支撑树支撑树若图若图T=(V, E )是图是图G=(V, E )的支撑子图，的支撑子图，且且G是一个树，则称是一个树，则称T是是G的一个的一个支撑树支撑树。V1V2V3V5V4e1e3e2e4e5e6e7V1V2V3V5V4e1e2e4e5最小支撑树最小支撑树在图在图G=(V, E )中，中，对每条边对每条边 vi, vj 相相应给一个数应给一个数wij，则，则G为为赋权图赋权图， wij称称为边为边 vi, vj 上的权。上的权。权可表示距离、时权可表示距离、时间、费用等。间、费用等。w12w25w23w34w45w15V1V2V3V5V4w2
16、5最小支撑树最小支撑树若若T =(V, E )是图是图G=(V, E )的一个支撑的一个支撑树，则树，则E中所有边的中所有边的权之和为支撑树权之和为支撑树T的的权。权。若支撑树若支撑树T的权的权 w（ T）是）是G的所有支的所有支撑树的权中最小者，撑树的权中最小者，则称则称T是是G的的最小支最小支撑树（最小树）撑树（最小树）。w12w25w23w34w45w15V1V2V3V5V4w25w12w23w45w15V1V2V3V5V4w12w23w34w45V1V2V3V5V4w12w23w34V1V2V3V5V4w25w12w25w23w34w45w15V1V2V3V5V4254453v1v2v
17、3v4243v1v2v3v4最小支撑树的避圈法最小支撑树的避圈法w（ T）=9最小支撑树的破圈法最小支撑树的破圈法254453v1v2v3v4254453v1v2v3v4w（ T）=9例：某大学准备对所属的例：某大学准备对所属的7个学院办公室计算机联个学院办公室计算机联网，可能连通的途径如图，请设计一个铺线方法网，可能连通的途径如图，请设计一个铺线方法既能连通既能连通7个学院办公室，又使总的线路长度最短。个学院办公室，又使总的线路长度最短。v1v2v3v4v5v6125333748v7104v1v2v3v4v5v6125333748v7123337v1v2v3v4v5v6v7104w（ T）=
18、19最短路问题最短路问题v1v8v7v6v5v4v3v26341014366122410v1 6v1 3v1 1v4 11v5 9v3 5v2 6v510v5 120Dijkstra 标号法标号法使用两种标号给图中每一点使用两种标号给图中每一点vi标号：标号：T标号标号（Temporary label），），P标号（标号（Permanent label）。）。给给vi点一个点一个P标号时，表示从始点标号时，表示从始点vs到到vi点的点的最短路权，此标号不再改变；给最短路权，此标号不再改变；给vi点一个点一个T标号时，表示从标号时，表示从vs到到vi点的最短路权的上界，点的最短路权的上界，是一种
19、临时标号，没有得到是一种临时标号，没有得到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（v
20、j）, P (vi)+Lij 3、比较所有具有比较所有具有T标号的点，把最小者改为标号的点，把最小者改为P标号标号若全部点均为若全部点均为P标号则停止，否则转回第标号则停止，否则转回第2步。步。无向图的无向图的Dijkstra 标号法标号法v1v9v8v7v6v5v4v3v26334210143662122 6537 11 1081912 6110用最短路解设备更新问题用最短路解设备更新问题v1v2v3v4v5v6161822413022301659312317412317V1，0V1，16V1，22V1，41V1，30V1，59V2，57V3，53V4，53年数年数0-11-22-33-44
21、-5费用费用5681118年份年份12345价格价格1111121213v1v2v3v4v5v6161822413022301659312317412317V1，0V1，16V1，22V1，41V1，30V1，59V2，57V3，53V4，53网络最大流问题网络最大流问题vsv4v2vt（4，3）（3，2）（5，2）（1，1）（5，3）（2，1）v3v1（4，2）例：例：流量流量容量容量基本概念基本概念1、网络网络在有向连通图在有向连通图D=(V, A )中，中， D的每条弧上有非负的每条弧上有非负数的权数的权Cij（弧的容量），且存在一个发点弧的容量），且存在一个发点Vs和一和一个收点个收点
22、Vt ，则称此则称此D为为网络。网络。 记为：记为： D=(V, A , C )vsv3v4v2v1vt2411532532、流、流在在网络网络D=(V, A , C )中，对任一弧（中，对任一弧（vi, vj ）有）有流量流量fij，称集合称集合f=fij为网络上的一为网络上的一个流个流。vsv3v4v2v1vt（4，3）（3，3）（5，1）（1，1）（3，0）（2，2）（5，3）（2，1）Cij（1，1）2、流、流如：如：vsv3v4v2v1vt 3 3 1 1 0 2 3 1 13、可行流、可行流vsv3v4v2v1vt（4，3）（3，3）（5，1）（1，1）（3，0）（2，2）（5，3
23、）（2，1）（1，1）（3，4）（5，2）3、可行流、可行流满足下列条件的流称为满足下列条件的流称为可行流可行流。（1）容量限制条件：）容量限制条件：0 fij Cij（2）平衡条件：平衡条件：对于中间点：对于中间点： 流入的流量流入的流量=流出的流量流出的流量对于发点对于发点Vs和收点和收点Vt ： Vs的流出量的流出量= Vt的流入量的流入量对于一个网络，可行流总存在，如所有对于一个网络，可行流总存在，如所有fij =0，就是一可行流，就是一可行流，v(f)=0。vsv3v4v2v1vt（4，0）（3，0）（5，0）（1，1）（3，0）（2，0）（5，0）（2，0）（1，1）4、最大流、最
24、大流网络中，从网络中，从Vs到到Vt流量最大的可行流为流量最大的可行流为该网络的该网络的最大流最大流。vsv4vt（4，3）（3，2）（5，2）（1，1）（5，3）（2，1）v3v1（4，2）v2v4vt（4，3）（3，3）（5，2）（1，0）（5，3）v3v1（4，2）v2vs（2，2）网络最大流问题网络最大流问题应用范围应用范围交通运输网络中，存在人流、车流、货物交通运输网络中，存在人流、车流、货物流，供水供气网络中存在水流、气流，流，供水供气网络中存在水流、气流，通讯系统中有信息流通讯系统中有信息流。最大流问题就。最大流问题就是在一定条件下，使网络系统中的某种是在一定条件下，使网络系统中
25、的某种流的流量达到最大。流的流量达到最大。有增广链：vsv4v2v2vt（4，3）（3，2）（5，2）（1，1）（5，3）（2，1）vsv3v1vt（4，2）（3，2）（1，1）（2，1）v3（3，3）（2，2）（1，0）5、增广链、增广链在可行流中，vsv3v4v2v1vt（4，3）（3，3）（5，1）（1，1）（3，0）（2，2）（5，3）（2，1）（1，1）fij = Cij的弧为的弧为饱和弧饱和弧fij Cij的弧为的弧为非饱和弧非饱和弧fij = 0的的弧为弧为零流弧零流弧fij 0的的弧为弧为非零流弧非零流弧5、增广链、增广链若若是从是从Vs到到Vt的一条链，的一条链， 弧的方向与
26、链的方向（弧的方向与链的方向（ VsVt ）一致，称一致，称前向弧前向弧； 弧的方向与链的方向（弧的方向与链的方向（ VsVt ）相反，称相反，称后向弧后向弧；v2vsvt（3，2）（1，1）（2，1）v3在可行流在可行流f中，中，是从是从Vs到到Vt的一条链，若的一条链，若满足满足对于前向弧，有对于前向弧，有0fij Cij（前向弧为非饱和弧）前向弧为非饱和弧）对于后向弧，有对于后向弧，有0 fij Cij（后向弧为非零流弧）后向弧为非零流弧）则称则称是关于是关于f的一条的一条增广链增广链。v2vsvt（3，2）（1，1）（2，1）v3最大流算法的基本思想最大流算法的基本思想增广链定理：一个
27、可行流增广链定理：一个可行流f是最大流的充是最大流的充分必要条件是没有关于分必要条件是没有关于f的增广链。的增广链。寻找最大流时，从任一可行流开始，寻寻找最大流时，从任一可行流开始，寻找这个可行流的一条增广链，增加原可找这个可行流的一条增广链，增加原可行流的流量，得到一较大的可行流。再行流的流量，得到一较大的可行流。再找新可行流的增广链，如此继续下去，找新可行流的增广链，如此继续下去，直到找不到增广链，这时的可行流就是直到找不到增广链，这时的可行流就是最大流。最大流。最大流的标号法最大流的标号法标号寻找增广链标号寻找增广链vsv3v4v2v1vt（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
