苑學梅，陳博文，劉真真

(軍事交通學院 基礎部，天津300161)

最小費用最大流問題是運籌學中的經典問題，在工程規(guī)劃、通信、交通運輸和物流等領域應用非常廣泛。很多實際問題中通?？紤]的是費用最小的問題［1-3］，但在軍事物流運輸活動中往往并不注重費用，更關注的是軍事物流運輸?shù)臅r效性和能力問題。文獻［4］提出了軍事物流運輸網絡的最小時間最大能力流問題并且給出了求解方法，由于實際軍事物流運輸網絡的復雜性，利用手工計算的方法求解最小時間最大能力流問題非常困難。本文主要給出了最小時間最大能力流問題的線性規(guī)劃數(shù)學模型求解過程，并結合Lingo 軟件進行求解。

1 最小時間最大能力流

1.1 基本概念

定義1［4］給定一個有向圖G=(V，E，N)，其中V為G中的節(jié)點集合，E為G中的弧集合，N為道路的通行能力集合。在G中指定一點vs稱為發(fā)點或源點，指定另一點vt稱為收點或匯點，其余點叫中間點。從發(fā)點vs到匯點vt運送軍用物資，則稱有向圖G= (V，E，N)為一個軍事物流運輸網絡。

定義2 軍事物流運輸網絡中弧集合E上的任一弧(vi，vj)，對應有一實際通行能力f(vi，vj)，簡記為fij，如果f滿足:①容量限制條件:對每一弧(vi，vj)∈E，0≤fij≤Nij;②平衡條件:對于中間點，流出量等于流入量，即

對于發(fā)點vs，記

對于匯點vt，記則稱函數(shù)f={fij}為軍事物流運輸網絡的可行能力流，其中v(f)為這個可行能力流的流量。

定義3 軍事物流運輸網絡中流量最大的可行能力流稱為最大可行能力流。

定義4［4］將軍事物流運輸網絡每條弧上的通行能力與距離的乘積，稱作弧(vi，vj)∈E的能力矩fijdij，其中dij為弧(vi，vj)的距離。

1.2 最小時間最大能力流問題

最小時間最大能力流問題就是在軍事物流運輸網絡中求一個最大能力流f，使得從發(fā)點到匯點的總輸送時間最小。由于時間tij=dij/ˉv，在軍事物流運輸網絡中能力矩fijdij最小就相當于總輸送時間最小，其中ˉv為弧上車輛的平均運行速度。

所以，軍事物流運輸網絡中的最小時間最大能力流問題的目標函數(shù)有2 個:①可行能力流f的流量v(f)取最大，即maxv(f);②能力矩取最小，即約束條件為

2 最小時間最大能力流模型的求解

對于最小費用最大流問題，大多數(shù)的求解方法是通過反復尋找最小費用增廣鏈及在增廣鏈上調整流量直到找到最小費用最大流為止［1-2，4-5］。這樣的算法對于簡單的問題很實用，但是實際的軍事物流運輸網絡往往比較復雜，下面給出適合解決復雜的軍事物流運輸網絡最小時間最大能力流問題的求解方法。

通過建立最小時間最大能力流問題的線性規(guī)劃數(shù)學模型，直接應用Lingo 軟件求解。由于最小費用最大流問題的目標函數(shù)有2 個，整個求解過程分成2 個階段進行:第1 階段求出軍事物流運輸網絡的最大能力流量v*;第2 階段利用最大能力流量v*，求出軍事物流運輸網絡的最小時間最大能力流。

(1)第1 階段:建立最大能力流的線性規(guī)劃模型，設計Lingo 程序，求出軍事物流運輸網絡的最大流量。數(shù)學模型為

在此階段可以求出軍事物流運輸網絡可以承載的最大能力流量v*。

(2)第2 階段:利用第1 階段求出的v*，建立最小時間最大能力流問題的數(shù)學模型為

對設計模型(2)的Lingo 程序求解，即可得到軍事物流運輸網絡中的最小時間最大能力流。

3 模擬算例

某一軍事物流運輸網絡如圖1 所示，從軍事物流物資中心vs發(fā)送一批軍事物資到某部隊vt，括號里第1 個數(shù)字代表路段的運行時間，第2 個數(shù)字代表路段的實際通行能力，試求從vs到vt的最小時間最大能力流。

圖1 軍事物流運輸網絡

(1)第1 階段。運用模型(1)求此軍事物流運輸網絡的最大能力流量，設計Lingo 程序如下:

sets:

由以上運行結果可知，此軍事物流運輸網絡的最小時間最大能力流如圖2 所示，圖中括號里第3 個數(shù)字代表實際通過的流量。

圖2 軍事物流運輸網絡最小時間最大流

4 結 語

在軍事領域中，最小費用最大流問題有著廣泛的應用領域和實用價值。為此，本文在文獻［4］的基礎上給出了最小時間最大能力流的模型求解及Lingo 軟件實現(xiàn)，為解決復雜的軍事物流運輸網絡中的最小時間最大能力流問題提供了方便。從而為組織軍事物流運輸，制訂合理的軍事物流運輸方案提供科學依據。

［1］ 謝凡榮.運輸網絡中求最小費用最大流的一個算法［J］. 運籌與管理，2000，9(4)，33-38.

［2］ 劉琳.最小費用最大流新算法及Lingo 實現(xiàn)［J］. 平頂山學院學報，2012，27(5):29-31.

［3］ 宋宇博，蔣兆遠，牟海波.基于Petri 網的網絡最小費用最大流算法［J］.蘭州交通大學學報，2011，30(3):67-70.

［4］ 海軍，陳斌.軍事物流運輸網絡最小時間最大能力流問題研究［J］.海軍后勤學報，2008(3):15-16.

［5］ 錢頌迪.運籌學［M］.4 版. 北京:清華大學出版社，2013.