运筹学——图与网络模型3.ppt

引例,某电力公司有三个发电厂，它们负责五个城市的供电任务，输电网络如下图所示。图中顶点v1、v2、v3代表发电厂，v4、v5、v6、v7、v8代表城市。已知三个发电厂在满足五个城市用电需求量后还分别剩余15MW、10MW和40MW的发电能力，见下图顶点v1、v2、v3上的数字。输电网还剩余输电能力，见下图中弧旁的数字。城市v8由于经济发展要求增加供应电力65MW。问该输电网的输电能力能否满足需要?若不能,应增建哪些输电线路。,设有向网络D=（V,A,C）,弧的权为容量，且。,四.最大流问题,1.网络流,通过弧的量称为流量，记作。,所有弧上流量的集合称为网络D的一个流,记作x。,为了在图中将cij和xij都表示出来，一般在弧(vi,vj)旁标上(cij，xij)。,标上流量和容量的图称为流量图。,D有两个特殊顶点s，t：,s仅有出弧而没有入弧，称为发点；,t仅有入弧而无出弧，称为收点。,网络中既非发点又非收点的其它点称为中间点。,下面只研究具有一个发点和一个收点的网络。,它表示发点s有值为v的出流,收点t有值为v的入流,除收点和发点外,流入顶点vi的流量等于流出vi的流量,称此规则为守恒方程。,流要满足守恒规则:,守恒方程,令为通过弧的流量，则有流量与容量的关系：,流量限制,最大流问题(MFP)：求流量最大的可行流问题。,可行流:满足流量限制和守恒方程的流称为可行流,也称为(s,t)流。,求最大流问题的线性规划模型为:,2.增广链与截集,1）前向弧、反向弧：设P是D中从S到t的途径,若其中某一弧的方向也是从S到t的方向,则称它为前向弧,否则称为反向弧。,2）增广链：设是G上一个可行流,如果对P的每个前向弧有,每个反向弧有,则称途径P是关于流的增广链。,某河流中有4个岛屿，从两岸至各岛屿之间共有13座桥梁相连。在一次敌对的军事行动中，指挥官决定炸断一些桥梁，以切断两岸的交通联系。问题是至少需要炸断哪几座桥梁，才能达到目的。,3）截集：将网络D=(V,A,C)的顶点集V分为两部分V1和V2，使，且，则把从V1指向V2的弧的全体称为分离V1和V2的一个截集，记为（V1，V2），即,截量：截集（V1，V2）中所有弧的容量之和称为该截集的截量，记为C(V1，V2)，即,5）几个结论,任一可行流的流量总不超过某个截集的截量。,(增广链定理):一个可行流是最大流的充要条件是不存在增广链。,(最大流最小截集定理):任何带发点s和收点t的容量网络中，最大流的流量等于最小截集的截量。,求网络图中最大流的流量。,+3,-2,+1,+4,+2,-1,v1,v3,v2,v5,v6,v1,v3,v2,3Ford-Fulkerson算法,1）基本思想,从任意一个可行流（例如零流）出发，找一条从S到t的增广链，并在这条增广链上增加流值，于是便得到一个新的可行流，继续此过程，直到找不出从S到t的增广链为止。该算法关键是找从S到t的增广链，这可通过标号法来实现，具体的规则如下：,（1）在标号过程中，一个顶点总处于下述三种状态之一：,已标号且已检查过（即该顶点已有一标号且所有相邻点该标的都已标好）；,已标号但未检查过；,未标号。,（2）一个顶点的标号有两个分量组成，形如或其第一个分量表示前继或后继顶点，第二个分量表示允许增加的流量。,（4）当过程继续到t被标号时，一个从S到t的增广链产生了，因而流量可以增加；如果过程没有进行到t就结束了，则不存在从S到t的增广链，说明当前已是最大流。,2）Ford-Fulkerson算法步骤：,第一步令是任意整数可行流，给s一个永久标号。,第二步（1）如果所有标号顶点都已检查过，转第四步。,（2）找一个已标号但未检查的顶点，并作如下检查:对每一条弧，如果且未标号，则给一个标号，其中；对每条弧，如果且未标号，则给一个标号，其中。,（3）如果t已被标号，转第三步，否则转（1）。,第四步此时当前流是最大流，且把所有标号点集记为，则是D的最小割。,第三步在增广链的每个弧上改变流量，其方法是：前向弧的流量增加，反向弧的流量减少。然后抹去除s外的所有顶点标号，转第二步。,求图的网络最大流，弧旁的权数表示（cij,xij）。,3）实例,解：用标号法。1.标号过程。（1）首先给vs标号（0，+）（2）看vs:在弧(vs,v2)上,xs2=cs3=3,不具备标号条件。在弧(vs,v1)上,xs1=10,故给v2标号（-v1,l(v2)）,其中l(v2)=minl(v1),x21=min4,1=1.,(0,+),(vs,4),(v1,1),(v2,1),(-v2,1),(v3,1),（4）看v2:在弧（v2,v4）上，x24=30,故给v3标号（-v2，l(v3),其中l(l(v3)=minl(v2),x32=min1,1=1。（5）在v3,v4中任意选一个，比如v3,在弧（v3,vt）上，x3t=1c3t=2,故给vt标号(v3,l(vt),其中l(vt)=minl(v3),(c3t-x3t)=min1,1=1.因为vt被标上号，根据标号法，转入调整过程。,2.调整过程从vt开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从vs到vt的增广链，如图中双箭线所示。不难看出,+=(vs,v1),(v3,vt),=(v2,v1),(v3,v2),取=1，在上调整x，得到,调整后的可行流x*，如图所示，再对这个可行流从新进行标号过程，寻找增广链。首先给vs标号（0，+），看vs,给v1标号（vs,3）。看v1,在弧（v1,v3）上，x13=c13,弧（v2,v1）上，x21=0,均不符合条件。因此标号过程无法进行下去，不存在从vS到vt的增广链，算法结束。,这时，网络中的可行流x*即是最大流，最大流的流量v(x*)=xs1+xs2=5.同时，也找出D的最小截集（V1，），其中V1是标号的集合，是未标号的集合。,3）实例,用FordFulkerson算法求解下图所示的网络最大流。,解先取一个可行流,流值为7。,网络的最大流为8。,3,1,7,5,4,3,练习:用FordFulkerson算法求解下图所示的网络最大流。,8,7,3,6,2,8,3,7,10,求图所示网络的最大流,解：给定初始可行流为全零流，即x（0）=0,给vs标号（0，+），检查vs：给v1标号(vs,4),给v2标号(vs,3),给v3标号(vs,10),(0,+),(vs,4),(vs,3),(vs,10),检查v1：给v4标号(v1,1)，检查完毕；,(v1,1),检查v2：给v5标号(v2,3)，检查完毕；,(v2,3),检查v5：给vt标号(v5,3)，检查完毕；,(v5,3),因为终点vt已标号，故找出一条从vs到vt的增广链：vsv2v5vt.取=3,(vs,4),(v1,3),(vs,10),(v1,1),（5,3）,(v2,2),(0,+),(v5,2),(vs,2),(v3,3),(vs,10),(v2,3),(v3,4),(0,+),(v4,3),（3,3）,(0,+),(vs,2),(vs,7),(v3,4),(v5,2),(v5,3),(0,+),(vs,2),(vs,4),(v1,1),(v1,1),(v4,1),(0,+),(vs,4),(vs,1),(v3,1),(v5,1),(v4,1),(0,+),(vs,1),(vs,3),(v1,1),(v2,1),(v4,1),(0,+),(vs,3),首先给vs标号（0，+），看vs,给v3标号（vs,3）。看v3,在弧（v3,v2）上，x32=c32,弧（v3,v5）上，x35=c35,均不符合条件。因此标号过程无法进行下去，不存在从vS到vt的增广链，算法结束。最大流量x*=11。,中国邮递员问题,1.问题的提出,一个邮递员从邮局带着所管辖地区的信件、报纸去投递,投递结束后回到邮局,为了投递完所有邮件,当然他必须经过其所管辖的每条街至少一次,请为他设计一条路线,使尽可能短.下图是一个投递区域,边旁的数字为街道的长度,邮局在。,这就是中国邮递员问题的原始模型,是我国管梅谷教授于1962年首先提出的。,用图论的语言来叙述,中国邮递员问题就是在连通赋权图G上求一个回路(未必是简单的),过每边至少一次，并使回路的权最小。,如何判断一个连通图能否一笔不重复地画出，这个问题由大数学家欧拉解决的，所以称为欧拉图问题。,定义：给一个连通多重图G，若存在一条链（圈）过每边一次且仅一次，则称这条链（圈）为欧拉链（圈）。,定义：一个圈如果存在欧拉圈，则称之为欧拉图。,说明：任意两点之间有链相连接，任何路相通就是连通图。多重是指任意两点的边多于一条。,很显然，一个图若能一笔不重复地画出，则这个图就是欧拉图或含有欧拉链。,定理：连通多重图G是欧拉图，当且仅当图中无奇点。,这个定理的结论是显然的，因为欧拉图从某一点出发又回到原来的出发点，这就要求与每个顶点相关联边数应是偶数，从而才能保证从一条边进入该点，从与该点相关联的另一条边出去。,推论：连通多重图G有欧拉链，当且仅当G恰有两个奇点（起点、终点）。,上面的定理和推论提供了识别一个图能否一笔不重复画出的简单方法。下图，是否能一笔画出？,因为有两个奇点，所以能一笔不重复的画出，从奇点V2开始一笔画到奇点V5。,注意：点可重复，边不能重复。,基本思路是：若街区路无奇点，显然按欧拉图定理，可以不重复地走遍所有街道回到出发位置。如果图中有奇点，每边只走一次又回到出发点是不可能的。如果要回到原地就得走些重复路，也就是原来的街区图上添加一些边，使有奇点的图转换成无奇点的图。由于我们要求总权数最小的方案。我们称增加重复边使图中无奇点的方案为可行方案，称总权数最小的方案为最优方案。,一般先确定一个可行方案，然后不断改善。釆用的方法是奇偶点作业法。,2奇偶点上作业法,如果图不是连通Euler图，则中含有奇点（但奇点的个数为偶数），此时图的一条邮递路线必定在某些街道上重复走了一次或多次，它等价于在这些边上加一条或多条重复边，使新图不含奇点，并且所加边的总权为最小。,设表示所有新增加边的集合，它是图边集的一个子集。下面的结论说明了如何求权最小的新增边集。,需要注意的是：要考虑所有的圈。该方法的困难在于检查图中的第一个圈。当图中点数，边数较大时，圈的个数将会很多。,6,3,13,8,9,10,例题1：有16名运动员参加8个项目的游泳比赛，已知运动员号码及参加比赛项目如下表所示（表中打者为参加项目）。为使参加多项比赛的运动员恢复体力要求比赛顺序安排保证每个运动员不连续参加两项比赛，问如何安排才能做到这一点。请设计出一个算法，并在计算机上实现。,解：将八个比赛项目用八个点表示，画一个图，其边为：如果一个运动员参加两个项目的比赛，则将对应的两个点用一条边连接。,安排方法：从度数最多的顶点开始，在其余顶点中选择与它不相邻，而且度数最多的顶点与之相连。如此下去，就得到了一个满足要求的安排方案。,进一步要求：1）将上述思想设计成算法，并且编制相应软件；2）如果不存在题中要求的方案，如何制定出最大限度满足需要的较好方案。,例题2：某种零件的生产经毛坯、机加工、热处理及检验四道工序，在同样满足技术要求的前提下，各道工序有不同的加工方案，其费用（元）如下表。试确定一个生产费用最低的零件加工方案。,解：根据表中资料得到下图。,这样此问题