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

防洪物資調(diào)運問題摘要 本題所研究的是防洪物質(zhì)調(diào)運問題。 在問題一中，要建立該地區(qū)公路交通網(wǎng)的數(shù)學模型。我們考慮到高等級公路與普通公路的運輸成本的差異，通過加權(quán)，求任意兩個點之間運費每一百件最少的路線。我們采用圖論和網(wǎng)絡優(yōu)化的方法，借助Dijkstra算法，得到各庫、企業(yè)之間的最短的加權(quán)路線，即公路交通網(wǎng)（見圖一）。 然后是問題二，以及問題三的求解。首先問題三是問題二的承接，我們只需要得出題二的模型，便可以解決。再者考慮物資的合理調(diào)運方案，重點保證國家儲備庫的情況下，運用動態(tài)規(guī)劃，使得在一個較短的時間內(nèi)完成對各庫預測庫存的需要，生產(chǎn)過剩的將分別運往儲備庫1、2，具體的調(diào)運方案見（表一）。于是，20天的調(diào)運方案，得到如下的結(jié)果：倉庫名倉庫1倉庫2倉庫3倉庫4倉庫5倉庫6倉庫7倉庫8儲備庫1儲備庫220天后庫存量50060030035045030050060038402740 最后是問題四的緊急調(diào)運方案的修改。考慮被洪水沖斷的路線，我們進行重新的圖論分析，使用Dijkstra算法，得到新的公路交通網(wǎng)（見圖二），再根據(jù)第二問的解題思路，我們可以實現(xiàn)模型的修改，得到了緊急調(diào)運方案（見表三）。 同時，模型的運用還可以擴展到許多的方面，如產(chǎn)品的分配，人員指派，最短路徑、設(shè)備的合理安排以及生產(chǎn)與庫存管理等等問題。1、問題的重述我國地域遼闊，氣候多變，各種自然災害頻頻發(fā)生，特別是每年在長江、淮河、嫩江等流域經(jīng)常爆發(fā)不同程度的洪澇災害，給國家和人民財產(chǎn)帶來重大損失，防洪抗?jié)吵蔀楦骷壵囊豁椫匾ぷ鳌，F(xiàn)有某地區(qū)為做好今年的防洪抗?jié)彻ぷ?，根?jù)氣象預報及歷史經(jīng)驗，決定提前做好某種防洪抗?jié)澄镔Y的儲備。已知該地區(qū)有生產(chǎn)該物資的企業(yè)三家，大小物資倉庫八個，國家級儲備庫兩個，各庫庫存及需求情況見附件1，其分布情況見附件2。經(jīng)核算該物資的運輸成本為高等級公路2元/公里百件，普通公路1.2元/公里百件，假設(shè)各企業(yè)、物資倉庫及國家級儲備庫之間的物資可以通過公路運輸互相調(diào)運。需要求解如下的問題：（1）請根據(jù)附件2提供的信息建立該地區(qū)公路交通網(wǎng)的數(shù)學模型，盡量滿足點與點的運輸路線最短。（2）設(shè)計該物資合理的調(diào)運方案，包括調(diào)運量及調(diào)運線路，在重點保證國家級儲備庫的情況下，為給該地區(qū)有關(guān)部門做出科學決策提供依據(jù)。（3）根據(jù)你的調(diào)運方案，20天后各庫的庫存量是多少。（4）如果汛期下列路段因洪水交通中斷，能否用問題二的模型解決緊急調(diào)運的問題，如果不能，請修改模型。 中斷路段：1423，1125，2627，9312、基本的假設(shè)1、各企業(yè)、物資倉庫及國家級儲備庫之間的物資可以通過公路運輸互相調(diào)運；2、每一條公路滿足最大時的車流量，即選擇的運輸路線順利通車，不出現(xiàn)較長時間的路障以及斷路；3、所有路線均可雙向行使，即車輛往返使用同一線路；4、不考慮貨物在運輸過程中的損壞和遺失，貨物全部安全到達目的地；5、物資調(diào)運的運輸時間不計，即運輸能力足夠大；3、符號的說明 表示i路段為j等級的距離,i=1,2,.n;j取1(高等級公路）或者j取2（普通公路）； 表示該地區(qū)所有交點路段數(shù)目； 表示物資的運輸成本為高等級公路2元/公里百件，表示普通公路1.2元/公里百件（r=1,2)；4、問題一 建立公路交通網(wǎng)4.1問題的分析 根據(jù)附件2提供的信息，要求建立該地區(qū)的公路交通網(wǎng)模型，也就是通過所給的公路長度數(shù)據(jù)，加權(quán)，采取一定的方法求解出各個點與點（企業(yè)、倉庫、儲備庫三者）之間的加權(quán)最短路徑。4.2問題的假設(shè)1、以百件為基本問題出發(fā)點，即運輸物資一百件；4.3問題模型的建立與求解4.3.1模型的建立 以倉庫，企業(yè)，儲備庫任一為出發(fā)點，余下的其中一點為終點，得到加權(quán)路線的函數(shù)表達式為 其中 表示加權(quán)路線函數(shù)，m表示虛擬的0-1變量 0 不通過此路徑 m= 1 通過此路徑于是可得目標函數(shù) 表示為在所有的中取最短路徑，即k=1時，取中所有路線最短的一條。4.3.2模型的求解 圖論是針對最短路徑的一種有效的解決方法，其中比較常用的算法有Dijkstra。4.3.2.1 Dijkstra基本思想Dijkstra算法建模的基本思想如下：如果，.，.，.是某圖G從到的最短路徑，這它的子路，.一定是從到的最短路徑.4.3.2.2 Difkstra算法的步驟該算法可求得網(wǎng)絡中從某頂點到其他所有頂點的最短路徑,算法步驟如下:(1)假設(shè)網(wǎng)絡G有n個頂點,用帶權(quán)的鄰接矩陣W來表示，W(i，j）表示從頂點到的弧或邊的 權(quán)值，不存在 弧或邊的權(quán)值用（在MATLAB中為inf)表示。S為已求出的從已知始點出發(fā)的 最短路徑的終點的集合，它的初始狀態(tài)為空集。則從出發(fā)到圖上其余各頂點可能達到的最短路徑長度的初值為：D(k)=minW(i,k)|V-i;(2)選擇，使得：D(k)=minW(i,k)|V-S;就是當前求得的一條從始點出發(fā)的 最短路徑的終點。令S=Sj；（3）修改從出發(fā)到集合V-S上任一頂點可達的最短路徑長度。如果D(j）+W(j,k)D(k),則修改D(k）為：D（k）=D(j）+W(j，k)；（4）重復操作（2）（3）共n-1次，并記錄各最短路徑經(jīng)過的所有頂點。由此得到從始點到圖上其余各頂點的最短路徑是依路徑長度遞增的序列。采用Difkstra算法，求得最短路徑，在使用photoshop cs工具，修改原圖，得到了該地區(qū)的公路交通網(wǎng)圖,如下庫倉庫35企業(yè)2企業(yè)3儲備庫2倉庫3倉庫8倉庫6倉庫4倉庫1倉庫7儲備庫1企業(yè)1倉庫2倉庫5儲備庫2企業(yè)2（圖一）注：1312123高等級公路 普通公路 河流 等表示公路交匯點；30，50，28等表示公路區(qū)間距離，單位：公里，如 與 之間距離為80公里。 從圖中可以看出在兩點之間的最短距離一般的是普通公路所連接的，也就是說，在運輸成本最少的情況下，盡可能的走的是普通公路，除非遇到兩路段點間的高等級公路上的運輸成本比普通公路的少（如2740段）。同時還可以發(fā)現(xiàn)，大部分路線的出發(fā)點都是以倉庫或者企業(yè)為基點。于是構(gòu)成了以倉庫或者企業(yè)連線包裹的公路交通網(wǎng)。5、問題二 物資的調(diào)運方案 問題三 20天各庫的庫存量5.1問題的分析 通過對該地區(qū)的公路交通網(wǎng)模型的進一步理解，在重點保證國家級儲備庫的情況下，考慮各個點之間的物資互運，但運量不確定，就需要根據(jù)已經(jīng)規(guī)劃的交通網(wǎng)，保證合理運輸時的成本費用最少，也就是方案的決定與時間的長短存在一定的聯(lián)系較短時間達到預測庫存與較長時間達到是有區(qū)別的，于是就需要分時間的階段性進行建模。再者第三問承接第二問而來，所以只需要將數(shù)值代入問題二中的模型，即可求解。5.2 模型的建立5.2.1模型I5.2.1.1 符號的說明 表示第k天由i單位運往庫j的物資的量，其中i取1，2，.13.j=1，2，.，10.儲備庫1和儲備庫2分別規(guī)定為庫9和庫10. 表示k天末的庫存（取a,b,c,e,f,g,h,p,q,r,t,v分別代表企業(yè)1，2，3,倉庫18，儲備庫1，2） 表示第k天的運輸成本 表示第k天某單位運出的物資量（取a,b,c,e,f,g,h,p,q,r,t,v分別代表企業(yè)1，2，3,倉庫18，儲備庫1，2） 表示第k天某單位運進的物資量（取a,b,c,e,f,g,h,p,q,r,t,v分別代表企業(yè)1，2，3,倉庫18，儲備庫1，2）5.2.1.2目標函數(shù) 狀態(tài)轉(zhuǎn)移方程 約束條件 當k=8時，其庫1到庫10的下限改為預測庫存量。通過分析附件一，發(fā)現(xiàn)在第8天生產(chǎn)完物資后，已經(jīng)可以達到各庫的預測值總和，于是我們采用最短時間（8天）完成預測物資的調(diào)配。所以，計算得到前8天的具體調(diào)運方案如下： 調(diào)運量（百件） 調(diào)運路線 調(diào)運費用/百件1 640.0000 企1儲1 24-26-27 120 350.0000 企3庫4 34-32-31 90 20.00000 企3庫6 34-1-33-36 174 110.0000 企3庫7 34-32-39-30-29 196.8 40.00000 企3庫8 34-32-38 111.6 60.00000 庫4儲1 31-9-27 189.6 250.0000 庫4儲2 31-32-39-30 152.4 330.0000 庫5庫2 22-19-18-23 166.8 20.00000 庫5儲1 22-19-26-27 204 2 40.00000 企1儲1 24-26-27 120 270.0000 企2庫1 41-42-28 69.6 150.0000 企2儲2 41-6-4-30 177.6 20.00000 企3庫8 34-32-38 111.6 3 40.00000 企1儲1 24-26-27 1204 40.00000 企1儲1 24-26-27 120 60.00000 企2儲2 41-6-4-30 177.6 40.00000 企3庫4 34-32-31 90 5 40.00000 企1儲1 24-26-27 120 30.00000 企2儲2 41-6-4-30 177.6 20.00000 企3庫4 34-32-31 90 6 30.00000 企2儲2 41-6-4-30 177.6 7 30.00000 企2庫1 41-42-28 69.6 40.00000 企3庫8 34-32-38 111.6 8 120.0000 企1儲1 24-26-27 120 30.00000 企2儲2 41-6-4-30 177.6 20.00000 企3庫4 34-32-31 90 150.0000 庫3儲2 35-32-39-30 210 (表一) 重點保證國家級儲備庫的情況下，當k（9，20）時，生產(chǎn)的物資按照企業(yè)1、2運往儲備庫1，企業(yè)3運往儲備庫2，于是得到20天后的各庫庫存情況：倉庫名倉庫1倉庫2倉庫3倉庫4倉庫5倉庫6倉庫7倉庫8儲備庫1儲備庫220天后庫存量50060030035045030050060038402740(表二)其總的運費成本為：506928.0元。6、問題四 模型的修改6.1問題的分析 根據(jù)問題二的調(diào)運方案中的調(diào)運路線看是否經(jīng)過斷橋的地方，如果不經(jīng)過（2）的調(diào)運方案是可行的，如果經(jīng)過那么要再考慮其它的路線，我們可以在圖一的模型中進行改進，再重復（2）的步驟求解。6.2模型的建立與求解倉庫2倉庫5倉庫1倉庫3倉庫8倉庫6倉庫4倉庫7企業(yè)1企業(yè)2企業(yè)3儲備庫1儲備庫2根據(jù)第一問的解題思路，可得到修改后的公路交通網(wǎng)為（圖二） 使用圖二中的交通運輸線路，避免了沖斷的路徑，按照最短路線的思想，根據(jù)第二問的模型，可以求解，得到緊急調(diào)運前8天的具體調(diào)運方案如下： 調(diào)運路線 調(diào)運量 企業(yè)1到儲備庫1 24-20-13-27 640.0000 企業(yè)2到庫1 41-42-28 90.00000 企業(yè)2到庫7 41-42-28-29 110.0000 企業(yè)2到儲備庫1 41-6-40-27 60.00000 企業(yè)2到儲備庫2 41-42-28-29-30 130.0000 企業(yè)3到庫6 34-01-33-36 20.00000 企業(yè)3到儲備庫2 34-32-39-30 500.0000 庫3到庫4 35-32-31 120.0000 庫3到儲備庫2 35-32-39-30 30.00000 庫5到庫2 22-19-18-23 330.0000 企業(yè)1到儲備庫1 24-20-13-27 80.00000 企業(yè)2到庫1 41-42-28 60.00000 企業(yè)3到儲備庫2 34-32-39-30 40.00000 企業(yè)1到儲備庫1 24-20-13-27 40.00000 企業(yè)2到庫1 41-42-28 30.00000 企業(yè)2到庫1 41-42-28 30.00000 企業(yè)3到庫8 34-32-38 40.00000 企業(yè)1到儲備庫1 24-20-13-27 80.00000 企業(yè)2到庫1 41-42-28 30.00000 企業(yè)3到庫8 34-32-38 20.00000 企業(yè)2到庫1 41-42-28 30.00000 企業(yè)3到庫8 34-32-38 20.00000 企業(yè)1到儲備庫1 24-20-13-27 80.00000 企業(yè)2到庫1 41-42-28 30.00000 企業(yè)3到庫8 34-32-38 20.00000 庫5到儲備庫1 22-19-18-15-42-28 20.00000（表三）其總的運費成本為：460204元。7、模型的優(yōu)缺點及改進 我們假設(shè)倉庫與倉庫之間存在調(diào)運，利用動態(tài)規(guī)劃求解其它的調(diào)運路線，使得我們的調(diào)運方案具有較好的完整性，但是由于20天的數(shù)據(jù)計算，變量太多，我們簡化了，采用8天，也就是所有物資滿足各庫的預測值，企業(yè)的基本無庫存。我們考慮在調(diào)運過程中與時間無關(guān)的情況，但是在實際情況中，如果遇到緊急情況時，可能使得防洪物質(zhì)短缺或者路段被沖斷，從而被迫我們必須得改變調(diào)運路線，選擇時間為上的原則，那樣將導致運費的增加。 該模型應該做以下改進： 1、應該增加貨物調(diào)運過程中的時間因素，并且為了預防某些路段因緊急情況而不能使用，則應該設(shè)有預備方案，這樣才能做到臨危不懼，從而確保防洪工作做得更好。 2、在現(xiàn)實生活中，每一次運輸?shù)倪\輸量會有一定的限制，在某種情況還會因為運量的多少而改變運費，例如運量過少，負責運輸單位會因運輸過程中的物質(zhì)耗費而虧本，因此負責運輸單位會為確保其利益，增加本次運輸費用，故無形中就會增加單位貨物的運輸費用。所以在模型的改進中，應該考慮這個因素，從而使該模型更具有現(xiàn)實性。 3、對于路線的選擇應該增加對于該路段的交通流量作出分析。比如流量高峰期為避免堵車，換走其他路線。8、模型的推廣本文的模型為物資調(diào)配問題，它可以用到許多領(lǐng)域：1、人員指派也可以應用此模型，但還需考慮人員的分布，地區(qū)的選擇等等。2、此模型可以推廣到商品的發(fā)放問題中。但還需要考慮更多的因素，如運輸過程中商品的變質(zhì)期限、商品的保鮮費用、市場變動情況等等。9、參考文獻1李維錚等 運籌學 北京 清華大學出版社 20062張宏偉等 LINGO8.0及其在環(huán)境系統(tǒng)優(yōu)化中的應用 天津大學出版社 20053梁國業(yè) 廖健平 數(shù)學建模 冶金工業(yè)出版社 20044胡良劍 孫曉君 MATLAB數(shù)學實驗 高等教育出版社 2006附錄一：Difkstra算法程序：function S,D=minRoute(i,m,W,opt)if nargin4,opt=0;enddd=;tt=;ss=;ss(1,1)=i;V=1:m;V(i)=;dd=0;i;kk=2;mdd,ndd=size(dd);while isempty(V) tmpd,j=min(W(i,V);tmpj=V(j); for k=2:ndd tmp1,jj=min(dd(1,k)+W(dd(2,k),V); tmp2=V(jj);tt(k-1,:)=tmp1,tmp2,jj; end tmp=tmpd,tmpj,j;tt;tmp3,tmp4=min(tmp(:,1); if tmp3=tmpd ss(1:2,kk)=i;tmp(tmp4,2); else tmp5=find(ss(:,tmp4)=0);tmp6=length(tmp5); if dd(2,tmp4)=ss(tmp6,tmp4) ss(1:tmp6+1,kk)=ss(tmp5,tmp4);tmp(tmp4,2); else,ss(1:3,kk)=i;dd(2,tmp4);tmp(tmp4,2); end;end dd=dd,tmp3;tmp(tmp4,2);V(tmp(tmp4,3)=; mdd,ndd=size(dd);kk=kk+1;end;if opt=1 tmp,t=sort(dd(2,:);S=ss(:,t);D=dd(1,t);else,S=ss;D=dd(1,:);end結(jié)果輸出程序clear;w=inf*ones(42);w(1,2,34,33)=48,54,72;w(2,1,3,7,9)=48,42,60,74.4;w(3,2,36,10)=42,60,50.4;w(4,29,30,5,6)=80,84,20,36;w(5,4,6,39,40)=20,56,170,76;w(6,4,5,40,11,41)=36,56,36,64,57.6;w(7,2,10,27)=60,96,140;w(8,15,14,28)=76,72,100;w(9,2,31,40,27)=74.4,62.4,33.6,48;w(10,3,7,12)=50.4,96,62.4;w(11,6,15,25,27)=64,112,80,96;w(12,10,13)=62.4,96;w(13,12,20,27)=96,81.6,100;w(14,8,17,23)=72,112,60;w(15,8,42,18,25,11)=76 33.6 69.6 55.2 112;w(16,18,21,23)=150 69.6 78;w(17,14,23)=112 62.4;w(18,15,23,16,19,25)=69.6 54 150 26.4 60;w(19,18,22,26)=26.4 86.4 33.6;w(20,13 24 22)=81.6 60 96;w(21,16 22)=69.6 54;w(22,19 21 20)=86.4 54 96;w(23,14 17 16 18)=60 62.4 78 54;w(24,20 26)=60 36;w(25,15 18 26 11)=55.2 60 21.6 80;w(26,25 19 24 27)=21.6 33.6 36 84;w(27,9 40 11 26 13 7)=48 64 96 84 100 140;w(28,8 42 29)=100 38.4 72;w(29,28 4 30)=72 80 74.4;w(30,29 4 39)=74.4 84 18;w(31,9 32)=62.4 60;w(32,35 39 31 34 38)=117.6 74.4 60 30 81.6;w(33,1 36 37)=72 48 45.6;w(34,1 32)=54 30;w(35,39 32)=204 117.6;w(36,3 33)=60 48;w(37,33 38)=45.6 42;w(38,32 37)=81.6 42;w(39,30 32 5 35)=18 74.4 170 204;w(40,5 6 27 9)=76 36 64 33.6;w(41,6 42)=57.6 31.2;w(42,28 15 41)=38.4 33.6 31.2;s1,d1=minroute(27,42,w,1);A=s1(:, 30)B=d1(:, 30) 所得結(jié)果：A1= 28 28 28 28 28 28 28 28 28 28 28 28 42 29 42 42 42 29 29 42 42 29 42 29 15 30 41 15 41 0 30 15 41 30 41 30 18 39 6 18 6 0 39 25 0 39 6 0 23 32 40 19 40 0 32 26 0 32 40 0 0 35 9 22 9 0 38 24 0 34 27 0 0 0 31 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 36 0 0 0 0 0 0 0B1= 195.6000 356.4000 259.2000 254.4000 373.2000 72.0000 320.4000 184.8000 69.6000 268.8000 227.2000 146.4000A2= 23 23 23 23 23 23 23 23 23 23 23 18 18 18 18 18 18 18 18 18 18 1 19 19 19 19 15 19 19 15 19 19 15 26 26 22 26 42 26 26 42 26 26 42 27 27 0 27 28 27 24 41 27 27 28 9 9 0 9 29 9 0 0 9 0 29 31 31 0 2 0 31 0 0 31 0 30 32 0 0 3 0 32 0 0 32 0 0 35 0 0 36 0 38 0 0 34 0 0B2= 195.6000 486.0000 308.4000 166.8000 422.4000 267.6000 450.0000 150.0000 188.4000 398.4000 198.0000 342.0000A3= 35 35 35 35 35 35 35 35 35 35 32 32 32 32 32 32 32 32 32 32 31 31 34 39 38 31 31 34 31 39 0 9 1 30 0 9 9 0 9 30 0 27 33 29 0 27 40 0 27 0 0 26 36 0 0 26 6 0 0 0 0 19 0 0 0 24 41 0 0 0 0 22 0 0 0 0 0 0 0 0B3= 177.6000 492.0000 321.6000 284.4000 199.2000 408.0000 367.2000 147.6000 288.0000 210.0000A4= 31 31 31 31 31 31 31 31 31 9 9 32 32 9 9 32 9 32 27 2 39 38 27 40 34 27 39 26 3 30 0 26 6 0 0 30 19 36 29 0 24 41 0 0 0 22 0 0 0 0 0 0 0 0B4= 314.4000 238.8000 226.8000 141.6000 230.4000 189.6000 90.0000 110.4000 152.4000A5= 22 22 22 22 22 22 22 22 19 19 19 20 19 19 19 19 26 18 26 24 18 26 26 18 27 15 27 0 15 27 27 15 9 42 9 0 42 9 0 42 2 28 31 0 41 31 0 28 3 29 32 0 0 32 0 29 36 0 38 0 0 34 0 30B5= 428.4000 326.4000 456.0000 156.0000 247.2000 404.4000 204.0000 400.8000A6= 36 36 36 36 36 36 36 3 33 3 3 33 3 33 2 37 2 2 1 2 1 9 38 9 9 34 9 34 40 0 27 40 0 27 32 6 0 26 6 0 0 39 4 0 24 41 0 0 30 29 0 0 0 0 0 0B6= 362.0000 135.6000 344.4000 303.6000 174.0000 224.4000 296.4000A7= 29 29 29 29 29 29 30 28 28 30 4 30 39 42 42 39 6 0 32 15 41 32 40 0 38 25 0 34 27 0 0 26 0 0 0 0 0 24 0 0 0 0B7= 248.4000 256.8000 141.6000 196.8000 216.0000 74.4000A8= 38 38 38 38 38 32 32 32 32 32 31 31 34 31 39 9 9 0 9 30 27 40 0 27 0 26 6 0 0 0 24 41 0 0 0 B8= 372.0000 331.2000 111.6000 252.0000 174.0000Aa= 24 24 24 24 26 26 26 26 25 27 27 25 15 9 0 11 42 31 0 6 41 32 0 4 0 34 0 30Ba= 177.6000 320.4000 120.0000 321.6000Ab= 41 41 41 6 6 6 40 40 4 9 27 30 31 0 0 32 0 0 34 0 0 0 0 0Bb= 279.6000 157.6000 177.6000Ac= 34 34 32 32 31 39 9 30 27 0Bc=200.4000 122.4000Ak2= 27 40 6 4 30Bk2= 220附件二：問題二程序結(jié)果：Objective value: 394896.0D1 241740.0 D2 52464.00 D3 4800.000 D4 19056.00 D5 11928.00 D6 5328.000 D7 6552.000 D8 53028.00 P( 1) 0.000000 P( 2) 0.000000 P( 3) 0.000000 P( 4) 500.0000 P( 5) 600.0000 P( 6) 300.0000 P( 7) 350.0000 P( 8) 450.0000 P( 9) 300.0000 P( 10) 500.0000 P( 11) 600.0000 P( 12) 3000.000 P( 13) 2500.000 調(diào)運量 調(diào)運路線 調(diào)運費用/百件1 640.0000 企1儲1 24-26-27 120 350.0000 企3庫4 34-32-31 90 20.00000 企3庫6 34-1-33-36 174 110.0000 企3庫7 34-32-39-30-29 196.8 40.00000 企3庫8 34-32-38 111.6 60.00000 庫4儲1