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

一、考虑下面给出的不完全初始单纯形表：C63025000θcBxBbX1X2X3X4X5X6

40310100

50021010

2021-1001

σ

1、把上面的表格填写完整；2、按照上面的完整表格，写出此线性规划模型；3、写出初始基可行解和其对应的目标函数值；4、为下一次迭代确定进基变量和出基变量，说明理由，并在表格上标出主元素。5、若解得此模型对偶问题最优解之一y1﹡=m，试说明其经济意义。一、考虑下面给出的不完全初始单纯形表：C63025000θc1二、求解下列运输问题，说明初始调运表中某变量检验数为负的经济意义。销地产地B1B2B3B4产量A1A283741642088A3571062销量5526

二、求解下列运输问题，说明初始调运表中某变量检验数为负的经济2三、五人翻译五种外文的速度（百个印刷符号/小时）如下表所示：语种人英俄日德法甲乙98456981056丙97358丁48695戊653108若规定每人专门负责一个语种的翻译工作，应如何指派，使总的翻译效率最高？三、五人翻译五种外文的速度（百个印刷符号/小时）如下表所示：3作业：将资金分配看作三阶段的动态过程1(项目A)2(项目B)3(项目C)可分配资金S1百万元可分配资金S2可分配资金S3分配U1百万元分配u2S4=0分配u3作业：将资金分配看作三阶段的动态过程1(项目A)2(项目B4资源分配问题模型1、设阶段为分配过程（步骤），K=1，2，32、状态变量SK为第K步可供分配的资金数(百万元)3、决策变量UK为分配给第K各项目的资金数4、状态转移方程：SK+1=SK－UK5、gK(UK)为UK资金分配给该项目所产生的收益6、fk(Sk)=max{gK+fk+1(SK+1)}

f4(S4)=0基本方程边界条件资源分配问题模型1、设阶段为分配过程（步骤），K=1，2，351、f4(S4)=0,fk(Sk)=max{gK(UK)+fk+1(SK+1)}2、K=3时，S3=0,1,2,3,4=max{g3(U3)+f4(S4)}=max[g3(U3)]∴U3=0,1,2,3,4f3(S3)1(项目A)2(项目B)3(项目C)可分配资金S1百万元可分配资金S2可分配资金S3分配U1百万元分配u2S4=0分配u31、f4(S4)=0,fk(Sk)62、K=3时，

S3=0,1,2,3,4U3=0,1,2,3,4

f3(S3)

=max{g3(U3)

+f4(S4)}

=max[g3(U3)]

47070437070326868216262103838043210U3﹡f3(S3)g3(U3)U3

S301234A3841486066B4042506065C38626870702、K=3时，

S3=0,1,2,3,473、K=2时，S2=0,1,2,3,4

B：分U2，盈利g2(U2)

C：分S2-U2，盈利f3(S3)

f2(S2)=max{g2(U2)+f3(S3)}312265+3860+6250+6842+7040+70211260+3850+6242+6840+70010850+3842+6240+68010242+3840+6207840+384321043210U2﹡f2(S2)g2(U2)+f3(S3)U2

S2S3f3(S3)U3﹡0380162126823703470401234A3841486066B4042506065C38626870703、K=2时，B：分U2，盈利g2(U2)C：分S2-U83、K=1时，

S1=4

甲：分U1，盈利g1(U1)

乙+丙：分4

–U1，盈利f2(S2)

f1(S1)=max{g1(U1)+f2(S2)}316266+7860+10248+10841+11238+122443210U1﹡f1(S1)g1(U1)+f2(S2)U1

S1S3f3(S3)U3﹡07801102021080311224122301234A3841486066B4042506065C38626870703、K=1时，

S1=4

甲：分U9资金分配问题最优方案A：追加投资3百万元B：0C：追加投资1百万元

最大盈利162百万元资金分配问题最优方案A：追加投资3百万元10s.t.X11+X12+

X13+

X14+

X15≤1

，

X21+X22+

X23+

X24+

X25≤1X31+X32+

X33+

X34+

X35≤1

，

设xij=1第i电厂在第j年投资0第i电厂在第j年不投资X41+X42+

X43+

X44+

X45≤170X11+50X21+

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)

≥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

s.t.X11+X12+X13+X14+11作业:9468585910697358486951053681642525104137526241505742作业:94685859106973584869510536812minZ′=∑∑(-cij)xijminZ〞=∑∑(M-cij)xij其中M是一大的常数目标函数极大化maxZ=∑∑cijxij0310234003115406020303530minZ′=∑∑(-cij)xijminZ〞=∑∑(M13第八章图与网络分析第八章图与网络分析14图论的起源哥尼斯堡七桥问题ABDCABCD图论的起源哥尼斯堡七桥问题ABDCABCD15一笔划问题V1V2V3V5V4一笔划问题V1V2V3V5V416中国邮递员问题（管梅谷）右图为一街道图。点表示街口，线表示街道。v点处有一邮局。某邮递员从邮局v出发送邮件，需每条街至少经过一次，最后回到邮局。问他应怎样选择路线，才能使走的路程最短？v中国邮递员问题（管梅谷）右图为一街道图。点表示街口，线表示街17图的基本概念图:反映现象之间关系的工具,由点和点间连线组成。如四国单循环制足球邀请赛，以图表示赛制V1V2V3V4图的基本概念图:反映现象之间关系的工具,由点和点间连线组18例:（V1）张林（V2）孙（V3）（V4）李吴（V6）王（V5）郑（V7）例:（V1）张林（V2）孙（V3）（V4）李吴（V6）王（V19（V1）张孙（V2）林（V3）（V4）李吴（V6）王（V5）郑（V7）（V1）张孙（V2）林（V3）（V4）李吴（V6）王（V5）20若以图表示比赛结果V1V2V3V4若以图表示比赛结果V1V2V3V421（V1）张王（V2）孙（V3）（V4）李吴（V6）林（V5）郑（V7）（V1）张王（V2）孙（V3）（V4）李吴（V6）林（V5）22无向图两点间不带箭头的联线称边边的集合记为E点的集合记为V一个由点及边构成的图，称为无向图，记为G=(V,E

)V1V2V3V4无向图两点间不带箭头的联线称边V1V2V3V423有向图两点间带箭头的联线称弧弧的集合记为A一个由点及弧构成的图，称为有向图，记为D=(V,A

)V1V2V3V4有向图两点间带箭头的联线称弧V1V2V3V424点的次以点v为端点的边的个数称为点v的次次为1的点——悬挂点

次为0的点——孤立点天津南京常州上海杭州郑州连云港济南徐州台北点的次以点v为端点的边的个数称为点v的次次为1的点次为0的点25链和圈链中，若vi1=vik，则称此链为一个圈。一个点边交错的序列(vi1,ei1,vi2,ei1,…vik-1,eik-1,vik)称为一条联结vi1和vik链。V1V2V3V5V4e1e3e2e4e5e6e7链和圈链中，若vi1=vik，则称此链为一个圈。一个点边交26连通图图G=(V,E

)中，若任何两点之间，至少有一条链，则称G为连通图，否则为不连通图。连通图图G=(V,E)中，若任何两点之间，至少有一条链，27路和回路在有向图中，若点弧交错形成的链中弧方向均相同，则为一条路。有向图中若点弧交错形成的圈中弧方向均相同，则为一条回路。v7v6v5v4v3v26341014366122410v8v1路和回路在有向图中，若点弧交错形成的链中弧方向均相同，则为一28支撑子图给定图G=(V,E

)，若有图G′=(V′,E′

)，使V′=V,E′∈E，则G′称G是的一个支撑子图。V1V2V3V5V4e1e3e2e4e5e6e7V1V2V3V5V4e1e3e2e5e6支撑子图给定图G=(V,E)，若有图G′=(V′,E′29树一个无圈的连通图为树。树的性质如下：必有次为1的点，称为树叶。树是无回路的连通图，所以任意两点之间有且仅有一条通路，任意去掉一个树枝，树被分成不连通图。天津南京常州上海郑州连云港济南徐州树一个无圈的连通图为树。树的性质如下：必有次为1的点，称为30树树的任意两个顶点间加一条边，构成一个回路，不再成为树。一个连通图有很多树，这些树都是原连通图的部分图，即包括了原连通图的所有顶点。天津南京常州上海郑州连云港济南徐州树树的任意两个顶点间加一条边，构成一个回路，不再成为树。天津31支撑树若图T=(V,E′

)是图G=(V,E

)的支撑子图，且G′是一个树，则称T是G的一个支撑树。V1V2V3V5V4e1e3e2e4e5e6e7V1V2V3V5V4e1e2e4e5支撑树若图T=(V,E′)是图G=(V,E)的支撑子32最小支撑树在图G=(V,E

)中，对每条边[vi,vj]相应给一个数wij，则G为赋权图，wij称为边[vi,vj]上的权。权可表示距离、时间、费用等。w12w25w23w34w45w15V1V2V3V5V4w25最小支撑树在图G=(V,E)中，对每条边[vi,vj33最小支撑树若T

=(V,E′

)是图G=(V,E

)的一个支撑树，则E′中所有边的权之和为支撑树T的权。若支撑树T﹡的权w（T﹡）是G的所有支撑树的权中最小者，则称T﹡是G的最小支撑树（最小树）。w12w25w23w34w45w15V1V2V3V5V4w25最小支撑树若T=(V,E′)是图G=(V,E)的一34w12w23w45w15V1V2V3V5V4w12w23w34w45V1V2V3V5V4w12w23w34V1V2V3V5V4w25w12w25w23w34w45w15V1V2V3V5V4w12w23w45w15V1V2V3V5V4w12w23w335254453v1v2v3v4243v1v2v3v4最小支撑树的避圈法w（T﹡）=9254453v1v2v3v4243v1v2v3v4最小支撑树36最小支撑树的破圈法254453v1v2v3v4254453v1v2v3v4w（T﹡）=9最小支撑树的破圈法254453v1v2v3v4254453v37例：某大学准备对所属的7个学院办公室计算机联网，可能连通的途径如图，请设计一个铺线方法既能连通7个学院办公室，又使总的线路长度最短。v1v2v3v4v5v6125333748v7104例：某大学准备对所属的7个学院办公室计算机联网，可能连通的途38v1v2v3v4v5v6125333748v7123337v1v2v3v4v5v6v7104w（T﹡）=19v1v2v3v4v5v6125333748v7123337v39最短路问题v1v8v7v6v5v4v3v26341014366122410﹢∞﹢∞﹢∞﹢∞﹢∞﹢∞﹢∞＼v16v13v11v411v59v35v26v510v512＼＼＼＼＼＼＼＼0最短路问题v1v8v7v6v5v4v3v263410143640Dijkstra标号法•使用两种标号给图中每一点vi标号：T标号（Temporarylabel），P标号（Permanentlabel）。•给vi点一个P标号时，表示从始点vs到vi点的最短路权，此标号不再改变；给vi点一个T标号时，表示从vs到vi点的最短路权的上界，是一种临时标号，没有得到P标号的点都是T标号。•计算的每一步就是把某一点的T标号改为P标号，当所有点都得到P标号时，计算结束。Dijkstra标号法•使用两种标号给图中每一点vi标号：41Dijkstra标号法步骤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标号法步骤1、给始点vs以P标号，P(42无向图的Dijkstra标号法v1v9v8v7v6v5v4v3v26334210143662122﹢∞＼65＼﹢∞3＼﹢∞＼﹢∞7＼﹢∞1110＼＼﹢∞8＼1﹢∞9＼﹢∞12＼＼6＼110无向图的Dijkstra标号法v1v9v8v7v6v5v443用最短路解设备更新问题v1v2v3v4v5v6161822413022301659312317412317V1，0V1，16V1，22V1，41V1，30V1，59V2，57V3，53V4，53年数0-11-22-33-44-5费用5681118年份12345价格1111121213用最短路解设备更新问题v1v2v3v4v5v6161822444v1v2v3v4v5v6161822413022301659312317412317V1，0V1，16V1，22V1，41V1，30V1，59V2，57V3，53V4，53v1v2v3v4v5v616182241302230165945网络最大流问题vsv4v2vt（4，3）（3，2）（5，2）（1，1）（5，3）（2，1）v3v1（4，2）例：流量容量网络最大流问题vsv4v2vt（4，3）（3，2）（5，2）46基本概念1、网络在有向连通图D=(V,A

)中，D的每条弧上有非负数的权Cij（弧的容量），且存在一个发点Vs和一个收点Vt，则称此D为网络。记为：D=(V,A,C

)vsv3v4v2v1vt241153253基本概念1、网络vsv3v4v2v1vt241153253472、流在网络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、流在网络D=(V,A,C)中，对任一弧（vi,482、流如：vsv3v4v2v1vt3311023112、流如：vsv3v4v2v1vt3493、可行流vsv3v4v2v1vt（4，3）（3，3）（5，1）（1，1）（3，0）（2，2）（5，3）（2，1）（1，1）（3，4）（5，2）3、可行流vsv3v4v2v1vt（4，3）（3，3）（5，503、可行流满足下列条件的流称为可行流。（1）容量限制条件：0≤fij≤Cij（2）平衡条件：对于中间点：流入的流量=流出的流量对于发点Vs和收点Vt：Vs的流出量=Vt的流入量对于一个网络，可行流总存在，如所有fij=0，就是一可行流，v(f)=0。3、可行流满足下列条件的流称为可行流。对于一个网络，可行流总51vsv3v4v2v1vt（4，0）（3，0）（5，0）（1，1）（3，0）（2，0）（5，0）（2，0）（1，1）vsv3v4v2v1vt（4，0）（3，0）（5，0）（1，524、最大流网络中，从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）4、最大流网络中，从Vs到Vt流量最大的可行流为该网络的最大53网络最大流问题应用范围交通运输网络中，存在人流、车流、货物流，供水供气网络中存在水流、气流，通讯系统中有信息流…。最大流问题就是在一定条件下，使网络系统中的某种流的流量达到最大。网络最大流问题应用范围54有增广链：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）有增广链：vsv4v2v2vt（4，3）（3，2）（5，2）555、