宋江海，池 宏，高敏剛

(1.中國科學(xué)院科技戰(zhàn)略咨詢研究院，北京 100190；2.中國科學(xué)院大學(xué)，北京 100049)

1 引言

隨著高鐵的普及、電子商務(wù)的飛速發(fā)展，使得航空公司的競爭日益激烈，成本控制成為航空公司增強市場競爭力的關(guān)鍵，加強對各項運營成本的控制顯得尤為重要。

機上周轉(zhuǎn)品是航空公司為旅客提供的且能進(jìn)行反復(fù)清洗回收使用的餐食用品及用具、盥洗用品及用具，如瓷器、玻璃制品、餐車、毛巾等。大型的航空公司為保障生產(chǎn)運營，一般在多個重要機場設(shè)有基地(或分公司)。由于往返航班配備的機上周轉(zhuǎn)品數(shù)量不同，容易導(dǎo)致一些基地倉庫出現(xiàn)積壓而另一些基地倉庫產(chǎn)生短缺；加之，對整個機上周轉(zhuǎn)品的庫存系統(tǒng)缺乏有效的信息共享及調(diào)運機制，使得機上周轉(zhuǎn)品的訂貨成本一直居高不下。

目前民航領(lǐng)域關(guān)于機上周轉(zhuǎn)品的研究相對較少，并且缺乏定量的模型分析。趙桂紅和馬志剛[1]針對機供品的組成、特點以及在成本控制方面存在的問題，提出了不同類型的機供品成本控制的解決方案。谷偉強[2]以某航空公司自主開發(fā)的“機供品管理平臺”為例，分析了機供品管理信息系統(tǒng)的設(shè)計與實現(xiàn)的全過程。

與機上周轉(zhuǎn)品類似的物品有托盤、集裝箱等，那么關(guān)于此類物品的研究大多集中在如何進(jìn)行調(diào)度方面。有些專家很早就提出建立共用系統(tǒng)來解決托盤回收再利用問題[3-4]，但對于托盤共用系統(tǒng)中如何合理地進(jìn)行回收、調(diào)度等研究還有待深入。任建華和章雪巖[5-7]針對托盤共用系統(tǒng)的回收問題，分別考慮到供給、需求、運輸和裝卸能力等因素的隨機不確定性，提出了幾個托盤共用隨機規(guī)劃模型，并采用機會約束規(guī)劃方法對其進(jìn)行求解。而對于托盤共用系統(tǒng)調(diào)度的全過程(購買或租借、分派、再分派、回收)，任建華等[8]綜合考慮損壞率、整車運輸?shù)缺姸鄻O端不確定性因素，構(gòu)建了一個混合型號托盤的托盤共用系統(tǒng)調(diào)度多情景規(guī)劃模型，該模型能夠幫助托盤共用系統(tǒng)管理者在沒有充足歷史數(shù)據(jù)情況下制定有效的托盤調(diào)度方案。吉清凱等[9]從管理層次、運輸方式及研究方法等多角度對國內(nèi)外關(guān)于集裝箱的空箱調(diào)度研究進(jìn)行了綜述，并提到復(fù)雜空箱物流中的庫存控制策略將是未來的發(fā)展方向之一。Li等[10]將多港口的空箱調(diào)度問題看作成具有正負(fù)需求的多階段庫存問題，提出了一種臨界策略，并用啟發(fā)式算法進(jìn)行了求解。施欣[11]通過對海運集裝箱空箱流轉(zhuǎn)過程的分析，建立了空箱調(diào)運模型，并通過數(shù)字仿真分析了成本參數(shù)及載運能力對空箱調(diào)運策略的影響。計明軍等[12]針對沿海港口間的空箱調(diào)運問題，提出了一種不確定目的港的空箱調(diào)運策略，建立了以總調(diào)運費用最小為目標(biāo)的規(guī)劃模型，采用遺傳算法進(jìn)行求解。卜祥智等[13]基于收益管理的思想，考慮海運集裝箱需求的隨機性，分別建立了考慮和不考慮空箱調(diào)運的集裝箱艙位分配隨機規(guī)劃模型，并采用穩(wěn)健優(yōu)化的方法轉(zhuǎn)化為確定性整數(shù)規(guī)劃模型進(jìn)行求解。

而對于物流網(wǎng)絡(luò)中同級節(jié)點(比如庫存節(jié)點、銷售節(jié)點等)間的相互調(diào)貨在研究中被稱作庫存共享或橫向轉(zhuǎn)運。這種策略可以降低整個系統(tǒng)的缺貨成本和庫存成本，同時提高系統(tǒng)的服務(wù)水平(降低缺貨率)，關(guān)于此類問題的綜述性文獻(xiàn)可見Paterson等[14]。針對不同倉儲物品的特性，學(xué)者們的研究主要集中在備件的庫存共享與消耗品的庫存共享。最早關(guān)于備件的庫存共享研究是Sherbrooke提出的METRIC模型[15]，該模型針對航空領(lǐng)域可修復(fù)件，假設(shè)需求服從泊松分布，基于(S-1,S)的補貨策略求得最佳的庫存水平。Seidscher和Minner[16]針對備件的多點庫存系統(tǒng)，基于one-for-one訂貨策略和需求服從泊松分布下，提出了一個半馬爾科夫決策模型，并分別采用主動轉(zhuǎn)運和被動轉(zhuǎn)運策略進(jìn)行分析。戢守峰等[17]針對三級備件分銷網(wǎng)絡(luò)，構(gòu)建了考慮庫存共享和服務(wù)水平限制下的橫向轉(zhuǎn)運模型，并針對模型具有非線性和復(fù)雜性的特點設(shè)計了貪婪算法進(jìn)行了求解。Archibald[18]假設(shè)備件需求滿足二項分布，構(gòu)建了一個基于周期性檢查補貨策略的多點庫存模型，分析了最優(yōu)訂貨和調(diào)運策略的特點，并設(shè)計了三種簡便的啟發(fā)式調(diào)運策略。Wong等[19]考慮橫向轉(zhuǎn)運時間限制及延遲情形，構(gòu)建了一個可完全共享的多點可修復(fù)庫存模型，并轉(zhuǎn)化成一個多維的馬爾科夫模型進(jìn)行求解。而最早關(guān)于消耗品的庫存共享問題研究是Allen提出的[20]，他考慮了一個在多個庫存點之間的庫存分配問題，各庫存點的需求是獨立隨機的，在某一時點通過運輸對各庫存點的庫存量進(jìn)行重新分配，使得總的運輸及未來缺貨成本最小。Herer和Michal[21-22]針對消耗品，研究其在多個基地間的動態(tài)調(diào)運問題，在已知總訂貨量等于總需求量下，分別考慮固定訂貨成本、固定運輸成本等限制條件，構(gòu)建了多周期的動態(tài)調(diào)運模型，并借鑒Wagner和Whitin動態(tài)優(yōu)化方法[23]，設(shè)計了一個最優(yōu)的求解算法對每個階段的訂貨量和調(diào)運量進(jìn)行求解。?zdemir等[24]研究了一個消耗品的多點庫存系統(tǒng)，在已知各點的隨機需求，考慮供應(yīng)商生產(chǎn)能力限制，構(gòu)建了一個隨機型的多周期的調(diào)運模型，并采用樣本均值逼近方法(SAA)進(jìn)行了求解。以上研究都是基于多點間可以相互調(diào)運的情形，而對于單向的橫向調(diào)運問題，Axs?ter、Olsson等學(xué)者也進(jìn)行了深入的研究[25-26]。還有些學(xué)者從不同的角度對多基地的庫存共享問題進(jìn)行了研究。陳敬賢和孟慶峰[27]針對兩個銷售商的庫存系統(tǒng)，構(gòu)建了一個應(yīng)對突發(fā)事件的非合作博弈模型，證明了其納什均衡解的唯一存在性，并設(shè)計了一個啟發(fā)式的求解算法。

以上研究主要考慮在庫存系統(tǒng)中遇到的各種不確定性因素，去解決回收再利用過程中的一次性調(diào)度問題；或針對備件或消耗品在不同特征下的多點庫存系統(tǒng)，研究其補貨或調(diào)運策略。而本文考慮的是航空公司機上周轉(zhuǎn)品的多基地庫存系統(tǒng)，研究其在一個訂貨周期內(nèi)的動態(tài)補貨問題，決策期初的訂貨方案以及周期內(nèi)的調(diào)運方案，實現(xiàn)庫存共享和降低成本。構(gòu)建了一個庫存優(yōu)化模型，分析了最優(yōu)解的性質(zhì)，并設(shè)計了相應(yīng)的算法進(jìn)行求解，通過算例驗證了方法的有效性。

2 問題與模型構(gòu)建

2.1 問題描述

某航空公司擁有多個基地，每個基地設(shè)有一個存儲倉庫和一個回收倉庫，負(fù)責(zé)機上周轉(zhuǎn)品的采購、倉儲、配備及清洗。各基地的存儲倉庫設(shè)有一定的安全庫存來應(yīng)對未來一段時間內(nèi)的需求，并且機上周轉(zhuǎn)品在回收倉庫經(jīng)過一段時間(清洗周期)后可以返回存儲倉庫再次使用。各基地之間每天都有往返航班，當(dāng)某個基地的庫存量低于安全庫存量時，可通過航班由其它基地進(jìn)行調(diào)運。在期初，航空公司根據(jù)整個庫存系統(tǒng)的需求統(tǒng)一訂貨，然后再根據(jù)各個基地的需求進(jìn)行分配。已知每個基地的需求量、回收量和安全庫存量，求各個基地在期初的訂貨量以及每天的調(diào)運量，使得整個系統(tǒng)在一個訂貨周期內(nèi)所產(chǎn)生的總成本(訂貨成本、存儲成本、調(diào)運成本及回收處理成本)最小。

2.2 基本假設(shè)與參數(shù)說明

基本假設(shè)：

1)不考慮訂貨提前期，即供貨方的生產(chǎn)能力足夠大；

2)各基地的運輸能力足夠大，并且可以在當(dāng)天完成。

3)各基地的倉庫容量足夠大。

4)機上周轉(zhuǎn)品在每個基地的回收周期和損耗比例為常數(shù)。

參數(shù)設(shè)置：

基本參數(shù)

N：基地集合

T：訂貨周期

Si0：基地i的初始庫存量，i∈N

sit：基地i第t天的安全庫存量，i∈N，t∈T

dit：基地i第t天的需求量，i∈N，t∈T

rit：基地i第t天的回收量，i∈N，t∈T

決策變量

xi：基地i期初的訂貨量，i∈N

yijt：第t天基地i調(diào)運到基地j的機上周轉(zhuǎn)品數(shù)量，i≠j，i,j∈N，t∈T

過程變量

Iit：基地i第t天的庫存量

整個系統(tǒng)在訂貨周期內(nèi)產(chǎn)生的總成本包括總訂貨成本、總存儲成本、總調(diào)運成本以及總回收處理成本，即：

(1)

其中，ci為基地i的單位訂貨成本，hi為基地i存儲倉庫的單位存儲成本，pij為從基地i到基地j的單位調(diào)運成本，qi為基地i回收倉庫的單位回收處理成本。

由于各基地的回收量已知，那么整個系統(tǒng)總回收處理成本為確定值，故不將此項成本計入目標(biāo)函數(shù)中。

2.3機上周轉(zhuǎn)品多基地庫存優(yōu)化模型(R1)

(1.1)

s.t.Ii0=Si0+xi

(1.2)

(1.3)

Iit≥sit

(1.4)

xi,Iit,yijt∈Ν

(1.5)

約束(1.2)表示第0天基地i的庫存量等于其初始庫存量與訂貨量之和；約束(1.3)表示基地i第t天的庫存平衡關(guān)系式；約束(1.4)表示基地i第t天的庫存量必須大于或等于其安全庫存量；約束(1.5)表示變量約束，都為非負(fù)整數(shù)。

3 模型求解與算法

令I(lǐng)it=sit+zit且si0=Si0，那么模型R1中的目標(biāo)函數(shù)(1.1)可以表示成：

(2)

由于各基地的安全庫存量已知，因此等式(2)右邊第三項為確定值，亦可以不計入模型目標(biāo)函數(shù)中。那么，模型R1等價于如下模型(R2)：

(2.1)

s.t.xi=zi0

(2.2)

(2.3)

xi,zit,yijt∈Ν

(2.4)

該模型是一個線性整數(shù)規(guī)劃模型，并且變量較多，直接求解非常困難。本文將在模型最優(yōu)解分析的基礎(chǔ)上，給出一個多項式求解算法，求得問題的最優(yōu)解。

3.1 最優(yōu)解分析

令

X1=

X2=

證明：見附錄，下同。

(C1)c1=c2=…=cN=c；

(C2)h1=h2=…=hN=h；

因此，當(dāng)模型R2的參數(shù)滿足條件(C1)-(C3)時，模型R2的最優(yōu)解等價于求解如下模型(R3)的最優(yōu)解：

(3.1)

s.t.xi=zi0

(3.2)

(3.3)

(3.4)

xi,zit,yijt∈Ν

(3.5)

為此，將模型R3轉(zhuǎn)化為最小費用最大流問題進(jìn)行求解。剩下的問題就是如何去構(gòu)造網(wǎng)絡(luò)，以及如何得到最小費用最大流。

3.2 網(wǎng)絡(luò)流求解算法及最優(yōu)性

針對模型R3，構(gòu)造一個多基地動態(tài)補貨網(wǎng)絡(luò)，記為D(0)=(V,A,C,B)，對于每一條弧(vi,vj)∈A上，都對應(yīng)有一個容量和單位費用對(cij,bij)，如圖1所示。

圖1 多基地動態(tài)補貨網(wǎng)絡(luò)

其中，節(jié)點s為發(fā)點，節(jié)點t為收點，節(jié)點0為訂貨點，節(jié)點1、2為虛擬點，節(jié)點(i,j)為基地i的所有庫存點(i=1,2,…,N，j=1,2,…,T)，M為一個很大的數(shù)；并稱節(jié)點0到節(jié)點(i,1)的弧為訂貨弧(i=1,2,…,N)，節(jié)點(i,j)到節(jié)點(i,j+1)的弧為庫存弧(i=1,2,…,N，j=1,2,…,T-1)，節(jié)點(i,j)到節(jié)點(k,j)的弧為調(diào)運弧(i≠k，i,k=1,2,…,N，j=1,2,…,T)，節(jié)點1到節(jié)點(i,j)的弧為回收弧(i=1,2,…,N，j=1,2,…,T)，節(jié)點(i,j)到節(jié)點2的弧為需求弧(i=1,2,…,N，j=1,2,…,T)。

令節(jié)點s到節(jié)點0的弧、回收弧和需求弧的集合為τ，那么多基地動態(tài)補貨網(wǎng)絡(luò)流模型，如下所示：

(4.1)

s.t.fij=cij(vi,vj)∈τ

(4.2)

0≤fij≤cij(vi,vj)∈A-τ

(4.3)

fij∈Ν(vi,vj)∈A

(4.4)

考慮到網(wǎng)絡(luò)D(0)=(V,A,C,B)中存在雙向的調(diào)運弧，借鑒文獻(xiàn)[28]的方法，即若存在兩個不同的頂點i和j，使得弧aij=(i,j)和aji=(j,i)都存在，那么在弧aij=(i,j)中增加一個虛擬點x，把弧aij=(i,j)變成兩條弧aix=(i,x)和弧axj=(x,j)，使得c(aix)=c(axj)=cij，b(aix)=b(axj)=0.5bij，直到任意兩個不同頂點間最多存在一條弧為止，并將此時的網(wǎng)絡(luò)記為D(1)。那么，將含有回收的動態(tài)網(wǎng)絡(luò)流模型的求解算法可以分為三步：

步驟1：取f(0)=0，為初始流。令k=0，在網(wǎng)絡(luò)D(1)中構(gòu)造賦權(quán)有向圖W(f(k))；

步驟2：在W(f(k))中，尋求從發(fā)點vs到收點vt的最短路，若不存在最短路(即最短路權(quán)是+)，則f(k)就是最小費用流，算法結(jié)束；若存在最短路，則在原網(wǎng)絡(luò)中得到相應(yīng)的增廣鏈μ，在增廣鏈μ上對f(k)進(jìn)行調(diào)整。調(diào)整量為：令

得到新的流f(k+1)，轉(zhuǎn)步驟3；

步驟3：對f(k+1)重復(fù)步驟2。

定理2在含有回收的動態(tài)補貨網(wǎng)絡(luò)流模型中采用最小費用流求解算法得到的流f*，其訂貨弧、調(diào)運弧、庫存弧上的流量即為模型R3的最優(yōu)解。

由于求解期初最優(yōu)訂貨總量的算法時間復(fù)雜度為Ο(N*T)，而在網(wǎng)絡(luò)中尋找從發(fā)點到收點的最短路的算法平均時間復(fù)雜度約為O(|V|2)=O((N*T+5)2)，增廣次數(shù)最壞情況下為X1，因此，整個算法的時間復(fù)雜度約為O(X1*(N*T)2)。

3.3 啟發(fā)式求解算法

這說明原問題最優(yōu)的總訂貨量也一定落在區(qū)間M上，其中，M=[X1,X2]。

為此，我們結(jié)合上述的網(wǎng)絡(luò)流求解算法，針對原問題即模型R2設(shè)計一個啟發(fā)式算法，具體算法步驟如下：

步驟1：調(diào)整網(wǎng)絡(luò)D(0)的容量和單位費用對，將節(jié)點0到節(jié)點(i,1)的弧(即訂貨弧)上的費用調(diào)整為ci，節(jié)點(i,j)到節(jié)點(i,j+1)的弧(即庫存弧)上的費用調(diào)整為hi，調(diào)整后的網(wǎng)絡(luò)記為D(2)。

步驟2：將區(qū)間M=[X1,X2]等分成Q份，其中各端點分別記為Xi=X1+?i(X2-X1)/Q」，其中?*」表示向下取整。

4 算例

本文以國內(nèi)某大型航空公司為例，分析某一種機上周轉(zhuǎn)品(沙拉碗)在一個訂貨周期內(nèi)的補貨策略。該公司在全國擁有八個基地，各基地位置及調(diào)運網(wǎng)絡(luò)如圖所示。

圖2 各基地位置及調(diào)運網(wǎng)絡(luò)圖

假設(shè)訂貨周期T=7(天)，各基地的參數(shù)設(shè)置如下：機上周轉(zhuǎn)品的單位訂貨成本為10(元/個)，單位存儲成本為0.1(元/個*天)，單位調(diào)運成本為0.01(元/個*天)，初始庫存量、日需求量、日回收量及日安全庫存量見表1～4。

由于上述參數(shù)滿足定理1的條件，因此通過定理1的計算公式可以得到期初最優(yōu)的訂貨總量為：x*=3571。

表1 各基地的初始庫存量

表2 各基地的日需求量

表3 各基地的日回收量

表4 各基地的日安全庫存量

通過最小費用流求解算法進(jìn)行求解，最終得到各基地最優(yōu)的期初訂貨量和每日最優(yōu)的調(diào)運量，見表5～6：

表5 各基地期初最優(yōu)的訂貨方案

下面分析各基地單位調(diào)運成本不同的情形，假設(shè)基地A與基地C之間的單位調(diào)運成本為0.02(元/個*天)，而其它參數(shù)保持不變。從定理1可知，期初最優(yōu)的訂貨總量依然為3571(個)。而各基地的期初最優(yōu)訂貨方案以及每日的調(diào)運方案如下：

表6 各基地間最優(yōu)的調(diào)運方案

表7 各基地期初最優(yōu)的訂貨方案

表8 各基地間最優(yōu)的調(diào)運方案

由于基地C到基地A的單位調(diào)運成本的增加，使得基地C調(diào)出到基地A的量減少，調(diào)出到其它基地(B、E、F、H)的量增加，進(jìn)而使得基地A的期初訂貨量增加，其它基地(B、E、F、H)的期初訂貨量減少。由此可以看出，訂貨和調(diào)運方案會受到各基地之間的單位調(diào)運成本的影響。

接下來分析當(dāng)各基地的單位訂貨成本和單位存儲成本不相同的情形。通過引理2的分析，得到各基地的期初缺貨量(見表9)。

表9 各基地的期初缺貨量

因此，原問題的期初最優(yōu)訂貨總量所處的區(qū)間為[3571，4151]。

假設(shè)基地A的單位訂貨成本為5(元/個)，而其它參數(shù)不變。令Q=10，ε=10-3，通過啟發(fā)式算法得到一個較優(yōu)的訂貨和調(diào)運方案如下：

表10 各基地期初的訂貨方案

表11 各基地間的調(diào)運方案

假設(shè)基地A的單位存儲成本為0.5(元/個*天)，而其它參數(shù)不變。令Q=10，ε=10-3，同樣通過啟發(fā)式算法得到一個較優(yōu)的訂貨和調(diào)運方案如下：

表12 各基地期初的訂貨方案

表13 各基地間的調(diào)運方案

通過上述兩個例子，可以得出期初的訂貨方案和每天的調(diào)運方案同樣也會受到單位訂貨成本以及單位存儲成本的影響。

通過該啟發(fā)式算法只能得到眾多可行解中的一個較優(yōu)的訂貨和調(diào)運方案，而通過對3.1節(jié)最優(yōu)解的分析，當(dāng)不滿足條件(C1)-(C3)下，目標(biāo)函數(shù)的單調(diào)性無法確定，進(jìn)而模型的最優(yōu)解很難得到，故而該啟發(fā)式算法的精度也不能確定；當(dāng)滿足條件(C1)-(C3)下，因為啟發(fā)式算法的可行解中包含最優(yōu)訂貨量(X1)，故最終得到的解相同。

接下來分析不同單位成本參數(shù)對整個系統(tǒng)總庫存成本的影響情況(見圖3～5)。

圖3 基地A的單位庫存成本的變化對整個系統(tǒng)總庫存成本的影響

圖4 基地之間的單位調(diào)運成本的變化對系統(tǒng)總庫存成本的影響

圖5 基地A的單位訂貨成本的變化對系統(tǒng)總庫存成本的影響

由此可見，各基地的單位訂貨成本、單位存儲成本以及各基地之間的調(diào)運成本會影響整個系統(tǒng)的總庫存成本，進(jìn)而影響到整個系統(tǒng)的訂貨和調(diào)運方案。

5 結(jié)語

本文研究航空公司機上周轉(zhuǎn)品多基地庫存優(yōu)化問題，構(gòu)建了一個單周期的動態(tài)補貨模型。該模型在已知每個基地的每日需求量、回收量及安全庫存量下，對期初的訂貨量以及每日的調(diào)入調(diào)出量進(jìn)行決策，使得整個系統(tǒng)的庫存總成本(包括訂貨成本、存儲成本、調(diào)運成本、回收成本)最小化。并對該模型的最優(yōu)解進(jìn)行了分析，參考網(wǎng)絡(luò)流算法，給出了一個在成本參數(shù)滿足一定條件下的多項式求解算法；此外，設(shè)計了一個求解原問題的啟發(fā)式算法。最終結(jié)合實際的例子，驗證了算法的有效性。但本文所提出的問題還有待深入研究的地方，比如考慮隨機需求、擴展到多周期的補貨問題等。

附錄：

(1)引理1的證明

(2)引理2的證明

(3)引理3的證明

當(dāng)條件(C1)(C2)成立時，將約束條件(2.2)-(2.4)代入模型R2的目標(biāo)函數(shù)G(xi,zit,yijt)并化簡可得：

(4)定理1的證明

(5)定理2的證明

對于最小費用流模型中的任何一個可行流f，若令節(jié)點0到節(jié)點(i,1)的弧上的流量為xi(i=1,2,…,N)，節(jié)點(i,j)到節(jié)點(i,j+1)的弧上的流量為zij(i=1,2,…,N，j=1,2,…,T-1)，節(jié)點(i,j)到節(jié)點(k,j)的弧上的流量為yikj(i≠k，i,k=1,2,…,N，j=1,2,…,T)，而其他弧上的單位費用為零，故由(4.1)可知此流的總輸送費用為：

由于f是一個可行流，因此由約束條件(4.2)可知其節(jié)點s到節(jié)點0的弧、回收弧和需求弧上的流量都等于其容量，并令xi=zi0，那么對任一個節(jié)點(i,j)，由出入流量平衡可知，

并且由約束(4.4)可知，xi,zit,yijt∈Ν，因此含有回收的網(wǎng)絡(luò)流模型中所有的可行流上訂貨、庫存和調(diào)運弧的流量皆為模型R3的可行解，并且目標(biāo)函數(shù)都一致。

下證，最小費用流算法一定能得到含有回收的網(wǎng)絡(luò)流模型中使得總費用最小的可行流。在含有回收的動態(tài)補貨網(wǎng)絡(luò)D(0)中，當(dāng)發(fā)點vs到訂貨點v0弧上的流量fs0小于其容量x*時，對于任意一個基地i，一定存在一條從發(fā)點vs到收點vt的路ξ，這條路經(jīng)過訂貨點v0和基地i的所有庫存點vit，且權(quán)值為c+Th<+。因此按照最小費用流算法可以依次調(diào)整權(quán)小于等于c+Th的從發(fā)點vs到收點vt的路(增廣鏈)上的流量，此時增廣鏈上一定包含弧集合τ中的一條或多條弧，直到弧集合τ上所有弧的流量都等于其容量，此時，已找不到從發(fā)點vs到收點vt的最短路，那么最終得到的流f*是最小費用流模型的一個可行流；由最小費用最大流問題可知，f*是所有流量等于的總費用最小的一個流，故f*是最小費用流模型中使得總費用最小的可行流。