防洪物資調(diào)運(yùn)問題2 精品.docVIP

防洪物資調(diào)運(yùn)問題每年，洪澇災(zāi)害都會使我國人民的生命財(cái)產(chǎn)遭受嚴(yán)重?fù)p失。因此，提前做好抗災(zāi)物資的調(diào)運(yùn)工作，對于防洪抗?jié)尘哂兄匾饬x。問題一是圖論當(dāng)中的最短路問題。我們首先從該地區(qū)的交通狀況圖中提煉出兩個矩陣，用來表征圖中連通的兩點(diǎn)之間的距離和運(yùn)輸成本。利用這兩個矩陣，我們根據(jù)Dijkstra算法的原理建立了規(guī)劃模型：最優(yōu)路徑模型。利用這個模型，我們求出了任意兩個調(diào)運(yùn)節(jié)點(diǎn)之間運(yùn)費(fèi)最小的路徑。在處理問題二時，我們充分考慮了各個調(diào)運(yùn)節(jié)點(diǎn)的庫存情況，利用已經(jīng)求出的調(diào)運(yùn)節(jié)點(diǎn)之間的最優(yōu)路徑及其運(yùn)費(fèi)，建立了模型：最優(yōu)調(diào)運(yùn)模型。這個模型以總運(yùn)費(fèi)最小為目標(biāo)函數(shù)，只要給定了調(diào)運(yùn)期限T和可容相對誤差，就可以求解出最優(yōu)調(diào)運(yùn)方案。在將T定為8天，定為5時，我們得到了相應(yīng)的最優(yōu)調(diào)運(yùn)方案。問題三實(shí)際上是模型的應(yīng)用。將給定的條件代入模型中，我們得到了在這個具體情況下的最優(yōu)調(diào)運(yùn)方案。當(dāng)汛期到來，需要對物資進(jìn)行緊急調(diào)運(yùn)的情況下，我們將路程最短作為最優(yōu)目標(biāo)，利用模型，求出了各個調(diào)運(yùn)節(jié)點(diǎn)之間的最短路徑。以此為基礎(chǔ)，我們引入“量程積”的概念，將模型進(jìn)行了調(diào)整，建立了以量程積最小為目標(biāo)函數(shù)的優(yōu)化模型，得出了問題四所要求的調(diào)運(yùn)方案。通過前面得出的結(jié)果，我們發(fā)現(xiàn)當(dāng)T取值不同時，總運(yùn)費(fèi)也不同。利用模型：最佳時間模型，我們求出了一系列不同T值所對應(yīng)的總運(yùn)費(fèi)。通過對比我們發(fā)現(xiàn)，總運(yùn)費(fèi)隨著T的增大而減小。當(dāng)T在22天以上時，總運(yùn)費(fèi)達(dá)到最小值，并保持穩(wěn)定不變。由此我們得出結(jié)論：在調(diào)運(yùn)期限為22天時，總運(yùn)費(fèi)最小。另外，我們還研究了的取值對總運(yùn)費(fèi)的影響。我們發(fā)現(xiàn)，隨著的增大，總運(yùn)費(fèi)減少。比較T和的影響效果，發(fā)現(xiàn)的影響更顯著。最后，我們對如何預(yù)測汛期、合理安排調(diào)運(yùn)期限提出了合理的建議。一、 背景分析（略）二、 問題的提出與重述（略）三、 基本假設(shè)1、高等級公路與普通級公路的調(diào)運(yùn)速度是恒定且相等的，因此運(yùn)輸時間只與路程遠(yuǎn)近有關(guān)。2、由于該地區(qū)任意兩點(diǎn)之間的距離不大，認(rèn)為運(yùn)輸能力沒有限制，即無論運(yùn)輸路程多遠(yuǎn)、運(yùn)輸件數(shù)多少，運(yùn)輸都能在一天內(nèi)完成。3、各企業(yè)、物資倉庫及國家級倉儲庫之間的物資可以通過公路運(yùn)輸互相調(diào)運(yùn)。4、企業(yè)可以生產(chǎn)也可以不生產(chǎn)。5、預(yù)測值指的是各庫存最終需要盡量滿足的目標(biāo)值。四、 變量符號說明為了便于描述問題，我們在此列出文中主要使用一些符號和基本變量，其他一些變量將在文中陸續(xù)說明。表1符號意義單位從圖上點(diǎn)到圖上點(diǎn)之間的路程公里從圖上點(diǎn)到圖上點(diǎn)之間的運(yùn)輸成本元/公里百件從圖上點(diǎn)到圖上點(diǎn)之間路線的權(quán)重將要進(jìn)行運(yùn)輸調(diào)度的地點(diǎn)依次命名為調(diào)運(yùn)節(jié)點(diǎn)，其中，這13個點(diǎn)構(gòu)成了一個完全圖（見附件1）從調(diào)運(yùn)節(jié)點(diǎn)到調(diào)運(yùn)節(jié)點(diǎn)之間的最短路程公里從調(diào)運(yùn)節(jié)點(diǎn)到調(diào)運(yùn)節(jié)點(diǎn)之間最優(yōu)路線的權(quán)重元/百件從調(diào)運(yùn)節(jié)點(diǎn)到調(diào)運(yùn)節(jié)點(diǎn)之間的物資運(yùn)輸量百件調(diào)運(yùn)節(jié)點(diǎn)的最小庫存量百件調(diào)運(yùn)節(jié)點(diǎn)的最大庫存量百件調(diào)運(yùn)節(jié)點(diǎn)的現(xiàn)有庫存量百件調(diào)運(yùn)節(jié)點(diǎn)調(diào)運(yùn)后的庫存量百件調(diào)運(yùn)節(jié)點(diǎn)的預(yù)測庫存量百件調(diào)運(yùn)節(jié)點(diǎn)（企業(yè)）生產(chǎn)速度，百件/天調(diào)運(yùn)節(jié)點(diǎn)（企業(yè)）在調(diào)運(yùn)計(jì)劃中的生產(chǎn)天數(shù)天可容相對誤差，即與調(diào)運(yùn)節(jié)點(diǎn)預(yù)測庫存的偏離程度總調(diào)運(yùn)費(fèi)用元五、 問題分析題目的第一問要求我們根據(jù)該地區(qū)交通情況示意圖所提供的信息建立該地區(qū)公路交通網(wǎng)的數(shù)學(xué)模型。從圖中我們可以看出，各個運(yùn)輸節(jié)點(diǎn)在該地區(qū)的分布較為均勻。要建立公路交通網(wǎng)的數(shù)學(xué)模型，就需要將構(gòu)成公路交通運(yùn)輸系統(tǒng)的各個運(yùn)輸節(jié)點(diǎn)間的最短路徑找出來，從這幅比較龐雜的大圖中提煉出一幅包含這些運(yùn)輸節(jié)點(diǎn)的小圖。第二問要求我們設(shè)計(jì)物資合理的調(diào)運(yùn)方案。我們認(rèn)為，合理的調(diào)運(yùn)方案要在盡可能地滿足各個運(yùn)輸節(jié)點(diǎn)的需求的前提下，盡量使運(yùn)輸費(fèi)用最小。利用第一問的結(jié)果，我們應(yīng)該可以很方便的建立一個優(yōu)化模型，作為物資調(diào)度的指導(dǎo)依據(jù)。問題三實(shí)際上是問題二的應(yīng)用。將具體的時間代入到第二問的模型中，可以很容易得出計(jì)算結(jié)果。問題四和問題二略有不同。在緊急情況下，要首先考慮的不再是費(fèi)用問題，而是怎樣最快地將救災(zāi)物資送到指定地點(diǎn)。所以我們的優(yōu)化模型的目標(biāo)函數(shù)應(yīng)該與問題二有所不同。而且，由于道路受到洪水的影響發(fā)生了改變，各個運(yùn)輸節(jié)點(diǎn)之間的最短路徑都應(yīng)該進(jìn)行重新計(jì)算，利用新的路徑，給出合理的調(diào)度方案。六、 問題1模型的建立與求解該地區(qū)交通的示意圖上，分布著42個不同的點(diǎn)。任意兩個相連的點(diǎn)之間的距離在圖上標(biāo)出。因此，我們可以從中提煉出一個4242的矩陣，用表示從圖上點(diǎn)到圖上點(diǎn)之間的路程，用表示從圖上點(diǎn)到圖上點(diǎn)之間的運(yùn)輸成本。根據(jù)這個矩陣，我們建立了模型，用來找出任意兩個調(diào)運(yùn)節(jié)點(diǎn)之間的最優(yōu)路徑。1、 模型準(zhǔn)備顯然，這是圖論中的“最短路問題”。我們首先對這幅圖做出一些定義和說明：定義 1圖中是有限集合，。稱中的元素為圖的頂點(diǎn)，中的元素為圖的邊或弧。定義 2如果是一個圖，并且，則稱是的子圖。對于圖，如果對，賦予一個實(shí)數(shù)，則稱為邊的權(quán)，連同邊上的權(quán)重稱為賦權(quán)圖。定義 3如果，則稱和鄰接，具有個頂點(diǎn)的圖的鄰接矩陣是一個階矩陣，其分量為個頂點(diǎn)賦權(quán)圖的賦權(quán)矩陣是一個階矩陣，其分量為2、 模型的建立Dijkstra算法是解決最短路問題的一種很有效的方法，它的原理如下：假設(shè)是的真子集且，并以記。若是從到的最短路，則顯然且的節(jié)必然是最短路。所以，并且從到的距離由公式給出。這個公式便是Dijkstra算法的基礎(chǔ)。在整個算法中，每個頂點(diǎn)給以標(biāo)號，它是的一個上界。開始時，而對，則有。在算法進(jìn)行時，這些標(biāo)號不斷被修改：在第步結(jié)束時 對成立并且 對成立下面是具體的Dijkstra算法操作流程圖：當(dāng)算法結(jié)束時，從到的距離由標(biāo)號的終值給出。假設(shè)圖有個頂點(diǎn)，現(xiàn)需要求從頂點(diǎn)到頂點(diǎn)的最短路。設(shè)決策變量為，當(dāng)，說明弧位于頂點(diǎn)到頂點(diǎn)的路上；否則。由此，我們可以寫出求解此問題的模型最優(yōu)路徑模型：3、 模型的求解。在利用這個模型求解任意兩點(diǎn)之間的最優(yōu)路徑時，需要注意目標(biāo)函數(shù)中的每段路線上的權(quán)重。的含義不同，最終的結(jié)果也不同。當(dāng)情況緊急，需要尋找一條最短最快捷的路徑時，可以將定義為兩點(diǎn)之間路線的長度，目標(biāo)函數(shù)變?yōu)檫@樣的形式：所求出來的結(jié)果就是出發(fā)點(diǎn)與目的地之間的最短路徑。如果情況不是很緊急，則應(yīng)該綜合考慮運(yùn)輸費(fèi)用，此時，我們可以定義權(quán)重為單位運(yùn)輸成本與路程的乘積：，這樣得到的目標(biāo)函數(shù)是：這樣求出來的路徑就是運(yùn)輸費(fèi)用最低的路徑?？紤]一般情況，我們都選擇運(yùn)輸費(fèi)用最低的路徑，即定義，利用lingo 8.0軟件編程求解，我們得到：企業(yè)1到企業(yè)2之間的最優(yōu)路徑是 242625154241，在這條路徑上運(yùn)輸物資的費(fèi)用為177.6元/百件。由于篇幅所限，全部13個運(yùn)輸節(jié)點(diǎn)之間的最優(yōu)路徑及在該路徑上的運(yùn)輸費(fèi)用將在附件2、3 中列出。七、 問題2的模型建立與求解要得到一個最合理的調(diào)運(yùn)方案，就需要建立一個優(yōu)化模型，用來求出最佳調(diào)運(yùn)量以及調(diào)運(yùn)路線。1、 約束條件的確定我們令按照模型求出的從i調(diào)運(yùn)節(jié)點(diǎn)到j(luò)調(diào)運(yùn)節(jié)點(diǎn)的調(diào)運(yùn)量為， 。則調(diào)運(yùn)結(jié)束后各個節(jié)點(diǎn)的庫存為：題目列出了各庫庫存與需求情況，其中列出了預(yù)測庫存一項(xiàng)。我們認(rèn)為，按照運(yùn)輸方案進(jìn)行調(diào)度之后，各個運(yùn)輸節(jié)點(diǎn)的庫存，應(yīng)該盡可能地接近或大于預(yù)測庫存。 令為能夠接受的實(shí)際庫存與預(yù)測庫存的偏離程度，預(yù)測庫存量，有：另外，一個節(jié)點(diǎn)需要的庫存能力有限制，必須不超過最大庫存，有：此外，要重點(diǎn)保證國家級儲備庫的庫存。因此，我們要求的方案必須使國家級儲備庫的庫存達(dá)到或者超過其預(yù)測值，即：2、 目標(biāo)函數(shù)的建立我們希望我們的調(diào)運(yùn)方案在滿足各項(xiàng)要求的基礎(chǔ)上，所花費(fèi)的運(yùn)輸費(fèi)用最小。從第一問的結(jié)果中，我們已經(jīng)得到了任意兩個調(diào)運(yùn)節(jié)點(diǎn)之間花費(fèi)最小的最優(yōu)路徑，該路徑的每百件物資的運(yùn)輸費(fèi)用為元。顯然，如果從調(diào)運(yùn)節(jié)點(diǎn)i運(yùn)輸百件物資到調(diào)運(yùn)節(jié)點(diǎn)j，一定會從已經(jīng)求得的最優(yōu)路徑進(jìn)行運(yùn)輸。這樣，調(diào)運(yùn)結(jié)束之后，花費(fèi)的總費(fèi)用為：3、 模型建立根據(jù)上面的分析，我們建立了模型最優(yōu)調(diào)運(yùn)模型： 其中：通過這個模型，在給定了偏離程度以及調(diào)運(yùn)天數(shù)T的情況下，就可以求出相應(yīng)的最優(yōu)方案。4、 一種情況下的最優(yōu)方案我們用一種特殊情況來演示模型的效果。由于不知道汛期何時到來，我們需要盡快做好準(zhǔn)備，在最短的時間內(nèi)使各個調(diào)運(yùn)節(jié)點(diǎn)的預(yù)測庫存得到盡量滿足。我們可以先進(jìn)行一個粗略的估算：各個調(diào)運(yùn)節(jié)點(diǎn)的原有庫存之和，而各個調(diào)運(yùn)節(jié)點(diǎn)的預(yù)測庫存之和，即相差670。因此，要基本滿足要求，需要各企業(yè)至少生產(chǎn)8天。我們就以8天為調(diào)運(yùn)期，求出最優(yōu)方案。我們假定取0.05，于是模型變?yōu)椋豪胠ingo 8.0編程求解，得到最低總運(yùn)輸費(fèi)用為321680元。調(diào)運(yùn)方案及其線路如表2所示：表2調(diào)運(yùn)方案線路調(diào)運(yùn)量（百件）企業(yè)1儲備庫1242627920企業(yè)2倉庫1414228275企業(yè)2倉庫74142282985企業(yè)2儲備庫1416402780企業(yè)2儲備庫2416430160企業(yè)3倉庫434323145企業(yè)3倉庫634133365企業(yè)3倉庫834323870企業(yè)3儲備庫234323930540倉庫3倉庫435323157.5倉庫5倉庫222191823300其中三個企業(yè)都生產(chǎn)8天。八、 問題三的解答利用模型，我們可以很容易地求出結(jié)果。仍令取0.05，此時，模型為：編程求解可求得最優(yōu)調(diào)運(yùn)方案（見附件4）。此時的運(yùn)輸費(fèi)用為299763元，20天后各個調(diào)運(yùn)節(jié)點(diǎn)的庫存情況如表3 所示：表3調(diào)運(yùn)后庫存預(yù)測庫存企業(yè)120企業(yè)20企業(yè)32.5倉庫1475500倉庫2570600倉庫3450300倉庫4332.5350倉庫5800400倉庫6285300倉庫7475500倉庫8570600儲備庫130003000儲備庫225002500九、 問題四的解答問題四要求緊急情況下的調(diào)運(yùn)方案。由于是緊急情況，所以應(yīng)該考慮速度盡可能快，路程盡可能少，對運(yùn)費(fèi)的要求就不是那么重要了。因此，我們要重新計(jì)算各個調(diào)運(yùn)節(jié)點(diǎn)之間的最短路徑。另外，由于洪水使部分道路不能使用，新的最短路徑必然與上面計(jì)算的最優(yōu)路徑有很大區(qū)別。利用模型I： 我們重新計(jì)算出各個調(diào)運(yùn)節(jié)點(diǎn)之間的最短路徑，由此，我們得到了一組新的，由于此時的意義是兩調(diào)運(yùn)節(jié)點(diǎn)之間的最短路程，因此，我們用來表示這個量。我們引入“量程積”的概念。量程積，即，運(yùn)輸數(shù)量與運(yùn)輸路程之積，單位是百件公里。由于是緊急情況，我們必須盡快完成調(diào)運(yùn)，并且使總量程積最小，我們?nèi)砸?guī)定在8天內(nèi)完成調(diào)運(yùn)任務(wù)。利用模型：我們解出了在這種情況下的最優(yōu)調(diào)度方案（見附件4）。此時的總量程積為：314297.5百件公里。十、 模型的進(jìn)一步討論1、 調(diào)運(yùn)期的長短與運(yùn)費(fèi)的關(guān)系在求解問題2和問題3的時候，我們發(fā)現(xiàn)，在調(diào)運(yùn)期為8天的時候，總運(yùn)費(fèi)為321680元，調(diào)運(yùn)期為20天的時候，總運(yùn)費(fèi)為299763元。顯然，調(diào)運(yùn)時間的長短對最終運(yùn)費(fèi)有著顯著影響。我們希望能夠找到一個最佳的時間，使得總運(yùn)費(fèi)能夠達(dá)到最小，同時，各個調(diào)運(yùn)點(diǎn)的能夠達(dá)到或超過預(yù)測值。為了找出這個最佳時間，我們在模型的基礎(chǔ)上作了一點(diǎn)改動，建立了模型最佳時間模型： 由于模型中與預(yù)測庫存的偏差的取值對最終費(fèi)用的大小有影響，因此，在這個模型中，我們對于調(diào)運(yùn)后的庫存量進(jìn)行了強(qiáng)制約束，要求在調(diào)度完畢之后，各庫的庫存都要達(dá)到或超過預(yù)測值。通過這個模型，代入不同的T值，將求出的結(jié)果互相比較，就可以得到最佳的調(diào)運(yùn)期限。利用lingo 8.0，我們將T從8開始，逐漸增加后代入求解。最終，我們得到每次的T值與其對應(yīng)的總運(yùn)費(fèi)，如圖1 所示：圖1從圖1中我們能不難看出，隨著調(diào)運(yùn)期的增加，總的調(diào)運(yùn)費(fèi)用不斷下降。當(dāng)T增加到22天的時候，調(diào)運(yùn)費(fèi)用趨于平衡，不再發(fā)生改變。造成這種情況的原因是，隨著調(diào)運(yùn)期限的增加，企業(yè)可用來生產(chǎn)的天數(shù)也增加，因而企業(yè)能夠運(yùn)出的物資量也增加，相應(yīng)的輸出選擇面和靈活度也增加，從而使總運(yùn)費(fèi)降低。因此，我們能夠得出如下結(jié)論：（1） 調(diào)運(yùn)期限越長，所要花費(fèi)的總運(yùn)費(fèi)越少。（2） 22天是最佳調(diào)運(yùn)期限，此后的調(diào)運(yùn)費(fèi)用不發(fā)生改變，因此沒有必要制定多于22天的調(diào)運(yùn)計(jì)劃。 （3） 如果能夠?qū)τ谘雌诘牡絹磉M(jìn)行比較準(zhǔn)確的預(yù)測，則在汛期到來之前22天開始進(jìn)行調(diào)運(yùn)，到汛期到來前一天結(jié)束，能夠得到最合適的結(jié)果。2、 調(diào)運(yùn)期的長短、的取值對于費(fèi)用的影響的取值對于費(fèi)用也有著重要的影響。因此，我們希望能夠找到和T對于總費(fèi)用的影響效果。模型：中同時含有和T兩個因素，因此，我們分別取不同的和T值，得到不同的費(fèi)用（見附件5 ），作出了圖2 ：圖2從上述圖表中我們可以很容易地看到：總調(diào)運(yùn)費(fèi)用y是關(guān)于普通倉庫預(yù)測庫存相對誤差和調(diào)運(yùn)周期T的二元函數(shù)；且總調(diào)運(yùn)費(fèi)用y均隨著可容相對誤差和物資生產(chǎn)天數(shù)T的增加而減少。這是非常符合實(shí)際情況的，因?yàn)楫?dāng)可容相對誤差的增大使得調(diào)運(yùn)工作的約束條件減弱，自由度增加，因而總的調(diào)運(yùn)費(fèi)用降低；物資生產(chǎn)天數(shù)T的增加使得各個企業(yè)的輸出能力增大，故導(dǎo)致調(diào)運(yùn)任務(wù)的靈活性增加，因而總的調(diào)運(yùn)費(fèi)用降低。同時，從上圖中我們也可以很明顯地看出：可容相對誤差的波動對總調(diào)運(yùn)費(fèi)用y的影響比物資生產(chǎn)天數(shù)T的改變對總調(diào)運(yùn)費(fèi)用y的影響要大。3、 汛期的預(yù)測前面說過，如果能夠?qū)ρ雌陂_始的時間做出準(zhǔn)