管理运筹学第七章网络优化模型

管理运筹学第七章网络优化模型第1页，课件共57页，创作于2023年2月哥尼斯堡七桥问题ABDC简捷表示事物之间的本质联系，归纳事物之间的一般规律ACDB第2页，课件共57页，创作于2023年2月在一个人群中，对相互认识这个关系我们可以用图来表示。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e57.1图与网络的基本概念第3页，课件共57页，创作于2023年2月4

当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用下图来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5第4页，课件共57页，创作于2023年2月5a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈

如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。第5页，课件共57页，创作于2023年2月7.1图与网络的基本概念7.1.1图与网络的概念及分类1、图：图由点和边组成G=(V,E)点集V={vi}边集E={ei}vjvie每一条边和两个端点关联，一条边可以用两个端点表示（vi，vj）边数：m(G)=|E|点数：n(G)=|V|

第6页，课件共57页，创作于2023年2月7.1图与网络的基本概念无向边：有向边：无向图：由无向边构成的图有向图：由有向边构成的图2、无向图和有向图第7页，课件共57页，创作于2023年2月7.1图与网络的基本概念3、简单图和多重图环：e9

多重边：e6和e7简单图：不含环和多重边多重图：含多重边第8页，课件共57页，创作于2023年2月判断下列哪些图是简单图，哪些图是多重图？7.1图与网络的基本概念第9页，课件共57页，创作于2023年2月7.1图与网络的基本概念4、次：以点v为端点的边数叫做点v的次，d(v)

奇点：次为奇数 偶点：次为偶数悬挂点：d(v)=1 孤立点:d(v)=0定理7.1：任何图，Σd(vi)=2m定理7.2：任何图，奇点有偶数个第10页，课件共57页，创作于2023年2月7.1图与网络的基本概念出次d+(vi)：有向图中，以vi为始点的边数入次d-(vi)

：有向图中，以vi为终点的边数Σd+(v)=Σd-(v)=m第11页，课件共57页，创作于2023年2月7.1图与网络的基本概念5、链、圈、路、回路、连通图：链：无向图G=（V,E）前后相继的点边序列称为链初等链：点边序列中没有重复的点和重复边的链称为初等链(v1,e1,v2,e6,v4,e3,v3,e8,v5

)第12页，课件共57页，创作于2023年2月7.1图与网络的基本概念圈：无向图G=（V,E）中起点和终点重合的链称为圈初等圈：没有重复点(除起点和终点外)和重复边的圈称为初等圈(v1,e1,v2,e6,v4,e3,v3,e5,v1

)第13页，课件共57页，创作于2023年2月7.1图与网络的基本概念对于有向图来说，如果链和圈中边的方向与有向图中所标方向相同，那么链就称为道路，圈就称为回路。连通图：无向图中，任意两个点之间至少有一条链相连的图称为连通图第14页，课件共57页，创作于2023年2月7.1图与网络的基本概念6、子图与生成子图：子图：图G=(V,E)，E’是E的子集，V’是V的子集，且E’的边与V’的顶点想关联，G’=(V’,E’)是图G的一个子图。生成子图：若V’=V，则G’是G的生成子图第15页，课件共57页，创作于2023年2月7.1图与网络的基本概念6、网络：网络（赋权图）：由点、边以及与点边相关联的权数所构成的图称为网络，记作N={V,E,W}v4v2v3v16215846v4v2v3v16215846无向网络 有向网络第16页，课件共57页，创作于2023年2月7.1图与网络的基本概念7.1.2树的概念及性质1、树（T）：无圈的连通图称为树

树叶

分枝点第17页，课件共57页，创作于2023年2月7.1图与网络的基本概念7.1.2树的概念及性质2、树的性质性质7.1

树中任意两点之间有且只有一条链。性质7.2

如图G中任意两点之间，有且只有一条链，则该图G是一个树。性质7.3

一个树，则m=n-1。性质7.4

树中任意两个不相邻的点之间增加一条边，则形成唯一的圈。性质7.5

一个树如果去掉任何一条边，该图就不再连通。第18页，课件共57页，创作于2023年2月7.1图与网络的基本概念7.1.2树的概念及性质3、图的生成树生成树（支撑树）：图G的生成子图是一棵树，则称该树为G的生成树图G中属于生成树的边称为树枝，不属于生成树的边称为弦定理7.3：图G=（V,E）,有生成树的充分必要条件为G是连通图第19页，课件共57页，创作于2023年2月4、最小生成树：图G=(V，E)的生成树所有树枝上的权数的总和,称为生成树的权。权数最小的生成树称为最小生成树。寻找最小生成树的方法：避圈法、破圈法最小生成树权=11第20页，课件共57页，创作于2023年2月5、根树有向树：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。根树：有向树T，恰有一个结点入次d-(vi)=0，其余各点入次d-(vi)=1，则称T为根树根树中入次d-(vi)=0的点称为根出次d+(vi)=0称为叶其他点称为分枝点7.1图与网络的基本概念第21页，课件共57页，创作于2023年2月在根树中，若每个顶点的出次d-(vi)≤m，称这棵树为m叉树。若每个顶点的出次d-(vi)=m或0，则称这棵树为完全m叉树7.1图与网络的基本概念第22页，课件共57页，创作于2023年2月v2v3v7v1v8v4v5v66134105275934682求从v1到v8的最短路径标号：T标号（试探性标号）

P标号（永久性标号）1、狄克斯托算法（Dijkstra）:标号法7.2最短路问题第23页，课件共57页，创作于2023年2月V2V3V7V1V8V4V5V66134105275934682S={v1}P(v1)=0,T(vi)=∞T(v2)=2,T(v4)=1,T(v6)=3min{T(v2),T(v4),T(v6)}=min{2，1，3}=1P(v4)

=1S={v1,v4}P(v1)=0L12=2L14=1L16=3P(v4)=1第24页，课件共57页，创作于2023年2月v2v3v7v1v8v4v5v66134105275934682S={v1,v4}P(v2)

=2P(v1)=0P(v4)=1T(v2)=2T(v6)=3T(v7)=3min{T(v2),T(v6),T(v7)}=min{2，3，3}=2P(v2)

=2S={v1,v4,v2}L12=2L16=3L42=11L47=3第25页，课件共57页，创作于2023年2月v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2}P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L16=3L47=3L23=8L25=7T(v6)=3T(v7)=3T(v3)=8T(v5)=7min{T(v6),T(v7),T(v3),T(v5)}=min{3,

3,8,7}=3P(v6)

=3S={v1,v4,v2,v6}第26页，课件共57页，创作于2023年2月v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6}P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L47=3L23=8L25=7L67=7T(v7)=3T(v3)=8T(v5)=7min{T(v7),T(v3),T(v5)}=min{3,8,7}=3P(v7)

=3S={v1,v4,v2,v6,v7}第27页，课件共57页，创作于2023年2月v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7}P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L23=8L25=7L75=6L78=11T(v3)=8T(v5)=6T(v8)=11min{T(v3),T(v5),T(v8)}=min{8,6,11}=6P(v5)

=6S={v1,v4,v2,v6,v7,v5}第28页，课件共57页，创作于2023年2月v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7,v5}P(v3)

=8P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L23=8L53=15L58=10L78=11T(v3)=8T(v8)=10min{T(v3),T(v8)}=min{8,10}=8P(v3)

=8S={v1,v4,v2,v6,v7,

v5,

v3}第29页，课件共57页，创作于2023年2月v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7,

v5,

v3}P(v8)

=10P(v3)

=8P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2L38=14L58=10L78=11T(v8)=10P(v8)

=10S={v1,v4,v2,v6,v7,

v5,

v3,v8}第30页，课件共57页，创作于2023年2月v2v3v7v1v8v4v5v66134105275934682S={v1,v4,v2,v6,v7,

v5,

v3,v8}v1到v8的最短路径为{v1,v4,v7,

v5,

v8}，长度为10P(v8)

=10P(v3)

=8P(v5)

=6P(v7)

=3P(v6)

=3P(v1)=0P(v4)=1P(v2)

=2第31页，课件共57页，创作于2023年2月狄克斯托算法（Dijkstra）的适用条件：1、用于赋权有向图。对于赋权无向图的处理2、权数wij

≥0第32页，课件共57页，创作于2023年2月2、逐次逼近算法可用于网络中有权数为负数的边7.2最短路问题第33页，课件共57页，创作于2023年2月7.2最短路问题第34页，课件共57页，创作于2023年2月v1v3v4v2v5vtvsww6243743179887.3最大流问题第35页，课件共57页，创作于2023年2月1、流量和容量有向连通图G=(V，E),G的每条边（vi，vj）上有非负数cij称为边的容量，仅有一个入次为0的点vs称为发点，一个出次为0的点vt称为收点，其余点为中间点，这样的网络G称为容量网络，记为G=（V,E,C）。7.3.1基本概念7.3最大流问题第36页，课件共57页，创作于2023年2月2、可行流和最大流可行流必须满足的两个条件 （1）容量限定条件：0≤fij≤cij

（2）流量守恒条件：中间点的流入量等于流出量7.3最大流问题第37页，课件共57页，创作于2023年2月vjvifij=5cij=5饱和边、不饱和边、流量间隙(剩余流量)（vi，vj）是饱和的2、如果fij<cij，流从vi到vj的方向是不饱和的(vi，vj)是不饱和的间隙为δ12=c12-f12=5–3=21、如果cij=fij，流从vi到vj的方向是饱和的vjvifij=3cij=53、增广链第38页，课件共57页，创作于2023年2月容量网络G，若u为网络中从vs到vt的一条链，u上的边与u同向的称为前向边，与u反向的称为后向边给定一个G的一个可行流，u如果满足：则称u为从vs到vt的增广链。定理7.4

可行流f是最大流的充要条件是不存在从vs到vt的可增广链。7.3最大流问题第39页，课件共57页，创作于2023年2月v1v3v4v2v5vtvsww6243743179884、割集S=(vs,v3)=(v1,v2,v4,v5,vt)为G的割集割集E’的容量=14v1v3v4v2v5vtvsww624374317988其中S=(vs,v1,v3,v4)=(v2,v5,vt)为G的割集(vs,v1),(v3,v4),(v3,v5)的容量和为割集E’的容量=13第40页，课件共57页，创作于2023年2月其中容量最小的割集称为网络G的最小割集(最小割)定理7.5：（流量—割集定理）设f为网络G=（V,E,C）的任一可行流，S是任一割集，则有W(f)≤定理7.6：(最大流-最小割定理)任一个网络G中，从vi到vj的最大流的流量等于分离vi，vj的最小割的容量7.3最大流问题第41页，课件共57页，创作于2023年2月vsv2v3v1v4v5vtv6(5,0)(3,0)(4,0)(3,0)(2,0)(5,0)(3,0)(4,0)(5,0)(3,0)(2,0)ff7.3.2最大流算法7.3最大流问题第42页，课件共57页，创作于2023年2月vsv2v3v1v4v5vtv6(5,0)(3,0)(4,0)(3,0)(2,0)(5,0)(3,0)(4,0)(5,0)(3,0)(2,0)ff解：从零流开始，寻找增广链vs→v1→v4→vt

最小容量min{5，5，4}=4(5,4)(5,4)(4,4)vs→v1→v5→vt

最小容量min{1，3，3}=1(5,5)(3,1)(3,1)vs→v2→v5→vt

最小容量min{4，3，2}=2(4,2)(3,2)(3,3)vs→v2→v6→vt

最小容量min{2，2，5}=2(4,4)(2,2)(5,2)vs→v3→v6→vt

最小容量min{3，2，3}=2(3,2)(2,2)(5,4)∴网络最大流量=11，流量安排如上图第43页，课件共57页，创作于2023年2月vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)从任一可行流开始寻找最大流，采用标号法寻找增广链(,+∞)解：先给发点标号，即：vs标（，+∞

）第44页，课件共57页，创作于2023年2月(vs，v1)fs1=cs1=5(vs，v2)

fs2=2<cs2=4δs2=2

所以给v2标号(+vs，2)(vs，v3)

fs3=2<cs3=3δs3=1

所以给v3标号(+vs，1)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)第45页，课件共57页，创作于2023年2月(v2，v5)f25=0<c25=3δ25=min[3,2]

所以给v5标号(+v2，2)(v2，v6)

f26=2=c26(v3，v6)

f36=2=c36vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)(+v2,2)第46页，课件共57页，创作于2023年2月(v5，vt)f5t=3=c5t(v5，v1)

f15=3>0δ51=min[3,2]=2

所以给v1标号(-v5，2)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)第47页，课件共57页，创作于2023年2月(v1，v4)f14=2<c24=5δ51=min[3,2]=2

所以给v2标号(+v1，2)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)第48页，课件共57页，创作于2023年2月(v4，vt)f4t=2<c4t=4δ4t=min[2,2]=2

所以给vt标号(+v4，2)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(+v4,2)第49页，课件共57页，创作于2023年2月存在一条从vs到vt的可增广链δ=2调整流量vsv2v3v1v4v5vtv6(5,5)(3,2)(4,2)(3,0)(2,2)(5,2)(3,3)(4,2)(5,4)(3,3)(2,2)(,+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(+v4,2)(4,4)(3,2)(3,1)(5,4)(4,4)第50页，课件共57页，创作于2023年2月(vs，v1)fs1=cs1=5(vs，v2)

fs2=4=cs2=4(vs，v3)

fs3=2<cs3=3δs3=1

所以给v3标号(+vs，1)vsv2v3v1v4v5vtv6(5,5)(3,2)(4,4)(3,2)(2,2)(5,4)(3,3)(4,4)(5,4)(3,1)(2,2)(,+∞)(+vs,1)第51页，课件共57页，创作于2023年2月(v3，v6)fs1=c