最小费用最大流理论在救灾物资运输模型中的应用

洪玲玲

摘 要：在保证救灾物资快速调运的情况下且满足各受灾地的需求，使总的费用最小。根据实际情况建立相应的运输问题的数学模型，用最小费用最大流理论求解。当给出问题中所涉及的所有参数的具体数值，该模型就可以用Mathematica或者LINDO软件来求解，得到问题的最优救灾物资调运方案，该问题具有很好的通用性和实用性。

关键词：最小费用最大流；救灾物资；运输规划

一、问题的背景

我国是自然灾害多发的国家之一。因此严重的自然灾害一旦发生，就需要紧急调运大量的救灾物资，用于抢险救灾，所以如何快速调运就是一个需要研究的实际问题。在实际中，各种物资的储存地与受灾地的位置不同、距离不同，物资的需求量也不同，有时或许还需要经过中转站等情况。当然，在救灾物资的调运过程中，包括运输和中转等都是需要成本的。于是，怎么样才能在保证快速调运的情况下，使总的费用最小。

二、问题的提出

因某地区发生了严重的自然灾害，需要紧急调运一批救灾物资，现在所掌握的情况是共有位于m个不同地方的仓库存有该种物资，并且第i个仓库的储存量为ai（i=1，2，…m），根据不同受灾地的实际需求，共有n个受灾地需要这些物资，且第j个受灾地的需求量为bj（j=1，2，…n）。已知要将这批救灾物资从各个储存仓库运送到各受灾地时途中都需要经过个中转站之一，每启用一次第个中转站（无论转运量多少）均发生固定费用fk（k=1，2，…p），且已知在要求的时间内第k个中转站的最大转运量为ck（k=1，2，…p），用dik和ekj分别表示从第i个储存仓库到第k个中转站和从第个中转站到第j个受灾地的运输费用。现在的问题是如何确定一个方案来快速调运这批救灾物资，使得总的费用最少。

三、问题的分析

对问题进行分析可知，这个问题是一个比较复杂的有中转站的运输问题。在该问题中所产生的费用来自3个方面，即从各个储存地到某个中转站的运输费用、从中转站到各个受灾地的运输费用和每个中转站的启用费用，因此这个问题的优化目标为3个方面费用之和的最小化。为了建立问题的数学模型引入如下的决策变量：用xik表示从第i个储存仓库到第k个中转站的转运物资数量；用yki表示从第k个中转站到第j个受灾地的运输物资数量；用lk表示0-1变量，当启用第k个中转站时取值为1，当不启用第k个中转站时取值为0.

四、模型的建立与求解

（一）模型的建立。

（二）模型求解。求解该不平衡的运输问题有两种方法。一是用运输单纯形法，二是用网络流中的最小费用最大流思想。在这里主要介绍最小费用最大流求解运输问题。

最小费用最大流的实质：将问题转化为最短路问题求解，即能求解救灾物资的快速调运问题。

定义：设f是一个可行流，如果存在一条从发点vs到收点vt的链，满足：（1）所有前向弧上fij0，则该链称为增广链，记为μ，前向弧集合记为μ+，后向弧集合记为μ-。定理：设f是最小费用流，而μ是关于f的所有增广链中费用最小的一条，则在μ上对f进行调整后所得到的新流仍是最小费用流。

五、模型的评价

这里给出了具有一般意义的运输规划模型，如果能够给出问题中的所有参数的具体数值，该模型就可以用Mathematica或者LINDO软件来求解，得到问题的最优救灾物资的调运方案。该问题具有很好的通用性和实用性，在实际中可以根据灾情的变化及最低需求量来改变运输方案。

参考文献：

[1] 熊伟. 运筹学[M]. 北京：机械工业出版社，2009.9.

[2] 邱攀，胡圣能. 网络流理论在地震救灾物资运输模型中的应用[J]. 物流科技，2010年第三期.