军事物流运输网络最小时间最大能力流的模型求解及Lingo 实现

苑学梅，陈博文，刘真真

(军事交通学院 基础部，天津300161)

最小费用最大流问题是运筹学中的经典问题，在工程规划、通信、交通运输和物流等领域应用非常广泛。很多实际问题中通常考虑的是费用最小的问题［1-3］，但在军事物流运输活动中往往并不注重费用，更关注的是军事物流运输的时效性和能力问题。文献［4］提出了军事物流运输网络的最小时间最大能力流问题并且给出了求解方法，由于实际军事物流运输网络的复杂性，利用手工计算的方法求解最小时间最大能力流问题非常困难。本文主要给出了最小时间最大能力流问题的线性规划数学模型求解过程，并结合Lingo 软件进行求解。

1 最小时间最大能力流

1.1 基本概念

定义1［4］给定一个有向图G=(V，E，N)，其中V为G中的节点集合，E为G中的弧集合，N为道路的通行能力集合。在G中指定一点vs称为发点或源点，指定另一点vt称为收点或汇点，其余点叫中间点。从发点vs到汇点vt运送军用物资，则称有向图G= (V，E，N)为一个军事物流运输网络。

定义2 军事物流运输网络中弧集合E上的任一弧(vi，vj)，对应有一实际通行能力f(vi，vj)，简记为fij，如果f满足:①容量限制条件:对每一弧(vi，vj)∈E，0≤fij≤Nij;②平衡条件:对于中间点，流出量等于流入量，即

对于发点vs，记

对于汇点vt，记则称函数f={fij}为军事物流运输网络的可行能力流，其中v(f)为这个可行能力流的流量。

定义3 军事物流运输网络中流量最大的可行能力流称为最大可行能力流。

定义4［4］将军事物流运输网络每条弧上的通行能力与距离的乘积，称作弧(vi，vj)∈E的能力矩fijdij，其中dij为弧(vi，vj)的距离。

1.2 最小时间最大能力流问题

最小时间最大能力流问题就是在军事物流运输网络中求一个最大能力流f，使得从发点到汇点的总输送时间最小。由于时间tij=dij/¯v，在军事物流运输网络中能力矩fijdij最小就相当于总输送时间最小，其中¯v为弧上车辆的平均运行速度。

所以，军事物流运输网络中的最小时间最大能力流问题的目标函数有2 个:①可行能力流f的流量v(f)取最大，即maxv(f);②能力矩取最小，即约束条件为

2 最小时间最大能力流模型的求解

对于最小费用最大流问题，大多数的求解方法是通过反复寻找最小费用增广链及在增广链上调整流量直到找到最小费用最大流为止［1-2，4-5］。这样的算法对于简单的问题很实用，但是实际的军事物流运输网络往往比较复杂，下面给出适合解决复杂的军事物流运输网络最小时间最大能力流问题的求解方法。

通过建立最小时间最大能力流问题的线性规划数学模型，直接应用Lingo 软件求解。由于最小费用最大流问题的目标函数有2 个，整个求解过程分成2 个阶段进行:第1 阶段求出军事物流运输网络的最大能力流量v*;第2 阶段利用最大能力流量v*，求出军事物流运输网络的最小时间最大能力流。

(1)第1 阶段:建立最大能力流的线性规划模型，设计Lingo 程序，求出军事物流运输网络的最大流量。数学模型为

在此阶段可以求出军事物流运输网络可以承载的最大能力流量v*。

(2)第2 阶段:利用第1 阶段求出的v*，建立最小时间最大能力流问题的数学模型为

对设计模型(2)的Lingo 程序求解，即可得到军事物流运输网络中的最小时间最大能力流。

3 模拟算例

某一军事物流运输网络如图1 所示，从军事物流物资中心vs发送一批军事物资到某部队vt，括号里第1 个数字代表路段的运行时间，第2 个数字代表路段的实际通行能力，试求从vs到vt的最小时间最大能力流。

图1 军事物流运输网络

(1)第1 阶段。运用模型(1)求此军事物流运输网络的最大能力流量，设计Lingo 程序如下:

sets:

由以上运行结果可知，此军事物流运输网络的最小时间最大能力流如图2 所示，图中括号里第3 个数字代表实际通过的流量。

图2 军事物流运输网络最小时间最大流

4 结 语

在军事领域中，最小费用最大流问题有着广泛的应用领域和实用价值。为此，本文在文献［4］的基础上给出了最小时间最大能力流的模型求解及Lingo 软件实现，为解决复杂的军事物流运输网络中的最小时间最大能力流问题提供了方便。从而为组织军事物流运输，制订合理的军事物流运输方案提供科学依据。

［1］ 谢凡荣.运输网络中求最小费用最大流的一个算法［J］. 运筹与管理，2000，9(4)，33-38.

［2］ 刘琳.最小费用最大流新算法及Lingo 实现［J］. 平顶山学院学报，2012，27(5):29-31.

［3］ 宋宇博，蒋兆远，牟海波.基于Petri 网的网络最小费用最大流算法［J］.兰州交通大学学报，2011，30(3):67-70.

［4］ 海军，陈斌.军事物流运输网络最小时间最大能力流问题研究［J］.海军后勤学报，2008(3):15-16.

［5］ 钱颂迪.运筹学［M］.4 版. 北京:清华大学出版社，2013.