运筹学图与网络模型.ppt

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页，2024年2月25日，星期天v1v2v3v4v5v6161817171623312322304159413022(0,s)(16,1)(30,1)(41,1)(53,4)(53,3)(22,1)第33页,共56页，2024年2月25日，星期天§4最大流问题最大流问题：给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。第34页,共56页，2024年2月25日，星期天4.1最大流的数学模型例：某石油公司拥有一个管道网络，使用这个网络可以把石油从开采地运送到一些销售点。由于管道的直径的变化，他的各段管道(vi,vj)的流量cij也不一样，如下图所示。cij的单位为万加仑/小时。如果使用这个网络系统从开采地v1向销地v7运送石油，问每小时能运送多少加仑石油？v1v6v3v4v5v2v761223236542第35页,共56页，2024年2月25日，星期天设弧(vi,vj)上的流量为fij，网络上的总的流量为F，则上述问题的线性规划模型为：目标函数：maxF=f12+f14约束条件：f12=f23+f25f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fij?cij,(i=1,2,...,6;j=2,...,7)fij?0,(i=1,2,...,6;j=2,...,7)第36页,共56页，2024年2月25日，星期天4.2最大流问题网络图论的解法对一条弧(vi,vj)的容量用一对数(cij,0)标在弧(vi,vj)上，cij表示从vi到vj容许通过的容量，0表示从vj到vi容许通过的容量。vivjvivjvivjcijvivj0cjicijcijcjicij第37页,共56页，2024年2月25日，星期天求最大流的基本算法找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于0。如果不存在这样的路，则已求得最大流。找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤①。注意：在步骤①中尽量选择包含弧数最少的路。第38页,共56页，2024年2月25日，星期天引例的Ford-Fulkerson标号算法：(贝尔曼-福特算法)第一次迭代：选择路为：v1?v4