光明市的菜籃子工程

1、PAGE PAGE - 12 -數(shù)學建模論文 題 目：光明市的菜籃子工程姓 名： 時 間: 2012 / 6 / 26 光明市的菜籃子工程摘要 在各種假設的基礎上，建立了解決蔬菜分配和運輸問題的線性規(guī)劃模型。由于變量較少，約束條件也為線性，目標函數(shù)也為一次，所以利用Lingo軟件，對數(shù)據(jù)進行預處理和模型最優(yōu)化求解，可以很快得求出最優(yōu)化的分配和運輸方案。 另外，我們在原始模型的基礎上我們對模型進行了部分約束條件的修改與改進，并分析了其對總費用和訂購運輸計劃的影響。在論文中，還對所建立的模型的優(yōu)缺點和需要改進的地方進行了討論，并進行了相關的經(jīng)濟效益和社會效益的分析。關鍵詞：運輸問題 弗洛伊德算法

2、線性規(guī)劃 1問題的重述光明市共有三個蔬菜收購點，要在每天五點前，將三個收購點的蔬菜送往本市的八個菜市場，在已知常年情況下，A、B、C三個采購點每天的采購量和各菜市場的每天需求量及發(fā)生供應短缺時帶來的損失，且假設從收購點至各菜市場蔬菜調(diào)運費用為1元，解決如下情況：要求為該市設計一個從各收購點至各菜市場的定點供應方案，使用于蔬菜調(diào)運及預期的短期損失最小。若規(guī)定各菜市場短缺量一律不超過需求量的20%，重新設計定點供應方案。為滿足城市居民的蔬菜供應，光明市的領導規(guī)劃增加蔬菜種植面積，試問增加的蔬菜每天應分別向A、B、C三個采購點個供應多少最經(jīng)濟合理。2問題的分析3個收購點向8菜市場調(diào)運蔬菜，要求用于蔬

3、菜調(diào)運的運輸費用及預期的短期損失最小，結合已知3個收購點每天收購量分別為200kg、170kg、160kg，可以利用線性規(guī)劃的最決策問題進行思考。根據(jù)已知求出運輸費用和預期短期損失最少的目標函數(shù)，以及相應的約束條件。對于第二問和第三問都是在第一問線性規(guī)劃目標函數(shù)的基礎上對約束條件進行一定的改變，而求解的新的優(yōu)化問題。3模型的假設與符號的說明3.1 模型的假設（1）假設蔬菜在運送過程中不存在損壞。（2）假設不存在道路不通，無法運送的情況。（3） 假設各蔬菜市場的蔬菜只來源于A、B、C3個收購站，不包含外來送貨狀況。（4） 假設該市經(jīng)濟保持相對穩(wěn)定，3個收購站每年的收購量相對穩(wěn)定。（5） 假設蔬菜

4、價格一致，不存在惡意競爭。（6） 假設各收購站可作為中轉(zhuǎn)站。（7） 不計算該市的新建市場，只考慮該題固定的8個菜市場。（8） 不考慮該市的新增路段，只在題中路段進行選擇。3.2符號說明xij：第i個收購點向j市場供給的數(shù)量cij：第i個收購點向j 市場供給的單位運費ai：第i個收購點供應量bj：第j個市場需求量dj:第j個市場因供給量小于需求量的單位短缺損失4.問題分析、模型建立及求解4.1模型(a)的分析及建模4.1.1 模型分析目標函數(shù)總費用Z,包括兩項: 蔬菜調(diào)運費Q，各市場供給量小于需求量的短缺損失PZ=P+Q其中:P= Q= 約束條件為 = 1 * GB3 3個收購點的蔬菜全部供給給

5、8個市場 （i=1，2，3） = 2 * GB3 3個收購點分別向每個市場供應的總量不超過每個市場的需求量（j=1,8）變量非負性限制（i=1，2，3，j=1,8）從而得出問題(a)的數(shù)學模型如下： min Z=+ s.t. （i=1，2，3） （j=1,8） （i=1，2，3，j=1,8）4.1.2模型求解(一) 為了求解模型，必須求出系數(shù)（），其中每一表示第i個收購點向j市場供給單位量蔬菜的運費，但因為從收購點至各菜市場單位量蔬菜單位路程的調(diào)運費用為1元/（100kg*100m），而蔬菜的單位量為100kg，單位距離為100m ，則可求出第i個收購點到第j市場每單位蔬菜的單位距離運費為1元

6、/（100m *100kg）*100m *100kg=1元。因而 在數(shù)值上等于第i個收購點到第j市場的距離值，從而等價于一個求最短路的問題，（1）標志距離：將圖中15個點標號，分別為A,B,C,o,p,q,r,1,2,3,4,5,6,7,8.并由此構成15*15的權矩陣W15*15，其中Wij表示第I個點到第j個點的距離，若第I個點和第j個點不相鄰，則wij=。（2）列出矩陣：對得到的W，使用弗洛依德算法，得到最短距離，也就是單位最小費用矩陣。從中抽取出第i（i=1,2,3）行和第j(j=8,.,15)列的子矩陣W，其中的值wij即對應為第i個收購站到第j個市場的單位最小費用。表1 單位最小運

7、費12345678A488191162220B14771612162317C20191114615510(3) 結合上述分析，根據(jù)建立的模型，利用LINGO軟件，輸入目標函數(shù)和約束條件，求解模型的最優(yōu)解，解如表2。表2 各收購點向市場供應量分配表12345678A75000705500B06080300000C00003009040 總計費用：4610（元）已知各市場每單位短缺損失（表3）表3 各市場每單位短缺損失（元/100kg） 市場1234 5 678短缺損失10851010858(二) 比較表1中每個收購點到市場的單位蔬菜的運價cij和表3 每個市場的單位蔬菜短缺的損失價格dj，若ci

8、jdj,即運費大于短缺損失，則不運，否則增加宏觀經(jīng)濟的損失。由此，我們得出表512345678A可運運或不運可運B可運C可運運或不運而表2 中B3 ,B4,A5,C8的路線上發(fā)生了運輸往來，不利于整個宏觀經(jīng)濟值增加。 (1)考慮到如C收購點到8市場的單位量蔬菜的運輸費用大于8市場單位量蔬菜的短缺損失等情況，模型2修改模型1的 = 6 * GB3 假設，為允許3個收購點分別向每個市場供應的總量可超過每個市場的需求量。即改變約束條件2，此時模型為min Z=+s.t. （i=1，2，3） （j=1,8） （i=1，2，3，j=1,8）根據(jù)建立的上述模型，利用LINGO軟件，輸入目標函數(shù)和約束條件，

9、求解模型（b）的最優(yōu)解。表6 各收購點向市場供應量分配表 1234567806080300000C00001000600 總計費用：4460（元）比較表2和表6，從第二個模型所求得分配方式中可以看到A5,C8兩條不合理的運輸路線已被取消，同時最終的運費也有所下降，下降了150元。(2)仍然考慮到如C收購點到8市場的單位量蔬菜的運輸費用大于8市場單位量蔬菜的短缺損失等情況，在模型1的基礎上，對模型1 的 = 6 * GB3 假設做出了另一種修改，為允許每個收購點的蔬菜可以只運部分。即改變約束條件1，可得模型min Z=+s.t. （i=1，2，3）（j=1,7） （i=

10、1，2，3，j=1,7） 根據(jù)建立的模型，利用LINGO軟件，輸入目標函數(shù)和約束條件，求解模型的最優(yōu)解。表7 各收購點向市場供應量分配表12345678A7500005500 B060000000 C0000100000 總計費用：3840（元）(3) 比較表2與表7，從第三個模型所求得分配方式中可以看到B3,B4,A5,C8四條不合理路線都被取消，同時總運費減少了545元。(三)在市場經(jīng)濟下，模型c，隨著市場的調(diào)節(jié)，最終A只愿供應12000千克，B只愿供應6000千克，C只愿供應10000千克，大大小于各收購點常年的每天收購量20000千克，17000千克，16000千克。4.2模型(b)的

11、分析及建模4.2.1模型分析按題中問題(b)規(guī)定各菜市場短缺量一律不超過需求量的20%的條件，我們對需求量的約束條件進行了修改。min Z=+ s.t. （i=1，2，3） （j=1,8） （j=1,8） （i=1，2，3，j=1,8）4.2.2模型求解(1)根據(jù)建立的模型，利用LINGO軟件，輸入目標函數(shù)和約束條件，求解模型的最優(yōu)解。表8 各收購點向市場供應量分配表12345678A751000605500B05064560000C00002407264 總計費用：4806（元）(2)比較表2和表8，主要是對3，4，7，8市場的供應量作出了調(diào)整。其中的主要原因是對于3，4，7，8市場，從收購

12、點到其的單位量蔬菜的運輸費用大于該市場單位量蔬菜的短缺損失，所以，當加入各菜市場短缺量一律不超過需求量的20%的約束條件后，為了保證4，8市場的需求，在考慮到3，7市場相對其他市場運輸代價較高的情況下，在這四個市場之間做出平衡供給量的調(diào)整。4.3模型(c)的分析及建模4.3.1模型分析為滿足城市居民的蔬菜供應，光明市的領導規(guī)劃增加蔬菜種植面積，即模型為min Z=+s.t. （i=1，2，3） （j=1,8） （i=1，2，3，j=1,8） t0（i=1，2，3）4.3.2模型求解 (1)根據(jù)建立的模型，利用LINGO軟件，輸入目標函數(shù)和約束條件，求解模型的最優(yōu)解。表9 各收購點向市場供應量分

13、配表12345678A754000305500B02080700000C00007009080 總計費用：4770（元）各收購點增加的蔬菜收購量如下表：ABCt0080(2)比較表2和表9，對于4，8市場做了比較大的調(diào)整，主要是因為從收購點到其的單位量蔬菜的運輸費用大大高于這兩個市場單位量蔬菜的短缺損失，供應這兩個市場并不能獲得收益，反而會受到較大損失。在市場機制的主導下，無法滿足這兩個市場的需求量。但是，光明市的領導為保證城市居民的蔬菜供應，規(guī)劃增加蔬菜種植面積，提高收購點的蔬菜收購量，在承擔一定損失的情況下，滿足了這兩個市場的蔬菜需求。5 模型評價(1)以上各模型的優(yōu)點： = 1 * GB

14、3 所建立的模型簡潔明了，便于使用數(shù)學工具。如Lingo,降低了編程求解的難度，縮短了運行時間，提高了工作效率。對同一個問題從不同的角度進行了考慮，建立了多個模型，并進行了結果的比較分析，既結合題目要求，又考慮了實際意義。 = 3 * GB3 從社會效益和經(jīng)濟效益對問題進行了分析，也表現(xiàn)出現(xiàn)實生活中政府在尋求兩者之間的平衡中做出的努力。(2)不足之處：以上模型均只考慮在降低運輸費用和短缺費用的目標下的優(yōu)化方案，并未涉及到市場上蔬菜供過于求和收購點蔬菜積壓而導致的存儲費用等，而使所建立的模型不能很好地符合實際情況,還有待改進。參考文獻1姜啟源，謝金星，葉俊 .數(shù)學建模M,北京：高等教育出版社，2

15、004.2謝金星 ,薛毅.優(yōu)化建模與LINDO/LINGO軟件M，北京：清華大學出版社，2005.7.3胡運權.運籌學基礎及應用M,北京:高等教育出版社,2008.6.附錄部分1.數(shù)據(jù)預處理部分：求最小費用的LINGO的文件如下：model:SETS:NODES/A,B,C,o,p,q,r,1,2,3,4,5,6,7,8/;ROADS(NODES, NODES)/A,o A,p A,1 A,2 A,3 A,6 B,o B,r B,2 B,3 C,q C,5 C,7 C,8 o,2 o,3 p,3 p,5 p,6 q,5 q,6 q,7 r,3 r,4 r,5 r,8 1,2 1,6 3,5 7

16、,8/:W0;LINK(NODES, NODES): W, D;NNN(Nodes,nodes,nodes):U; ENDSETS DATA:BIG=1000;W0=7 4 4 8 8 6 6 11 7 7 8 6 5 10 3 5 4 7 5 6 7 10 6 5 3 6 7 5 5 11;TEXT(FinalCost.txt)=writefor(nodes(i)|i#le#3: writefor(nodes(j)|j#ge#8 #and# j#le#15: format(D(i,j),5.0f) );ENDDATACALC:FOR(LINK(i,j)|IN(ROADS,i,j): W(i,

17、j) = W0(i, j); W(j,i) = W0(i,j); ); FOR(LINK(i,j)|i#eq#j: W(i,j) = 0 ); FOR(LINK(i,j)|i#ne#j #and# #not#IN(ROADS,i,j) #and# #not#IN(ROADS,j,i): W(i,j) = BIG;W(j,i) = BIG; ); FOR(NNN(i,j,k)|k#eq#1: U(i,j,k) = W(i,j) );For(nodes(k)|k#lt#size(nodes): FOR(LINK(i,j): U(i,j,k+1) = if(U(i,j,k) #le# U(i,k,k

18、)+U(k,j,k), U(i,j,k), U(i,k,k)+U(k,j,k);FOR(NNN(i,j,k)|k#eq#size(nodes): D(i,j) = if(U(i,j,k) #le# U(i,k,k)+U(k,j,k), U(i,j,k), U(i,k,k)+U(k,j,k) ); ENDCALCEnd求得最短路部分結果如下：Variable ValueD( A, B) 13.00000D( A, C) 17.00000D( A, O) 7.000000D( A, P) 4.000000D( A, Q) 13.00000D( A, R) 14.00000D( A, 1) 4.000000D( A, 2) 8.000000D( A, 3) 8.000000D( A, 4) 19.00000D( A, 5) 11.00000D( A, 6) 6.000000D( A, 7) 22.00000D( A, 8) 20.000002模型主體LINGO程序如下（只取其中一個，其他類同）：MODEL:SETS:SUPPLY/A,B,C/:S;NEED/1.8/:B,P;LINK(Supply, need): C, X;ENDSETSDATA:S=200 170 160;B=75 60 80 70 100 55 90 80;P=10 8 5 10 10 8 5 8;C