整單數量價格折扣運輸問題新的簡便解法

□ 賈春玉

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

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

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

1.1 整單數量價格折扣

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

1.2 數量價格折扣的描述

(1)

1.3 整單數量價格折扣運輸問題數學模型

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

(2)

(3)

(4)

(5)

Xij≥0

(6)

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

2.1 新方法求解過程及原理

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

2.2 最優解區間及優化程度的確定

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

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

優化程度≥1-100%×(優化結果數值-最優解下限)/最優解下限

3 計算實例

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

表2 第一次規劃求解、第一次調整可行解Sheet2

表3 第二次規劃求解、第二次調整可行解Sheet2

解:①首先求解，給出第一次規劃求解后可行調整方案。

a.第一次規劃求解過程和結果如下：

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

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

b.給出第一次規劃求解后可行調整方案：

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

②然后進行第二次規劃求解，給出第二次規劃求解后可行調整方案。

a.第二次規劃求解過程和結果如下：

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

b.給出第二次規劃求解后可行調整方案：

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

③擇優選取最好的方案作為近似最優解

因為第一次調整后可行方案為63442,大于第二次調整后可行方案為63302,所以，選第二次調整后可行方案為近似最優解。

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

4 二次規劃求解調整解比較分析

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

5 結論

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