运筹学中的组合优化 高等运筹教学PPT课件.ppt

* 　最小费用最大流问题 二、最小费用最大流的网络图论解法 对网络上弧（vi,vj）的（cij,bij）的表示作如下改动，用(b)来表示(a)。 用上述方法对例7中的图形进行改进，得图如下页： vi vj vi vj （cij,bij ） （0,-bij ） （a） （b） （cij,bij ） （cij,bij ） vi vj （cji,bji ） （cij,bij ） vi vj （cji,bji ） （0,-bji) （0,-bji) （c） （d） * 　最小费用最大流问题 求最小费用最大流的基本算法 在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样，不同的只是在步骤（1）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。 (6,6) (3,4) (5,7) (2,5) (0,-4) （2,3） (4,4) (1,3) (2,8) （3,2） v1 v2 v5 v7 v4 v3 v6 (6,3) (0,-3) (0,-8) (0,-3) （0,-2） (0,-6) (0,-4) (0,-5) （2,4） (0,-7) (0,-4) （0,-3） 图11-28 * 　最小费用最大流问题 用上述方法对例7求解： 第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后总流量为1，总 费用10。 v5 (6,6) (3,4) (5,7) (2,5) (0,-4) （2,3） (3,4) (0,3) (2,8) （3,2） v1 v2 v7 v4 v3 v6 (5,3) (1,-3) (0,-8) (1,-3) （0,-2） (0,-6) (0,-4) (0,-5) （2,4） (0,-7) (1,-4) （0,-3） 图11-29 * 　最小费用最大流问题 第二次迭代：找到最短路v1 v4 v7。第二次迭代后总流量为3，总费用 32。 (6,6) (3,4) (5,7) (2,5) (0,-4) （2,3） (3,4) (0,3) (0,8) （3,2） v1 v2 v5 v7 v4 v3 v6 (3,3) (3,-3) (2,-8) (1,-3) （0,-2） (0,-6) (0,-4) (0,-5) （2,4） (0,-7) (1,-4) （0,-3） 图11-30 * 　最小费用最大流问题 第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后总流量为 5，总费用56。 (6,6) (3,4) (5,7) (2,5) (0,-4) （0,3） (1,4) (0,3) (0,8) （1,2） v1 v2 v5 v7 v4 v3 v6 (1,3) (5,-3) (2,-8) (1,-3) （2,-2） (0,-6) (0,-4) (0,-5) （2,4） (0,-7) (3,-4) （2,-3） 图11-31 * 　最小费用最大流问题 第四次迭代：找到最短路v1 v4 v3 v5 v7 。第四次迭代后总流量为 6，总费用72。 (6,6) (3,4) (4,7) (2,5) (1,-4) （0,3） (1,4) (0,3) (0,8) （0,2） v1 v2 v5 v7 v4 v3 v6 (1,3) (6,-3) (2,-8) (1,-3) （3,-2） (0,-6) (0,-4) (0,-5) （1,4） (1,-7) (3,-4) （2,-3） 图11-32 * 　最小费用最大流问题 第五次迭代：找到最短路v1 v2 v5 v7 。第五次迭代后总流量为9，总 费用123。 (3,6) (0,4) (1,7) (2,5) (1,-4) （0,3） (1,4) (0,3) (0,8) （0,2） v1 v2 v5 v7 v4 v3 v6 (0,3) (6,-3) (2,-8) (1,-3) （3,-2） (3,-6) (3,-4) (0,-5) （1,4） (4,-7) (3,-4) （2,-3） 图11-33 * 　最小费用最大流问题 第六次迭代：找到最短路v1 v2 v3 v5 v7 。第六次迭代后总流量为 10，总费用145。已经找不到从v1到v7的每条弧容量都大于零的路了，故 已求得最小费用最大流了。 (3,6) (0,4) (1,7) (2,5) (1,-4) （0,3） (1,4) (0,3) (0,8) （0,2） v1 v2 v5 v7 v4 v3 v6 (0,3) (6,-3) (2,-