大学运筹学经典课件第十一章——图与网络模型.ppt

* §5　最小费用最大流问题 用上述方法对例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 * §5　最小费用最大流问题 第二次迭代：找到最短路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 * §5　最小费用最大流问题 第三次迭代：找到最短路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 * §5　最小费用最大流问题 第四次迭代：找到最短路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 * §5　最小费用最大流问题 第五次迭代：找到最短路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 * §5　最小费用最大流问题 第六次迭代：找到最短路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,-8) (1,-3) （3,-2） (3,-6) (3,-4) (0,-5) （1,4） (4,-7) (3,-4) （2,-3） 图11-34 * §5　最小费用最大流问题 如果对例7求一个最小费用流的问题：每小时运送6万加仑石油从v1到v7的最小费用是多少，或者每小时运送7万加仑呢？我们可以从第四次迭代及图11-32即可得到运送6万加仑最小费用72百元，其运送方式通过比较图11-28及图11-32即得图11-36所示。 至于每小时运送7万加仑，我们可以在图11-36的基础上，再按第五次迭代所选的最短路运送1万加仑即得最小费用：72+1*17=89百元，其运送方式如图11-37所示。 3 5 1 2 3 1 2 6 v1 v2 v5 v4 v3 v6 10 3 4 2 v7 10 第六次迭代后总流量 图11-35 * §5　最小费用最大流问题 1 2 3 1 2 6 v1 v2 v5 v4 v3 v6 6 3 1 v7 图11-36 1 2 1 2 3 1 2 6 v1 v2 v5 v4 v3 v6 3 1 1 v7 图11-37 注：“管理运筹学软件”有专门的子程序用于解决这类问题。 *