资源描述：
《运筹学课件13》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、引例某电力公司有三个发电厂，它们负责五个城市的供电任务，输电网络如下图所示。图中顶点v、v、v代表发电厂，v、v、v、v、v代表城市。12345678已知三个发电厂在满足五个城市用电需求量后还分别剩余15MW,10MW,40MW的发电能力，见下图顶点v,v,v上的数字。123输电网还剩余输电能力，见下图中弧旁的数字。城市v由于经济发展要求增加供应电力65MW。8输电网的输电能力能否满足需要?若不能,应增建哪些输电线路。vv210510104020v1515151v6v8v415304540v20v371四、最大流问题1.网
2、络流设有向网络D=（V,A,C）,弧(vi,vj)的权cij≥0为容量，cij∈C。通过弧(vi,vj)的量称为流量，记作xij。所有弧上流量的集合{xij}称为网络D的一个流，记作x。为了在图中将c和x都表示出来，一般在弧(v,v)旁标上(c，x)。ijijijijij标上流量和容量的图称为流量图。（2,1v1）v2C={cs1,cs3,c12,c23,c2t,c34,c42,c4t}（3,1（3,2）={3，2，2，1，3，2，1，2}）s（1,0t）（1,1）x={x,x,x,x,x,x,x,x}s1s312232t
3、34424t（2,2（2,1）vv）={1，2，1，0，2，2，1，1}3（2,24）2D有两个特殊顶点s，t：s仅有出弧而没有入弧，称为发点；t仅有入弧而无出弧，称为收点。网络中既非发点又非收点的其它点称为中间点。下面只研究具有一个发点和一个收点的网络。vv210510v（2,1v1）210（3,140（3,2）2010）15vss15（1,015tts151）（1,1v6tv8v4）（2,2（2,11540）vv30）453（2,2440）v20v373令xij为通过弧(vi,vj)的流量，则有流量与容量的关系：0≤x
4、≤c—流量限制ijij流x=(xij)要满足守恒规则:+vvi=s∑xij−∑xji=0vi≠s,t—守恒方程vjvj−vv=ti它表示发点s有值为v的出流,收点t有值为v的入流,除收点和发点外,流入顶点v的流量等于流出v的流量。ii（2,1v1）v2C={cs1,cs3,c12,c23,c2t,c34,c42,c4t}（3,1（3,2）={3，2，2，1，3，2，1，2}）ss（1,0tt）（1,1）x={x,x,x,x,x,x,x,x}s1s312232t34424t（2,2（2,1）vv）={1，2，1，0
5、，2，2，1，1}3（2,24）4+vvi=s0≤xij≤cij∑xij−∑xji=0vi≠s,t—守恒方程—流量限制vjvj−vv=ti可行流:满足流量限制和守恒方程的流称为可行流,也称为(s,t)－流。最大流问题(MFP)：求流量最大的可行流问题。求最大流问题的线性规划模型为:maxv∑xij−∑xji=v,vi=svjvj∑xij−∑xji=−v,vi=ts.t.vjvj∑xij−∑xji=0,vi≠s,tvvjj0≤xij≤cij,对任意(vi,vj)∈A52.增广链与截集1）前向弧
6、、反向弧：设P是D中从S到t的途径,若其中某一弧（v,v）的方向ij也是从S到t的方向,则称它为前向弧,否则称为反向弧。2）增广链：设x=(x)是D上一个可行流,ij如果对途径P的每个前向弧（v,v）有x0,ijij则称途径P是关于流x=(x)的增广链。ij前向弧(2,1)(2,2)v1v2v1v2(3,1)(3,2)(3,2)(3,2)s(1,0)(1,1)ts(1,0)t(1,0)(2,2)(2,1)(2,2)(2,2)v3(2,2)v4v3(2,2)v4前向弧反向弧6E10
7、某河流中有4个岛屿，从两岸至各岛屿之间共有13座桥梁相连。6AC13在一次敌对的军事行动中，指挥官决定炸断一些桥梁，1259以切断两岸的交通联系。7112问题是至少需要炸断哪几座桥梁，才能达到目的。14FD83BA1256BC10437D9E1112138F73）截集：将网络D=(V,A,C)的顶点集V分为两部分V和V，使12s∈V1,t∈V2且V1IV2=φ,V1UV2=V则把从V指向V的弧的全体称为分离V和V的一个截集，1212记为（V,V），即12(V,V)={(v,v):v∈V,v∈V,(v,v)∈A}12iji1
8、j2ij截量：截集（V,V）中所有弧的容量之和称为该截集的截量，12记为C(V,V)，即12C(V1,V2)=∑cij(vi,vj)∈(V1,V2)84）几个结论①任一可行流的流量总不超过每个截集的截量。②(增广链定理):一个可行流是最大流的充要条件是不存在增广链。③(最大流最小截集定理):任何带发点s
