救災物資最優化

吳施 楊金凇

摘 要：生產救災物資生產廠家分布在全國各地。除了捐贈以外，其余的救災物資由國家救災指揮部統一購買。政府需要支付救災物資的購買費用以及物資運輸費用。根據發生災害的具體情況，初步有一個總費用計劃，再根據災害的情況不斷進行調整。由于政府的預算資金有限，希望以最小的費用代價，最優的完成救災物資的訂購和運輸要求。

問題一：針對以最小費用最優的完成物資訂購與運輸問題，建立費用優化模型。根據題目中具體的限制條件，由于部分物資的使用是可以相互替代的，供應商的供應能力有限，有生產的最大值，對每個地區而言，有最低需求量和額外需求量，確立出可以解決實際自然災害的費用優化模型。

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

關鍵詞：優化模型 Dijkstra算法 最短路徑

一、問題重述

救災物資生產廠家分布在全國各地。 除了生產廠家的捐贈以外，另外的物資由國家救災指揮部統一購買，各個地區的民政部門負責本地區的物資集中和運送。需要付出物資的購買費用以及運輸費用。

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

產品的訂購價格按照一定的數量實施分段定價原則。

問題一：請建立一般的數學模型，來確定生產訂單以及物資運送路線，希望以最小的費用代價，完成救災物資的訂購和運輸要求。

問題二：根據問題中提供的有關具體數據，求出最小費用和運輸路線。

二、問題分析

（一）問題一的分析

問題一屬于模型優化問題，對于解決此類問題我們一般是根據題目中的要求建立目標函數，再根據題目中的已知信息列出約束條件。

在綜合考慮影響運輸費用的各個因素之后，建立優化模型，尋求在滿足運輸費用最小的條件下，生產訂單方案和物資運輸路線，更好的完成政府的物資訂購和運輸要求。

根據題目中的信息發現此優化模型有限制條件：第一，物資實際生產狀況要求，部分供應物資生產量有最低要求，如果訂單量低于此線，那么那些供應商會選擇不開工生產。第二，由于部分物資是相互替代品，對于需求地區Dj，j=1，2，3，7，12 ，如果要訂購的話，M1 和M2 只需要訂購其中一種，M3 和M5 只需要訂購其中一種。第三，根據各種物資的實際作用，對每個需求地區而言，有最低需求量和額外需求量。

（二）問題二的分析

根據題目中所提供的有關供應物資生產廠家的供應量、物資需求地區的需求量以及二者之間的距離等具體數據，求出最小費用和運輸路線。

針對供應廠家S到物資需求方D最優運輸路線的解法，使用MATLAB編寫程序，得出滿足費用最小的條件下的最優路徑。

因為題目給了一個無向路徑圖，標記出了出了各個節點間的距離權重，且無負權重。因為沒給出每個節點在某坐標系下的坐標，所以不妨用鄰接矩陣來表示該無向路徑圖。然后使用解決無負權重最優路徑問題中，較為可靠的Dijkstra算法進行距離的求解。針對最小費用的解法，根據第一問所建立的優化模型，帶入附表中的具體數據，使用lingo編寫程序，得到滿足供應商和物資需求方的最優化的費用。

三、模型假設

1、假設題目中所給的數據真實可靠；

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

3、所有的貨物由國家宏觀統一計劃，不受供求關系影響，貨物價格穩定；

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

5、物資在運輸途中不會發生丟失或損耗；

四、定義與符號說明

五、模型的建立與求解

第一部分、問題一的優化模型

根據題目信息建立優化模型，以確定生產訂單以及物資運送路線。希望以最小的費用代價，制定最好的完成救災物資的訂購和運輸方案。

建立優化函數： （1）

其中，S（i，j，k） 表示第i種物資從第j供應商運到k地的數量；J（j，k） 表示從第j供應商到目的地k的距離；Y（i） 表示物資i的單位運價；P（i） 表示物資i的單位價格；G（I，j） 表示第j個供應商供應物資的最大值。s（I，j，k）.P（i） 表示物資i的從供應商j運到k地的總價格；J（j，k）·Y（i） ·s（i，j，k） 表示物資i的從供應商j運到k地的運價。

限制條件：

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

一、求供應廠家S到物資需求方D的最小運輸路線問題

因為題目給了一個無方向路徑圖，標記出了出了各個節點間的距離權重，且無負權重。因為沒給出每個節點在某坐標系下的坐標，所以不妨用鄰接矩陣來表示該無向圖。然后使用解決無負權重最優路徑問題中，較為可靠的Dijkstra算法進行距離的求解。

1.算法進行前的輔助矩陣

1.1鄰接矩陣a

1.1.1鄰接矩陣的定義

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

1.1.2鄰接矩陣的各項數值

因為此題是無方向路徑圖，在當求最短路徑，即a（i，j）時，分為三種情況：

1）當i=j時，其為0；

2）當i與j之間無法直接或者通過中間節點相連時，其為無窮大，在MATLAB中可以用自帶常變量inf表示；

3）當i與j之間可以相連時其值為其所有連線方法中總權值之和最小值；

1.2距離輔助矩陣d

d是個10*28的數組，其用來儲存每一次si到全部28個端點的初始路程，此時的d數組成為最短路徑估計值。

2.確定28個點到某一個物資需求方的最短路徑

2.1標記端點

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

2.2設置路徑長度

設置供應商源點s到自己本身點的最短路徑為0，即d[i]=0。若存在源點有能直接到達的端點i，則把初始距離d[i]設為e[s][i]。同時把所有其它供應商源點s不能直接到達的端點的最短路徑為設為無窮大∞。

2.3松弛操作

在最短路徑不確定的端點矩陣Q的所有端點中選擇一個離供應商源點s最近的端點u（即d[u]最小）加入到集合P。并觀察題目所有以點u為起點的路線。

假如存在一條從離供應商最近的點u到目的地v的路線，那么可以通過將路線uv添加到路線su的后面，來拓展一條從供應商s到目的地v的路徑，這條路徑的長度是d[u]+e[u][v]。如果這個值比原始的d[v]的小，即用新值d[u]+e[u][v]來替代當前值d[v]。

2.4循環運行

循環運行第3步，當最短路徑不確定的端點矩陣Q為空，算法結束。最終距離輔助矩陣d數組中的值就是源點到所有端點的最短路徑。

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

4.供應廠家S到物資需求方D的最小運輸路線結果。

5.一共有5種不同的物資，從10個物資供應商運輸到18個物資需求方的運輸方案有900中。

二、最小費用問題

根據問題一的優化模型，希望以最小的費用代價，最好的完成救災物資的訂購和運輸要求。

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

六、模型評價與改進

模型較好的解決了題目給出的問題。建立了優化數學模型確定生產訂單以及物資運送路線，以最小的費用代價，完成救災物資的訂購和運輸要求。

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

問題二：針對最短路徑問題，運用Dijkstra算法，使用MATLAB編寫程序得出，從供應廠商到物資需求方的的最短運輸路線共有180種；在考慮五種不同的物資，最優的運輸路線有900種不同的結果。運算出數量太多，沒有再找到方法使結果更加簡單。針對最小費用問題，是在第一問的優化模型基礎上，使用lingo編寫程序，代入數據，得出最優化結果下的運輸費用。

參考文獻：

[1]基于Dijkstra算法的大型停車場最優泊車路徑規劃[J]. 吳若偉，樓佩煌. 工業控制計算機. 2013（05）

[2]改進Dijkstra算法在GIS導航應用中最短路徑搜索研究[J]. 董俊，黃傳河. 計算機科學. 2012（10）

[3]改進的Dijkstra最短路徑算法及其應用研究[J]. 王樹西，吳政學. 計算機科學. 2012（05）

[4]求解震后最優路徑的改進Dijkstra算法[J]. 李敬賢，厲小潤. 計算機工程. 2012（06）

[5]基于改進的Dijkstra算法的動態最短路計算方法[J]. 劉建美，馬壽峰，馬帥奇. 系統工程理論與實踐. 2011（06）

[6]復雜路網下多客戶間最短路徑的扇面Dijkstra算法[J]. 鄭四發，曹劍東，連小珉. 清華大學學報（自然科學版）. 2009（11）

[7]基于Dijkstra距離剪枝的測地線求解算法[J]. 周競文，程志全，金士堯. 系統仿真學報. 2009（S1）

作者簡介：

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