汪 軍, 孫志紅, 劉信斌

(徐州空軍學(xué)院基礎(chǔ)部,江蘇徐州 221000)

防洪物資調(diào)運(yùn)的數(shù)學(xué)模型

汪 軍, 孫志紅, 劉信斌

(徐州空軍學(xué)院基礎(chǔ)部,江蘇徐州 221000)

首先構(gòu)建防洪物資調(diào)運(yùn)的交通網(wǎng)絡(luò)矩陣模型,并利用Dijkstra算法尋找各調(diào)運(yùn)節(jié)點(diǎn)之間的最優(yōu)路線,然后在平時(shí)以追求最小總調(diào)運(yùn)費(fèi)用、緊急情況下以追求最快調(diào)運(yùn)速度為目標(biāo)建立了防洪物資調(diào)運(yùn)的優(yōu)化模型,在此過程中引入偏離控制量以便充分考慮各調(diào)運(yùn)節(jié)點(diǎn)的需求,討論了調(diào)運(yùn)期、偏離控制量對(duì)調(diào)運(yùn)費(fèi)用的影響,為科學(xué)制定調(diào)運(yùn)方案提供依據(jù),較好地解決了防洪物資的調(diào)運(yùn)問題.

物資調(diào)運(yùn);Dijkstra算法;偏離控制量;調(diào)運(yùn)節(jié)點(diǎn)

1 問題背景及重述

2007年5月江蘇省工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)及中國礦業(yè)大學(xué)聯(lián)合主辦了第四屆蘇北數(shù)學(xué)建模聯(lián)賽,聯(lián)賽得到包括武漢大學(xué)、國防科技大學(xué)、中國農(nóng)業(yè)大學(xué)等跨及全國12個(gè)省市60多所高校的積極參與,本文詣在解決其中的C題——防洪物資調(diào)運(yùn)問題.

2 模型假設(shè)

(i)高等級(jí)公路與普通級(jí)公路的調(diào)運(yùn)速度是恒定且相等的;

(ii)各企業(yè)、物資倉庫及國家級(jí)倉儲(chǔ)庫之間的物資可以通過公路運(yùn)輸互相調(diào)運(yùn)且所有公路均可雙向運(yùn)輸;

(iii)調(diào)運(yùn)物資的運(yùn)輸車輛是充足的,即一旦確定調(diào)運(yùn)方案,即刻可調(diào)運(yùn)完畢;

(iv)調(diào)運(yùn)節(jié)點(diǎn)指生產(chǎn)企業(yè)、物資倉庫、國家儲(chǔ)備庫共13個(gè),調(diào)運(yùn)期系指開始實(shí)施調(diào)運(yùn)的時(shí)間;

(v)只考慮運(yùn)輸費(fèi)用,不考慮物資裝卸、儲(chǔ)存等其它費(fèi)用.

3 變量及符號(hào)假設(shè)

ri——調(diào)運(yùn)節(jié)點(diǎn)i調(diào)運(yùn)后的庫存量(百件)

xij——從調(diào)運(yùn)節(jié)點(diǎn)i到調(diào)運(yùn)節(jié)點(diǎn)j之間的物資調(diào)運(yùn)量(百件)Mi——調(diào)運(yùn)節(jié)點(diǎn)i的最大庫存量(百件)

為了實(shí)現(xiàn)城市規(guī)劃中各中心城區(qū)與邊緣居住綠色分隔，要對(duì)當(dāng)?shù)氐膶?shí)際情況進(jìn)行調(diào)查分析，并根據(jù)不同的地理環(huán)境，遵循景觀生態(tài)學(xué)的原理與方法科學(xué)合理的布局，從而更好的保護(hù)耕地，有效提升耕地綜合利用率。

fi——調(diào)運(yùn)節(jié)點(diǎn)i的預(yù)測(cè)庫存量(百件)

vi——生產(chǎn)企業(yè)i的產(chǎn)量(百件/天),i=1,2,3

ti——生產(chǎn)企業(yè)i在調(diào)運(yùn)期的生產(chǎn)天數(shù)(天)

z——總調(diào)運(yùn)費(fèi)用(元)

4 問題分析

通過對(duì)問題的分析,該地區(qū)的公路交通網(wǎng)絡(luò)數(shù)學(xué)模型應(yīng)該是指包含42個(gè)頂點(diǎn)的賦權(quán)圖.所謂合理的調(diào)運(yùn)方案就是要在盡可能地滿足各個(gè)調(diào)運(yùn)節(jié)點(diǎn)需求的前提下,平時(shí)盡量使調(diào)運(yùn)費(fèi)用最小,而在緊急情況下應(yīng)盡快地將防洪物資調(diào)運(yùn)到各需求點(diǎn),這些都需要去尋找各調(diào)運(yùn)節(jié)點(diǎn)之間的最優(yōu)路徑,所以這是一個(gè)優(yōu)化問題,可以考慮建立該問題的規(guī)劃模型.

5 模型的建立及求解

1.交通網(wǎng)絡(luò)模型

在該地區(qū)交通網(wǎng)絡(luò)圖中調(diào)運(yùn)節(jié)點(diǎn)共有13個(gè),包括企業(yè)三家、物資倉庫八個(gè)、國家儲(chǔ)備庫兩個(gè),為表達(dá)方便,我們按企業(yè)1,企業(yè)2、企業(yè)3、物資倉庫1、……、物資倉庫8、國家儲(chǔ)備庫1、國家儲(chǔ)備庫2的順序編號(hào)為1到13,防洪物資的調(diào)運(yùn)只限于在13個(gè)節(jié)點(diǎn)之間進(jìn)行調(diào)運(yùn),故需找到它們之間的最優(yōu)調(diào)運(yùn)路線,平時(shí)應(yīng)以最少運(yùn)輸成本W(wǎng)ij(i,j=1,2,…,13)為優(yōu).這里尋找最優(yōu)路線時(shí)我們用Dijkstra算法來解決.

2.問題2及問題3的模型建立及求解

問題2要求設(shè)計(jì)一個(gè)在重點(diǎn)保證國家級(jí)儲(chǔ)備庫的情況下的合理調(diào)運(yùn)方案,為此設(shè)從調(diào)運(yùn)節(jié)點(diǎn)i到調(diào)運(yùn)節(jié)點(diǎn)j的調(diào)運(yùn)量為xij(百件),xij≥0,i,j=1,2,…,13.則調(diào)運(yùn)結(jié)束后各個(gè)調(diào)運(yùn)節(jié)點(diǎn)的庫存量為

為重點(diǎn)保證國家級(jí)儲(chǔ)備庫的庫存,合理調(diào)運(yùn)方案必須使國家級(jí)儲(chǔ)備庫的庫存達(dá)到或者超過其預(yù)測(cè)值:ri≥fi,i=12,13.倉庫1到倉庫8的應(yīng)盡量達(dá)到或超過預(yù)測(cè)庫存,為此考慮用一個(gè)偏離控制量ε(ε＞0)來控制,即

根據(jù)調(diào)運(yùn)計(jì)劃及各企業(yè)生產(chǎn)能力,調(diào)運(yùn)期至少應(yīng)為8天,才能滿足基本要求,若給定ε=0.05,通過Lingo求解得調(diào)運(yùn)方案見表1.

表1 調(diào)運(yùn)期為8天時(shí)的最優(yōu)調(diào)運(yùn)方案

按此方案調(diào)運(yùn)的最低總運(yùn)輸費(fèi)用為321680元.

對(duì)于問題3,在問題2中令T=20,可以計(jì)算求得新的調(diào)運(yùn)方案,此時(shí)調(diào)運(yùn)總費(fèi)用為299763元, 20天后各個(gè)調(diào)運(yùn)節(jié)點(diǎn)的庫存情況如表2所示.

表2 20天后各個(gè)調(diào)運(yùn)節(jié)點(diǎn)的庫存

3.問題4的模型建立及求解

問題4要求解決汛期部分路段中斷情況下的緊急調(diào)運(yùn)問題,此時(shí)應(yīng)該考慮速度盡可能快,而無須考慮運(yùn)費(fèi).鑒于洪水導(dǎo)致路段中斷,故應(yīng)構(gòu)建新的交通網(wǎng)絡(luò)賦權(quán)圖G(V,E′),其中每條邊的權(quán)值為smn,E′為集合E中去除邊○14○23,○11○25,○26○27,⑨○31的集合,利用Dijkstra算法計(jì)算各調(diào)運(yùn)節(jié)點(diǎn)之間的最短路徑Sij(i,j=1,2,…,13),在問題2中將目標(biāo)函數(shù)修改為

以8天為調(diào)運(yùn)期,在約束條件不變的情況下,得到最優(yōu)調(diào)運(yùn)方案如表3.

表3 調(diào)運(yùn)期為8天時(shí)緊急情況下的最優(yōu)調(diào)運(yùn)方案

6 模型的進(jìn)一步討論

1.調(diào)運(yùn)期的長短與運(yùn)費(fèi)的關(guān)系

在求解問題2和問題3的時(shí)候,我們發(fā)現(xiàn),在調(diào)運(yùn)期為8天的時(shí)候,總運(yùn)費(fèi)為321680元,調(diào)運(yùn)期為20天的時(shí)候,總運(yùn)費(fèi)為299763元.顯然,調(diào)運(yùn)期的長短對(duì)最終運(yùn)費(fèi)有著顯著影響.

我們希望能夠找到一個(gè)最佳的時(shí)間,使得總運(yùn)費(fèi)能夠達(dá)到最小,同時(shí)使各調(diào)運(yùn)點(diǎn)的庫存能夠達(dá)到或超過預(yù)測(cè)值.為此對(duì)問題2中的模型進(jìn)行修改,建立最佳時(shí)間模型如下.

在這個(gè)模型中,要求在調(diào)運(yùn)完畢后,各庫的庫存都要達(dá)到或超過預(yù)測(cè)值.令T=8,9,10,…,計(jì)算得到調(diào)運(yùn)期與總調(diào)運(yùn)費(fèi)用之間的關(guān)系如圖1.

圖1 調(diào)運(yùn)期與總調(diào)運(yùn)費(fèi)用之間的關(guān)系

從圖1可以看出,隨著調(diào)運(yùn)期的增加,總的調(diào)運(yùn)費(fèi)用不斷下降.當(dāng)T增加到22天的時(shí)候,調(diào)運(yùn)費(fèi)用趨于平衡,不再發(fā)生改變.造成這種情況的原因是,隨著調(diào)運(yùn)期限的增加,企業(yè)可用來生產(chǎn)的天數(shù)也增加,因而企業(yè)能夠運(yùn)出的物資量也增加,相應(yīng)的輸出選擇面和靈活度也增加,從而使總運(yùn)費(fèi)降低.因此,根據(jù)此模型防汛部門可以科學(xué)制訂調(diào)運(yùn)期,特別是在準(zhǔn)確預(yù)測(cè)汛期的情況下,對(duì)于提前做好科學(xué)決策有重要意義.

2.調(diào)運(yùn)期的長短、ε的取值對(duì)費(fèi)用的影響

ε的取值對(duì)于費(fèi)用也有著重要的影響,我們希望能夠找到ε和T對(duì)于總費(fèi)用的影響效果.為此,在問題2的模型中,分別取不同的ε和T值從而得到總調(diào)運(yùn)費(fèi)用與ε及調(diào)運(yùn)期T的關(guān)系如圖2.

圖2 總調(diào)運(yùn)費(fèi)用與ε及調(diào)運(yùn)期T的關(guān)系

從圖2可以看到,總調(diào)運(yùn)費(fèi)用均隨著偏離控制量ε和物資生產(chǎn)天數(shù)T的增加而減少.這是非常符合實(shí)際情況的,因?yàn)棣诺脑龃笫沟眉s束條件減弱,因而總的調(diào)運(yùn)費(fèi)用降低;物資調(diào)運(yùn)期T的增加使得各個(gè)企業(yè)的產(chǎn)量增大,故導(dǎo)致調(diào)運(yùn)任務(wù)的靈活性增加,因而總的調(diào)運(yùn)費(fèi)用降低.同時(shí),從圖2可以很明顯地看出:ε波動(dòng)對(duì)總調(diào)運(yùn)費(fèi)用的影響比物資調(diào)運(yùn)期T的改變對(duì)總調(diào)運(yùn)費(fèi)用的影響要大.所以ε的控制效果是非常明顯的.

[1] 汪軍,等.戰(zhàn)時(shí)航空油料的優(yōu)化調(diào)撥[J].南京航空航天大學(xué)學(xué)報(bào),1999,31(1):112-115.

[2] 姜啟源,等.數(shù)學(xué)模型[M].北京:高等教育出版社,2004.

[3] 錢頌迪,等.運(yùn)籌學(xué)[M].北京:清華大學(xué)出版社,1990.

[4] 袁新生,邵大宏,等.L INGO和Excel在數(shù)學(xué)建模中的應(yīng)用[M].北京:科學(xué)出版社,2007.

[5] 謝金星薛毅.優(yōu)化建模與L INGO/L INDO軟件[M].北京:清華大學(xué)出版社,2004.

Mathematics M odel on Flood-Preven ting Material D ispatching

WANGJun,SUNZhi-hong,LIUXin-bin
(Foundation Department,Xuzhou Airforce College,Xuzhou 221000,China)

The dispatching netwo rk matrix modelwas constructed firstly,and the op timal dispatching routes between allocating and transporting points were seeked by virtue of Dijkstra algorithm.Furthermore,the optimal model of flood p revention material dispatching was constructed in pursuit of the fastest transferring speed in emergency.

In this p rocess,in o rder to fully consider the needsof all transport node,the deviate control variable was introduced, and the impact of the transpo rtation period,the deviate control variable on transpo rt costswere discussed,w hich p rovides the scientific basis fo r transferring p rogram,and give a better solution to flood-p reventing material dispatching p roblem.

material dispatching;Dijkstra algo rithm;deviate control variable;transport node

O221.1

B

1672-1454(2010)03-0137-05

2007-10-26