郭京生　劉璘

摘要：運用圖論的相關(guān)理論知識，針對物流系統(tǒng)中運輸網(wǎng)絡(luò)的特點，以最大限度的提高運輸效率，同時以節(jié)約運輸總成本為目標，提出了解決運輸網(wǎng)絡(luò)優(yōu)化問題的最小費用最大流網(wǎng)絡(luò)模型，并利用matlab編程實現(xiàn)，為優(yōu)化物流運輸網(wǎng)絡(luò)路線提供了一種可行方法。

關(guān)鍵詞：運輸網(wǎng)絡(luò)；最小費用最大流；網(wǎng)絡(luò)流量；matlab

中圖分類號：F25文獻標識碼：A文章編號：16723198（2015）17005302

0引言

運輸作為現(xiàn)代物流過程的主要職能之一，是物流各項業(yè)務(wù)的中心活動。同時，運輸產(chǎn)生的費用也是供應(yīng)鏈和整個物流系統(tǒng)成本結(jié)構(gòu)的重要組成部分?？梢哉f，一個高效率、低成本和高反應(yīng)能力的運輸網(wǎng)絡(luò)對一個成功的物流配送體系至關(guān)重要，這就使得運輸網(wǎng)絡(luò)的優(yōu)化成為配送體系中一項重要的運營決策，關(guān)系到物流設(shè)計體系的成功與否。運輸網(wǎng)絡(luò)的優(yōu)化主要是對運輸路線的安排，即選擇合理的配送路線，既能保證配送效率的最大化，又能同時使運輸成本最低。

圖論是運籌學(xué)中一個重要的分支，是用來描述運輸網(wǎng)絡(luò)的數(shù)學(xué)理論基礎(chǔ)。本文基于圖論的相關(guān)理論知識，針對物流運輸中最小費用最大流問題，建立了基于matlab的優(yōu)化數(shù)學(xué)模型，以求最大限度的提高運輸效率，同時節(jié)約運輸費用。

1最小費用最大流模型

1.1網(wǎng)絡(luò)流量基本概念及定義

為了實現(xiàn)對網(wǎng)絡(luò)流量最大流值和最低成本的優(yōu)化，首先需明確幾個基本定義：

定義1：容量—費用網(wǎng)絡(luò)。給定一個有向圖D=V，A，對任意的弧vi，vj∈A，設(shè)lij，uij為弧的運輸容量上下界函數(shù)，其中0≤lij≤uij，也稱uij為弧的容量；cij是弧vi，vj上單位流量的費用，稱之為費用函數(shù)；對任意的節(jié)點vi∈V，稱avi為節(jié)點vi的供應(yīng)量或需求量，稱之為供需函數(shù)，且滿足vi∈Va（vi）=0。由此得到的網(wǎng)絡(luò)稱為容量—費用網(wǎng)絡(luò)。

定義2：可行流及其總費用。設(shè)fij是給定網(wǎng)絡(luò)N上的由節(jié)點vi到節(jié)點vj的一個流量，且滿足：

f+（vi）-f-（vi）=f（vi）

lij≤fij≤uij （1）

式中，f+vi=vj∈Vfij，f-vi=vj∈Vfji，分別稱為流出和流入節(jié)點vi的流量，fvi為該節(jié)點的凈輸出量。

當滿足式（1）時，則稱f=fij為網(wǎng)絡(luò)N 上的一個可行流，且可行流f的總費用為

c（f）=（vi，vj）∈Acijfij （2）

1.2最小費用問題概念及數(shù)學(xué)模型

最小費用問題是物流運輸網(wǎng)絡(luò)優(yōu)化的核心問題，目標是在滿足供應(yīng)條件的前提下，尋求供應(yīng)網(wǎng)絡(luò)總成本最小的最優(yōu)解。

根據(jù)上述定義，最小費用問題屬于線性規(guī)劃問題。其數(shù)學(xué)模型如下：

min z=c（f）=（vi，vj）∈Acijfij （3）

約束條件為式（1）。

其中，目標函數(shù)是通過網(wǎng)絡(luò)N供應(yīng)的總成本最小。決策變量fij指通過弧vi，vj的流量。約束條件有供應(yīng)點的凈流量（總流出量減去總流入量）為正，所有需求點的凈流量為負，對于所有中轉(zhuǎn)點（中間點）的凈流量為0，所有弧的流量受到弧的容量lij，uij的限制，且弧的流量為非負。

1.3最大流問題概念及數(shù)學(xué)模型

最大流問題也與網(wǎng)絡(luò)中的流有關(guān)，但是其優(yōu)化目標與最小費用流不同，最大流問題是尋求一個可行流的方案，使得通過網(wǎng)絡(luò)的流量最大。

根據(jù)最大流問題的概念，最大流問題也屬于線性規(guī)劃問題。其數(shù)學(xué)模型如下：

max z=fvs （4）

除滿足約束條件式（1）外，還應(yīng)滿足式（5）：

f+（vi）-f-（vi）=fvs，i=s（源）

-fvs，i=t（匯）

0，i≠s，t（中轉(zhuǎn)點）（5）

其中，目標函數(shù)是通過供應(yīng)點vs的凈流出量f（vs）（或需求點vt的凈流入量f（vt））最大，決策變量是通過各個弧的流量fij，約束條件有所有中轉(zhuǎn)點的凈流量為0，所有弧的流量受到弧的容量lij，uij的限制，且弧的流量為非負。

1.4最小費用最大流問題概念及數(shù)學(xué)模型

前面小節(jié)中介紹的“最小費用流問題”的目標是在完成規(guī)定任務(wù)的條件下，使得網(wǎng)絡(luò)供應(yīng)的總成本最小，即解決流量一定成本最小的路線安排問題?！白畲罅鲉栴}”的目標是尋求一個可行流的方案，使得通過供應(yīng)網(wǎng)絡(luò)的流量最大，即不考慮成本的情況下，解決單純的流量最大的路線安排問題。但是實際情況往往比較復(fù)雜，不僅考慮流量還需要兼顧費用。例如，物流系統(tǒng)中一個運輸網(wǎng)絡(luò)，不僅要爭取網(wǎng)絡(luò)中貨運量最大，還要力求使總費用最小，即解決更貼合實際的流量最大成本最低的路線安排問題，這就是“最小費用最大流問題”。

因此，我們可以把“最小費用最大流問題”看成是“最小費用流問題”和“最大流問題”的結(jié)合。求解該問題自然可以分為兩步：首先，按照“最大流量問題”的求解方法找到網(wǎng)絡(luò)可通過的最大流量；其次，在保證該最大流量的前提下找到成本最小的線路。

根據(jù)最小費用最大流問題的概念，最小費用最大流問題也屬于線性規(guī)劃問題。其數(shù)學(xué)模型如下：

min z=（i，j）∈Acijfij （6）

s.t.f+（vi）-f-（vi）=fvs，i=s（源）

-fvs，i=t（匯）

0，i≠s，t（中轉(zhuǎn)點）

0≤lij≤fij≤uij（（i，j）∈A） （7）

2算例

基于上述分析，本文以某公司鏈接產(chǎn)地到銷地的物流運輸體系為例進行說明。其中，產(chǎn)品運輸網(wǎng)絡(luò)如下圖1所示，圖中各弧表示運輸?shù)缆?。由于道路實際地質(zhì)情況不同，使得每條道路上的運輸費用也不同，因此優(yōu)化該運輸系統(tǒng)除考慮貨物的最大流外，還需要考慮道路運輸?shù)淖钚≠M用，即可基于本文所提的最小費用最大流模型予以求解。

圖1某公司產(chǎn)品運輸網(wǎng)絡(luò)圖1中弧上括號內(nèi)的數(shù)字分別表示對應(yīng)運輸?shù)缆返娜萘肯拗坪蛦挝贿\費。

對算例按照最小費用最大流問題建模，過程如下：

（1）建立最大流模型。

maxz=fvs=fs1+fs2 （8）

滿足約束條件（1）。

（2）建立最小費用模型。

minz=（vi，vj）∈Acijfij （9）

滿足約束條件（7）。

（3）利用MATLAB軟件實現(xiàn)算例，在命令窗口中編寫MATLAB程序并執(zhí)行，得到結(jié)果如圖2所示。

圖2程序仿真結(jié)果由圖2所示，該運輸網(wǎng)絡(luò)最大運輸量為14噸，最小運輸總成本為20500元，優(yōu)化后的運輸方案如圖3所示。

圖3優(yōu)化運輸方案3結(jié)束語

隨著電子商務(wù)和物流業(yè)的迅速發(fā)展，物流運輸?shù)牡匚辉絹碓绞艿街匾?。本文將最小費用最大流模型運用到物流運輸網(wǎng)絡(luò)的優(yōu)化中，為優(yōu)化運輸網(wǎng)絡(luò)路線提供了一種可行方法，實現(xiàn)了在實際優(yōu)化中既考慮最大運量同時也尋求運輸總成本最小化的目標。需要指出的是：在優(yōu)化運輸網(wǎng)絡(luò)過程中，優(yōu)化運輸路線只是其中的一個部分，還需要對物流節(jié)點進行優(yōu)化，比如物流節(jié)點的選址問題，這兩類問題應(yīng)該綜合考慮進行優(yōu)化，這些問題有待進一步的研究。

參考文獻

[1]杜潔，郝妍，王璐.多目標應(yīng)急物流運輸問題優(yōu)化研究[J].物流工程與管理，2010，32（4）：113114.

[2]王桂平，王衍，任嘉辰.圖論算法理論、實現(xiàn)及應(yīng)用[M].北京：北京大學(xué)出版社，2011：131208.

[3]王銳，甘凱.圖論優(yōu)化法在物流運輸中的運用[J].商場現(xiàn)代化，2005，（28）：137138.

[4]張建林.MATLAB&EXCEL定量預(yù)測與決策[M].北京：電子工業(yè)出版社，2012.

[5]林方明，馬建軍，龐淵.物流配送決策中的運輸網(wǎng)絡(luò)優(yōu)化問題研究[J].山西建筑，2004，30（08）：8485.