□ 賈春玉

(寧波工程學(xué)院,浙江 寧波 315211)

經(jīng)典運輸問題是指單位運價固定不變，許多學(xué)者作了大量研究[1-5],有效解法很多。運輸問題可以擴展為很多種類型，如多目標(biāo)運輸問題、運量及時間限制問題、具有價格折扣和無價格折扣等問題。對于有運價折扣的運輸問題，國內(nèi)外相關(guān)研究很少，國內(nèi)只查到3篇相關(guān)論文[6-8]，且只是針對連續(xù)折扣計價模式,分別用遺傳算法、分支定界法和表上作業(yè)法求解。遺傳算法雖然能解決這類問題，但復(fù)雜、不易掌握、優(yōu)化程度不高;分支定界法繁瑣和表上作業(yè)法相對繁瑣、效率不高。尚沒查到整單數(shù)量價格折扣運輸問題解法相關(guān)文獻，因此，需要研究簡便、易掌握的新的解法。

1 整單數(shù)量價格折扣運輸問題的描述

1.1 整單數(shù)量價格折扣

價格折扣形式常見有整單數(shù)量價格折扣和分段增量價格折扣(連續(xù)計價模式)。整單數(shù)量價格折扣是指不同的運輸量，單位運價不同整單只按一個價格計價；分段增量價格折扣(連續(xù)計價模式)，對超出一定數(shù)量的運量進行價格折扣，沒超出部分價格不折扣。

1.2 數(shù)量價格折扣的描述

(1)

1.3 整單數(shù)量價格折扣運輸問題數(shù)學(xué)模型

為了簡化起見，這里直接討論產(chǎn)銷平衡運輸問題(不平衡虛擬一行或一列就可變成平衡問題)，根據(jù)上面的假設(shè)和描述，可得整單數(shù)量價格折扣運輸問題數(shù)學(xué)模型中目標(biāo)函數(shù)為：

(2)

(3)

(4)

(5)

Xij≥0

(6)

2 整單數(shù)量價格折扣運輸問題新解法原理

2.1 新方法求解過程及原理

這類問題是非線性規(guī)劃問題,雖然可用遺傳算法和分支定界法求解，但不易掌握、效率不高，為了解決這一問題，提出新的簡便解法獲得近似最優(yōu)解。新的解法是取全部價格，然后規(guī)劃求解，再根據(jù)求解結(jié)果方案中運量數(shù)值大小,根據(jù)價格折扣區(qū)間調(diào)整對應(yīng)運價，求出第一次調(diào)整可行解,在此基礎(chǔ)上根據(jù)調(diào)整后的運價,再規(guī)劃求解,再根據(jù)求解結(jié)果方案中運量數(shù)值大小,根據(jù)價格折扣區(qū)間調(diào)整對應(yīng)運價，求出第二次調(diào)整可行解。新的解法運用Excel規(guī)劃求解和相關(guān)Excel計算公式，可快速、高效給出優(yōu)化方案。

2.2 最優(yōu)解區(qū)間及優(yōu)化程度的確定

最優(yōu)解下限，所有價格均按最低價格，然后規(guī)劃求解，得出規(guī)劃求解數(shù)值即為最優(yōu)解下限。知道下限，可解決至少需要多少運費。

最優(yōu)解上限，所有價格均按最高(無折扣)價格，然后規(guī)劃求解，得出規(guī)劃求解數(shù)值即為最優(yōu)解上限。知道上限，可知道最多需要多少運費。

優(yōu)化程度≥1-100%×(優(yōu)化結(jié)果數(shù)值-最優(yōu)解下限)/最優(yōu)解下限

3 計算實例

表1 原始數(shù)據(jù)sheet1(全部價格)

表2 第一次規(guī)劃求解、第一次調(diào)整可行解Sheet2

表3 第二次規(guī)劃求解、第二次調(diào)整可行解Sheet2

解:①首先求解，給出第一次規(guī)劃求解后可行調(diào)整方案。

a.第一次規(guī)劃求解過程和結(jié)果如下：

表2中單元格K21=SUM(C21∶J21),即該行變量之和,K22至K25與此類似,從略;C26= SUM(C21∶C25),即該列變量之和,D26至J26與此類似,從略;C27=C26+C27,即第一個需求點變量之和,E27、G27、I27與此類似，從略；目標(biāo)函數(shù)單元格C29= SUMPRODUCT(C4∶J8,C21∶J25)。需求量為C28=C9，余者類推，從略。

Excel規(guī)劃求解參數(shù)如下：目標(biāo)函數(shù)為單元格C29，變量為C21∶J25，約束條件為，K21∶K25=L21∶L25，C27=C28，E27=E28，G27=G28，I27=I28，即每行變量之和等于該行供應(yīng)量，每個需求點運輸量之和等于各需求點需求量。選擇變量為非負(fù)，線性規(guī)劃(或選者單純型法)，然后點擊求解，可自動求出規(guī)劃求解方案，求解結(jié)果參見表2區(qū)域C21∶J25數(shù)值，此時目標(biāo)函數(shù)為60800(最優(yōu)解下限)。

b.給出第一次規(guī)劃求解后可行調(diào)整方案：

在表2中，單位運價(區(qū)域C32∶J36)是根據(jù)區(qū)域C21∶J25的數(shù)值，運用條件語句，調(diào)整后的單位運價，例如C32=IF(C21<=C12,C4,D4)，余者類似，從略。單元格C37為第一次規(guī)劃求解結(jié)果(變量數(shù)值)與調(diào)整后單位運價計算的總運費,計算公式為:C37=SUMPRODUCT(C21∶J25,C32∶J36),數(shù)值為63442。

②然后進行第二次規(guī)劃求解，給出第二次規(guī)劃求解后可行調(diào)整方案。

a.第二次規(guī)劃求解過程和結(jié)果如下：

第二次規(guī)劃求解基礎(chǔ)數(shù)據(jù)等于第一次規(guī)劃求解原始數(shù)據(jù)(sheet1)，即sheet2區(qū)域B2∶K17與sheet1對應(yīng)區(qū)域完全相等，為了節(jié)省篇幅從略省去這部分。規(guī)劃約束條件等與第一次規(guī)劃求解類似,從略,目標(biāo)函數(shù)單元格(C29)與第一次規(guī)劃求解不同，C29= SUMPRODUCT(C32∶J36,C21∶J25)。區(qū)域C32∶J36等于表2(sheet1)中區(qū)域C32∶J36數(shù)值，即根據(jù)第一次規(guī)劃求解調(diào)整后的單位運價，規(guī)劃求解方案參見表3區(qū)域C21∶J25數(shù)值，此時目標(biāo)函數(shù)為63302。

b.給出第二次規(guī)劃求解后可行調(diào)整方案：

與第一次單位運價調(diào)整類似，第二次規(guī)劃求解后調(diào)整運價為區(qū)域C39：J43，單元格C44為根據(jù)第二次規(guī)劃求解結(jié)果，計算公式為C44=SUMPRODUCT(C21:J25,C39:J44)，數(shù)值63302，參見表3。

③擇優(yōu)選取最好的方案作為近似最優(yōu)解

因為第一次調(diào)整后可行方案為63442,大于第二次調(diào)整后可行方案為63302,所以，選第二次調(diào)整后可行方案為近似最優(yōu)解。

優(yōu)化程度≥[1-(63302-60800)/60800]×100%≈96%

4 二次規(guī)劃求解調(diào)整解比較分析

隨即選取30個運輸問題樣本，樣本中均采用5個供應(yīng)地、4個需求地，單位價格、數(shù)量折扣區(qū)間、各地需求流量、各供應(yīng)地供應(yīng)量隨即變化。按全部運價二次求解結(jié)果，第一次規(guī)劃求解調(diào)整解小于二次為20次，占66.7%，大于9次占30%，二者相等1次，占0.3%；優(yōu)化程度最低93.5%,最高100%，平均至少96,78%。

5 結(jié)論

具有價格數(shù)量折扣運輸問題是復(fù)雜組合優(yōu)化問題，雖然可用智能搜索、分支定界法等方法求解，但方法復(fù)雜、求解效率不高、優(yōu)化程度不夠理想。新的簡便解法按全部運價進行二次規(guī)劃求解法并調(diào)整優(yōu)化方案，可高效、快速獲得優(yōu)化程度高的近似最優(yōu)解。雖然第一次規(guī)劃求解后獲得調(diào)整后可行解優(yōu)化程度明顯高于第二次規(guī)劃求解后獲得調(diào)整可行解，但為了提高優(yōu)化程度，應(yīng)進行第二次規(guī)劃求解，二者擇優(yōu)，作為最終優(yōu)化方案。新方法簡單、易于掌握、優(yōu)化程度高，平均優(yōu)化程度至少在96.7%以上，優(yōu)化程度理想。