吳施 楊金凇

摘 要：生產(chǎn)救災(zāi)物資生產(chǎn)廠家分布在全國(guó)各地。除了捐贈(zèng)以外，其余的救災(zāi)物資由國(guó)家救災(zāi)指揮部統(tǒng)一購(gòu)買。政府需要支付救災(zāi)物資的購(gòu)買費(fèi)用以及物資運(yùn)輸費(fèi)用。根據(jù)發(fā)生災(zāi)害的具體情況，初步有一個(gè)總費(fèi)用計(jì)劃，再根據(jù)災(zāi)害的情況不斷進(jìn)行調(diào)整。由于政府的預(yù)算資金有限，希望以最小的費(fèi)用代價(jià)，最優(yōu)的完成救災(zāi)物資的訂購(gòu)和運(yùn)輸要求。

問(wèn)題一：針對(duì)以最小費(fèi)用最優(yōu)的完成物資訂購(gòu)與運(yùn)輸問(wèn)題，建立費(fèi)用優(yōu)化模型。根據(jù)題目中具體的限制條件，由于部分物資的使用是可以相互替代的，供應(yīng)商的供應(yīng)能力有限，有生產(chǎn)的最大值，對(duì)每個(gè)地區(qū)而言，有最低需求量和額外需求量，確立出可以解決實(shí)際自然災(zāi)害的費(fèi)用優(yōu)化模型。

問(wèn)題二：針對(duì)供應(yīng)廠家S到物資需求方D最優(yōu)運(yùn)輸路線的解法，使用Dijkstra算法，使用MATLAB編寫程序，得出滿足費(fèi)用最小的條件下的最優(yōu)路徑，得出從10個(gè)供應(yīng)廠家到18個(gè)物資需求方的運(yùn)輸五種不同物資的最優(yōu)路線，共有900個(gè)結(jié)果。針對(duì)最小費(fèi)用的解法，根據(jù)第一問(wèn)所建立的優(yōu)化模型，帶入附表中的具體數(shù)據(jù)，使用lingo編寫程序，得到滿足供應(yīng)商和物資需求方的最優(yōu)化的費(fèi)用為0.9224303×1012元。

關(guān)鍵詞：優(yōu)化模型 Dijkstra算法 最短路徑

一、問(wèn)題重述

救災(zāi)物資生產(chǎn)廠家分布在全國(guó)各地。 除了生產(chǎn)廠家的捐贈(zèng)以外，另外的物資由國(guó)家救災(zāi)指揮部統(tǒng)一購(gòu)買，各個(gè)地區(qū)的民政部門負(fù)責(zé)本地區(qū)的物資集中和運(yùn)送。需要付出物資的購(gòu)買費(fèi)用以及運(yùn)輸費(fèi)用。

現(xiàn)在已知：產(chǎn)品的生產(chǎn)廠家有10家，用 Si，i=1，2…10表示，能夠提供的物資有5種，分別是：M1，M2 ，M3 ，M4 ，M5 。需要物資供應(yīng)的地區(qū)有18個(gè)，用 Dj，j=1，2…18 表示。各個(gè)廠家的生產(chǎn)能力，以及需求地區(qū)的需求數(shù)量已知。根據(jù)物資實(shí)際生產(chǎn)狀況要求，部分供應(yīng)物資生產(chǎn)量有最低要求：如果訂單量低于此線，則不開(kāi)工生產(chǎn)。由于部分物資的使用可以相互替代，對(duì)于需求地區(qū)Dj，j=1，2，3，7，12 ，如果要訂購(gòu)的話，M1 和M2 僅需訂購(gòu)一種，M3 和M5 僅需訂購(gòu)一種，其它需求沒(méi)有特別的要求。根據(jù)各種物資的實(shí)際作用，對(duì)每個(gè)需求地區(qū)而言，有最低需求量和額外需求量。

產(chǎn)品的訂購(gòu)價(jià)格按照一定的數(shù)量實(shí)施分段定價(jià)原則。

問(wèn)題一：請(qǐng)建立一般的數(shù)學(xué)模型，來(lái)確定生產(chǎn)訂單以及物資運(yùn)送路線，希望以最小的費(fèi)用代價(jià)，完成救災(zāi)物資的訂購(gòu)和運(yùn)輸要求。

問(wèn)題二：根據(jù)問(wèn)題中提供的有關(guān)具體數(shù)據(jù)，求出最小費(fèi)用和運(yùn)輸路線。

二、問(wèn)題分析

（一）問(wèn)題一的分析

問(wèn)題一屬于模型優(yōu)化問(wèn)題，對(duì)于解決此類問(wèn)題我們一般是根據(jù)題目中的要求建立目標(biāo)函數(shù)，再根據(jù)題目中的已知信息列出約束條件。

在綜合考慮影響運(yùn)輸費(fèi)用的各個(gè)因素之后，建立優(yōu)化模型，尋求在滿足運(yùn)輸費(fèi)用最小的條件下，生產(chǎn)訂單方案和物資運(yùn)輸路線，更好的完成政府的物資訂購(gòu)和運(yùn)輸要求。

根據(jù)題目中的信息發(fā)現(xiàn)此優(yōu)化模型有限制條件：第一，物資實(shí)際生產(chǎn)狀況要求，部分供應(yīng)物資生產(chǎn)量有最低要求，如果訂單量低于此線，那么那些供應(yīng)商會(huì)選擇不開(kāi)工生產(chǎn)。第二，由于部分物資是相互替代品，對(duì)于需求地區(qū)Dj，j=1，2，3，7，12 ，如果要訂購(gòu)的話，M1 和M2 只需要訂購(gòu)其中一種，M3 和M5 只需要訂購(gòu)其中一種。第三，根據(jù)各種物資的實(shí)際作用，對(duì)每個(gè)需求地區(qū)而言，有最低需求量和額外需求量。

（二）問(wèn)題二的分析

根據(jù)題目中所提供的有關(guān)供應(yīng)物資生產(chǎn)廠家的供應(yīng)量、物資需求地區(qū)的需求量以及二者之間的距離等具體數(shù)據(jù)，求出最小費(fèi)用和運(yùn)輸路線。

針對(duì)供應(yīng)廠家S到物資需求方D最優(yōu)運(yùn)輸路線的解法，使用MATLAB編寫程序，得出滿足費(fèi)用最小的條件下的最優(yōu)路徑。

因?yàn)轭}目給了一個(gè)無(wú)向路徑圖，標(biāo)記出了出了各個(gè)節(jié)點(diǎn)間的距離權(quán)重，且無(wú)負(fù)權(quán)重。因?yàn)闆](méi)給出每個(gè)節(jié)點(diǎn)在某坐標(biāo)系下的坐標(biāo)，所以不妨用鄰接矩陣來(lái)表示該無(wú)向路徑圖。然后使用解決無(wú)負(fù)權(quán)重最優(yōu)路徑問(wèn)題中，較為可靠的Dijkstra算法進(jìn)行距離的求解。針對(duì)最小費(fèi)用的解法，根據(jù)第一問(wèn)所建立的優(yōu)化模型，帶入附表中的具體數(shù)據(jù)，使用lingo編寫程序，得到滿足供應(yīng)商和物資需求方的最優(yōu)化的費(fèi)用。

三、模型假設(shè)

1、假設(shè)題目中所給的數(shù)據(jù)真實(shí)可靠；

2、運(yùn)輸速度只與路程有關(guān)，不考慮與其他如天氣、交通情況等因素；

3、所有的貨物由國(guó)家宏觀統(tǒng)一計(jì)劃，不受供求關(guān)系影響，貨物價(jià)格穩(wěn)定；

4、不考慮車輛行駛過(guò)程中的非正常燃油消耗；

5、物資在運(yùn)輸途中不會(huì)發(fā)生丟失或損耗；

四、定義與符號(hào)說(shuō)明

五、模型的建立與求解

第一部分、問(wèn)題一的優(yōu)化模型

根據(jù)題目信息建立優(yōu)化模型，以確定生產(chǎn)訂單以及物資運(yùn)送路線。希望以最小的費(fèi)用代價(jià)，制定最好的完成救災(zāi)物資的訂購(gòu)和運(yùn)輸方案。

建立優(yōu)化函數(shù)： （1）

其中，S（i，j，k） 表示第i種物資從第j供應(yīng)商運(yùn)到k地的數(shù)量；J（j，k） 表示從第j供應(yīng)商到目的地k的距離；Y（i） 表示物資i的單位運(yùn)價(jià)；P（i） 表示物資i的單位價(jià)格；G（I，j） 表示第j個(gè)供應(yīng)商供應(yīng)物資的最大值。s（I，j，k）.P（i） 表示物資i的從供應(yīng)商j運(yùn)到k地的總價(jià)格；J（j，k）·Y（i） ·s（i，j，k） 表示物資i的從供應(yīng)商j運(yùn)到k地的運(yùn)價(jià)。

限制條件：

由于部分物資的使用可以相互替代，對(duì)于需求地區(qū)Dj，j=1，2，3，7，12 ，如果要訂購(gòu)的話，M1 和M2 僅需訂購(gòu)一種，M3 和 M5僅需訂購(gòu)一種。

一、求供應(yīng)廠家S到物資需求方D的最小運(yùn)輸路線問(wèn)題

因?yàn)轭}目給了一個(gè)無(wú)方向路徑圖，標(biāo)記出了出了各個(gè)節(jié)點(diǎn)間的距離權(quán)重，且無(wú)負(fù)權(quán)重。因?yàn)闆](méi)給出每個(gè)節(jié)點(diǎn)在某坐標(biāo)系下的坐標(biāo)，所以不妨用鄰接矩陣來(lái)表示該無(wú)向圖。然后使用解決無(wú)負(fù)權(quán)重最優(yōu)路徑問(wèn)題中，較為可靠的Dijkstra算法進(jìn)行距離的求解。

1.算法進(jìn)行前的輔助矩陣

1.1鄰接矩陣a

1.1.1鄰接矩陣的定義

不妨記鄰接矩陣a（i，j）為當(dāng)前所找到的從起始點(diǎn)（si（i=1-10））到其它每個(gè)目的地端點(diǎn)的長(zhǎng)度。為了程序編寫方便，將供應(yīng)廠家S1-S10和物資需求方D1-D18，這一共28個(gè)點(diǎn)一起構(gòu)造矩陣SDj（j=1-28），這個(gè)矩陣就是鄰接矩陣。

1.1.2鄰接矩陣的各項(xiàng)數(shù)值

因?yàn)榇祟}是無(wú)方向路徑圖，在當(dāng)求最短路徑，即a（i，j）時(shí)，分為三種情況：

1）當(dāng)i=j時(shí)，其為0；

2）當(dāng)i與j之間無(wú)法直接或者通過(guò)中間節(jié)點(diǎn)相連時(shí)，其為無(wú)窮大，在MATLAB中可以用自帶常變量inf表示；

3）當(dāng)i與j之間可以相連時(shí)其值為其所有連線方法中總權(quán)值之和最小值；

1.2距離輔助矩陣d

d是個(gè)10*28的數(shù)組，其用來(lái)儲(chǔ)存每一次si到全部28個(gè)端點(diǎn)的初始路程，此時(shí)的d數(shù)組成為最短路徑估計(jì)值。

2.確定28個(gè)點(diǎn)到某一個(gè)物資需求方的最短路徑

2.1標(biāo)記端點(diǎn)

將28個(gè)端點(diǎn)點(diǎn)分成兩類：最短路程確定的端點(diǎn)矩陣P 和最短路徑不確定的端點(diǎn)矩陣Q。開(kāi)始時(shí)確定的端點(diǎn)矩陣P中只有源點(diǎn)一個(gè)端點(diǎn)。不妨用一個(gè)0-1數(shù)組保存在P中的點(diǎn)。若某個(gè)點(diǎn)在這個(gè)數(shù)組中為1，則代表其在矩陣P中；相反若某個(gè)點(diǎn)在數(shù)組中為0，則代表其并不在矩陣P中，而是在不確定的端點(diǎn)矩陣Q中。

2.2設(shè)置路徑長(zhǎng)度

設(shè)置供應(yīng)商源點(diǎn)s到自己本身點(diǎn)的最短路徑為0，即d[i]=0。若存在源點(diǎn)有能直接到達(dá)的端點(diǎn)i，則把初始距離d[i]設(shè)為e[s][i]。同時(shí)把所有其它供應(yīng)商源點(diǎn)s不能直接到達(dá)的端點(diǎn)的最短路徑為設(shè)為無(wú)窮大∞。

2.3松弛操作

在最短路徑不確定的端點(diǎn)矩陣Q的所有端點(diǎn)中選擇一個(gè)離供應(yīng)商源點(diǎn)s最近的端點(diǎn)u（即d[u]最?。┘尤氲郊螾。并觀察題目所有以點(diǎn)u為起點(diǎn)的路線。

假如存在一條從離供應(yīng)商最近的點(diǎn)u到目的地v的路線，那么可以通過(guò)將路線uv添加到路線su的后面，來(lái)拓展一條從供應(yīng)商s到目的地v的路徑，這條路徑的長(zhǎng)度是d[u]+e[u][v]。如果這個(gè)值比原始的d[v]的小，即用新值d[u]+e[u][v]來(lái)替代當(dāng)前值d[v]。

2.4循環(huán)運(yùn)行

循環(huán)運(yùn)行第3步，當(dāng)最短路徑不確定的端點(diǎn)矩陣Q為空，算法結(jié)束。最終距離輔助矩陣d數(shù)組中的值就是源點(diǎn)到所有端點(diǎn)的最短路徑。

3.重復(fù)以上步驟10次，即求的s1-s10的所有結(jié)果，求得的矩陣是10行28列的。由題意只需要供應(yīng)廠商s到物資需求方d的距離，所以只需取該矩陣11列到28列。

4.供應(yīng)廠家S到物資需求方D的最小運(yùn)輸路線結(jié)果。

5.一共有5種不同的物資，從10個(gè)物資供應(yīng)商運(yùn)輸?shù)?8個(gè)物資需求方的運(yùn)輸方案有900中。

二、最小費(fèi)用問(wèn)題

根據(jù)問(wèn)題一的優(yōu)化模型，希望以最小的費(fèi)用代價(jià)，最好的完成救災(zāi)物資的訂購(gòu)和運(yùn)輸要求。

使用lingo編寫程序，帶入具體數(shù)值，求得滿足條件的最小費(fèi)用為0.9224303×1012元。

六、模型評(píng)價(jià)與改進(jìn)

模型較好的解決了題目給出的問(wèn)題。建立了優(yōu)化數(shù)學(xué)模型確定生產(chǎn)訂單以及物資運(yùn)送路線，以最小的費(fèi)用代價(jià)，完成救災(zāi)物資的訂購(gòu)和運(yùn)輸要求。

問(wèn)題一：充分考慮題目中的具體信息，建立了使物資購(gòu)買費(fèi)用和運(yùn)輸費(fèi)用最小化的優(yōu)化模型。但是在現(xiàn)實(shí)生活中，影響實(shí)際的費(fèi)用花費(fèi)有很多的因素，例如物資運(yùn)輸過(guò)程中的損耗或丟失，由于車輛行駛中的非正常行駛導(dǎo)致的燃油費(fèi)用的增加等等。在模型中并未考慮，卻在實(shí)際生活中要綜合考慮這些不可控的因素所造成的影響。

問(wèn)題二：針對(duì)最短路徑問(wèn)題，運(yùn)用Dijkstra算法，使用MATLAB編寫程序得出，從供應(yīng)廠商到物資需求方的的最短運(yùn)輸路線共有180種；在考慮五種不同的物資，最優(yōu)的運(yùn)輸路線有900種不同的結(jié)果。運(yùn)算出數(shù)量太多，沒(méi)有再找到方法使結(jié)果更加簡(jiǎn)單。針對(duì)最小費(fèi)用問(wèn)題，是在第一問(wèn)的優(yōu)化模型基礎(chǔ)上，使用lingo編寫程序，代入數(shù)據(jù)，得出最優(yōu)化結(jié)果下的運(yùn)輸費(fèi)用。

參考文獻(xiàn)：

[1]基于Dijkstra算法的大型停車場(chǎng)最優(yōu)泊車路徑規(guī)劃[J]. 吳若偉，樓佩煌. 工業(yè)控制計(jì)算機(jī). 2013（05）

[2]改進(jìn)Dijkstra算法在GIS導(dǎo)航應(yīng)用中最短路徑搜索研究[J]. 董俊，黃傳河. 計(jì)算機(jī)科學(xué). 2012（10）

[3]改進(jìn)的Dijkstra最短路徑算法及其應(yīng)用研究[J]. 王樹(shù)西，吳政學(xué). 計(jì)算機(jī)科學(xué). 2012（05）

[4]求解震后最優(yōu)路徑的改進(jìn)Dijkstra算法[J]. 李敬賢，厲小潤(rùn). 計(jì)算機(jī)工程. 2012（06）

[5]基于改進(jìn)的Dijkstra算法的動(dòng)態(tài)最短路計(jì)算方法[J]. 劉建美，馬壽峰，馬帥奇. 系統(tǒng)工程理論與實(shí)踐. 2011（06）

[6]復(fù)雜路網(wǎng)下多客戶間最短路徑的扇面Dijkstra算法[J]. 鄭四發(fā)，曹劍東，連小珉. 清華大學(xué)學(xué)報(bào)（自然科學(xué)版）. 2009（11）

[7]基于Dijkstra距離剪枝的測(cè)地線求解算法[J]. 周競(jìng)文，程志全，金士堯. 系統(tǒng)仿真學(xué)報(bào). 2009（S1）

作者簡(jiǎn)介：

吳施，男 （1997-），籍貫：四川省廣安市人，民族（漢），職稱（無(wú)），學(xué)歷（高中）.