(西南石油大學(xué) 四川 成都 610500)

引言

我國是自然災(zāi)害頻發(fā)國之一，自然災(zāi)害給我國帶來的損失巨大。由此，國家特別重視自然災(zāi)害救助問題，在各地相繼建立救災(zāi)物資儲備庫，救災(zāi)物資儲備庫的物資由分布在全國各地的生產(chǎn)廠家提供。除了生產(chǎn)廠家捐贈(zèng)的救災(zāi)物資以外，另外的物資由國家救災(zāi)指揮部統(tǒng)一購買，各個(gè)地區(qū)的民政部門負(fù)責(zé)本地區(qū)的物資集中和運(yùn)送，并需要付出物資的購買費(fèi)用以及運(yùn)輸費(fèi)用。

問題提出

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

節(jié)點(diǎn)之間(包括生產(chǎn)廠家、需求地區(qū)，以及道路的連接點(diǎn))的道路里程如圖1所示，標(biāo)注在圖中道路一側(cè)，每種物資單位里程平均運(yùn)輸費(fèi)用已知，產(chǎn)品的訂購價(jià)格按照一定的數(shù)量實(shí)施分段定價(jià)原則。通過建立數(shù)學(xué)模型，來確定生產(chǎn)訂單以及物資運(yùn)送路線，希望以最小的費(fèi)用代價(jià)，完成救災(zāi)物資的訂購和運(yùn)輸要求。

圖1 地區(qū)分布圖

問題分析

為了得到以最小費(fèi)用為代價(jià)的生產(chǎn)訂單與物資運(yùn)送路線組合[1]，需要知道各個(gè)地區(qū)的所需物資組合。但由于各種約束條件，該組合是動(dòng)態(tài)變化的，可以分兩個(gè)階段來考慮。

階段一：最簡單的模型是找到生產(chǎn)廠家到地區(qū)之間單位數(shù)量物資所花費(fèi)用最低的路徑。

階段二：在階段一的前提下，繼續(xù)滿足各廠家Si供給各地區(qū)Dj物資Mk的數(shù)量的各項(xiàng)約束條件，即為各個(gè)廠家供應(yīng)能力、廠家物資生產(chǎn)的最低數(shù)量要求、各個(gè)地區(qū)的額外物資需求、最低需求量和部分物資的使用可以相互替代等約束條件，那么一定會在階段一中的路徑中找到一簇符合最優(yōu)總費(fèi)用的最優(yōu)路徑，即可確定生產(chǎn)訂單。

動(dòng)態(tài)規(guī)劃模型的建立

第一階段 最短路模型[2]的建立

由問題分析可知，物資的總費(fèi)用P包括購買費(fèi)用Pmj以及運(yùn)輸費(fèi)用Ptj，讓總費(fèi)用達(dá)到最小化，核心的問題是廠家Si(i=1,2,…,10)到需要物資供應(yīng)的地區(qū)Dj(j=1,2,...,18)的路程最優(yōu)。

對于題中的距離問題，將18個(gè)需要物資供應(yīng)的地區(qū)Dj、10家生產(chǎn)廠家Si以及道路的連接點(diǎn)Ru看做由35個(gè)點(diǎn)連接成的網(wǎng)絡(luò)圖(其中，生產(chǎn)廠家Si為1～18，道路的連接點(diǎn)Ru為11～17，地區(qū)Dj為18～35)，構(gòu)造賦權(quán)圖[3]G(V,E,W)，如圖2所示。其中，頂點(diǎn)集V={v1,…,vn},其中v1,…,vn表示35個(gè)頂點(diǎn)，E為邊的集合；鄰接矩陣W=(wxy)n×n,wxy表示頂點(diǎn)vx和vy之間的距離，若兩點(diǎn)之間無道路相通，則wxy=∞，問題便是求賦權(quán)圖G中兩頂點(diǎn)所具有最小權(quán)的路。

圖2 物資運(yùn)輸問題的無向賦權(quán)圖

取點(diǎn)i到點(diǎn)j的路程dij作為邊(vi,vj)的權(quán)wij，即

假設(shè)先不考慮廠家的供應(yīng)能力、廠家物資生產(chǎn)的最低數(shù)量要求以及各個(gè)地區(qū)的額外物資需求等約束條件，使得地區(qū)Dj到距自己最短路程的生產(chǎn)廠家處就能滿足自己所需物資的最低需求，通過賦權(quán)圖計(jì)算兩點(diǎn)之間的最短距離。

目標(biāo)函數(shù) 若設(shè)決策變量xij=1表示邊所選擇的路線均為各單位之間的最短距離，此時(shí)的權(quán)重為dij。則地區(qū)Dj到廠家Si的距離dij的最短路模型為：

若設(shè)單位物資所花費(fèi)用為pij，此時(shí)的最優(yōu)路徑距離為sij。我們將定義目標(biāo)函數(shù)每段路線上的權(quán)重wij=pijsij，則目標(biāo)函數(shù)變?yōu)椋?/p>

求得的結(jié)果為生產(chǎn)廠家到地區(qū)之間單位數(shù)量物資所花費(fèi)用最低的路徑。

第二階段 在第一階段的基礎(chǔ)上，繼續(xù)滿足各個(gè)廠家供應(yīng)能力、廠家物資生產(chǎn)的最低數(shù)量要求以及各個(gè)地區(qū)的額外物資需求等約束條件，此時(shí)將在階段一的結(jié)果——生產(chǎn)廠家到地區(qū)之間所花費(fèi)用最低的路徑中找到滿足約束條件的總費(fèi)用的最優(yōu)路徑。

約束條件

xijk為廠家Si供給地區(qū)Dj物資Mk的數(shù)量，xijk≥0。則：

(6)

最后，由于部分物資的使用可以相互替代，M1和M2僅需訂購一種，M3和M5僅需訂購一種。因此：

目標(biāo)函數(shù) 設(shè)任意生產(chǎn)廠家到任意地區(qū)之間所花費(fèi)用最低的最優(yōu)路徑的每單位物資Mk共花費(fèi)用為Wijk元。則可得到生產(chǎn)廠家到地區(qū)之間所花費(fèi)用最低的路徑中找到滿足約束條件的總費(fèi)用的目標(biāo)函數(shù)為：

生產(chǎn)訂單數(shù)Xik目標(biāo)函數(shù)為：

綜上，整合為：

模型求解 此模型的求解采用Floyd(弗洛伊德)算法[4]，它是一種矩陣(表格)迭代方法，該算法是通過對表示有向圖的鄰接矩陣作迭代計(jì)算，來解決有向圖任意一對頂點(diǎn)之間的最短路徑問題。

Step1:整合所有數(shù)據(jù)，求得任意兩點(diǎn)的距離矩陣。

Step2:結(jié)合Floyd算法，求出關(guān)于單位物資所花費(fèi)用為pij的任意兩點(diǎn)的鄰接矩陣，該鄰接矩陣即為任意兩點(diǎn)的最優(yōu)路徑。

Step3:在Step2所得路徑下，帶入廠家Si供給地區(qū)Dj物資Mk的數(shù)量xijk，使用目標(biāo)費(fèi)用函數(shù)求得總費(fèi)用。

Step4:將上步中得到的總費(fèi)用進(jìn)行比較，得到最小總費(fèi)用。

Step5:根據(jù)廠家Si供給地區(qū)Dj物資Mk的數(shù)量xijk確定生產(chǎn)訂單。

模型總結(jié)

本文采用的動(dòng)態(tài)規(guī)劃模型能夠得到題中所需的一簇最優(yōu)解，動(dòng)態(tài)規(guī)劃方法反映了動(dòng)態(tài)過程演變的聯(lián)系和特征，在計(jì)算時(shí)可以利用實(shí)際知識和經(jīng)驗(yàn)提高求解效率。本文的最短路模型采用Floyd算法，其算法可以求解任意兩點(diǎn)之間的距離，應(yīng)用范圍比Dijkstra算法要廣。模型的劣勢表現(xiàn)在文中的動(dòng)態(tài)規(guī)劃模型沒有統(tǒng)一的標(biāo)準(zhǔn)模型，在數(shù)值方法求解時(shí)存在維數(shù)災(zāi)，采用最短路模型的Floyd算法，其時(shí)間復(fù)雜度比較高，并且在對數(shù)據(jù)的整合分析過程中，不考慮額外需求量對最低費(fèi)用的影響，會對結(jié)果產(chǎn)生相應(yīng)的誤差。在第二階段中，將各個(gè)影響總費(fèi)用的因素采取先分后合的方法，對于因素的影響具有一定的主觀因素。