图与网络模型.ppt

第十章 图与网络模型,网络的基本概念最短路径问题 最小生成树问题最大流问题 最小费用最大流问题,1.图与网络的基本概念,在城市交通线路图中,交通站点一般用实心点表示站点,直线表示运行轨迹.象这种由点、线相连组成的集合在图论中称为图。,图论中常用的名词,图子图和生成子图网络图链、路、圈和回路连通图简单图,一、图：无向图,一、图：无向图,其中V是G中点的集合，E是G中边的集合。,由点和边组成的图叫无向图。简称图，记作G=（V，E）,有向图,a1,a2,a3,有向图,由点和弧构成的图叫有向图，记为D=（V，A），,其中，V是图D的点集合，A为图D的弧有集合。,二、子图与生成子图,三、网络图,各边赋予一定的物理量，例如距离，则叫做网络图。所赋予的物理量叫做权。权可以是：距离、时间、成本、容量等,对一个无向图G的每一边（i,j）,相应地有一个数wij,称为权，此图称为赋权图。对一个有向图D的每一条弧（i,j）,相应地有一个数Cij,称为权，此图称为赋权图。在赋权的有向图D中指定了一点，称为发点（记为VS），指定另一点为收点（记为Vt)，其余的点称为中间点，并把D中每弧的权称为容量，这样的图被称为网络。,四、链、圈、路、回路,初等链：在无向图中，顶点和边相互交替出现的点不重复序列。圈：起点和终点相同的链叫做圈。路：在有向图中，点弧交错，方向和链的走向一致的链。即前后相继并且方向相同的边序列 P=v1,(1,2),V2,(2,3),v3,(3,4)回路：起点和终点相同的路叫做回路。,4,2,3,1,4,2,3,1,4,2,3,1,五、连通图和简单图,连通图：在图中，任意两点之间至少有一条链相连，叫做连通图。否则是非连通图。非连通图可以由几个连通图构成。环、多重边简单图：没有环和多重边的图是简单图。,不连通图,连通图 任意两个节点之间至少有一条链的图称为连通图,2,4,3,5,1,4,2,3,1,树(Tree)一个无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点,2.最短路径问题,最短路径问题是对一个赋权的有向图D中指定的的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上的所有弧的权数的总和最小。,一、求解最短路的Dijkstra算法,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从1到8的最短路径,Dijkstra算法适合于CIJ大于等于0的图，又称为双标号法。,一、求解最短路的Dijkstra算法,Dijkstra算法适合于Cij大于等于0的图，又称为双标号法。对图中的点Vj赋予两个标号（Lj,Kj),Lj代表从vs到vj 的最短路的长度，kj表示最短路上前一个邻点的下标。,一、求解最短路的Dijkstra算法,Dijkstra算法实施步骤：1。给起点V1以标号（0，s)表示从V1到V1的的距离0，V1为起点。2。找出已标号的点的集合I，没标号的点的集合J以及弧的集合（Vi,Vj）|ViI,VjJ,一、求解最短路的Dijkstra算法,Dijkstra算法实施步骤：3.如果上述弧的集合是空集，则计算结束。如果Vt已标号（lt,kt）,则vs到Vt的距离为lt，而从Vs到Vt的最短距离为lt，其路径可反向追踪到起点vs而得到。如果Vt未标号，则不存在有向路，无最短路。如果上述不是空集，则转下一步。4。对上述弧的集合中每一条弧，计算Sij=li+cij在所有的SIJ中找到其值最小的弧，不妨设此弧为（Vc,Vd),则给此弧的终点以双标号（Scd,C),返回步骤2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,I=1,J=2，3，4，5，6，7，8,S12=L1+c12=0+2=2;S14=L1+c14=0+1=1;S16=L1+c16=0+3=3,(1,1),（0，S）,已标号的点的集合,未标号的点的集合,min s12,s14,s16=min 0+2,0+1,0+3=min 2,1,3=1,S14=1,V4(1,1),I=1,4,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,I=1,4,J=2,3,5,6,7,8,min s12,s16,s42,s47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2V2(2,1),s12=2,I=1,2,4,(0,S),(1,1),(2,1),2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,I=1,2,4 J=3,5,6,7,8,min s16,s23,s25,s47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3V6(3,1),I=1,2,4,6,(2,1),(1,1),(0,S),(3,1),2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,I=1,2,4,6,J=3,5,7,8,min s23,s25,s47,s67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3,(2,1),(1,1),(0,S),(3,1),(3,4),V7(3,4),S47=3,I=1,2,4,6,7,J=3,5,8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min s23,s25,s75,s78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7,w5=6,(2,1),(1,1),(0.S),(3,1),(3,4),(6,7),2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,I=1,2,4,5,6,7,J=3,8,min s23,s53,s58,s78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7,w3=8,w4=1,(0,S),(8,2),(2,1),(3,1),(3,4),(6,7),2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8,w8=10,(2,1),(1,1),(0,s),(3,1),(3,4),(6,7),(8,2),(10,5),2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,I=1,2,3,4,5,6,7,8 J=,1到10的最短路径为1，4，7，5，8，长度为10。,(2,1),(1,1),(0,S),(3,1),(3,4),(6,7),(8,2),(10,5),二、最短路径的应用：,例2。电信公司准备在甲乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？,v2,v7,v5,v1,v6,v4,v3,17,3,10,4,6,5,6,4,2,15,甲地,乙地,解：采用无方向的Dijkstra算法.起点V1(0,S)2.I=1,J=2,3,4,5,6,7,边的集合=1,2,1,3S12=15,s13=10,v3(10,1),v2,v7,v5,v1,v6,v4,v3,17,3,10,4,6,5,6,4,2,15,甲地,乙地,(0,S),(10,1),解：采用无方向的Dijkstra算法.3.I=1,3,J=2,4,5,6,7,边的集合=1,2,3,2,3,5S12=0+15,s32=10+3=13,s35=10+4=14,min13,14,15=13=s32,V2(13,3),v2,v7,v5,v1,v6,v4,v3,17,3,10,4,6,5,6,4,2,15,甲地,乙地,(0,S),(10,1),(13,3),解：采用无方向的Dijkstra算法.4.I=1,2,3,J=4,5,6,7,边的集合=2,4,2,7,3,5S24=13+6=19,s27=13+17=30,s35=10+4=14,min19,30,14=14=s35,V5(14,3),v2,v7,v5,v1,v6,v4,v3,17,3,10,4,6,5,6,4,2,15,甲地,乙地,(0,S),(10,1),(13,3),(14,3),解：采用无方向的Dijkstra算法.5.I=1,2,3,5,J=4,6,7,边的集合=2,4,2,7,5,4,5,6S24=13+6=19,s27=13+17=30,s54=14+4=18,s56=14+2=16 min19,30,18,16=16=s56,V6(16,5),v2,v7,v5,v1,v6,v4,v3,17,3,10,4,6,5,6,4,2,15,甲地,乙地,(0,S),(10,1),(13,3),(14,3),(16,5),解：采用无方向的Dijkstra算法.6.I=1,2,3,5,6,J=4,7,边的集合=2,4,2,7,5,4,6,7S24=13+6=19,s27=13+17=30,s54=14+4=18,s67=16+6=22 min19,30,18,22=18=s54,V4(18,5),v2,v7,v5,v1,v6,v4,v3,17,3,10,4,6,5,6,4,2,15,甲地,乙地,(0,S),(10,1),(13,3),(14,3),(16,5),(18,5),解：采用无方向的Dijkstra算法.7.I=1,2,3,4,5,6,J=7,边的集合=2,7,4,7,6,7s27=13+17=30,s67=16+6=22,s47=18+5=23 min30,22,23=22=s67,V7(22,6),v2,v7,v5,v1,v6,v4,v3,17,3,10,4,6,5,6,4,2,15,甲地,乙地,(0,S),(10,1),(13,3),(14,3),(16,5),(18,5),(22,6),解：采用无方向的Dijkstra算法.8.I=1,2,3,4,5,6,7,J=,计算结束;9.最短路径:(1,3,5,6,7),v2,v7,v5,v1,v6,v4,v3,17,3,10,4,6,5,6,4,2,15,甲地,乙地,(0,S),(10,1),(13,3),(14,3),(16,5),(18,5),(22,6),什么是树？构造生成树的方法最小生成树问题寻找最小生成树的方法,3 最小生成树问题,一、什么是树？,树：无圈的连通图或 不含圈的连通图,2,4,3,5,1,(a),(b),(C),一、什么是树？,树的基本性质任意两点之间有且只有一条链若树有p个顶点，则共有q=p-1条边若图是连通的，且q=p-1，则该图不含圈，因此是树若图不含圈，且q=p-1，则该图连通的，因此是树。,3 最小生成树问题,树的性质,任何树至少有一个悬挂节点,2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,如果树的节点个数为m，则边的个数为m-1,树中任意两个节点之间只有唯一的一条链,在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈,树中只与一条边关联的节点称为悬挂节点,网络的生成树,一个无向图G=(V,E),如果保留G中所有节点,而删除部分G的边所获得的图,称为G的生成子图.如果生成子图是一个树,则称这个生成子图为生成树.由网络的所有节点（m个）和网络的m-1条边组成的树称为网络的生成树，网络中不属于生成树的边称为生成树的弦,网络的生成树,由网络的所有节点（m个）和网络的m-1条边组成的树称为网络的生成树，网络中不属于生成树的边称为生成树的弦,网络的生成树的变换,网络的一个生成树，增加一条弦，形成唯一的圈，去掉生成树的一条边，得到一个新的网络的生成树,生成树2,生成树3,生成树1,/,/,网络的生成树和线性规划的关系,网络的一个生成树对应于线性规划的一个基生成树上的边对应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树的变换对应于线性规划单纯形法的进基和离基变换,二、求解最小生成树的破圈法,最小生成树:在一个赋权的连通的无向图G中找出一个生成树,并使得这个生成树的所有边的权数之和为最小.,破圈法:将连通图中所有边权从大到小排列,在不破坏连通的条件下,依次去掉最大边破圈,直到所有节点连通为止.,二、求解最小生成树的破圈法,最小生成树:在一个赋权的连通的无向图G中找出一个生成树,并使得这个生成树的所有边的权数之和为最小.,破圈法步骤:(0)边权排序.(1)在给定的赋权的连通图上找一个大边权圈.(2)在所找的圈中去掉一条权数最大的边(相同者任去一条)(3)如果所余下的图已不含圈,则计算结束,所剩余下的图即为最小生成树,否则转回第一步。,二、求解最小生成树的破圈法,1,2,3,4,5,6,7,10,3,3,3,1,4,5,4,2,7,8,二、求解最小生成树的破圈法,1,2,3,4,5,6,7,10,3,3,3,1,4,5,4,2,7,8,二、求解最小生成树的破圈法,1,2,3,4,5,6,7,10,3,3,3,1,4,5,4,2,7,8,二、求解最小生成树的破圈法,1,2,3,4,5,6,7,10,3,3,3,1,4,5,4,2,7,8,二、求解最小生成树的破圈法,1,2,3,4,5,6,7,10,3,3,3,1,4,5,4,2,7,8,二、求解最小生成树的破圈法,1,2,3,4,5,6,7,10,3,3,3,1,4,5,4,2,7,8,二、求解最小生成树的破圈法,1,2,3,4,5,6,7,10,3,3,3,1,4,5,4,2,7,8,二、求解最小生成树的破圈法,1,2,3,4,5,6,7,10,3,3,3,1,4,5,4,2,7,8,二、求解最小生成树的破圈法,1,2,3,4,5,6,7,10,3,3,3,1,最小生成树的总权数：3=3+3=1=2=7=19,5,2,7,8,避圈法,三、应用举例,水塔,5,7,2,3,5,1,6,4,4,最小生成树的数学模型,四、寻找最小生成树的方法,Kruskal方法破圈法矩阵计算法,Kruskal方法,矩阵计算方法,T,矩阵计算方法,T,T,矩阵计算方法,T,T,T,矩阵计算方法,T,T,T,T,矩阵计算方法,T,T,T,T,T,矩阵计算方法,T,T,T,T,T,T,矩阵计算结果,习题,P.231，第10章习题1、2。,第4节 网络最大流问题,许多系统中包含了流量问题,公路系统中有车流量,供水系统中有水流量,金融系统中有现金流量,车站机场商场服务中有客流量等.通过了解系统流量,对系统进行最优的控制和管理.所谓最大流量问题就是:给出一个带收发点的网络,其每条弧的赋权称之为容量,在不超过每条弧的容量的前提下,求出从发点到收点的最大流量.,第4节 网络最大流问题,一、最大流的数学模型,例6 某石油公司拥有一个管理网络，使用该网络可以把石油从采地运往销地。各管道（Vi,Vj）的流量（容量）为Cij万加仑。如果使用这个网络从采地V1向销地V7运送石油，问每小时能运送多少加仑石油？,2,4,3,5,6,7,1,5,7,f,f,3,2,2,0,6,3,1,2,2,5,4,6,0,第4节 网络最大流问题,一、最大流的数学模型,解：设弧(Vi,Vj)上的流量为fij，网络上的总流量为F,则有：目标函数：max F=f12+f14约束条件：,2,4,3,5,6,7,1,5,7,f,f,3,2,2,0,6,3,1,2,2,5,4,6,0,第4节 网络最大流问题,一、最大流的数学模型,解：设弧(Vi,Vj)上的流量为fij，网络上的总流量为F,则有：目标函数：max F=f12+f14约束条件：f12=f23+f25 f14=f43+f46+f47 f23+f43=f35+f36 f25+f35=f57 f36+f46=f67 f57+f67+f47=f12+f14fij=0,第4节 网络最大流问题,解：利用LINDO 求解max f12+f14s.t.f23+f25-f12=0 f43+f46+f47-f14=0 f23+f43-f35-f36=0 f25+f35-f57=0 f36+f46-f67=0 f57+f67+f47-f12-f14=0 f12=6 f14=6 f25=3 f23=2 f35=2；f36=2；f43=3；f47=2；f46=1；f57=5；f67=4；end,第4节 网络最大流问题,一、最大流的数学模型,O.ITERATIONS=12 LP OPTIMUM FOUND AT STEP 7 OBJECTIVE FUNCTION VALUE 1)10.00000 VARIABLE VALUE REDUCED COST F12 5.000000 0.000000 F14 5.000000 0.000000 F23 2.000000 0.000000 F25 3.000000 0.000000 F43 2.000000 0.000000 F46 1.000000 0.000000 F47 2.000000 0.000000 F35 2.000000 0.000000 F36 2.000000 0.000000 F57 5.000000 0.000000 F67 3.000000 0.000000,ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.000000 3)0.000000 0.000000 4)0.000000 0.000000 5)0.000000 0.000000 6)0.000000-1.000000 7)0.000000-1.000000 8)1.000000 0.000000 9)1.000000 0.000000 10)0.000000 0.000000 11)0.000000 0.000000 12)0.000000 0.000000 13)0.000000 1.000000 14)1.000000 0.000000 15)0.000000 1.000000 16)0.000000 1.000000 17)0.000000 1.000000 18)1.000000 0.000000,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,f,f,3,2,2,0,6,3,1,2,2,5,4,6,0,边的容量和流量容量uij，流量xij可行流满足以下条件的流称为可行流：1、每一个节点流量平衡2、0 xij uij,边的容量和流量、可行流,饱和边、不饱和边、流量的间隙,（1，2）是饱和的,2、如果xijuij，边从i到j的方向是不饱和的；,（1，2）是不饱和的间隙为12=u12-x12=5-3=2,1、如果xij=uij，边从i到j的方向是饱和的；,3、如果xij=0，边从j到i的方向是饱和的；,（2，1）是饱和的,如果xij0，边从j到i的方向是不饱和的；,（2，1）是不饱和的间隙为12=x12=5,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,5,f,f,3,2,2,6,3,1,2,2,5,4,6,0,0,0,0,0,0,0,0,0,0,0,第4节 网络最大流问题,二、最大流问题网络图论的解法,求最大流的基本算法：（1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已求得最大流。（2）找出这条路上各弧的最小的顺流容量PF，通过这条路增加网络的流量PF（3）在这条路上，减少每一条弧的顺流容量PF，同时增加这些弧的逆流容量PF，返回步骤（1）。,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,5,f,f,3,2,2,6,3,1,2,2,5,4,6,0,0,0,0,0,0,0,0,0,0,pf=0,pf=0,0,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,5,f,f,3,2,2,4,3,1,0,2,4,6,0,0,0,2,2,0,0,0,0,0,pf=2,pf=2,0,2,0,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,5,f,f,3,2,2,4,3,1,2 0,2,5,4,6,0,0,0,2,0 2,0,0,0,0,0,pf=2,pf=2,0,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,f,f,3,2,2,4,3,1,2 0,2,2,4,3,3,0,3,2,0 2,0,0,0,0,0,pf=5,pf=5,0,3,0,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,f,f,0,2,2,4,3,1,0,2,2,4,3,3,3,3,2,2,0,0,0,0,0,pf=5,pf=5,0,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,5,f,f,0,2,2,2,1,1,0,0,2,2,3,3,3,3,4,2,2,0,2,0,0,pf=7,pf=7,2,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,f,f,0,2,2,2,1,1,0,0,2,2,3,3,3,3,4,2,2,0,2,0,0,pf=7,pf=7,2,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,f,f,0,2,2,2,1,1,0,0,2,2,3,3,3,3,4,2,2,0,2,0,0,pf=7,pf=7,2,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,f,f,0,0,0,2,1,1,0,0,0,2,1,5,3,5,4,2,2,2,2,2,0,pf=9,pf=9,2,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,f,f,0,0,0,2,1,1,0,0,0,2,1,5,3,5,4,2,2,2,2,2,0,pf=9,pf=9,2,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,5,f,f,0,0,0,1,1,0,0,0,0,1,1,5,3,5,5,2,2,2,3,2,1,pf=10,pf=10,2,第4节 网络最大流问题,二、最大流问题网络图论的解法,例子：某石油公司：,2,4,3,5,6,7,1,f,f,0,0,0,1,1,0,0,0,0,1,1,5,3,5,5,2,2,2,3,2,1,pf=10,pf=10,2,第4节 网络最大流问题,一、最大流的数学模型例2.,给出一个初始的可行流xij=0,2,3,5,4,6,7,1,f=0,f=0,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,找到所有的不饱和边，以及各边可以调整流量的方向,2,3,5,4,6,7,1,f=0,f=0,6,2,4,3,7,4,3,1,7,9,8,8,0,0,0,0,0,0,0,0,0,0,0,0,2,3,5,4,6,7,1,f=0,f=0,6,2,4,3,7,4,3,1,7,9,8,8,0,0,0,0,0,0,0,0,0,0,0,0,链的间隙为：=min8,6,9=6调整链的流量：xij=xij+;pf=0+6,=6,=9,=8,2,3,5,4,6,7,1,f=6,f=6,0,2,4,3,7,4,3,1,7,3,8,2,6,0,0,0,0,0,0,6,0,0,0,6,2,3,5,4,6,7,1,f=6,f=6,0,2,4,3,7,4,3,1,7,3,8,2,6,0,0,0,0,0,0,6,0,0,0,6,2,3,5,4,6,7,1,f=6,f=6,0,2,4,3,6,4,3,0,7,3,6,2,6,0,0,1,0,0,0,6,1,1,0,6,2,3,5,4,6,7,1,f=7,f=7,0,2,4,3,6,4,3,0,7,3,6,2,6,0,0,1,0,0,0,6,1,1,0,6,2,3,5,4,6,7,1,f=10,f=10,0,2,4,3,3,1,0,0,7,3,3,2,6,0,3,4,0,3,0,6,4,1,0,6,链的间隙为：=min6,4,3,6=3,2,3,5,4,6,7,1,f=7,f=7,0,2,4,3,6,4,3,0,7,3,6,2,6,0,0,1,0,0,0,6,1,1,0,6,链的间隙为：=min6,4,3,6=3,2,3,5,4,6,7,1,f=11,f=11,0,2,3,3,2,0,0,0,7,2,3,2,6,0,4,5,1,3,0,7,4,1,0,6,已求得最大流,2,3,5,4,6,7,1,f=11,u=6,u=2,u=4,u=3,u=7,u=4,u=3,u=1,u=7,u=9,u=8,u=8,x=6,x=0,x=4,x=5,x=3,x=1,x=0,x=9,x=2,x=1,x=6,x=0,f=11,最大流f=11，最小割集为（2,5）（3,4）（3,5）u25+u34+u35=6+4+1=11,第5节 最小费用最大流问题,在求解最大流问题时，我们常常要考虑“费用”问题，期望费用最小。所谓最小费用最大流问题：给一个带收发点的网络，对每一条弧（Vi,Vj）,除了给出容量Cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总费用最小。,第5节 最小费用最大流问题,一、最小费用最大流的数学模型,2,4,3,5,6,7,1,(5,7),f,f,(3,4),(2,5),(6,3),(1,3),(2,8),(2,3),(4,4),(6,6),(2,4),(3,2),某运输管网,P225,问怎样运输才能使油量最多,费用最小?,第5节 最小费用最大流问题,解：利用线性规划求解。第一步：先求出此网络图中最大流量F，其模型为线性规划模型,可以通过软件求解。第二步；在最大流量F的所有解中，找出一个最小费用的解，先建立模型。,第4节 网络最大流问题,一、最大流的数学模型,解：设弧(Vi,Vj)上的流量为fij，网络上的总流量为F,则有：目标函数：max F=f12+f14约束条件：f12=f23+f25 f14=f43+f46+f47 f23+f43=f35+f36 f25+f35=f57 f36+f46=f67 f57+f67+f47=f12+f14fij=0,第4节 网络最大流问题,一、最大流的数学模型,解：利用LINDO 求解max f12+f14s.t.f23+f25-f12=0 f43+f46+f47-f14=0 f23+f43-f35-f36=0 f25+f35-f57=0 f36+f46-f67=0 f57+f67+f47-f12-f14=0 f12=6；f14=6；f25=3；f23=2；f35=2；f36=2；f43=3；f47=2；f46=1；f57=5；f67=4；end,第4节 网络最大流问题,一、最大流的数学模型,O.ITERATIONS=12 LP OPTIMUM FOUND AT STEP 7 OBJECTIVE FUNCTION VALUE 1)10.00000 VARIABLE VALUE REDUCED COST F12 5.000000 0.000000 F14 5.000000 0.000000 F23 2.000000 0.000000 F25 3.000000 0.000000 F43 2.000000 0.000000 F46 1.000000 0.000000 F47 2.000000 0.000000 F35 2.000000 0.000000 F36 2.000000 0.000000 F57 5.000000 0.000000 F67 3.000000 0.000000,ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.000000 3)0.000000 0.000000 4)0.000000 0.000000 5)0.000000 0.000000 6)0.000000-1.000000 7)0.000000-1.000000 8)1.000000 0.000000 9)1.000000 0.000000 10)0.000000 0.000000 11)0.000000 0.000000 12)0.000000 0.000000 13)0.000000 1.000000 14)1.000000 0.000000 15)0.000000 1.000000 16)0.000000 1.000000 17)0.000000 1.000000 18)1.000000 0.000000,第4节 网络最大流问题,第二步，已获取最大流量后，在最大流量解中，找出一个最小费用的解。目标函数：min Z=fij*bij=6f12+3f14+4f25+5f23+2f43+4f35+7f57+3f36+3f46+8f47+4f67约束条件：F12+f14=F=10f12=f23+f25;f14=f43+f46+f47;f23+f43=f35+f36;f25+f35=f57;f36+f46=f67 f57+f67+f47=f12+f14;fij=0,第4节 网络最大流问题,解：利用LINDO软件求解：min 6f12+3f14+4f25+5f23+2f43+4f35+7f57+3f36+3f46+8f47+4f67s.t.f12+f14=10 f23+f25-f12=0 f43+f46+f47-f14=0 f23+f43-f35-f36=0;f25+f35-f57=0 f36+f46-f67=0 f57+f67+f47-f12-f14=0 f12=6；f14=6；f25=3；f23=2；f35=2；f36=2；f43=3；f47=2；f46=1；f57=5；f67=4；end,第4节 网络最大流问题,LP OPTIMUM FOUND AT STEP 9 OBJECTIVE FUNCTION VALUE 1)145.0000 VARIABLE VALUE REDUCED COST F12 4.000000 0.000000 F14 6.000000 0.000000 F25 3.000000 0.000000 F23 1.000000 0.000000 F43 3.000000 0.000000 F35 2.000000 0.000000 F57 5.000000 0.000000 F36 2.000000 0.000000 F46 1.000000 0.000000 F47 2.000000 0.000000 F67 3.000000 0.000000,第4节 网络最大流问题,LP OPTIMUM FOUND AT STEP 9 OBJECTIVE FUNCTION VALUE 1)145.0000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000-22.000000 3)0.000000 3.000000 4)0.000000 0.000000 5)0.000000-8.000000 6)0.000000-12.000000 7)0.000000-15.000000 8)0.000000-19.000000 9)2.000000 0.000000 10)0.000000 0.000000,11)0.000000 5.000000 12)1.000000 0.000000 13)0.000000 0.000000 14)0.000000 4.000000 15)0.000000 6.000000 16)0.000000 11.000000 17)0.000000 12.000000 18)0.000000 0.000000 19)1.000000 0.000000 NO.ITERATIONS=9,第5节 最小费用最大流问题,二、最小费用最大流的网络图论解,2,4,3,5,6,7,1,(5,7),f,f,(3,4),(2,5),(6,3),(1,3),(2,8),(2,3),(4,4),(6,6),(2,4),(3,2),第5节 最小费用最大流问题,二、最小费用最大流的网络图论解,前期准备：1.我们对网络上弧(Vi,Vj)的表示作如下改进。,（cij,bij),（cij,bij),（0,-bij),第5节 最小费用最大流问题,二、最小费用最大流的网络图论解,前期准备：1.我们对网络上弧(Vi,Vj)的表示作如下改进。,（cij,bij),（cij,bij),（cji,bji),（cji,bji),（0,-bij),（0,-bji),第5节 最小费用最大流问题,二、最小费用最大流的网络图论解,2,4,3,5,6,7,1,(0,-7),f,(0,-4),(2,5),(6,3),(1,3),(2,8),(2,3),(4,4),(6,6),(2,4),(0,-2),(0,-6),(3,4),(5,7),(0,-3),(3,2),(0,-3),(0,-8),(0,-5),(0,-3),(0,-4),(0,-4),第5节 最小费用最大流问题,二、最小费用最大流的网络图论解,解：(0)先规范标识网络图，找出网络中单价最短路；(1)找出一条从发点到收点的路,在这条路上,每个节点的顺流量大于0。如果不存在这样的路，则已求得最优解。（2）找出这条路上各弧的最小的顺流容量PF，通过这条路增加网络的流量PF（3）在这条路上，减少每一条弧的顺流容量PF，同时增加这些弧的逆流容量PF，返回步骤（1）。,2,4,3,5,6,7,1,f,(9,3),(5),(3),(3),(8),(3),(4),(6),(4),(5,4),(6,1),(4),(7),(3,1),(2),(11,4),(8,3),第一次迭代：先找到一条最短路：V1V4V6V7,Min jg=10,pf=1,总费用=10*1=10同时修改顺序流量:,(0,s),2,4,3,5,6,7,1,(0,-7),f,(0,-4),(2,5),(6,3),(1,3),(2,8),(2,3),(4,4),(6,6),(2,4),(0,-2),(0,-6),(3,4),(5,7),(0,-3),(3,2),(0,-3),(0,-8),(0,-5),(0,-3),(0,-4),(0,-4),第一次迭代：先找到一条最短路：V1V4V6V7,Min jg=10,pf=1,总费用=10*1=10同时修改顺序流量:,2,4,3,5,6,7,1,(0,-7),Pf=1,(0,-4),(2,5),(5,3),(0,3),(2,8),(2,3),(3,4),(6,6),(2,4),(0,-2),(0,-6),(3,4),(5,7),(1,-3),(3,2),(1,-3),(0,-8),(0,-5),(0,-3),(0,-4),(1,-4),第一次迭代：先找到一条最短路：V1V4V6V7,Min jg=10,pf=1,总费用=10*1=10同时修改顺序流量:,Pf=1,2,4,3,5,6,7,1,f,(9,3),(5),(3),(3),(8),(3),(4),(6),(4),(5,4),(6,1),(4),(7),(3,1),(2),(11,4),(8,3),第二次迭代：V(4,6)已饱和,(0,s),2,4,3,5,6,7,1,(0,-7),V=3,(0,-4),(2,5),(3,3),(0,3),(0,8),(2,3),(3,4),(6,6),(2,4),(0,-2),(0,-6