最小费用最大流在实际问题中的应用.doc

1、楚雄师范学院2012届本科毕业生毕业论文 题 目 最小费用最大流在实际问题中的应用 姓 名 任 富 绳 系（院） 数学系08级 专 业 信息与计算科学 指导老师 杨 波 2012年6月20日 最小费用最大流在物资运输中的应用 摘要：本文对最小费用最大流理论进行了介绍，讨论了该理论在物资运输中的运用、及推广；并以一般性的物资需求为例进行了讨论。关于物资运输方案的优化设计原则可以归结为：满足物资需求地区的物资需求量和总运输费用最小。针对这一原则建立线性规划模型，运用最小费用最大流理论对模型进行求解。关键词：最小费用最大流 物资运输 1 概 述在实际生活中，不管是石油运输、物资、材料等的运输，都可以

2、归结为“流”的问题，人们不仅要考虑的是流量，而且还要考虑“费用”的因素。因此，关于具体的运输问题，可以运用最小费用最大流理论来建立线性规划模型求解。 对于运输问题面对着复杂的道路交通情况和各地物资需求量的不同，如果不统筹安排会造成运输费用增加，局部物资短缺或过剩，影响物资供给。这就给决策者提出一个问题：怎样在满足各地区物资需求的前提下，以最低的运输费用将尽可能多的物资运送到各地区?本文在对最小费用最大流理论研究的基础上，运用最小费用最大流理论对物质运输问题进行了分析，建立物资运输的数学模型，得出了在满足各地区物质需求条件下的合理运输费用。2 最小费用最大流理论的原理2.1 相关定义(1) 前向

3、弧和后向弧：在网络 中，如果是连接源点和汇点的一条链，定义链的方向为从到，则当链中弧的方向与规定的方向一致时，称弧为前向弧，否则称为后向弧。(2) 增广链：设是一可行流，如果存在从源点到汇点的链，在链上，若同时满足“对于上的前向弧有”或“对于上的后向弧有”两条件，则称为增广链。(3) 可行流：同时满足下列条件的流称为可行流。1、容量限制条件：对每一弧 2、 平衡条件：对于中间点有 对于源点记 对于汇点记(4) 增广链的费用：设对于可行流存在增广链，当以调整而得到可行流时，两流的费用之差为： 称为增广链的费用，其中和分别表示上的前向弧集和后向弧集。22 最小费用最大流问题的描述在网络中，对应每一

4、条弧，除了已给弧的容量外，还给了一个单位流量通过弧的费用。是的一条可行流，则其总费用为： 则求使得为最小且流量最大的问题称为最小费用最大流问题。最小费用最大流问题是一个特殊的线性规划问题，即：在一可行流上求最大流，使得取值最小。23最小费用最大流理论的算法思想若是流量为的可行流中费用最小者，而是关于的所有增广链中费用最小的增广链，那么沿着以去调整，得到的可行流就是流量为的所有可行流中的最小费用流。这样，当为最大流时，它也就是我们所要求的最小费用最大流了。（一） 取，是零流中费用最小的流；（二） 构造赋权有向图，使其顶点与的顶点相同，且将中每条弧均变成两个方向相反的弧和。中各弧的权值定义为：（三

5、） 采用最短路算法，在赋权有向图中找出到的最短路，此时分以下两种情况：（1） 若不存在最短路，则就是最小费用最大流，算法终止。（2） 若存在最短路，记为，则是原网络中的一个增广链，在增广链上对进行调整另，转入第二步。3 最小费用最大流在物资运输中的应用3.1 物资运输模型的建立物资运输要求在满足各地区物资需求的前提下,以最低的运输费用将尽可能多的物资从各仓库运送到各地区,这要求考虑3个问题: （1）满足各地区的最低物资需求；（2）在满足最低物资需求的前提下,将尽可能多的物资从各仓库运送到各地区；（3）总运输费用最小。为了更好地处理这3个问题,我们定义两个常量和。为运送单位物资从第个仓库到第个地

6、区所需的费用；为从第个仓库到第个地区运送物资的数量。这样以总运输费用最小和物资运输量最大为目标函数,以各仓库的物资储备量、道路运输能力、各地区所需要的最小物资量为约束条件构造模型如下:式中为第个仓库的物资储备数量；为第个地区至少所需要的物资数量；为从第个仓库到第个地区的道路运输能力。第1个约束条件表示从第个仓库运走的所有物资数量必须小于第个仓库的物资储备量；第2个约束条件表示运送到第个地区的所有物资数量必须大于第个地区最少需求量；第3个约束条件表示从第个仓库到第个地区的物资运输量必须在道路运输能力范围内。解决最小费用最大流问题可先求出最大流，再解决最小费用问题。由此，建立线性规划模型。（1）有

7、个内结点个分段的网络最大流问题：其中是流量函数，由通过始点的流量确定；是流量函数的系数，以列向量形式出现；是分段流量，以列向量形式出现；是阶矩阵，与网络图有关；是流量下界；为流量上界。（2）最小费用问题：3.2 建立相应的网络1.将物资的仓库视为A类结点，设共有m个，表示为2.将地区视为B类结点，设共有n个，表示为 3.将交通道路网上的其余交点视为C类结点，设共有l个，表示为4.按交通道路网用箭线吧各结点连通成网，所有箭线均遵循箭尾在结点，箭头在结点的原则建立。5另设点为总源,点为总汇。把点与类结点连通, 箭线从指向，把类结点与点连通, 箭线从指向。6按下列原则对各弧进行标注:1)每条件弧均在

8、弧旁加小括号(),小括号内标以双标号。2)对于 这类弧, 其比标号定为: 第一标号表示单位物资流经路段所需运输费用；第二标号表示该路段的运输能力。3)对于这类弧, 其双标号定为: 第一标号表示物资供应地（仓库）处单位物资运输成本，第二标号表示处物资的可供数量。4)对于这类弧, 其双标号定为: 第一标号表示地区处单位物资应负担的运输费用;第二标号表示处的最高需求量。4 实例 中国天然气公司天然气的运输中国石油天然气集团公司在东海有一个油气田（节点），该公司要将开采的天然气通过管道运送到上海的一个配送中心（节点），天然气在运送途中要经过两次管道换接点（节点和），换接前后的管道长短不一，而且不同的管

9、道对应不同的单位流量费。图1是天然气运输的管道网络图，弧线表示管道，弧旁的数字表示管道上的单位流量费用和容量。公司希望选择一个经济实惠的管道路线运输天然气，既运输最多的天然气又使总运输费用最少。（1,4）（3,5）（4,2）（3,3）（2,1）（2,5）（4,2）（1,3）（1,1）图1现以线性规划建立模型，运用Matlab程序求解： g=zeros(9,1); g(1)=1; g(2)=1; f=-g; q=zeros(4,9); q(1,1)=1; q(1,3)=-1; q(1,4)=-1; q(1,5)=1; q(2,2)=1; q(2,3)=1; q(2,6)=-1; q(3,4)=1

10、; q(3,7)=1; q(3,8)=-1; q(4,6)=1; q(4,5)=-1; q(4,7)=-1; q(4,9)=-1; aeq=q; beq=zeros(4,1); lb=zeros(9,1); ub=4 5 1 3 1 2 3 5 2; x,fval,exitflag,output,lambda=linprog(f,aeq,beq,lb,ub)Optimization terminated successfully.x = 3.0789 1.9211 0.0789 3.0000 0.0000 2.0000 0.8008 3.8008 1.1992fval = -5.0000exi

11、tflag = 1output = iterations: 6 cgiterations: 0 algorithm: large-scale: interior pointlambda = ineqlin: 0x1 double eqlin: 4x1 double upper: 9x1 double lower: 9x1 double f1=1 3 1 3 2 4 1 2 4; aq=1 1 zeros(1,7); aeq1=aq;aeq; beq1=-fval;beq; z,fval1,exitflag,output,lambda=linprog(f1,aeq1,beq1,lb,ub)Opt

12、imization terminated successfully.z = 4.0000 1.0000 1.0000 3.0000 0.0000 2.0000 2.0000 5.0000 0.0000fval1 = 37.0000exitflag = 1output = iterations: 6 cgiterations: 0 algorithm: large-scale: interior pointlambda = ineqlin: 0x1 double eqlin: 5x1 double upper: 9x1 double lower: 9x1 doublefval = -5.0000

13、表示网络最大流量为5，相应最小费用值为fval1 = 37.00005 模型的推广及应用 本文针对天然气的运送运用了最小费用最大流理论，运用该理论可以推广到汽车、轮船、飞机运送物资的最大流最小费用求解；同时凡是涉及到关于最小费用的实际问题都可以转化为图论的最小费用最大流理论，从而有效解决实际问题。6 结语最小费用最大流理论可以求解出任意的对应于某个最低运输量的运输方案,即只给定每座地区的最低需求量,就可以根据最小费用最大流理论求解出在这个最低运输量限制下的运输方案,实际中可以根据旱情的变化,随时改变每处地区的最低需求量,从而改变运输方案。参考文献:1 林诒勋. 线性规划与网络流. 开封:河南大学出版社,2003.2 卢向南,李俊杰,寿涌毅. 应用运筹学. 浙江: 浙江大学出版社,2005.3 杨菊花,盖宇仙. 用最小费用最大流理论确定铁路货物运价问题的研究. 兰州交通大学学报(自然科学版) ,2005 , (1) .4 孙宏杜,文徐杰. 最小费用最大流模型在航班衔接问题中的应用.南京航空航天大学学报,2001 , (10) .5 蒋长浩.图论与网络流.中国林业出版社，2001，（7）.6 田丰，马仲番.图与网络流理论.科学出版社.7 朱必文，刘峙山.图论.高等教育出版社，1990.12