物資調運問題的優(yōu)化模型

物資調運問題的優(yōu)化模型肖鳳蓮涂禮才何三才摘要：本題所說的是防洪抗?jié)澄镔|調運問題。在此問題中我們求各企業(yè)、物資倉庫及國家級儲備庫之間物資的運費每一百件最少的路線，把附件2（生產企業(yè)，物資倉庫及國家級儲備庫分布圖）的分布圖轉化為數(shù)學直觀簡圖（見模型求解中圖1），所得圖是連通圖，設為G=（V,E），各個邊的權為相連兩點每百件物資的運費。我們利用“破圈法”和“最短路”求任意企業(yè)、物資倉庫及國家級儲備庫兩兩之間及倉庫與倉庫之間的最優(yōu)路線，顯然我們建立的數(shù)學（簡單圖形）模型是可行的、合理的。得出最優(yōu)路線見表二、三、四、五。?y)?y)+￡￡(z?w)+￡￡(z?w))ijijijijijiji=1j=1mmF=Ax(將￡(xi=1j=1i=1k=b+1+心￡￡(x?y)+￡￡(z.w)))ikikikik運用Lingo軟件對我們所建立線性規(guī)劃問題進行計算。再把天數(shù)為20帶入上述線性規(guī)劃，運用Lingo運用軟件進行計算，可以得到20天后各庫的庫存量好下：倉庫名倉庫1倉庫2倉庫3倉庫4倉庫5倉庫6倉庫7倉庫8儲備庫1儲備庫220天后庫存量50060045035080030055060035502500由于汛期路段26—27交通中斷，中斷路線改為企業(yè)1-20-13-儲備庫1,企業(yè)2-6-40—儲備庫1,其他中斷路段對物資運輸?shù)穆肪€無影響。建立線性規(guī)劃，運用Lingo運用軟件求解，其結果見問題4的求解。此模型簡單易懂，容易推廣。運用了LINGO數(shù)學軟件，提高了計算的速度。解得的結果符合實際。關鍵詞：破圈法、最短路、線性規(guī)劃模型、Lingo.

、問題的重述我國地域遼闊，氣候多變，各種自然災害頻頻發(fā)生，特別是每年在長江、淮河、嫩江等流域經(jīng)常爆發(fā)不同程度的洪澇災害，給國家和人民財產帶來重大損失，防洪抗?jié)吵蔀楦骷壵囊豁椫匾ぷ鳌Ｄ车貐^(qū)為做好今年的防洪抗?jié)彻ぷ?，根?jù)氣象預報及歷史經(jīng)驗，決定提前做好某種防洪抗?jié)澄镔Y的儲備。已知該地區(qū)有生產該物資的企業(yè)三家，大小物資倉庫八個，國家級儲備庫兩個，各庫庫存及需求情況見附件1,其分布情況見附件2。經(jīng)核算該物資的運輸成本為高等級公路2元/公里?百件，普通公路1.2元/公里?百件，假設各企業(yè)、物資倉庫及國家級儲備庫之間的物資可以通過公路運輸互相調運。（1）請根據(jù)附件2提供的信息建立該地區(qū)公路交通網(wǎng)的數(shù)學模型。（2）設計該物資合理的調運方案，包括調運量及調運線路，在重點保證國家級儲備庫的情況下，為給該地區(qū)有關部門做出科學決策提供依據(jù)。（3）根據(jù)你的調運方案，20天后各庫的庫存量是多少？（4）如果汛期下列路段因洪水交通中斷，能否用問題二的模型解決緊急調運的問題，如果不能，請修改你的模型。中斷路段：14—23，11—25，26—27，9—31二、模型的假設1、物資從各企業(yè)調運到每個倉庫的運輸時間不計，即運輸能力足夠大；2、在滿足倉庫和儲備庫的庫存要求之下，我們可以任意的進行物資調運;3、調運過程無任何意外情況發(fā)生；4、企業(yè)之間物資的生產互不影響；5、企業(yè)與企業(yè)不存在運輸關系；6、倉庫與倉庫、儲備庫與儲備庫之間權值相同；7、倉庫與儲備庫之間可以相互運輸。三、符號說明（單位:百件）（單位（單位:百件）（單位:公里）（單位:百件）（單位:公里）（單位:百件）ljy:表示企業(yè)，向倉庫j運輸?shù)淖疃搪烦?；ijx:表示企業(yè)i向儲備庫左運輸?shù)呢浳锪?；iky:表示企業(yè)i向儲備庫k運輸?shù)淖疃搪烦?ikZj表示倉庫i向倉庫j運輸?shù)呢浳锪浚?/p>

w.：表示倉庫，向倉庫/?運輸?shù)淖疃搪烦?；（單?公里）知:表示倉庫，向儲備庫k運輸?shù)呢浳锪?；（單?百件）w^:表示倉庫，向儲備庫k運輸?shù)淖疃搪烦?；（單?公里）M:表示企業(yè)，現(xiàn)有的庫存量；i（單位:百件）M:表示企業(yè)泊勺最大庫存量；maxi（單位:百件）C〃以：表示儲備庫k的最大庫存量；（單位:百件）C:表示倉庫.的最大庫存量；（單位:百件）C..：表示倉庫.的最低庫存量；（單位:百件）Cmink：表示儲備庫k的最低庫存量；（單位:百件）Y：：表示倉庫.的預測庫存量；（單位:百件）Y:表示儲備庫k的預測庫存量；k（單位:百件）X：：表示倉庫.的現(xiàn)有庫存量；（單位:百件）Xk：表示儲備庫k的現(xiàn)有庫存量；（單位:百件）T:表示企業(yè)i的生產時間；i（單位:天）B：表示企業(yè)i每天的產量;（單位：百件，天）A：表示每公里運輸物資的費；（單位:元公里百件）。：表示企業(yè)的個數(shù);。：表示倉庫的個數(shù)；C：表示儲備庫的個數(shù);〃：表示倉庫的權值；0:表示儲備庫的權值;四、模型的分析和建立我們根據(jù)題目及附件1中的數(shù)據(jù)信息加以分析，把實際圖形轉化為數(shù)學圖形，再根據(jù)圖論知識，將數(shù)學圖放在圖論中，進行假設與分析，從而建立了比較優(yōu)化的數(shù)學模型。我們分析得到：合理的調運方案實際上就是在滿足倉庫、儲備庫各自需求的前提下，要求總運費最少，因此建立了一個線性規(guī)劃模型。因為高等級公路和普通公路的路程價錢不同，為了使計算過程簡單化，我們結合高等級公路和普通公路的路程價錢的比例關系將高等級公路路程轉化為普通公路路程，所以我們就避免了路程和價錢同時考慮的現(xiàn)象，從而我們就將價錢和里程的關系轉化為單一的里程問題，因此簡化了問題。所以我們需要求出企業(yè)與物資倉庫之間的最短路％，企業(yè)與國家級儲備庫之間的最短路*，物資倉庫與國家級儲備庫之間的最短路w^，物資倉庫與物資倉庫之間的最短路七，而最短路路線可以根據(jù)附件2由圖論中的“破圈法1”統(tǒng)計出來。我們的目的是在滿足倉庫、儲備庫各自的需求下，要求總運費最少，即可以轉化為轉移物資和路程的長度之積。首先我們只考慮的運輸關系為：企業(yè)與物資倉庫，企業(yè)與國家級儲備庫。建立目標函數(shù)1為：minF=Ax(匹3-y)+^工蕓3-y))ijijikiki=1j=1i=1k=b+1然后經(jīng)過分析我們考慮到了物資倉庫與國家級儲備庫還存在著運輸關系，因此我們將目標函數(shù)1做了進一步的修改，得到目標函數(shù)2：minF=Ax(p(Ef(x?y)+E嘗(z?w))+ijijijiji=1j=1i=1k=b+1q(E如*?吃)+E如(七?wik)))i=1k=b+1i=1k=b+1綜合上面的分析，最后我們得出了物資調運的線形規(guī)劃模型:目標函數(shù)：minF=Ax(p(EE(x?y)+E噠(z?w)+EE(z?w))ijijijijijiji=1j=1i=1k=b+1i=1j=1+q(EE(x?y)+EE(z?w)))ikikikik約束條件:y王x+?+xjcjijijjmaxjTOC\o"1-5"\h\zi=1i=1土嘉七心疽XkJCmaxk

i=1i=1M+BTzIZx+￡如xiiiijik、i=1j=1i=1k=9五、模型的求解我們由圖論知識可以把題中給的生產企業(yè)，物資倉庫及國家級儲備庫分布圖進行簡化可以得以下的簡圖：

結合上圖，我們要找到生產企業(yè)、物資倉庫及國家級儲備庫每兩兩之間的最短路，所以我們使用“破圈法”一一任取一個圈，從圈中去掉一條權（圖中為每兩點間的距離）最大的邊（但如果有兩條或兩條以上的邊上的權都是最大的邊，則任意的去掉其中一條）。在余下的圖中，重復這個步驟，直至得到一個不含圈的圖為止。我們求企業(yè)2到倉庫1的方法如下：由圖知：企業(yè)2到倉庫1之間的路徑有5條，此圖為連通圖，但為了求（任意兩點之間的距離）最大的邊，他們之間的最短路，因此應去掉該圖中的權由“破圈法”得到最終圖形為下圖1：（任意兩點之間的距離）最大的邊，所以由最短路的相關知識可以得到企業(yè)2到倉庫1的最短路程為：y2158，路徑為：41（企業(yè)2）—42—28（倉庫1）。同理得：y,y*，w,w^及相關路徑（見附件1:表二、表三、表四、表五）根據(jù)以上算出的數(shù)據(jù)，由題意可得首先應該重點保證國家級儲備庫；再是考慮公路區(qū)間長短及運輸貨物的費用，采用就近原則進行貨物調運。又因為各處發(fā)生洪澇災害的情況是突發(fā)的，對時間并沒有限制，有附錄表1中的數(shù)據(jù)得到各倉庫和儲備庫的現(xiàn)有庫存量都超過最底庫存量，所以假定倉庫與倉庫之間、倉庫與儲備庫之間不進行貨物的調運，各個企業(yè)之間也不會相互聯(lián)系的。那么現(xiàn)在只有企業(yè)與倉庫，企業(yè)和儲備庫才有運輸關系，因此我們根據(jù)圖論中的最短路和破圈法可以得到各個企業(yè)和倉庫、儲備庫的調運關系，如下表所示：企業(yè)i運輸目的地企業(yè)1倉庫2倉庫5儲備庫1企業(yè)2倉庫1倉庫7儲備庫1儲備庫2企業(yè)3倉庫3倉庫4倉庫6倉庫8儲備庫2由附錄中的表1可知，從倉庫1到倉庫8和兩個儲備庫的儲量來看他們現(xiàn)有的庫存都是介于最低庫存和預測庫存之間，因此我們要從企業(yè)調運物資來使得他們的庫存達到預測庫存以上。對于企業(yè)1要使得他的庫存來滿足倉庫2、倉庫5和儲備庫1的預測庫存，就必須的生產，那么企業(yè)一至少要生產多少天才可以達到倉庫2、倉庫5和儲備庫1的預測庫存呢。有（（Y2-X2）+（七-X5）+（Y9-X「）-40=18.25天，企業(yè)1至少要生產18.25天才可以滿足倉庫2、倉庫5和儲備庫1的存儲量達到預測庫存以上；同理可以得企業(yè)2要生產22天才可以滿足倉庫1、倉庫7和儲備庫2的存儲量達到預測庫存以上，企業(yè)3要生產22天才可以滿足倉庫3、倉庫4、倉庫6、倉庫8和儲備庫2的存儲量達到預測庫存以上。1、問題二的求解：有前面的模型和現(xiàn)在分析的情況可以得到一個新的模型：目標函數(shù)：￡(%-氣))乂Aj=3.4.6.8.10j=3.4.6.8.10minF=(￡￡(x.,)+￡￡(x?,)+￡1ji1j2j2jj=1.5.9j=1.5.9j￡(%-氣))乂Aj=3.4.6.8.10j=3.4.6.8.10約束條件：r￡x2xj=2^.9￡x<X+C-Tj=宇￡x>Xj=1,79,10jj￡x<X+C-Tj=1,7^10￡x.>X+j=3，￡8,10jjiij=3,4,6,8,10x>(Y—X)xij<(Cmaxj-Yk)i=1,2,3;j=1.....10企業(yè)1到倉庫2、倉庫5和儲備庫1的最短路程為：125,80，100公里；企業(yè)2到倉庫1、倉庫7、儲備庫1和儲備庫2的最短路程為：58，118，131.1,148公里；企業(yè)3到倉庫3、倉庫4、倉庫6、倉庫8和儲備庫2的最短路程為:123,75，145,93，102公里。在附錄表1中有Y,X,C,C的值T.的取值為kimaxjiI22天。把數(shù)據(jù)和目標條件和約束條件放在Lingo軟件去解：

解得最小費的最優(yōu)解為：315876最優(yōu)解為：x=330,x=0,x=1000,x=300,x=110,x=0,121519212729x=0,x=0,x=120,x=20,x=100,x=70021033343638310即：企業(yè)1向倉庫2運輸330百件，企業(yè)1向儲備庫1運輸1000百件;企業(yè)2向倉庫1運輸300百件，企業(yè)2向倉庫7運輸110百件；企業(yè)3向倉庫4運輸120百件，企業(yè)3向倉庫6運輸20百件，企業(yè)3向倉庫8運輸100百件，企業(yè)3向儲備庫2運輸700百件。2、問題三的求解：我們是規(guī)定的20天完成，那么又可以得一個目標規(guī)劃模型：

minF=我們是規(guī)定的20天完成，那么又可以得一個目標規(guī)劃模型：

minF=(￡￡(x...y)+￡￡(x..,)+￡j=1,7.9.10j=1.7.9.101jij=1.5.9j=1.5.9￡(x3J.七/XAj=3.4.6.8.10j=3.4.6.8.10約束條件：r￡xx1jjj=^.5.9￡x<X+C-T1jjiij=￡x>X2jjj=1寸,9,10￡x<X+C-T2jjiij=1,￡,10>Xx3jjj=a,》^/,］。<X+C-Tx3jjiij=3,4,6,8,10x>(Y—X)ijkix<(C-Y)ijmaxji=1,2,3;j=1企業(yè)1到倉庫2、倉庫5和儲備庫1的最短路程為：125,80，100公里；企業(yè)2到倉庫1、倉庫7、儲備庫1和儲備庫2的最短路程為：58，118，131.1,148公里；企業(yè)3到倉庫3、倉庫4、倉庫6、倉庫8和儲備庫2的最短路程為:123,75，145,93，102公里。在附錄表1中有匕,X,C.的值，T的值取20天。把數(shù)據(jù)和目標條件和約束條件放在Lingo軟件去解：那么最小費用的優(yōu)解為：302532最優(yōu)解為：

X=330,X=0,X=1000,X=300,X=110,X=550,TOC\o"1-5"\h\z121519212729\o"CurrentDocument"x=00,x=0,x=120,X=20,X=100,x=70021033343638310即：企業(yè)1向倉庫2運輸330百件，企業(yè)1向儲備庫1運輸1000百件;企業(yè)2向倉庫1運輸300百件，企業(yè)2向倉庫7運輸110百件，企業(yè)2向儲備庫1運輸550百件；企業(yè)2向儲備庫2運輸0百件；企業(yè)3向倉庫4運輸120百件，企業(yè)3向倉庫6運輸20百件，企業(yè)3向倉庫8運輸100百件，企業(yè)3向儲備庫2運輸700百件。3、問題四的求解:由于汛期路段14—23，11—25,26—27,9—31，因洪水交通中斷，26—27影響到了企業(yè)1到儲備庫1,企業(yè)2到儲備1的路線；我們把這條邊去掉，然后在用破圈法和最短路進行計算可得：企業(yè)1到儲備庫1的最短路：七1=234.6，4——20——13——27；企業(yè)2到儲備庫1的最短路：y29=131.3,41--6--40--27。現(xiàn)在根據(jù)題意可得，我們應該選者企業(yè)2到儲Zj)j=3.4.6.8.10j=3.4.6.8.10備庫1的路線即：y29=131.3,41Zj)j=3.4.6.8.10j=3.4.6.8.10minF=ZZ(x?y)+￡￡(x?y)+￡1ji1j2j2jj=1.5.j=1.5j=1,7.9.10j=1.7.9.10約束條件：r￡x2xj=25￡X<X+C-Tj=中￡x>Xj=W,1。jj￡x<X+C-Tj=1,￡10X3j-jj=3?6,8,10￡X<X+C-Tj=3,4,6,8,10x>(Y—X)Xij<(Cmaxj-Yk)i=1,2,3;j=1.....10這里的T=20，用問題三的求解方法對問題四的求解得結果為;那么最小費用的優(yōu)解為：324234最優(yōu)解為：X=400,X=200,X=0,X=300,X=110,X=550,TOC\o"1-5"\h\z121519212729\o"CurrentDocument"x=0,x=0,x=120,X=20,X=100,x=70021033343638310即：企業(yè)1向倉庫2運輸400百件，企業(yè)1向倉庫5運輸200百件；企業(yè)2向倉庫1運輸300百件，企業(yè)2向倉庫7運輸110百件，企業(yè)2向儲備庫1運輸550百件，企業(yè)2向儲備庫2運輸0百件;企業(yè)3向倉庫4運輸120百件，企業(yè)3向倉庫6運輸20百件，企業(yè)3向倉庫8運輸100百件，企業(yè)3向儲備庫2運輸700百件。六、模型的結果和分析我們在本問題的求解中沒有考慮各個倉庫之間的調運關系，也沒有考慮倉庫和儲備庫之間的調運關系，而在實際生活當中它們的關系是存在的。但在特殊的情況下有特殊的處理，災害具有突發(fā)性，不是人們所能控制的，所以我們在處理這道題的過程當中就沒有必要去考慮各個倉庫之間的調運關系、倉庫和儲備庫之間的調運關系。在運輸貨物的時候是需要時間的，然而我們在題中也沒有考慮時間的關系，因此我們還可以增加貨物調運過程中的時間因素，并且為了預防某些路段因緊急情況而不能使用，則應該設有預備方案，從而確保防洪工作做得更好。在現(xiàn)實生活中，每一次運輸?shù)倪\輸量會有一定的限制，在某種情況還會因為運量的多少而改變運費，例如運量過少，負責運輸單位會因運輸過程中的物質耗費而虧本，因此負責運輸單位會為確保其利益，增加本次運輸費用，故無形中就會增加單位貨物的運輸費用。所以在模型的改進中，應該考慮這個因素，從而使該模型更具有現(xiàn)實性七、模型的評價及推廣優(yōu)點：我們利用圖論有關知識把復雜的交通路線圖簡化為帶權圖，再根據(jù)權的大小及“破圈法”和“最短路”來判定欲求兩點的最短路徑，即為調運路線。根據(jù)實際情況（就近原則）來確定具體的調運方案，既有理論依據(jù)，又符合實際要求。缺點：我們在運算中假設倉庫與倉庫之間沒有調運，利用直觀就近原則可能忽略了其它的調運路線，使得我們的調運方案具有局限性，從而使總路費存在誤差。我們考慮在調運過程中與時間無關的情況，但是在實際情況中，如果遇到緊急情況時，可能使得防洪物質短缺或者路段被沖斷，從而被迫我們必須得改變調運路線，導致運費改變。本文是關于物資調運問題，在實際的社會當中涉及許多領域，就此模型進行推廣。此模型可以推廣到商品的發(fā)放問題中。但還需要考慮更多的因素，如運輸過程中商品的變質期限、商品的保鮮費用、市場變動情況等等。其中最短路問題是重要的最優(yōu)化問題之一，他不僅可以直接應用與解決生產實際的許多問題，如:管道鋪設、線路安排、廠區(qū)布局、設備更新、南水北調工程和西氣東輸?shù)葐栴}。參考文獻：蕭樹鐵，數(shù)學實驗，：高等教育出版社，2002,2。李大潛，中國大學生數(shù)學建模競賽，：高等教育出版社，1998,8。許國志，運籌學，：清華大學出版社，2005,6。何聰，規(guī)劃論，：四川大學出版社，2005,9。附錄附件1:庫存單位、現(xiàn)有庫存預測庫存最低庫存最大庫存產量（/天）企業(yè)1600——80040企業(yè)2360——60030企業(yè)3500——60020倉庫1200500100800—倉庫2270600200900—倉庫3450300200600—倉庫4230350100400—倉庫58004003001000—倉庫6280300200500—倉庫7390500300600—倉庫8500600400800—儲備庫12000300010004000—儲備庫21800250010003000—表1、各企業(yè)到每個倉庫的最短路最'、倉倉庫1倉庫2倉庫3倉庫4倉庫5倉庫6倉庫7倉庫816412534019280287280308企業(yè)126,25,15,42,2826,19,18,2320,27,9,3,32,3526,27,9,3126,19,2226,27,40,9,2,3,3626,27,40,6,4,2926,27,9,31,32,3858157306158206253118276企業(yè)242,2842,15,18,236,40,9,31,32,356,40,9,3142,15,18,19,226,40,9,2,3,3642,28,296,40,9,31,32,38企業(yè)3224332123753371451649332,39,30,29,2832,31,9,27,26,19,18,2332,3532,3132,31,9,27,26,19,221,33,3632,39,30,2932,38表2、各企業(yè)到每個儲備庫的最短路

企7^路^儲備庫1儲備庫2業(yè)企業(yè)1100283.326,2726,27,40,6,4,30企業(yè)2131.31486,40,276,4,30企業(yè)316710232,31,9,2732,39,30表三3、儲備庫與倉庫之間的最短路最短儲備、倉庫1心倉庫2倉庫3倉庫4倉庫5倉庫6倉庫7倉庫8由儲備庫1庫1891652409217018718021040,6,41,42,2826,19,18,239,31,32,359,3126,4,19,229,2,3,3640,6,4,299,31,32,38儲備庫21222851751273342476214529,2829,28,9,1518,2339,32,3539,32,3129,28,42,15,18,19,2239,32,34,1,33,362939,32,38表四4、倉庫與倉庫之間的最短路」最~短￥倉庫1倉庫2倉庫3倉庫4倉庫5倉庫6倉庫7倉庫8倉庫1—1632972162123116026742,15,18,2329,30,39,32,3542,41,6,40,9,3142,15,18,19,2242,41,6,40,9,2,3,362929,30,39,32,38倉庫2163—40525713935222337542,15,18,2318,19,26,27,9,31,32,3518,19,26,27,9,3118,19,2218,19,26,27,9,2,3,3618,15,42,28,2918,19,26,27,9,31,32,38倉庫3297405—14841026823716629,30,39,32,3518,19,26,27,9,31,32,3532,3132,31,9,27,26,19,2232,34,1,33,3632,39,30,2932,38倉庫4216257148—26222018911842,41,6,40,9,3118,19,26,27,9,3132,319,27,26,19,2232,34,1,33,3632,39,30,2932,38倉庫5212139410262—35727238042,15,18,18,19,2232,31,9,9,27,219,26,27,19,18,1519,26,27

19,2227,26,19,226,19,229,2,3,36,42,28,29,9,31,32,38倉庫6311352268220357—301.711342,41,6,40,9,2,3,3618,19,26,27,9,2,3,3632,34,1,33,3632,34,1,33,3619,26,27,9,2,3,363,2,9,40,6,4,2933,37,38倉庫760223237189272301.7—2072918,15,42,28,2932,39,30,2932,39,30,2919,18,15,42,28,293,2,9,40,6,4,2930,39,32,38倉庫8267375166118380113207—29,30,39,32,3818,19,26,279,31,32,3832,3832,3819,26,27,9,31,32,3833,37,3830,39,32,38表五（注：一表該倉庫與這一倉庫之間最短路不考慮）附件2：生產企業(yè)，物資倉庫及國家級儲備庫分布圖3650.K9.；2830.—-/■5830\:“"24】26401132倉庫7701^5^52jj注：高等級公路普通公路河流等表示公路交匯點；30,50,28等表示公路區(qū)間距離，單位：公里，如一I?與13之間距離為80公里。附件3程序1:min=(x12*125+x15*130+x19*100+x21*58+x27*118+x29*131.3+x210*148+x33*123+x34*75+x36*145*+x38*83+x310*102)*1.2;x12+x15+x19>=600;x12+x15+x19<=1480;x21+x27+x29+x210>=360;x21+x27+x210+x29<=1020;x33+x34+x36+x38+x310>=300;x33+x34+x36+x38+x310<=940;x12>