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

1、物資調(diào)運問題的優(yōu)化模型 肖鳳蓮 涂禮才 何三才摘 要:本題所說的是防洪抗?jié)澄镔|調(diào)運問題。在此問題中我們求各企業(yè)、物資倉庫及國家級儲備庫之間物資的運費每一百件最少的路線，把附件2（生產(chǎn)企業(yè)，物資倉庫及國家級儲備庫分布圖）的分布圖轉化為數(shù)學直觀簡圖（見模型求解中圖1），所得圖是連通圖，設為，各個邊的權為相連兩點每百件物資的運費。我們利用“破圈法”和“最短路”求任意企業(yè)、物資倉庫及國家級儲備庫兩兩之間及倉庫與倉庫之間的最優(yōu)路線，顯然我們建立的數(shù)學（簡單圖形）模型是可行的、合理的。得出最優(yōu)路線見表二、三、四、五。我們根據(jù)實際情況，在保證國家級儲備庫的情況下，采用就近原則，在此基礎上建立線性規(guī)劃模型（如

2、下）：運用Lingo軟件對我們所建立線性規(guī)劃問題進行計算。再把天數(shù)為20帶入上述線性規(guī)劃，運用Lingo運用軟件進行計算，可以得到20天后各庫的庫存量好下：倉庫名倉庫1倉庫2倉庫3倉庫4倉庫5倉庫6倉庫7倉庫8儲備庫1儲備庫220天后庫存量50060045035080030055060035502500由于汛期路段2627交通中斷，中斷路線改為企業(yè)12013儲備庫1，企業(yè)2640儲備庫1，其他中斷路段對物資運輸?shù)穆肪€無影響。建立線性規(guī)劃，運用Lingo運用軟件求解，其結果見問題4的求解。此模型簡單易懂，容易推廣。運用了LINGO數(shù)學軟件，提高了計算的速度。解得的結果符合實際。關鍵詞：破圈法、最

3、短路、線性規(guī)劃模型、Lingo.一、問題的重述我國地域遼闊，氣候多變，各種自然災害頻頻發(fā)生，特別是每年在長江、淮河、嫩江等流域經(jīng)常爆發(fā)不同程度的洪澇災害，給國家和人民財產(chǎn)帶來重大損失，防洪抗?jié)吵蔀楦骷壵囊豁椫匾ぷ?。某地區(qū)為做好今年的防洪抗?jié)彻ぷ?，根?jù)氣象預報及歷史經(jīng)驗，決定提前做好某種防洪抗?jié)澄镔Y的儲備。已知該地區(qū)有生產(chǎn)該物資的企業(yè)三家，大小物資倉庫八個，國家級儲備庫兩個，各庫庫存及需求情況見附件1，其分布情況見附件2。經(jīng)核算該物資的運輸成本為高等級公路2元/公里百件，普通公路1.2元/公里百件，假設各企業(yè)、物資倉庫及國家級儲備庫之間的物資可以通過公路運輸互相調(diào)運。（1）請根據(jù)附件2提供

4、的信息建立該地區(qū)公路交通網(wǎng)的數(shù)學模型。（2）設計該物資合理的調(diào)運方案，包括調(diào)運量及調(diào)運線路，在重點保證國家級儲備庫的情況下，為給該地區(qū)有關部門做出科學決策提供依據(jù)。（3）根據(jù)你的調(diào)運方案，20天后各庫的庫存量是多少？（4）如果汛期下列路段因洪水交通中斷，能否用問題二的模型解決緊急調(diào)運的問題，如果不能，請修改你的模型。中斷路段： 1423，1125，2627，931 二、模型的假設1、 物資從各企業(yè)調(diào)運到每個倉庫的運輸時間不計，即運輸能力足夠大；2、 在滿足倉庫和儲備庫的庫存要求之下，我們可以任意的進行物資調(diào)運；3、 調(diào)運過程無任何意外情況發(fā)生；4、 企業(yè)之間物資的生產(chǎn)互不影響；5、 企業(yè)與企業(yè)

5、不存在運輸關系；6、 倉庫與倉庫、儲備庫與儲備庫之間權值相同；7、 倉庫與儲備庫之間可以相互運輸。三、符號說明四、模型的分析和建立我們根據(jù)題目及附件1中的數(shù)據(jù)信息加以分析，把實際圖形轉化為數(shù)學圖形，再根據(jù)圖論知識，將數(shù)學圖放在圖論中，進行假設與分析，從而建立了比較優(yōu)化的數(shù)學模型。我們分析得到：合理的調(diào)運方案實際上就是在滿足倉庫、儲備庫各自需求的前提下，要求總運費最少，因此建立了一個線性規(guī)劃模型。因為高等級公路和普通公路的路程價錢不同，為了使計算過程簡單化，我們結合高等級公路和普通公路的路程價錢的比例關系將高等級公路路程轉化為普通公路路程，所以我們就避免了路程和價錢同時考慮的現(xiàn)象，從而我們就將價

6、錢和里程的關系轉化為單一的里程問題，因此簡化了問題。所以我們需要求出企業(yè)與物資倉庫之間的最短路，企業(yè)與國家級儲備庫之間的最短路，物資倉庫與國家級儲備庫之間的最短路，物資倉庫與物資倉庫之間的最短路，而最短路路線可以根據(jù)附件2由圖論中的“破圈法1”統(tǒng)計出來。我們的目的是在滿足倉庫、儲備庫各自的需求下，要求總運費最少，即可以轉化為轉移物資和路程的長度之積。首先我們只考慮的運輸關系為：企業(yè)與物資倉庫，企業(yè)與國家級儲備庫。建立目標函數(shù)1為： 然后經(jīng)過分析我們考慮到了物資倉庫與國家級儲備庫還存在著運輸關系，因此我們將目標函數(shù)1做了進一步的修改，得到目標函數(shù)2：綜合上面的分析，最后我們得出了物資調(diào)運的線形規(guī)

7、劃模型：目標函數(shù)：約束條件：五、模型的求解 我們由圖論知識可以把題中給的生產(chǎn)企業(yè)，物資倉庫及國家級儲備庫分布圖進行簡化可以得以下的簡圖： 圖1 結合上圖，我們要找到生產(chǎn)企業(yè)、物資倉庫及國家級儲備庫每兩兩之間的最短路，所以我們使用“破圈法”任取一個圈，從圈中去掉一條權（圖中為每兩點間的距離）最大的邊（但如果有兩條或兩條以上的邊上的權都是最大的邊，則任意的去掉其中一條）。在余下的圖中，重復這個步驟，直至得到一個不含圈的圖為止。我們求企業(yè)2到倉庫1的方法如下：由圖知：企業(yè)2到倉庫1之間的路徑有5條，此圖為連通圖，但為了求他們之間的最短路，因此應去掉該圖中的權（任意兩點之間的距離）最大的邊，由“破圈法

8、”得到最終圖形為下圖1：所以由最短路的相關知識可以得到企業(yè)2到倉庫1的最短路程為：， 路徑為：41（企業(yè)2）4228 （倉庫1）。同理得：及相關路徑（見附件1：表二、表三、表四、表五）根據(jù)以上算出的數(shù)據(jù)，由題意可得首先應該重點保證國家級儲備庫；再是考慮公路區(qū)間長短及運輸貨物的費用，采用就近原則進行貨物調(diào)運。又因為各處發(fā)生洪澇災害的情況是突發(fā)的，對時間并沒有限制，有附錄表1中的數(shù)據(jù)得到各倉庫和儲備庫的現(xiàn)有庫存量都超過最底庫存量，所以假定倉庫與倉庫之間、倉庫與儲備庫之間不進行貨物的調(diào)運，各個企業(yè)之間也不會相互聯(lián)系的。那么現(xiàn)在只有企業(yè)與倉庫，企業(yè)和儲備庫才有運輸關系，因此我們根據(jù)圖論中的最短路和破圈

9、法可以得到各個企業(yè)和倉庫、儲備庫的調(diào)運關系，如下表所示：企業(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è)調(diào)運物資來使得他們的庫存達到預測庫存以上。對于企業(yè)1要使得他的庫存來滿足倉庫2、倉庫5和儲備庫1的預測庫存，就必須的生產(chǎn)，那么企業(yè)一至少要生產(chǎn)多少天才可以達到倉庫2、倉庫5和儲備庫1的預測庫存呢。 有天，企業(yè)1至少要生產(chǎn)18.25天才可以滿足倉庫2、倉庫5和儲備庫1的存儲量達到預測庫存以上；

10、同理可以得企業(yè)2要生產(chǎn)22天才可以滿足倉庫1、倉庫7和儲備庫2的存儲量達到預測庫存以上，企業(yè)3要生產(chǎn)22天才可以滿足倉庫3、倉庫4、倉庫6、倉庫8和儲備庫2的存儲量達到預測庫存以上。1、問題二的求解：有前面的模型和現(xiàn)在分析的情況可以得到一個新的模型：目標函數(shù)：約束條件：企業(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中有的值的取值為22天。把數(shù)據(jù)和目標條件和約束條件放

11、在Lingo軟件去解：解得最小費的最優(yōu)解為：315876最優(yōu)解為： 即：企業(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ī)劃模型：約束條件：企業(yè)1到倉庫2、倉庫5和儲備庫1的最短路程為：125，80，100公里；企業(yè)2到倉庫1、倉庫7、儲備庫1和儲備庫2的最短路程為：58，118，131.1，148公里；企業(yè)3到倉庫3、倉庫4、倉庫6、倉庫

12、8和儲備庫2的最短路程為：123，75，145，93，102公里。在附錄表1中有的值，T的值取20天。把數(shù)據(jù)和目標條件和約束條件放在Lingo軟件去解：那么最小費用的優(yōu)解為：302532最優(yōu)解為：即：企業(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、問題四的求解：由于汛期路段1423，1125，2627，931，因洪水交通中斷，2627影響

13、到了企業(yè)1到儲備庫1，企業(yè)2到儲備1的路線；我們把這條邊去掉，然后在用破圈法和最短路進行計算可得：企業(yè)1到儲備庫1的最短路：，4201327；企業(yè)2到儲備庫1的最短路：?，F(xiàn)在根據(jù)題意可得，我們應該選者企業(yè)2到儲備庫1的路線即：，然后對我們先前的模型的數(shù)據(jù)進行改變可以的：約束條件：這里的T=20，用問題三的求解方法對問題四的求解得結果為；那么最小費用的優(yōu)解為：324234最優(yōu)解為：即：企業(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è)

14、3向倉庫6運輸20百件，企業(yè)3向倉庫8運輸100百件，企業(yè)3向儲備庫2運輸700百件。六、模型的結果和分析 我們在本問題的求解中沒有考慮各個倉庫之間的調(diào)運關系，也沒有考慮倉庫和儲備庫之間的調(diào)運關系，而在實際生活當中它們的關系是存在的。但在特殊的情況下有特殊的處理，災害具有突發(fā)性，不是人們所能控制的，所以我們在處理這道題的過程當中就沒有必要去考慮各個倉庫之間的調(diào)運關系、倉庫和儲備庫之間的調(diào)運關系。在運輸貨物的時候是需要時間的，然而我們在題中也沒有考慮時間的關系，因此我們還可以增加貨物調(diào)運過程中的時間因素，并且為了預防某些路段因緊急情況而不能使用，則應該設有預備方案，從而確保防洪工作做得更好。在現(xiàn)

15、實生活中，每一次運輸?shù)倪\輸量會有一定的限制，在某種情況還會因為運量的多少而改變運費，例如運量過少，負責運輸單位會因運輸過程中的物質耗費而虧本，因此負責運輸單位會為確保其利益，增加本次運輸費用，故無形中就會增加單位貨物的運輸費用。所以在模型的改進中，應該考慮這個因素，從而使該模型更具有現(xiàn)實性七、模型的評價及推廣優(yōu)點：我們利用圖論有關知識把復雜的交通路線圖簡化為帶權圖，再根據(jù)權的大小及“破圈法”和“最短路”來判定欲求兩點的最短路徑，即為調(diào)運路線。根據(jù)實際情況（就近原則）來確定具體的調(diào)運方案，既有理論依據(jù)，又符合實際要求。缺點：我們在運算中假設倉庫與倉庫之間沒有調(diào)運，利用直觀就近原則可能忽略了其它的

16、調(diào)運路線，使得我們的調(diào)運方案具有局限性，從而使總路費存在誤差。我們考慮在調(diào)運過程中與時間無關的情況，但是在實際情況中，如果遇到緊急情況時，可能使得防洪物質短缺或者路段被沖斷，從而被迫我們必須得改變調(diào)運路線，導致運費改變。 本文是關于物資調(diào)運問題，在實際的社會當中涉及許多領域，就此模型進行推廣。此模型可以推廣到商品的發(fā)放問題中。但還需要考慮更多的因素，如運輸過程中商品的變質期限、商品的保鮮費用、市場變動情況等等。其中最短路問題是重要的最優(yōu)化問題之一，他不僅可以直接應用與解決生產(chǎn)實際的許多問題，如：管道鋪設、線路安排、廠區(qū)布局、設備更新、南水北調(diào)工程和西氣東輸?shù)葐栴}。參考文獻：1 蕭樹鐵，數(shù)學實驗

17、，北京：高等教育出版社，2002，2。2 李大潛，中國大學生數(shù)學建模競賽，北京：高等教育出版社，1998，8。3 許國志，運籌學，北京：清華大學出版社，2005，6。4 何聰， 規(guī)劃論，成都：四川大學出版社，2005，9。附錄附件1：庫存單位現(xiàn)有庫存預測庫存最低庫存最大庫存產(chǎn)量（/天）企業(yè)160080040企業(yè)236060030企業(yè)350060020倉庫1200500100800倉庫2270600200900倉庫3450300200600倉庫4230350100400倉庫58004003001000倉庫6280300200500倉庫7390500300600倉庫8500600400800儲備庫

18、12000300010004000儲備庫21800250010003000表 一1、各企業(yè)到每個倉庫的最短路倉庫最短路企業(yè)倉庫1倉庫2倉庫3倉庫4倉庫5倉庫6倉庫7倉庫8企業(yè)11641253401928028728030826,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,38企業(yè)25815730615820625311827642,2842,15,18,236,40,9,31,32,356,40,9,3142,15,18,19,226,4

19、0,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è)到每個儲備庫的最短路儲備庫最短路企業(yè)儲備庫1儲備庫2企業(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

20、倉庫5倉庫6倉庫7倉庫8儲備庫11891652409217018718021040,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倉庫11632972162123116026742,15,1

21、8,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倉庫216340525713935222337542,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倉庫329740514841026823716629,30,39,32,3518,19,26,27,9,31,32,3532,3132,31,9,27,26,19

22、,2232,34,1,33,3632,39,30,2932,38倉庫421625714826222018911842,41,6,40,9,3118,19,26,27,9,3132,319,27,26,19,2232,34,1,33,3632,39,30,2932,38倉庫521213941026235727238042,15,18,19,2218,19,2232,31,9,27,26,19,229,27,26,19,2219,26,27,9,2,3,3619,18,15,42,28,2919,26,27,9,31,32,38倉庫6311352268220357301.711342,41,6,4

23、0,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.72072918,15,42,28,2932,39,30,2932,39,30,2919,18,15,42,28,293,2,9,40,6,4,2930,39,32,38倉庫826737516611838011320729,30,39,32,3818,19,26,279,31,32,3832,3832,3819,26,27,9,31,32,3833,37,3830,39,32,38表 五(注： 表該倉庫與這一倉庫之間最短路不考慮)附件2：生產(chǎn)企業(yè)，物資倉庫及國家級儲備庫分布圖企業(yè)1倉庫5企業(yè)2企業(yè)3倉庫2倉庫4備庫1儲庫2倉庫3倉庫1倉庫6倉庫7倉庫8756552584572804522503028301868705080784048703240283038323010485