资源描述：
《运筹学图与网络模型ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、引例某电力公司有三个发电厂，它们负责五个城市的供电任务，输电网络如下图所示。图中顶点v1、v2、v3代表发电厂，v4、v5、v6、v7、v8代表城市。已知三个发电厂在满足五个城市用电需求量后还分别剩余15MW、10MW和40MW的发电能力，见下图顶点v1、v2、v3上的数字。输电网还剩余输电能力，见下图中弧旁的数字。城市v8由于经济发展要求增加供应电力65MW。问该输电网的输电能力能否满足需要?若不能,应增建哪些输电线路。10154010101515152020304045设有向网络D=（V,A,C
2、）,弧的权为容量，且。四.最大流问题1.网络流通过弧的量称为流量，记作。所有弧上流量的集合称为网络D的一个流,记作x。为了在图中将cij和xij都表示出来，一般在弧(vi,vj)旁标上(cij，xij)。标上流量和容量的图称为流量图。1,03,22,11,12,12,22,23,1D有两个特殊顶点s，t：s仅有出弧而没有入弧，称为发点；t仅有入弧而无出弧，称为收点。网络中既非发点又非收点的其它点称为中间点。下面只研究具有一个发点和一个收点的网络。（1,0）（3,2）（2,1）（1,1）（2,1）（2
3、,2）（2,2）（3,1）10154010101515152020304045101540它表示发点s有值为v的出流,收点t有值为v的入流,除收点和发点外,流入顶点vi的流量等于流出vi的流量,称此规则为守恒方程。流要满足守恒规则:—守恒方程令为通过弧的流量，则有流量与容量的关系：—流量限制1,03,22,11,12,12,22,23,1最大流问题(MFP)：求流量最大的可行流问题。可行流:满足流量限制和守恒方程的流称为可行流,也称为(s,t)－流。求最大流问题的线性规划模型为:—流量限制—守恒方程
4、1,03,22,11,12,12,22,23,12.增广链与截集1）前向弧、反向弧：设P是D中从S到t的途径,若其中某一弧的方向也是从S到t的方向,则称它为前向弧,否则称为反向弧。1,03,22,21,02,22,22,23,2前向弧反向弧前向弧2）增广链：设是G上一个可行流,如果对P的每个前向弧有,每个反向弧有,则称途径P是关于流的增广链。某河流中有4个岛屿，从两岸至各岛屿之间共有13座桥梁相连。在一次敌对的军事行动中，指挥官决定炸断一些桥梁，以切断两岸的交通联系。问题是至少需要炸断哪几座桥梁，才
5、能达到目的。32914567810111213ABCDEFABCDEF329145678101112133）截集：将网络D=(V,A,C)的顶点集V分为两部分V1和V2，使，且，则把从V1指向V2的弧的全体称为分离V1和V2的一个截集，记为（V1，V2），即截量：截集（V1，V2）中所有弧的容量之和称为该截集的截量，记为C(V1，V2)，即增广路特点：1、前向弧为非饱和弧。2、后向弧为非零流弧。其特点可说明：前向弧可增加流量。后向弧可减少流量。饱和弧：非饱和弧：零流弧：0非零流弧：04）5）几个结论
6、①任一可行流的流量总不超过某个截集的截量。②(增广链定理):一个可行流是最大流的充要条件是不存在增广链。③(最大流最小截集定理):任何带发点s和收点t的容量网络中，最大流的流量等于最小截集的截量。462215347求网络图中最大流的流量。4,46,32,22,21,05,53,24,47,3+3-2+1+44,46,42,12,21,15,53,24,47,4+2-1v1v3v2v5v6v1v3v23．Ford-Fulkerson算法1）基本思想从任意一个可行流（例如零流）出发，找一条从S到t的增广
7、链，并在这条增广链上增加流值，于是便得到一个新的可行流，继续此过程，直到找不出从S到t的增广链为止。该算法关键是找从S到t的增广链，这可通过标号法来实现，具体的规则如下：（1）在标号过程中，一个顶点总处于下述三种状态之一：①已标号且已检查过（即该顶点已有一标号且所有相邻点该标的都已标好）；②已标号但未检查过；③未标号。（2）一个顶点的标号有两个分量组成，形如或其第一个分量表示前继或后继顶点，第二个分量表示允许增加的流量。（4）当过程继续到t被标号时，一个从S到t的增广链产生了，因而流量可以增加；如果
8、过程没有进行到t就结束了，则不存在从S到t的增广链，说明当前已是最大流。（3）如果顶点被标号且存在一条弧,使，则给未标号的标上，其中；如果被标号且存在一条弧使，则给未标号的顶点标上，其中2）Ford-Fulkerson算法步骤：第一步令是任意整数可行流，给s一个永久标号。第二步（1）如果所有标号顶点都已检查过，转第四步。（2）找一个已标号但未检查的顶点，并作如下检查:对每一条弧，如果且未标号，则给一个标号，其中；对每条弧，如果且未标号，则给一个标号，其中。（3）如果t
