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

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

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

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

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

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

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

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

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

9、i<<i.今證若不然，設(shè)。 取i使i是滿足l(e)= 的所有i中指標最大的。所以對s>r,有l(wèi)(e)<l(e),及l(fā)( t)<l(e)顯然， e cs(e)e故e或等于e或等于e。由上面的假設(shè)，有l(wèi)(e)<l(e)這與e<c中權(quán)最大的邊矛盾，由定理:設(shè)t是g的一棵生成樹，t是g的唯一最小樹的充要條件是下列兩個條件中的任一個成立：對任意eg t,e是c(e)的唯一權(quán)最大的邊。對任意e t, e是s( e)的唯一權(quán)最小的邊?？芍?，h是最小樹。（2）、對于兩點間的路徑尋找，我們可以用動態(tài)規(guī)劃的順序遞推方法尋找費用的最短路徑。順序動態(tài)規(guī)劃方程的原理為：我們可以

10、考慮前部指標函數(shù)及最優(yōu)值函數(shù)。當時，得 于是得： （ * ）式中，或。其求解過程，根據(jù)邊界條件k=2開始，由前向后順推，最后求出時，就得到整個問題的最優(yōu)解。（ * ）式稱為順序動態(tài)規(guī)劃方程。（二）、對于問題二：要設(shè)計最合理的調(diào)運方案，我們采用的衡量指標為：總運費最少。我們可以利用上題的第二種的動態(tài)規(guī)劃的順序解法求解個兩點間的運費最短路問題：我們以求解企業(yè)1倉庫2的總運費最少時對應的路徑為例：（1）、當=1時， =,（2）、當=2時， =30*1.2=36元（3）、當=3時，（4）、當=4時，（5）、當=5時，故：當費用最少時，為150元，與其相對應的路徑為24-26-19-18-23。同樣地，

11、我們可以得出任何一個企業(yè)往任何一個儲備庫或者任一個倉庫進行物資調(diào)運時的最合理的路徑：企業(yè)1倉庫/儲備庫企業(yè)2倉庫/儲備庫企業(yè)3倉庫/儲備庫儲備庫1倉庫儲備庫2倉庫 在設(shè)計該物資的調(diào)運方案時，我們要重點保證國家級儲備庫。為了實現(xiàn)此目標，我們引進兩個加權(quán)值和，8個倉庫的加權(quán)系數(shù)為同一個優(yōu)先等級的，兩個儲備庫的加權(quán)系數(shù)為同一個優(yōu)先等級的。于是，有：即：又因在同等情況下，我們要更大可能地給國家儲備庫進行物資的調(diào)運以重點保證國家級儲備庫，于是，在保證最小運費的情況下，有：，即：，從而：我們?nèi)。?，因為預測庫存為最低保障下的庫存量，我們只需保證各庫的最終庫存量不少于預測庫存即可。而倉庫3與倉庫5的現(xiàn)存量大于

12、預測量。于是，企業(yè)和儲備庫沒有必要再向倉庫3和倉庫5進行物資的調(diào)運，并且我們可以考慮將兩庫的超過預測庫存量的那部分空閑物資進行調(diào)運。下面，我們分兩種情況來看究竟有沒有必要把倉庫3與倉庫5的那部分空閑物資進行調(diào)運。方案一：把倉庫3與倉庫5的那部分空閑物資進行調(diào)運： 要使總運費最小，我們對此問題進行如下的線性規(guī)劃：我們利用lindo軟件進行求解（具體代碼及結(jié)果見附錄一），得到： （單位：百件） 在此種情況下，總的運費為： =363816(元) 方案二：不把倉庫3與倉庫5的那部分空閑物資進行調(diào)運：要使總運費最小，我們對此問題進行如下的線性規(guī)劃：我們利用lindo軟件進行求解（具體代碼及結(jié)果見附錄二）

13、，得到： （單位：百件） 在此種情況下，總的運費為： =317076(元) 待添加的隱藏文字內(nèi)容1由上，我們可以看出： < 于是，我們應該選擇第二種方案。即：不把倉庫3與倉庫5的那部分空閑物資進行調(diào)運。綜上：在最合理的物資調(diào)運方案中，各物資的調(diào)運線路和調(diào)運量為：調(diào)運起始點調(diào)運線路調(diào)運量（百件）總運費(元)企業(yè)1倉庫22426191823330317076企業(yè)1儲備庫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儲備庫234-32-

14、39-30700（三）、對于問題三：在計算出各個調(diào)運線路及其調(diào)運量之后，我們利用各企業(yè)的調(diào)運量來對各企業(yè)的物資生產(chǎn)時間進行限制。因為企業(yè)的總庫存量應該始終小于最大庫存量，即：對于企業(yè)一：0 40 +600-1300 800 17.537.5對于企業(yè)二：0 30+360-410600 3.6736.7對于企業(yè)三：0 20+500-940600 2252我們對各個企業(yè)的生產(chǎn)過程只要求達到各個倉庫的預測庫存量，于是，我們只要取各企業(yè)的生產(chǎn)時間的最小值即可。即：=18 =4 =22于是，在20天后，企業(yè)1與企業(yè)2已將全部物資運完，此時，一些倉庫的庫存量為（單位：百件） ， ， ， ， 。而在20天后，

15、企業(yè)3還未將全部物資調(diào)運完，且上述第（2）種方案提出的結(jié)果為全部調(diào)運完時的總調(diào)運物資量，又由于我們假設(shè)企業(yè)向倉庫每天調(diào)運的量是相同的，即：企業(yè)3的調(diào)運量情況為線性遞增的。于是，在20天后，其他倉庫的庫存量（單位：百件）為：綜上，在20天之后，各個倉庫的庫存量為：倉庫庫存量（百件）倉庫1500倉庫2600倉庫3450倉庫4339.1倉庫5800倉庫6298.18倉庫7500倉庫8590.91儲備庫13000儲備庫22436.36我們用圖表的形式表示出來，如下圖：（四）、對于問題四：由第（2）題的結(jié)果可知，有些企業(yè)與倉庫之間不需要調(diào)運物資，于是其均為0。在最小調(diào)運費的條件、所有的調(diào)運路線中，只有企

16、業(yè)1 儲備庫1 之間的調(diào)運最短路徑2426 27發(fā)生中斷，于是，我們可以用三種方案來闡述一下在路段中斷的情況下，該如何做才能既保證物資的運輸量又能保證運輸費用最少：方案一：只改變企業(yè)1儲備庫1的調(diào)運路線，用次短路線24201327，此路線的運費為：z=241.6元/百件。此時，總運費為：方案二：因企業(yè)1儲存庫1的路發(fā)生了中斷，阻礙了倉庫1的物資來源，于是我們也可以考慮從其他資源庫（如企業(yè)2，企業(yè)3）進行物資的調(diào)整，又因從圖中顯而易見，從企業(yè)3到儲備庫1的運費明顯高于從企業(yè)2的運費，于是應選擇后者，此時：運輸量為（單位：百件）：總費用為（單位：元）：方案三：當1423，1125，2627，931

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