此问题的最小生成树如下：
*************************
起点 终点 距离 ---- ---- ---- 1 2 3 2 6 1.5 6 7 1.5 6 4 1.8 2 3 2 7 5 4
此问题的解为:13.8
第七节 网络最大流
1、求图7—1中的网络最大流，弧上数据为流量限制。
V2 （50） （60） V5 （80） （40） V1 （70） V7 V3 （50） （70） （40） （30） V6 图7—1 V4 从节点 1到节点7的最大流 *************************
起点 终点 距离
---- ---- ---- 1 2 70 1 3 50 1 4 30 2 5 30 2 6 40
第 26 页 共 31 页
3 5 50 4 6 30 5 7 80 6 7 70
此问题的解为:150
2、求如图7—1所示的网络从V1到V6的最大流，弧上数据为容量和可行流。
图7—1 V1 （16,5 （15,4） V3 （14,4） V6 （13,5 （16,2） （5,2 （13,0） ）））V2 （10,3） V4 （17,5） V5
从节点 1到节点6的最大流
*************************
起点 终点 距离 ---- ---- ---- 1 2 12 1 3 15 2 3 12 2 4 0 3 4 0 3 5 13 3 6 14 4 5 0 5 6 13
此问题的解为:27
第 27 页 共 31 页
第八节 最小费用最大流
1、求图8—1中的最小费用最大流，弧上数据为容量和单位费用。
V2 （8,3） （6,3 （5,1） （4,3） V3 （9,3） （8,2 V1 （10,1） ））V6 （3,2） （7,4） V4图8—1 （6,4） V5
从节点 1到节点6的最大流 *************************
起点 终点 流量 费用 ---- ---- ---- ----
1 2 6 3 1 4 9 1 2 3 5 1 2 5 1 3 3 6 8 3 4 3 3 2 4 5 6 4 5 6 7 4
此问题的最大流为:15
此问题的最小费用为:117
第 28 页 共 31 页
2、求8—2中从V1到V5的最小费用最大流，图中弧旁的数字为（bij，cij）
V2 （5,6） （3,2） （3,4） 图8—2 （4,1） V3 （1,1） （4,10） V1 （9,2） V4 V5 （2,3）
从节点 1到节点5的最大流 *************************
起点 终点 流量 费用 ---- ---- ---- ----
1 3 1 4 1 4 2 9 3 5 1 1 4 5 2 2
此问题的最大流为:3 此问题的最小费用为:27
第 29 页 共 31 页
参考文献
⑴ 刘满凤，等.运筹学教程.北京：清华大学出版社，2010年 ⑵ 胡运权，运筹学习题集.北京：清华大学出版社，2010年 ⑶ 运筹学，运筹学.南京：东南大学出版社，2003年
⑷ 廖敏，运筹学基础与应用.南京：南京大学出版社，2009年 ⑸ 胡运权，运筹学教程.北京：清华大学出版社，1998年 ⑹ 韩伯棠，管理运筹学.北京：高等教育出版社，2000年 ⑺ 刘满凤，等.运筹学模型与方法教程例题分析与题解.北京：清华大学出版社，
2001年 ⑻ 杨茂盛，运筹学（第二版）.西安：陕西科学技术出版社，2002年
第 30 页 共 31 页
第 31 页 共 31 页
