《管理运学》07-网络规划1.ppt

7.6最小费用最大流问题 第三节讨论了网络最大流问题，在实际中涉及流的问题时，人们考虑的不只是流量，同时要考虑“费用”的因素。 对D=(V,A,C), 给定一个单位流量的费用bij≥0, 最小费用最大流即:求一最大流f, 使 增广链μ的费用 最大流的算法是从某个可行流出发，寻找关于可行流的增广链μ，然后沿着增广链μ调整可行流的流量，得到一个新的可行流，反复以上过程即可得到最大流。 对于增广链μ, 若调整流量θ=1, 那么新可行流F’的费用比原可行流F的费用增加量为: 称为增广链μ的费用。 可以证明，若F是流量为f的所有可行流中费用最小的，而μ是关于F的费用最小的增广链，那么沿着增广链μ去调整流量，得到的新可行流F’，就是流量为f’的费用最小的可行流。这样当F’为最大流时，也就是所求的最小费用最大流。 基本思想 由于bij≥0，所以零流的费用总是最小的。所以可以从零流出发去寻找最小费用最大流。 这里主要需要解决的问题就是如何寻找关于F的费用最小的增广链。为此，可构造网络图D的相对应的赋权有向图W（F），其节点与原网络图D相同，将D中的每一条弧（ｖｉ，ｖｊ）都变成两方向相反的弧（ｖｉ，ｖｊ）与（ｖｊ，ｖｉ）定义W（F）中弧的权ｗｉｊ为： 权数为∞的弧表示不能通过，可以在W（F）中省略。 这样寻找关于F的费用最小增广链的问题就等价于在W（F）中寻找从网络始点到终点的最短路问题。 权数为∞的弧表示不能通过，可以在W（F）中省略。 具体算法 这样寻找关于F的费用最小增广链的问题就等价于在W（F）中寻找从网络始点到终点的最短路问题。 具体算法为：从零流出发，构造其W（F），在W（F）中寻找最短路，在F中对应一个增广链μ，增广链μ的调整量由下式确定： 沿增广链μ，对流量进行调整，调整方法同最大流的调整方法。然后对新得到的可行流继续做前述的工作，直到在赋权有向图W（F）中找不到从始点到终点的最短路（也就是在网络图D中不存在增广链）为止，即可得到最小费用最大流。 第8章 网络分析 * 最小费用最大流问题 例 在右图中，求最小费用最大流。 弧旁数字为： bij，cij 3, 7 5, 6 2, 8 1, 4 s 1 2 t 1, 6 解 取零流 F0为初始流。 3, 7, 0 5, 6, 0 2, 8, 0 1, 4, 0 s 1 2 t 1, 6, 0 (a) F0 3 5 2 1 s 1 2 t 1 (b) W( F0） ? = 4 第8章 网络分析 * 8.5 最小费用最大流问题 ? = 4 3, 7, 0 5, 6, 0 2, 8, 4 1, 4, 4 s 1 2 t 1, 6, 4 (a) F1 3 5 2 -1 s 1 2 t 1 (b) W( F1） -1 -2 3, 7, 4 5, 6, 0 2, 8, 8 1, 4, 4 s 1 2 t 1, 6, 4 (a) F2 3 5 -3 -1 s 1 2 t 1 (b) W( F2） -1 -2 ? = 3 第8章 网络分析 * 最小费用最大流问题 X* = F3 ， f * = 11 ， b(X*) = 2(8)+5(3)+1(1) + 3(7)+1(4) = 57 3, 7, 7 5, 6, 3 2, 8, 8 1, 4, 4 s 1 2 t 1, 6, 1 (a) F3 3, 7, 7 5, 6, 4 2, 8, 7 1, 4, 4 s 1 2 t 1, 6, 0 (a) F’ F’ 亦最大流， f (F’) = 11 但b(F’ ) = 59 57 = c(X*) 故不是最小费用最大流。 -3 5 -5 -1 s 1 2 t 1 (b) W( F3） -1 -2 7.8网络规划的应用 某公司有一个管道网络如图7-29所示，使用这个网络可以把石油从v1运到v7。由于输油管道长短不一，每段管道除了有不同的流量限制cij外，还有不同的单位流量的费用bij。图中每边上的数值表示（cij ，bij）。如果使用这个网络运送石油，怎样运送才能运送最多的石油，并使运送的费用最小？ v1 v3 v4 v6 v5 v2 v7 (6,6) (6,3) (2,5) (3,2) (2,4) (2,3) (1,3) (2,8) (4,4) (5,7) 图7-24. 应用问题图示 线性规划法求解 第一步：先求出网络的最大流 令（vi，vj）上的流量fij，则最大流的数学模型为： Max F=f12+f14 s.t. (f23+f25)- f12=0 (f35+f36)- (f23+f43)=0 (f43+f