整單數(shù)量?jī)r(jià)格折扣運(yùn)輸問(wèn)題新的簡(jiǎn)便解法

□ 賈春玉

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

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

1 整單數(shù)量?jī)r(jià)格折扣運(yùn)輸問(wèn)題的描述

1.1 整單數(shù)量?jī)r(jià)格折扣

價(jià)格折扣形式常見(jiàn)有整單數(shù)量?jī)r(jià)格折扣和分段增量?jī)r(jià)格折扣(連續(xù)計(jì)價(jià)模式)。整單數(shù)量?jī)r(jià)格折扣是指不同的運(yùn)輸量，單位運(yùn)價(jià)不同整單只按一個(gè)價(jià)格計(jì)價(jià)；分段增量?jī)r(jià)格折扣(連續(xù)計(jì)價(jià)模式)，對(duì)超出一定數(shù)量的運(yùn)量進(jìn)行價(jià)格折扣，沒(méi)超出部分價(jià)格不折扣。

1.2 數(shù)量?jī)r(jià)格折扣的描述

(1)

1.3 整單數(shù)量?jī)r(jià)格折扣運(yùn)輸問(wèn)題數(shù)學(xué)模型

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

(2)

(3)

(4)

(5)

Xij≥0

(6)

2 整單數(shù)量?jī)r(jià)格折扣運(yùn)輸問(wèn)題新解法原理

2.1 新方法求解過(guò)程及原理

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

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

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

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

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

3 計(jì)算實(shí)例

表1 原始數(shù)據(jù)sheet1(全部?jī)r(jià)格)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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