运筹学图与网络模型.ppt

起始点v1标以(0,s).I={v1},J={v2,v3,v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v2),(v1,v3),(v1,v4),(v1,v5),(v1,v6)}并有s12=l1+c12=0+16=16,s13=l1+c13=0+22=22,s14=l1+c14=0+30=30,s15=l1+c15=0+41=41,s16=l1+c16=0+59=59,min(s12,s13,s14,s15,s16)=s12=16.给弧(v1,v2)的终点v2标以(16,1).I={v1,v2},J={v3,v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v3),(v1,v4),(v1,v5),(v1,v6),(v2,v3),(v2,v4),(v2,v5),(v2,v6)}并有s23=l2+c23=16+16=32,s24=l2+c24=16+22=38,s25=l2+c25=16+30=46,s26=l2+c26=16+41=57,min(s13,s14,s15,s16,s23,s24,s25,s26)=s13=22.给弧(v1,v3)的终点v3标以(22,1).第31页，共56页，星期日，2025年，2月5日I={v1,v2,v3},J={v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v4),(v1,v5),(v1,v6),(v2,v4),(v2,v5),(v2,v6),(v3,v4),(v3,v5),(v3,v6)}并有s34=l3+c34=22+17=39,s35=l3+c35=22+23=45,s36=l3+c36=22+31=53,min(s14,s15,s16,s24,s25,s26,s34,s35,s36)=s14=30.给弧(v1,v4)的终点v4标以(30,1).I={v1,v2,v3,v4},J={v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v5),(v1,v6),(v2,v5),(v2,v6),(v3,v5),(v3,v6),(v4,v5),(v4,v6)}并有s45=l4+c45=30+17=47,s46=l4+c46=30+23=53,min(s15,s16,s25,s26,s35,s36,s45,s46)=s15=41.给弧(v1,v5)的终点v5标以(41,1).I={v1,v2,v3,v4,v5},J={v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v6),(v2,v6),(v3,v6),(v4,v6),(v5,v6)}并有s56=l5+c56=41+18=59,min(s16,s26,s36,s46,s56)=s36=s46=53.给弧(v3,v6)和(v4,v6)的终点v6标以(53,3)和(53,4).第32页，共56页，星期日，2025年，2月5日v1v2v3v4v5v6161817171623312322304159413022(0,s)(16,1)(30,1)(41,1)(53,4)(53,3)(22,1)第33页，共56页，星期日，2025年，2月5日§4最大流问题最大流问题：给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。第34页，共56页，星期日，2025年，2月5日4.1最大流的数学模型例：某石油公司拥有一个管道网络，使用这个网络可以把石油从开采地运送到一些销售点。由于管道的直径的变化，他的各段管道(vi,vj)的流量cij也不一样，如下图所示。cij的单位为万加仑/小时。如果使用这个网络系统从开采地v1向销地v7运送石油，问每小时能运送多少加仑石油？v1v6v3v4v5v2v761223236542第35页，共56页，星期日，2025年，2月5日设弧(vi,vj)上的流量为fij，网络上的总的流量为F，则上述问题的线性规划模型为：目标函数：maxF=f12+f14约束条件：f12=f23+f25f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14