關(guān)于防洪物資調(diào)運的優(yōu)化模型

1、關(guān)于防洪物資調(diào)運的優(yōu)化模型摘 要在充分理解題意的基礎(chǔ)上，我們將這個運輸問題歸結(jié)為先求最短路再進行線性規(guī)劃的問題，并給出運輸費用等價轉(zhuǎn)換和運輸?shù)匚坏葍r轉(zhuǎn)換兩個轉(zhuǎn)化法則，對模型的統(tǒng)一和簡化起了關(guān)鍵作用.在求解最短路時，我們采用了dijkstra和floyd兩種算法，并利用matlab軟件進行計算.分析我們的線性規(guī)劃模型，由于變量和約束條件較少，利用lingo軟件可以很容易給出最優(yōu)方案.對主要問題二，我們向當(dāng)?shù)赜嘘P(guān)部門提出的調(diào)運方案為16天達到各庫預(yù)測庫存，總運費為335330元.在問題二解決的基礎(chǔ)上，又對模型作了推廣，即在滿足預(yù)測庫存量后，繼續(xù)調(diào)運。那么20天后各庫庫存量為庫名倉庫1倉庫2倉庫3倉

2、庫4倉庫5倉庫6倉庫7倉庫8儲備庫1儲備庫2庫存量50060045035080030050060034802600模型的適應(yīng)度良好，在遇到如問題四的緊急情況時，模型仍然適用，從而大大拓廣了模型的適用范圍.在論文中，我們還對所建立的模型的優(yōu)缺點和需要改進的方向進行了討論.一、問題重述（略）二、基本符號說明與基本假設(shè)2.1 基本符號說明：提供物資的點：需要物資的點：從運往的運量（）：可以提供的物資量：處接收的物資量：單位距離單位百件數(shù)的運價：和之間的最短路（）：總運費2.2 基本假設(shè)1、 假定天氣情況對公路運輸?shù)挠绊懖淮?，可以忽略不計?、 從分布圖上可以看出最遠(yuǎn)的兩個運輸點之間的距離也不過是幾百

3、公里，按照現(xiàn)在的交通運輸水平，我們可以絕對保證物資在一天內(nèi)運到，這樣庫存就不再受到最大容量的約束；3、 假定無論運多少物資，我們都有足夠的車輛保證運輸量；4、 假定提前儲備的時間充分，無需在短時間內(nèi)完成；5、 假設(shè)各庫達到預(yù)測庫存后，企業(yè)就不再生產(chǎn).三、問題分析和基本思路3.1 問題分析和建模思路考慮問題的題設(shè)和要求，我們要解決的是防洪物資調(diào)運優(yōu)化配置問題.對題目仔細(xì)地分析后，我們決定首先建立該地區(qū)公路交通網(wǎng)的數(shù)學(xué)模型.各離散的交匯點之間的關(guān)系可以比較容易地用鄰接矩陣表示出來，難點是圖中有兩種不同的公路，它們的單位運輸費不同.我們分析了兩者之間的聯(lián)系，根據(jù)運輸費用等價轉(zhuǎn)換法則，將高等級公路轉(zhuǎn)化

4、為普通公路，這樣模型得到了統(tǒng)一.下面的問題便是一個典型的運輸問題.我們先求出圖中各企業(yè)、倉庫及儲備庫之間的最短路，進而利用線性規(guī)劃模型計算出運輸方案.在求解運輸方案時，我們根據(jù)運輸?shù)匚坏葍r轉(zhuǎn)化法則，將現(xiàn)有庫存量多余的倉庫轉(zhuǎn)化為企業(yè)，進一步簡化了模型.又考慮到要重點保證國家級儲備庫，我們分別從時間和費用兩方面考慮，給出優(yōu)化方案，并進行了比較. 由于數(shù)據(jù)量較大，我們借助計算機對模型進行最優(yōu)求解.3.2 思路流程圖下面的思路流程圖是我們文章結(jié)構(gòu)的一個縮影，它完整而形象地反映了我們文章的建模思路.圖1：建模思路流程圖運輸費用等價轉(zhuǎn)換法則公路交通網(wǎng)數(shù)學(xué)模型最短路問題dijkstra算法floyd算法線性

5、規(guī)劃模型最終調(diào)運方案lingo軟件運輸?shù)匚坏葍r轉(zhuǎn)換法則模型優(yōu)缺點評價四、模型的準(zhǔn)備運輸費用等價轉(zhuǎn)換法則：對于高等級公路線上的任意兩點、之間的長度，根據(jù)高等級公路單位運費（2元/公里百件）求得對應(yīng)的總運費為；設(shè)與等費用的普通公路的長度為，又根據(jù)普通公路單位運費（1.2元/公里百件），我們得到如下等式： .從而有 .由此，我們把兩種公路的交通網(wǎng)化歸為普通公路交通網(wǎng)，使模型得到了統(tǒng)一.運輸?shù)匚坏葍r轉(zhuǎn)換法則：按照我們的調(diào)運方案，倉庫3和倉庫5的地位和企業(yè)其實是一樣的，我們可以把它們看成是一種特殊的企業(yè)（產(chǎn)量為0），分別記為企業(yè)4和企業(yè)5.因此，我們就把運輸問題化為有5個提供物資的點，8個接收物資的點.

6、五、模型的建立與求解5.1 問題一：建立該地區(qū)公路交通網(wǎng)的數(shù)學(xué)模型我們把離散的各交匯點以鄰接矩陣的模式在計算機中存儲（主程序見附件2），其中0表示兩節(jié)點無邊直接相連，非0表示有邊直接相連，且鄰接矩陣中的元素以其兩節(jié)點之間的距離即權(quán)重來表示.由于該矩陣太大，且其僅作為解決后續(xù)問題的一個鋪墊，在此我們不再給出具體的表示，僅將統(tǒng)一后的交通網(wǎng)絡(luò)圖附上（說明見圖注）.生產(chǎn)企業(yè)、物資倉庫及國家級儲備庫分布圖5.2 問題二5.2.1用兩種算法求解最短路問題考慮問題的題設(shè)和要求，為了給調(diào)運方案做個鋪墊，我們首先要解決的是最短調(diào)運路線問題，即離散型優(yōu)化問題中的最短路問題.最短路問題是圖論應(yīng)用的基本問題，一般是在

7、賦權(quán)圖中討論.由問題一，我們很容易得到一張賦權(quán)圖，因此，我們可以直接利用以下兩種算法求解最短路問題.方法一：dijkstra算法dijkstra算法是一種標(biāo)號法：給賦權(quán)圖的每一個定點記一個數(shù)，稱為頂點的標(biāo)號臨時標(biāo)號（簡稱t標(biāo)號）或者固定標(biāo)號（簡稱p標(biāo)號）.t標(biāo)號表示從始頂點到這個頂點的最短路長的上界，p標(biāo)號則是從始頂點到這個頂點的最短路長.dijkstra算法步驟：（1）給頂點標(biāo)p標(biāo)號，給頂點標(biāo)t標(biāo)號；（2）在所有t標(biāo)號中取最小值，譬如，則把的t標(biāo)號改為p標(biāo)號，并重新計算具有t標(biāo)號的其它各頂點的t標(biāo)號：選頂點的t標(biāo)號與中較小者作為的新的t標(biāo)號，即設(shè)若 ，則改記為頂點的p標(biāo)號，于是，把中的頂點的

8、t標(biāo)號修改為，顯然，這里只需對與相鄰的具有t標(biāo)號的頂點重新t標(biāo)號即可.（3）重復(fù)上述步驟（2），直到.這時即為從頂點到的最短路長.根據(jù)最短路的如下性質(zhì)：若路徑為至的最短路徑，則必然就是至得最短路徑（即動態(tài)規(guī)劃中的最優(yōu)性原理），求最短路徑可以采用dijkstra算法直接做出判斷如下：表1 生產(chǎn)企業(yè)、物資倉庫及國家級儲備庫兩兩之間的最短距離企1企2企3倉1倉2倉3倉4倉5倉6倉7倉8儲1儲2企10154125192130100企2058157158118131企301237514593102倉115458060倉21251570139165倉31230175倉419215875092127倉513

9、01390170倉61450113倉711860018062倉8931130145儲1100131165921701800儲2102175127621450注：1）表中數(shù)據(jù)均已換算成普通公路區(qū)間距離，單位：公里；2）對于有的顯然不會影響最短路判斷的數(shù)據(jù)，我們就不再贅述了.由表中數(shù)據(jù)和最短路算法可以粗略得出調(diào)運量及調(diào)運方案如下：1） 從企業(yè)2的庫存中運300百件至倉庫1，則倉庫2達到預(yù)測庫存；2） 將企業(yè)2的剩余庫存60百件及生產(chǎn)了5/3天（假設(shè)三個企業(yè)從同一時刻開始24小時不停生產(chǎn)，即為40小時）后的產(chǎn)量全部運至倉庫7，則倉庫7達到預(yù)測庫存；3） 從企業(yè)1的庫存中運330百件至倉庫2，則倉庫2

10、達到預(yù)測庫存；4） 從企業(yè)3的庫存中運120百件至倉庫4，運20百件至倉庫6，運100百件至倉庫8，則倉庫4、倉庫6、倉庫8都達到預(yù)測庫存；5） 將倉庫3的多余庫存150百件、企業(yè)3的剩余庫存160百件及生產(chǎn)了19.5天后的產(chǎn)量全部運至儲備庫2，則儲備庫2達到預(yù)測庫存；6） 將倉庫5的多余庫存400百件、企業(yè)1的剩余庫存270百件及企業(yè)1在19.5天內(nèi)生產(chǎn)的產(chǎn)量中抽1000百件運至儲備庫1，則儲備庫1達到預(yù)測庫存.我們最終得到總運輸成本約為：方法二：floyd算法floyd 算法的基本思路是：從圖的帶權(quán)鄰接矩陣a=nn開始，遞歸地進行n次更新，即由矩陣d(0)=a，按一個公式，構(gòu)造出矩陣d(1

11、)；又用同樣地公式由d(1)構(gòu)造出d(2)；最后又用同樣的公式由d(n-1)構(gòu)造出矩陣d(n).矩陣d(n)的行列元素便是號頂點到號頂點的最短路徑長度，稱d(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣來記錄兩點間的最短路徑. 遞推公式為： d(0)=a；d(1)=dij(1)nn，其中dij(1)=mindij(0),di1(0)+d1j(0)；d(2)=dij(2) nn，其中dij(2)=mindij(1),di2(1)+d2j(1)；d(n)= dij(n) nn，其中dij(n)=mindij(n-1),di, n-1 (n-1)+d n-1,j(n-1)；采用循環(huán)迭代可以簡便求

12、出上述矩陣序列，具體算法如下： ：用表示，其含義為到的最短路徑存放在數(shù)組第個存儲單元中.：對應(yīng)于的路徑上的后繼點，最終的取值為到的最短路徑上的后繼點. 輸入帶權(quán)鄰接矩陣a=)nn 1）賦初值 對所有；當(dāng)時，否則；. 2）更新 對所有，若，則轉(zhuǎn)3）；否則，繼續(xù)執(zhí)行3）. 3）重復(fù)2）直到.根據(jù)上述算法，我們的得到了圖的距離矩陣d和后繼節(jié)點矩陣r（見附件5），現(xiàn)在把對我們有用的數(shù)據(jù)整理如下：表2 生產(chǎn)企業(yè)、物資倉庫及國家級儲備庫兩兩之間的最短距離企1企2企3倉1倉2倉3倉4倉5倉6倉7倉8儲1儲2企10148267154125340192130287214310100268企21480233581

13、57306158206253118276131148企326723302243321237533714516493167102倉115458224016329721621231160267189122倉21251573321630405257139352223375165285倉33403061232974050148410268237166240175倉419215875216257148026219918911892127倉51302063372121394102620357272380170334倉62872531453113522681993570302113187247倉721411

14、816460223237189272302020718062倉8310276932673751661183801132070210145儲1100131167189165240921701871802100183儲2268148102122285175127334247621451830我們通過dijkstra算法求得的部分最短路數(shù)據(jù)和計算機用floyd算法得出的完全吻合，這就基本保證了我們最終調(diào)運方案的可靠性和準(zhǔn)確性.根據(jù)上述表格中數(shù)據(jù)得出簡化的公路交通圖如下：5.2.2用線性規(guī)劃模型解決運輸分配問題設(shè)有個提供物資的點，可以提供的物資量為，所有物資運送到個接收點，在處接收的物資量為（）.又設(shè)

15、表示從運往的運量，表示和之間的最短路，表示單位距離的運價，用表示總運費，則有目標(biāo)函數(shù)： （5-1）下面我們來分析題目中的一些約束條件：首先，各個企業(yè)原有庫存、新生產(chǎn)的產(chǎn)量和倉庫原有的多余預(yù)測庫存的量應(yīng)該滿足國家級儲備庫和其它各個倉庫的需求，因此，總的供應(yīng)量總的需求量，即 （5-2）其次，運輸量只需讓各個倉庫都達到預(yù)測庫存即可，于是得到如下兩個約束條件： （5-3） （5-4）綜上，可以建立如下的數(shù)學(xué)模型 （5-5）由于問題可以轉(zhuǎn)化為5個企業(yè)向8個倉庫運輸問題，于是，對于上述線性規(guī)劃模型來說，由附件1可以很容易得出企業(yè)各自的供應(yīng)量和倉庫各自的需求量.設(shè) 根據(jù)此模型，我們用lingo語言編寫了通用

16、程序（見附件4），便于多次調(diào)用.根據(jù)題目要求，我們首先考慮國家儲備庫的物資運輸問題.方案一我們發(fā)現(xiàn)5個企業(yè)的總庫存為2010大于儲備庫的總需求量1700，所以在滿足最短時間滿足儲備庫的條件下，可以一天達到.利用lingo程序，算得總費用為240672元.但考慮到這種方案僅注意到時間，經(jīng)濟效果較差，不予采用，所以也不再給出分配方案.方案二我們發(fā)現(xiàn)，儲備庫和企業(yè)1、企業(yè)2、企業(yè)3之間路程最短，所以我們對方案一進行了修正，以企業(yè)1、企業(yè)2、企業(yè)3在最短時間（3天）內(nèi)生產(chǎn)出需求量為條件進行分配.此時企業(yè)最短距倉庫企業(yè)1企業(yè)2企業(yè)3企業(yè)4 （倉3）企業(yè)5 （倉5）需求量儲備庫11001311672401

17、701000儲備庫2268148102175334700供應(yīng)量720450560150400用lingo軟件解得企業(yè)供應(yīng) 量倉庫企業(yè)1企業(yè)2企業(yè)3企業(yè)4 （倉3）企業(yè)5 （倉5）儲備庫1720280000儲備庫2014056000總費用為223824元.此時企業(yè)2有庫存30，企業(yè)1、企業(yè)3為空.方案三在此我們不以最短時間運滿儲備庫為條件，而是先假設(shè)企業(yè)1、企業(yè)2、企業(yè)3的產(chǎn)量都可以滿足需求，由題目假設(shè)與分析知，庫容量已不再約束，所以有企業(yè)最短距倉庫企業(yè)1企業(yè)2企業(yè)3企業(yè)4 （倉3）企業(yè)5 （倉5）需求量儲備庫11001311672401701000儲備庫2268148102175334700供

18、應(yīng)量170017001700150400用lingo軟件解得企業(yè)供應(yīng) 量倉庫企業(yè)1企業(yè)2企業(yè)3企業(yè)4 （倉3）企業(yè)5 （倉5）儲備庫110000000儲備庫20070000總運費為205680元，用時10天.此時，企業(yè)1、企業(yè)3為空.下面我們解決其它倉庫的運輸調(diào)運問題，此時，我們可以不再受時間約束，僅以運費最小為目標(biāo)，沿用上面方案三的思想，各倉庫的總需求量為980，所以企業(yè)最短距倉庫企業(yè)1企業(yè)2企業(yè)3企業(yè)4 （倉3）企業(yè)5 （倉5）需求量倉庫115458224297212300倉庫2125157332405139330倉庫419215875148262120倉庫6287253145268357

19、20倉庫7214118164237272110倉庫8100131167240170100供應(yīng)量980980980980980用lingo軟件解得企業(yè)供應(yīng) 量倉庫企業(yè)1企業(yè)2企業(yè)3企業(yè)4 （倉3）企業(yè)5 （倉5）倉庫10300000倉庫23300000倉庫40012000倉庫6002000倉庫70110000倉庫80010000總費用為111396元.結(jié)合上述方案二、三，總時間分別為16天和22天，總運費分別為335220元和317086元.結(jié)合時效性和經(jīng)濟效果比較這兩個結(jié)果，我們選取方案二向當(dāng)?shù)赜嘘P(guān)部門提出建議.至此，我們順利完成了調(diào)運防洪抗?jié)澄镔Y的工作.問題三 20天后各庫庫存量 從問題二的

20、結(jié)果可看出，在16天內(nèi)便達到了各庫的預(yù)測庫存，在此我們繼續(xù)對上述方案進行擴展。20天后三個企業(yè)可提供的貨物量分別為350、130、100.考慮到仍然要優(yōu)先考慮國家儲備庫，則20天后各庫庫存量如下表庫名倉庫1倉庫2倉庫3倉庫4倉庫5倉庫6倉庫7倉庫8儲備庫1儲備庫2庫存量50060045035080030050060034802600問題四 因洪水交通中斷后的模型由于洪水沖毀了四條路，即這些交匯點之間斷開，所以我們只需對求最短路的matlab主程序數(shù)據(jù)稍加修改即可得到下表：表3 修改后的生產(chǎn)企業(yè)、物資倉庫及國家級儲備庫兩兩之間的最短距離企1企2企3倉1倉2倉3倉4倉5倉6倉7倉8儲1儲2企101

21、48378154125451403130342214421201276企2148025358157333328206253118293131148企337825302243871237541814516493187102倉115458224016329724921231160267189122倉21251573871630460412139410223430276285倉34513331232974600148509268237166310175倉4403328752494121480461220189118262127倉51302064182121395094610372272379231334倉63422531453114102682203720302113187247倉721411816460223237189272302020718062倉8421293932674301661183791132070275145儲12011311871892763102622311871802750