防洪物資調(diào)運(yùn)問題1

1、防洪物資調(diào)運(yùn)問題摘 要我們的模型主要用于解決如何在最少運(yùn)費(fèi)的情況下將必需物資調(diào)運(yùn)到各個(gè)倉庫以達(dá)到防洪的目的。對(duì)于問題一：我們采用賦權(quán)連通圖的圖論法，把兩地的運(yùn)費(fèi)作為它們之間線路的權(quán)值，然后利用“畫圈去大”原則進(jìn)行最小總權(quán)值的求解。然后，我們又引入了動(dòng)態(tài)規(guī)劃中的順序遞推法進(jìn)行兩地之間運(yùn)費(fèi)最短路的選擇。對(duì)于問題二：我們首先利用順序遞推法求解出任兩地之間的運(yùn)費(fèi)最短路徑。同時(shí)，由于要重點(diǎn)保證國(guó)家儲(chǔ)備庫，我們引進(jìn)加權(quán)系數(shù)、進(jìn)行調(diào)運(yùn)量的限制。由于倉庫3與倉庫5的現(xiàn)有庫存量大于預(yù)測(cè)庫存量，我們考慮是否應(yīng)將兩庫超過預(yù)測(cè)庫存量的那部分空閑物資進(jìn)行調(diào)運(yùn)，進(jìn)而建立了兩個(gè)模型。然后，我們分別運(yùn)用線性規(guī)劃的方法，給出目

2、標(biāo)函數(shù)，歸納如下：結(jié)合各自的約束條件，我們利用lindo軟件進(jìn)行解模，求出兩者的最優(yōu)調(diào)運(yùn)量及總運(yùn)費(fèi)。之后，進(jìn)行兩者總運(yùn)費(fèi)的比較，得出最終的最優(yōu)調(diào)運(yùn)方案。對(duì)于問題三：我們利用問題二的結(jié)果求出每個(gè)企業(yè)必要的最低生產(chǎn)天數(shù)，若企業(yè)的20天，則它所供給的倉庫以及儲(chǔ)備庫就已達(dá)到預(yù)測(cè)庫存量。若企業(yè)的20天，則可以用比例求解出20天后該企業(yè)向每個(gè)倉庫以及儲(chǔ)備庫的調(diào)運(yùn)量，進(jìn)而可以求出20天后各庫的庫存量。對(duì)于問題四：當(dāng)某路段遭破壞而不能保證某倉庫的儲(chǔ)存量時(shí)，我們考慮了三種方案。一為尋找次短路線進(jìn)行物資的重新調(diào)運(yùn)；二為從其他企業(yè)向供應(yīng)源中斷的倉庫進(jìn)行物資調(diào)配；三為進(jìn)行整體線路的重新調(diào)配。最后進(jìn)行三者總運(yùn)費(fèi)的比較，

3、確定了最經(jīng)濟(jì)合理的調(diào)配方案。一、問題重述（略）二、模型假設(shè)1、各企業(yè)的生產(chǎn)日期為無限。即在洪水之前各個(gè)企業(yè)均已將全部物資調(diào)運(yùn)到相應(yīng)的倉庫。2、在整個(gè)的生產(chǎn)過程中，生產(chǎn)費(fèi)用不予考慮。3、倉庫的物資的儲(chǔ)存費(fèi)、轉(zhuǎn)運(yùn)費(fèi)不予考慮。4、各個(gè)企業(yè)向倉庫轉(zhuǎn)運(yùn)的過程不予考慮，即轉(zhuǎn)運(yùn)的時(shí)間抽象為0。5、預(yù)測(cè)庫存即為能夠滿足最低保障的防洪物資量，最低庫存的物資量包含于其中。6、各企業(yè)的物資調(diào)運(yùn)在每天的分配里是均勻的，為線性遞增的。7、為了重點(diǎn)保證國(guó)家級(jí)儲(chǔ)備庫，我們引進(jìn)兩個(gè)滿足一定關(guān)系的權(quán)值系數(shù)、，這輛合格系數(shù)在一定程度上是切合實(shí)際的。三、符號(hào)說明： 階段： 從起點(diǎn)到第階段的狀態(tài)的最少費(fèi)用。： 之間的距離： 從地到地

4、的最少運(yùn)費(fèi)： 20天之后第個(gè)倉庫的庫存量： 從個(gè)企業(yè)到個(gè)倉庫每天的調(diào)運(yùn)量： 從個(gè)企業(yè)到個(gè)倉庫的總調(diào)運(yùn)量： 第個(gè)企業(yè)生產(chǎn)物資的天數(shù)： 從個(gè)企業(yè)到個(gè)倉庫調(diào)運(yùn)物資的天數(shù)： 前部指標(biāo)函數(shù)： 從起點(diǎn)到第階段的狀態(tài)的最少費(fèi)用。： 之間的距離、： 加權(quán)系數(shù)： 總費(fèi)用四、問題的分析對(duì)于問題一，我們要求解該地區(qū)的公路交通網(wǎng)的數(shù)學(xué)模型，即在此公路網(wǎng)中找出求解點(diǎn)對(duì)點(diǎn)的最短路徑，就可以使運(yùn)輸費(fèi)用最低。于是，我們想到了動(dòng)態(tài)規(guī)劃的方法。另外，還可以運(yùn)用一些其他的方法，如圖論連通附權(quán)值法。對(duì)于問題二，我們認(rèn)為可以不考慮企業(yè)的生產(chǎn)成本、企業(yè)生產(chǎn)天數(shù)的限制，而只需保證各倉庫儲(chǔ)存量以及國(guó)家級(jí)儲(chǔ)備庫的存儲(chǔ)量。又因需要重點(diǎn)保證國(guó)家儲(chǔ)

5、備庫。我們可以附權(quán)值系數(shù)、進(jìn)行調(diào)運(yùn)量的限制。然后，我們可以根據(jù)問題一中的動(dòng)態(tài)規(guī)劃的方法找到點(diǎn)對(duì)點(diǎn)的最短路徑。進(jìn)而，運(yùn)用線性規(guī)劃的方法，約定目標(biāo)函數(shù)然后進(jìn)行求解即可。對(duì)于問題三，我們可以利用問題二的結(jié)果求出了每個(gè)企業(yè)必要的最低生產(chǎn)天數(shù)，若某企業(yè)的20天，則它相應(yīng)的倉庫就已達(dá)到預(yù)測(cè)庫存量。若某企業(yè)的20天，則可以用比例法求解出20天后該企業(yè)向每個(gè)倉庫以及儲(chǔ)備庫的運(yùn)輸量，進(jìn)一步可以求出20天后各庫的庫存量；。對(duì)于問題四，當(dāng)某路段遭破壞而不能保證某倉庫的儲(chǔ)存量時(shí)，為求出其當(dāng)前的最短路徑，我們可以分析三個(gè)企業(yè)分別向該倉庫的運(yùn)費(fèi)情況，通過比較，得出哪個(gè)企業(yè)向其供給才使得總運(yùn)費(fèi)成本最低。五、模型的建立與求解

6、（一）、對(duì)于問題一：我們主要從附權(quán)連通圖和圖論、動(dòng)態(tài)規(guī)劃中的順序遞推法建立該地區(qū)公路交通網(wǎng)的數(shù)學(xué)模型。（1）、將生產(chǎn)企業(yè)，物資倉庫及國(guó)家級(jí)儲(chǔ)備庫計(jì)為相應(yīng)的頂點(diǎn)，將頂點(diǎn)之間的長(zhǎng)度用輸送單位物資量所需要的運(yùn)輸費(fèi)用來表示，計(jì)為邊的權(quán)，組合該運(yùn)輸問題所對(duì)應(yīng)的賦權(quán)連通圖，進(jìn)而求到該圖的最小樹，即為點(diǎn)對(duì)點(diǎn)運(yùn)輸成本最低的路線。其中的原則是：在點(diǎn)對(duì)點(diǎn)的運(yùn)輸過程中，盡量不要走回頭路。下面我們就以企業(yè) 1 向倉庫 5 和企業(yè) 1 向倉庫 2 的輸送最佳路徑的求解為例，闡釋一下我們的具體算法：根據(jù)附件2：1、我們得出企業(yè) 1 向倉庫 5 的簡(jiǎn)圖為接下來，我們求出費(fèi)用最短的路線，即運(yùn)輸路線。在此之前，我們引入上述算法

7、：在賦權(quán)圖中任取一個(gè)圈，然后去掉這個(gè)圈中權(quán)最大的邊，如果相等可以任去一條邊，如此繼續(xù)進(jìn)行下去直到圖中不再有圈為止。這時(shí)剩下的邊組成的子圖就是最小樹。從企業(yè)1到倉庫5有兩條路可走，分別為：路徑路程所需費(fèi)用24202213015624261922130156由以上的算法可知：由于兩條路徑相等，任意去掉一條，比如是242022，那么運(yùn)輸?shù)淖罴崖肪€為24261922。即路線圖為：2、我們得出企業(yè) 1 向倉庫 2 的簡(jiǎn)圖為即路線圖由以上的算法可知：任取一個(gè)閉合曲線，比如23181623，其中，1816運(yùn)費(fèi)最大，故舍去；再取23181922211623，其中，211623運(yùn)費(fèi)最大，故舍去；再取242022

8、192624，其中，24202219運(yùn)費(fèi)最大，故舍去，那么運(yùn)輸?shù)淖罴崖肪€為2426191823。為：對(duì)于我們引用的此種圖論方法，我們來證明這種方法的可行性：設(shè)在第一次去掉的邊為e,第二次去掉的邊為e,，最后去掉的邊為e,與這些邊對(duì)應(yīng)的圈為c,c,c,即每個(gè)e是c中權(quán)最大的邊。這里c是去掉邊e,e,e后剩下的圖中的圈，對(duì)于ij，c不屬于c。設(shè)去掉邊e, e, e后剩下的子圖為h，那么h是一棵樹。這是因?yàn)槊看稳サ舻倪卐都是圈中的邊，故去掉e后，圖仍是連通的。又去掉e后圖中沒有圈，因此剩下的子圖是一個(gè)無圈的連通圖，故是一棵樹。在h中任取一條邊e,s(e)=e,e, e, e且不妨設(shè)iir,有l(wèi)(e)

9、l(e),及l(fā)( t)l(e)顯然， e cs(e)e故e或等于e或等于e。由上面的假設(shè)，有l(wèi)(e)l(e)這與ec中權(quán)最大的邊矛盾，由定理:設(shè)t是g的一棵生成樹，t是g的唯一最小樹的充要條件是下列兩個(gè)條件中的任一個(gè)成立：對(duì)任意eg t,e是c(e)的唯一權(quán)最大的邊。對(duì)任意e t, e是s( e)的唯一權(quán)最小的邊。可知，h是最小樹。（2）、對(duì)于兩點(diǎn)間的路徑尋找，我們可以用動(dòng)態(tài)規(guī)劃的順序遞推方法尋找費(fèi)用的最短路徑。順序動(dòng)態(tài)規(guī)劃方程的原理為：我們可以考慮前部指標(biāo)函數(shù)及最優(yōu)值函數(shù)。當(dāng)時(shí)，得 于是得： （ * ）式中，或。其求解過程，根據(jù)邊界條件k=2開始，由前向后順推，最后求出時(shí)，就得到整個(gè)問題的最

10、優(yōu)解。（ * ）式稱為順序動(dòng)態(tài)規(guī)劃方程。（二）、對(duì)于問題二：要設(shè)計(jì)最合理的調(diào)運(yùn)方案，我們采用的衡量指標(biāo)為：總運(yùn)費(fèi)最少。我們可以利用上題的第二種的動(dòng)態(tài)規(guī)劃的順序解法求解個(gè)兩點(diǎn)間的運(yùn)費(fèi)最短路問題：我們以求解企業(yè)1倉庫2的總運(yùn)費(fèi)最少時(shí)對(duì)應(yīng)的路徑為例：（1）、當(dāng)=1時(shí)， =,（2）、當(dāng)=2時(shí)， =30*1.2=36元（3）、當(dāng)=3時(shí)，（4）、當(dāng)=4時(shí)，（5）、當(dāng)=5時(shí)，故：當(dāng)費(fèi)用最少時(shí)，為150元，與其相對(duì)應(yīng)的路徑為24-26-19-18-23。同樣地，我們可以得出任何一個(gè)企業(yè)往任何一個(gè)儲(chǔ)備庫或者任一個(gè)倉庫進(jìn)行物資調(diào)運(yùn)時(shí)的最合理的路徑：企業(yè)1倉庫/儲(chǔ)備庫企業(yè)2倉庫/儲(chǔ)備庫企業(yè)3倉庫/儲(chǔ)備庫儲(chǔ)備庫1倉庫

11、儲(chǔ)備庫2倉庫 在設(shè)計(jì)該物資的調(diào)運(yùn)方案時(shí)，我們要重點(diǎn)保證國(guó)家級(jí)儲(chǔ)備庫。為了實(shí)現(xiàn)此目標(biāo)，我們引進(jìn)兩個(gè)加權(quán)值和，8個(gè)倉庫的加權(quán)系數(shù)為同一個(gè)優(yōu)先等級(jí)的，兩個(gè)儲(chǔ)備庫的加權(quán)系數(shù)為同一個(gè)優(yōu)先等級(jí)的。于是，有：即：又因在同等情況下，我們要更大可能地給國(guó)家儲(chǔ)備庫進(jìn)行物資的調(diào)運(yùn)以重點(diǎn)保證國(guó)家級(jí)儲(chǔ)備庫，于是，在保證最小運(yùn)費(fèi)的情況下，有：，即：，從而：我們?nèi)。?，因?yàn)轭A(yù)測(cè)庫存為最低保障下的庫存量，我們只需保證各庫的最終庫存量不少于預(yù)測(cè)庫存即可。而倉庫3與倉庫5的現(xiàn)存量大于預(yù)測(cè)量。于是，企業(yè)和儲(chǔ)備庫沒有必要再向倉庫3和倉庫5進(jìn)行物資的調(diào)運(yùn)，并且我們可以考慮將兩庫的超過預(yù)測(cè)庫存量的那部分空閑物資進(jìn)行調(diào)運(yùn)。下面，我們分兩種情

12、況來看究竟有沒有必要把倉庫3與倉庫5的那部分空閑物資進(jìn)行調(diào)運(yùn)。方案一：把倉庫3與倉庫5的那部分空閑物資進(jìn)行調(diào)運(yùn)： 要使總運(yùn)費(fèi)最小，我們對(duì)此問題進(jìn)行如下的線性規(guī)劃：我們利用lindo軟件進(jìn)行求解（具體代碼及結(jié)果見附錄一），得到： （單位：百件） 在此種情況下，總的運(yùn)費(fèi)為： =363816(元) 方案二：不把倉庫3與倉庫5的那部分空閑物資進(jìn)行調(diào)運(yùn)：要使總運(yùn)費(fèi)最小，我們對(duì)此問題進(jìn)行如下的線性規(guī)劃：我們利用lindo軟件進(jìn)行求解（具體代碼及結(jié)果見附錄二），得到： （單位：百件） 在此種情況下，總的運(yùn)費(fèi)為： =317076(元) 待添加的隱藏文字內(nèi)容1由上，我們可以看出： 于是，我們應(yīng)該選擇第二種方案。

13、即：不把倉庫3與倉庫5的那部分空閑物資進(jìn)行調(diào)運(yùn)。綜上：在最合理的物資調(diào)運(yùn)方案中，各物資的調(diào)運(yùn)線路和調(diào)運(yùn)量為：調(diào)運(yùn)起始點(diǎn)調(diào)運(yùn)線路調(diào)運(yùn)量（百件）總運(yùn)費(fèi)(元)企業(yè)1倉庫22426191823330317076企業(yè)1儲(chǔ)備庫12426271000企業(yè)2倉庫141-42-28300企業(yè)2倉庫741-42-28-29110企業(yè)3倉庫434-32-31120企業(yè)3倉庫634-1-33-3620企業(yè)3倉庫834-32-38100企業(yè)3儲(chǔ)備庫234-32-39-30700（三）、對(duì)于問題三：在計(jì)算出各個(gè)調(diào)運(yùn)線路及其調(diào)運(yùn)量之后，我們利用各企業(yè)的調(diào)運(yùn)量來對(duì)各企業(yè)的物資生產(chǎn)時(shí)間進(jìn)行限制。因?yàn)槠髽I(yè)的總庫存量應(yīng)該始終小于最

14、大庫存量，即：對(duì)于企業(yè)一：0 40 +600-1300 800 17.537.5對(duì)于企業(yè)二：0 30+360-410600 3.6736.7對(duì)于企業(yè)三：0 20+500-940600 2252我們對(duì)各個(gè)企業(yè)的生產(chǎn)過程只要求達(dá)到各個(gè)倉庫的預(yù)測(cè)庫存量，于是，我們只要取各企業(yè)的生產(chǎn)時(shí)間的最小值即可。即：=18 =4 =22于是，在20天后，企業(yè)1與企業(yè)2已將全部物資運(yùn)完，此時(shí)，一些倉庫的庫存量為（單位：百件） ， ， ， ， 。而在20天后，企業(yè)3還未將全部物資調(diào)運(yùn)完，且上述第（2）種方案提出的結(jié)果為全部調(diào)運(yùn)完時(shí)的總調(diào)運(yùn)物資量，又由于我們假設(shè)企業(yè)向倉庫每天調(diào)運(yùn)的量是相同的，即：企業(yè)3的調(diào)運(yùn)量情況為線

15、性遞增的。于是，在20天后，其他倉庫的庫存量（單位：百件）為：綜上，在20天之后，各個(gè)倉庫的庫存量為：倉庫庫存量（百件）倉庫1500倉庫2600倉庫3450倉庫4339.1倉庫5800倉庫6298.18倉庫7500倉庫8590.91儲(chǔ)備庫13000儲(chǔ)備庫22436.36我們用圖表的形式表示出來，如下圖：（四）、對(duì)于問題四：由第（2）題的結(jié)果可知，有些企業(yè)與倉庫之間不需要調(diào)運(yùn)物資，于是其均為0。在最小調(diào)運(yùn)費(fèi)的條件、所有的調(diào)運(yùn)路線中，只有企業(yè)1 儲(chǔ)備庫1 之間的調(diào)運(yùn)最短路徑2426 27發(fā)生中斷，于是，我們可以用三種方案來闡述一下在路段中斷的情況下，該如何做才能既保證物資的運(yùn)輸量又能保證運(yùn)輸費(fèi)用最

16、少：方案一：只改變企業(yè)1儲(chǔ)備庫1的調(diào)運(yùn)路線，用次短路線24201327，此路線的運(yùn)費(fèi)為：z=241.6元/百件。此時(shí)，總運(yùn)費(fèi)為：方案二：因企業(yè)1儲(chǔ)存庫1的路發(fā)生了中斷，阻礙了倉庫1的物資來源，于是我們也可以考慮從其他資源庫（如企業(yè)2，企業(yè)3）進(jìn)行物資的調(diào)整，又因從圖中顯而易見，從企業(yè)3到儲(chǔ)備庫1的運(yùn)費(fèi)明顯高于從企業(yè)2的運(yùn)費(fèi)，于是應(yīng)選擇后者，此時(shí)：運(yùn)輸量為（單位：百件）：總費(fèi)用為（單位：元）：方案三：當(dāng)1423，1125，2627，931這些路段發(fā)生中斷時(shí)我們可以進(jìn)行總體路線大調(diào)整。當(dāng)已求得的最短路徑中包括上述4條路段的，找出其完整的無中斷的最短路徑，再進(jìn)行求解。我們同樣地利用線性規(guī)劃的方法進(jìn)行

17、在新的方案下調(diào)運(yùn)量的求解：我們利用lindo軟件進(jìn)行求解(具體過程和結(jié)果見附錄三)，結(jié)果為：（單位：百件） 很顯然，此種方法下與上述的第二種方法是一樣的：都是把原來企業(yè)1向儲(chǔ)備庫1提供的物資轉(zhuǎn)換為由企業(yè)2來提供。 此時(shí)，總的運(yùn)費(fèi)為：（元）綜上，我們得到：在汛期時(shí)，14-23,11-25,26-27,9-31路段因洪水而發(fā)生交通中斷時(shí)，我們的最優(yōu)措施就是：把原來企業(yè)1向儲(chǔ)備庫1提供的物資轉(zhuǎn)換為由企業(yè)2來提供，即：調(diào)運(yùn)起始點(diǎn)調(diào)運(yùn)量（百件）總運(yùn)費(fèi)(元)企業(yè)1倉庫2330354676企業(yè)2倉庫1300企業(yè)2倉庫7110企業(yè)2儲(chǔ)備庫11000企業(yè)3倉庫4120企業(yè)3倉庫620企業(yè)3倉庫8100企業(yè)3儲(chǔ)備庫2700六、模型的改進(jìn)1、我們可以使得每個(gè)企業(yè)向每個(gè)倉庫、儲(chǔ)備庫調(diào)運(yùn)物資的時(shí)間不一樣，即不同。在此情況下，我們同樣可以利用線性規(guī)劃建立如下模型：由于我們對(duì)lingo及matlab