基于單純形算法的物流配送費用優(yōu)化

陳玉仙

(長沙航空職業(yè)技術學院，湖南 長沙 410124)

隨著國民經(jīng)濟的不斷發(fā)展，作為“第三方利潤源”的物流業(yè)也日益興隆。為了節(jié)省物流成本，尋找一種合適的物流配送路徑成為物流業(yè)亟待解決的問題。［1－4］由于配送環(huán)境的不確定性和約束條件的復雜性，不少智能優(yōu)化算法被引入作為優(yōu)化配送路徑的決策工具。［5－8］一般的智能尋優(yōu)算法難以找到合理的優(yōu)化最值，并且軟件維護成本較高，因此對于一些問題并不是首選的尋優(yōu)工具。而一些傳統(tǒng)的優(yōu)化方案如單純形算法，由于其理論框架的完整性、使用的方便性和軟件界面的清晰性又重新被決策者所青睞。［9－10］文章通過引入合適的單純形算法，并應用于物流配送成本的控制中，取得了良好的優(yōu)化效果。

1 單純形算法

1.1 算法基本思想

單純形算法是一種求解優(yōu)化問題的通用算法，由美國數(shù)學家Dantzig于1947年首先提出來的。其理論根據(jù)是:待優(yōu)化問題的解空間是n維向量空間中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點處達到，頂點所對應的可行解稱為基本可行解。單純形法的基本思想是:先找出一個基本可行解，對它進行鑒別，看是否是最優(yōu)解;若不是，則按照一定法則轉換到另一改進的基本可行解，再鑒別;若仍不是，則再轉換，按此重復進行。因基本可行解的個數(shù)有限，故經(jīng)有限次轉換必能得出問題的最優(yōu)解。如果問題無最優(yōu)解也可用此法判別。

1.2 算法一般優(yōu)化步驟

單純形法的一般解題步驟可歸納如下:

1)將待優(yōu)化問題的約束方程組表達成典范型方程組，找出基本可行解作為初始基本可行解。

2)若基本可行解不存在，即約束條件有矛盾，則問題無解。

3)若基本可行解存在，從初始基本可行解作為起點，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數(shù)值更優(yōu)的另一基本可行解。

4)按步驟(3)進行迭代，直到對應檢驗數(shù)滿足最優(yōu)性條件(這時目標函數(shù)值不能再改善)，即得到問題的最優(yōu)解。

5)若迭代過程中發(fā)現(xiàn)問題的目標函數(shù)值無界，則終止迭代。

2 物流運輸問題的模型

已知有m個生產(chǎn)地Ai(i=1－m)，可供應某種物資，其供應的產(chǎn)量分別為ai(i=1－m)。有n個銷地Bj(j=1－n)，其需要量分別為bi(i=1－n)。運輸單位物資的運價(單價)為Cij，Xij表示從Ai到Bj的運量。在滿足各地需要的前提下，要求總運輸費用最小的配送方案。

根據(jù)物流運輸問題模型的建立方法，可得其對應的數(shù)學模型如下:

3 單純形算法在物流配送中的應用

3.1 實際問題建模

本節(jié)通過一個配送實例，說明單純形算法在其中的應用。

設某公司從三個產(chǎn)地A1、A2、A3將物品運往四個銷地 B1、B2、B3、B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如表1所示，求調度方案使總配送費用最小。

表1 配送費用表(運量單位:噸;運費單位:百元)

設xij表示從Ai到Bj的運量，故可以得到模型為:

3.2 基于WinQSB軟件的配送費用優(yōu)化

為了直觀起見，采用WinQSB軟件對單純形算法進行仿真分析以求解物流配送優(yōu)化問題。過程如下:

1)輸入相關數(shù)據(jù)，如圖1所示:

圖1 WinQSB輸入數(shù)據(jù)表

2)選擇元素差額法(Vogel近似法)求初始基本可行解。第一次迭代后的數(shù)據(jù)如圖2所示。

圖2 第一次迭代后數(shù)據(jù)表

將圖2中的優(yōu)化結果看成原始調度方案，可以得到如下結論:A1→B2，運量為 30;A1→B3，運量為 20;A2→B3，運量為40;A3→B1，運量為60;A3→B3，運量為 10;A3→B4，運量為10;總運費為 =30*10+20*5+40*7+60*12+10*15+10*10=1650。由圖2可以得知用元素差額法得到下列一組基本可行解:

其中x表示非基變量，其他為基變量?；趫D2可得出進基、出基變量和位勢即對偶變量(PualPi、PualPj)，從而求出檢驗數(shù)。

用位勢法求檢驗數(shù)的公式如式(5)所示。

其中I為問題基變量XB的下標集合，λij是問題的松弛變量。因此可以得出檢驗數(shù):

由檢驗數(shù)不全部非負可知得到的基可行解不是最優(yōu)解。由X42得檢驗數(shù)最小，而X44得運費最高得，將X44的運量作為出基變量，而將X42作為進基變量換基進行第二次迭代，通過不斷地改變基變量依次得到相應的優(yōu)化值。經(jīng)若干次迭代后得到數(shù)據(jù)如圖3所示。

圖3 迭代最終表

3)驗證最優(yōu)解

由圖3可以得知用元素差額法得到下列一組基本可行解:

其中x表示非基變量，其他為基變量。在圖3中還可以看出進基、出基變量，還可以得到位勢即對偶變量(PualPi、PualPj)，從而求出檢驗數(shù)。

因此由公式(5)可以得出檢驗數(shù):

圖4 最優(yōu)運輸方案

由以上的檢驗數(shù)全部非負可知，得到最優(yōu)解。最終得到的最優(yōu)配送方案如圖4所示。

故最優(yōu)配送方案如下:A1→B3，運量為50;A2→B1，運量為 20;A2→B3，運量為 20;A3→B1，運量為 40;A3→B2，運量為 20;A3→B4，運量為 20;總運費為=50*5+20*6+20*7+40*12+20*14+20*10=1470。

將最終方案與初始方案相比較，初始方案的配送費用=1650，而最終方案的配送費用=1470，可以得知最終方案配送費用比初始方案要節(jié)約180，從而優(yōu)化了物流配送費用。

4 結論

文章對基于單純形算法優(yōu)化的物流配送費用問題進行了分析，說明了方案優(yōu)化的步驟，通過具體實例詳細論述了算法的優(yōu)化過程?？梢钥闯觯瑔渭冃嗡惴ê喢鞫笠?，每一步迭代都不斷逼近最優(yōu)值，在一定程度上避免了智能優(yōu)化算法的優(yōu)化停滯現(xiàn)象。算法便于編程實現(xiàn)，有利于推出不斷成熟的軟件包，也為物流行業(yè)的數(shù)字化提供了良好的軟件基礎平臺。

［1］M.Grazia Speranza，Paul Stahly.配送物流新趨勢［M］.張耀平，王明志，黃艾舟，譯.北京:清華大學出版社，2004:79－92.

［2］Shad Dowlatshahi.A modeling approach to logistics in concurrent engineering［J］.European Journal of Operational Research，1999，115:59－76.

［3］Sung Hun Song，Kwan Suk Lee，Gi Sub Kim.A practical approach to solving a newspaper logistics problem using a digital map［J］.Computer ＆ Industrial Engineering，2002，43:315 －330.

［4］Lifei Cheng，Marco A.Duran.Logistics for world－ wide crude oil transportation using discrete event simulation and optimal control［J］.Computer and Chemical Engineering，2004，28:897 －911.

［5］Hongbo Li，Zengqi Sun，Badong Chen，et al.Intelligent scheduling controller design for networked control systems based on estimation of distribution algorithm［J］.Tsinghua Science＆ Technology，2008，13(1):71－77.

［6］A.Sadegheih.Optimization of network planning by the novel hybrid algorithms of intelligent optimization techniques.Energy，2009，34(10):1539 －1551.

［7］Feizhou Zhang，Xuejun Cao，Dongkai Yang.Intelligent scheduling of public traffic vehicles based on a hybrid genetic algorithm［J］.Tsinghua Science ＆ Technology，2008，13(5);625 －631.

［8］Mohammad Reza Sadeghi Moghadam，Amir Afsar，Babak Sohrabi.Inventory lot－ sizing with supplier selection using hybrid intelligent algorithm［J］.Applied Soft Computing，2008，8(4):1523 －1529.

［9］盧厚清，張永良，王寧生.求解運輸問題的一種算法［J］.運籌與管理，1999，8(1):27 －33.

［10］李軍，郭耀煌.物流配送車輛優(yōu)化調度理論與方法［M］.北京:中國物資出版社，2001:172－182.