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

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