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

陳玉仙

(長(zhǎng)沙航空職業(yè)技術(shù)學(xué)院，湖南 長(zhǎng)沙 410124)

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

1 單純形算法

1.1 算法基本思想

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

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

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

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

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

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

4)按步驟(3)進(jìn)行迭代，直到對(duì)應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件(這時(shí)目標(biāo)函數(shù)值不能再改善)，即得到問(wèn)題的最優(yōu)解。

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

2 物流運(yùn)輸問(wèn)題的模型

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

根據(jù)物流運(yùn)輸問(wèn)題模型的建立方法，可得其對(duì)應(yīng)的數(shù)學(xué)模型如下:

3 單純形算法在物流配送中的應(yīng)用

3.1 實(shí)際問(wèn)題建模

本節(jié)通過(guò)一個(gè)配送實(shí)例，說(shuō)明單純形算法在其中的應(yīng)用。

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

表1 配送費(fèi)用表(運(yùn)量單位:噸;運(yùn)費(fèi)單位:百元)

設(shè)xij表示從Ai到Bj的運(yùn)量，故可以得到模型為:

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

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

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

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

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

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

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

其中x表示非基變量，其他為基變量。基于圖2可得出進(jìn)基、出基變量和位勢(shì)即對(duì)偶變量(PualPi、PualPj)，從而求出檢驗(yàn)數(shù)。

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

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

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

圖3 迭代最終表

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

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

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

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

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

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

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

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

4 結(jié)論

文章對(duì)基于單純形算法優(yōu)化的物流配送費(fèi)用問(wèn)題進(jìn)行了分析，說(shuō)明了方案優(yōu)化的步驟，通過(guò)具體實(shí)例詳細(xì)論述了算法的優(yōu)化過(guò)程。可以看出，單純形算法簡(jiǎn)明扼要，每一步迭代都不斷逼近最優(yōu)值，在一定程度上避免了智能優(yōu)化算法的優(yōu)化停滯現(xiàn)象。算法便于編程實(shí)現(xiàn)，有利于推出不斷成熟的軟件包，也為物流行業(yè)的數(shù)字化提供了良好的軟件基礎(chǔ)平臺(tái)。

［1］M.Grazia Speranza，Paul Stahly.配送物流新趨勢(shì)［M］.張耀平，王明志，黃艾舟，譯.北京:清華大學(xué)出版社，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］盧厚清，張永良，王寧生.求解運(yùn)輸問(wèn)題的一種算法［J］.運(yùn)籌與管理，1999，8(1):27 －33.

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