苑學(xué)梅，陳博文，劉真真

(軍事交通學(xué)院 基礎(chǔ)部，天津300161)

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

1 最小時(shí)間最大能力流

1.1 基本概念

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

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

對(duì)于發(fā)點(diǎn)vs，記

對(duì)于匯點(diǎn)vt，記則稱函數(shù)f={fij}為軍事物流運(yùn)輸網(wǎng)絡(luò)的可行能力流，其中v(f)為這個(gè)可行能力流的流量。

定義3 軍事物流運(yùn)輸網(wǎng)絡(luò)中流量最大的可行能力流稱為最大可行能力流。

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

1.2 最小時(shí)間最大能力流問(wèn)題

最小時(shí)間最大能力流問(wèn)題就是在軍事物流運(yùn)輸網(wǎng)絡(luò)中求一個(gè)最大能力流f，使得從發(fā)點(diǎn)到匯點(diǎn)的總輸送時(shí)間最小。由于時(shí)間tij=dij/ˉv，在軍事物流運(yùn)輸網(wǎng)絡(luò)中能力矩fijdij最小就相當(dāng)于總輸送時(shí)間最小，其中ˉv為弧上車(chē)輛的平均運(yùn)行速度。

所以，軍事物流運(yùn)輸網(wǎng)絡(luò)中的最小時(shí)間最大能力流問(wèn)題的目標(biāo)函數(shù)有2 個(gè):①可行能力流f的流量v(f)取最大，即maxv(f);②能力矩取最小，即約束條件為

2 最小時(shí)間最大能力流模型的求解

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

通過(guò)建立最小時(shí)間最大能力流問(wèn)題的線性規(guī)劃數(shù)學(xué)模型，直接應(yīng)用Lingo 軟件求解。由于最小費(fèi)用最大流問(wèn)題的目標(biāo)函數(shù)有2 個(gè)，整個(gè)求解過(guò)程分成2 個(gè)階段進(jìn)行:第1 階段求出軍事物流運(yùn)輸網(wǎng)絡(luò)的最大能力流量v*;第2 階段利用最大能力流量v*，求出軍事物流運(yùn)輸網(wǎng)絡(luò)的最小時(shí)間最大能力流。

(1)第1 階段:建立最大能力流的線性規(guī)劃模型，設(shè)計(jì)Lingo 程序，求出軍事物流運(yùn)輸網(wǎng)絡(luò)的最大流量。數(shù)學(xué)模型為

在此階段可以求出軍事物流運(yùn)輸網(wǎng)絡(luò)可以承載的最大能力流量v*。

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

對(duì)設(shè)計(jì)模型(2)的Lingo 程序求解，即可得到軍事物流運(yùn)輸網(wǎng)絡(luò)中的最小時(shí)間最大能力流。

3 模擬算例

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

圖1 軍事物流運(yùn)輸網(wǎng)絡(luò)

(1)第1 階段。運(yùn)用模型(1)求此軍事物流運(yùn)輸網(wǎng)絡(luò)的最大能力流量，設(shè)計(jì)Lingo 程序如下:

sets:

由以上運(yùn)行結(jié)果可知，此軍事物流運(yùn)輸網(wǎng)絡(luò)的最小時(shí)間最大能力流如圖2 所示，圖中括號(hào)里第3 個(gè)數(shù)字代表實(shí)際通過(guò)的流量。

圖2 軍事物流運(yùn)輸網(wǎng)絡(luò)最小時(shí)間最大流

4 結(jié) 語(yǔ)

在軍事領(lǐng)域中，最小費(fèi)用最大流問(wèn)題有著廣泛的應(yīng)用領(lǐng)域和實(shí)用價(jià)值。為此，本文在文獻(xiàn)［4］的基礎(chǔ)上給出了最小時(shí)間最大能力流的模型求解及Lingo 軟件實(shí)現(xiàn)，為解決復(fù)雜的軍事物流運(yùn)輸網(wǎng)絡(luò)中的最小時(shí)間最大能力流問(wèn)題提供了方便。從而為組織軍事物流運(yùn)輸，制訂合理的軍事物流運(yùn)輸方案提供科學(xué)依據(jù)。

［1］ 謝凡榮.運(yùn)輸網(wǎng)絡(luò)中求最小費(fèi)用最大流的一個(gè)算法［J］. 運(yùn)籌與管理，2000，9(4)，33-38.

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

［3］ 宋宇博，蔣兆遠(yuǎn)，牟海波.基于Petri 網(wǎng)的網(wǎng)絡(luò)最小費(fèi)用最大流算法［J］.蘭州交通大學(xué)學(xué)報(bào)，2011，30(3):67-70.

［4］ 海軍，陳斌.軍事物流運(yùn)輸網(wǎng)絡(luò)最小時(shí)間最大能力流問(wèn)題研究［J］.海軍后勤學(xué)報(bào)，2008(3):15-16.

［5］ 錢(qián)頌迪.運(yùn)籌學(xué)［M］.4 版. 北京:清華大學(xué)出版社，2013.