邱 攀， 胡圣能 （华北水利水电学院，河南 郑州 450011）

地震是对人类生存安全危害最大的自然灾害之一。2007年全世界有灾情的地震共计13次，经济损失总数达200亿美元。2008年中国汶川8.0级大地震是新中国成立以来破坏性最强、涉及范围最广、救灾难度最大的一次地震，重灾区面积达10万平方公里；地震直接经济损失超过1万亿元人民币。地震的一大特点就是突发性强，以目前的预报水平，还不能准确地知道在什么时候、什么地方、发生多大地震，这就要求必须提高地震应急反应能力。

所谓应急物流，就是指以提供突发性自然灾害、突发性公共卫生事件等突发性事件所需应急物资为目的，以追求时间效益最大化和灾害损失最小化为目标的特种物流活动[1]。我国是世界上地震活动最强烈和地震灾害最严重的国家之一，历次地震灾害都造成了建筑损毁、人员死伤、交通中断等巨大损失。在灾害发生时，尽管各级政府均积极成立救灾指挥中心以及救灾专门小组，但面对复杂的道路交通情况和各地救灾物资需求量的不同，如果不统筹安排会造成运输费用增加，局部救灾物资短缺或过剩，会影响抢救生命财产的进度和社会稳定。这就给决策者提出一个问题：怎样在满足各受灾地区物资最小需求的前提下，以最低的运输费用将尽可能多的救灾物资运送到各灾区。本文在对最小费用最大流理论研究的基础上，建立地震救灾物资运输数学模型，得出在满足各灾区救灾物资最小需求的前提下，以最低的运输费用将救灾物资运送到各灾区的运输方案。

1 最小费用最大流理论[2－4]

定义1整个应急物流网络可以分解为若干条自起点vs到终点vt的链，每条链由若干个弧组成，若链上弧的方向与链的方向相同 （起点到终点），则称这个弧为链的正向弧，记为u+；否则称为逆向弧，记为u－。

定义2一个可行流，u是从起点vs到终点vt的一条链，若u满足下列条件，则称之为一条增广链。

（1） 在弧 （ vi, vj）∈u+上，0≤qi,j＜ci,j， 即u+中每一条弧是非饱和弧； （2） 在弧 （vi, vj）∈u－上，即 u－中每一条弧是非饱和弧。

1.1 最小费用最大流问题的描述。 在网络D=（V,A,C ）中， 对应每一条弧 （vi, vj）∈A， 除了已给弧 （vi,vj）的容量ci,j（ci,j＞0 ）外， 还给了一个单位流量通过弧 （vi,vj）的费用fi,j（fi,j＞0D的一条可行流，则其总费用为则求使最小且流量大的问题称为最小费用最大流问题。

1.2 最小费用最大流理论的算法思想。若q是流量为v（q ）的可行流中费用最小者，而u是关于q的所有增广链中费用最小的增广链，那么沿着u以ε去调整q，得到的可行流q'就是流量为v（ q'）（v（ q'）=v（q）+ε ）的所有可行流中的最小费用流。这样，当q'为最大流时，它也就是我们所要求的最小费用最大流了。根据这个结论，如果已知q是流值为v（q ）的最小费用流，则关键是要求出关于q的最小费用的增广链。为此，需要在原网络D的基础上构造一个新的赋权有向图h（q ），使其顶点与D的顶点相同， 且将D中每条弧 （vi, vj）均变成两个方向相反的弧 （vi, vj）和（vj, vi）。 新图h（q ）中各弧的权值与q中弧的权值有密切关系，图h（q ）中各弧的权值定义为：

由增广链费用的概念及图h（q ）中权的定义可知，在网络D中寻求关于可行最小费用增广链，等价于在图h（q）中寻求从源点到汇点的最短路。

2 数学模型

2.1 救灾物资模型建立。地震救灾物资运输要求在满足各灾区救灾物资需求的前提下，以最低的运输费用将尽可能多的救灾物资从各救灾物资收集点运送到各灾区，这要求考虑3个问题： （1）满足各灾区的最低物资需求； （2）在满足最低物资需求的前提下，将尽可能多的物资从各救灾物资收集点运送到灾区； （3）总运输费用最小。为了更好地处理这3个问题，我们定义两个常量fij和qij。fij为运送单位救灾物资从第i救灾物资收集点到第j灾区所需费用，qij为从第i救灾物资收集点到第j灾区运送救灾物资的数量。这样以总运输费用最小和救灾物资运输量最大为目标函数，以各救灾物资收集点的物资储备量、道路运输能力、各灾区所需要的最小物资量为约束条件构造模型如下：

式中pi为第i个仓库的物资储备数量，wi为第j个灾区至少所需要的物资数量，cij为从第i个仓库到第j个灾区道路运输能力，s表示起点，t表示终点。第1个约束条件表示各节点救灾物资流量守恒；第2个约束条件表示从第i个仓库到第j个灾区救灾物资运输量必须在运输能力范围内。第3个约束条件表示从第i个仓库运走的所有物资数量必须小于第i个仓库的物资储备量；第4个约束条件表示运送到第j个灾区的所有物资数量必须不小于第j个灾区最少需求量。

2.2 模型求解。最小费用最大流理论的求解过程是对单一源点到单一汇点进行的，当救灾物资运输问题涉及到多个储存物资的仓库 （源点）和多个需求物资的仓库 （汇点）时就需要引进s点作为单源，引进t点作为单汇。

定义1规定从s点到第i个仓库的道路运输能力为i个仓库的物资储备量，从s点运送到第i个仓库的单位物资运输费用为0；

定义2规定从第j个灾区到t点的道路运输能力为+∞，从第j个灾区运送到t点的单位物资运输费用为0。

这样一来，运输的总费用不会变，也可以应用最小费用最大流算法对模型进行求解。求解步骤如下:（1）确定初始可行流它是运输量为0的最小费用流； （2）经k次调整得到的最小费用流，构造赋权有向图（3） 在赋权有向图寻求从源点vs到汇点vt的最小费用路 （调用Dijkstra算法），若不存在最小费用路，是最小费用最大运量流，计算终止；若存在最小费用路，则此最小费用路即为原网络D中相应的增广链u，转入下一步； （4）在增广链μ上行调整，调整量为：（5）得到新的可行流使流值增大，令k=k+1，返回到第 （2）步骤。

3 结束语

利用最小费用最大流理论时应注意流的可行性和经济性。实际网络中的流必须是可行流，其流量不可以超过最大流量，费用不会低于最小费用时的费用。最小费用最大流理论可以求解出任意的对应于某个最低运输量的运输方案，即只要给定灾区的最低需求量，就可以根据最小费用最大流理论求解出在这个最低运输量限制下的运输方案，实际中可以根据灾情的变化，随时根据灾区的实际需求量，改变运输方案。

[1] 欧忠文，王会云，姜大力,等.应急物流[J].重庆大学学报，2004,27(3):164-167.

[2] 李德，钱颂迪.运筹学[M].北京：清华大学出版社，1982.

[3] 刘家壮，徐源.网络最大化[M].北京：高等教育出版社，1991.

[4] 郭耀煌,等.运筹学原理与方法[M].成都：西南交通大学出版社，2000.