蔬菜供應(yīng)方案設(shè)計

1、蔬菜供應(yīng)方案設(shè)計摘 要由于人們生活水平的發(fā)展，開始講求天然產(chǎn)品，這使蔬菜產(chǎn)品有了廣闊的市場。商業(yè)企業(yè)要求最好的銷售和利潤的最大化，于是要設(shè)定合適的蔬菜供應(yīng)方案力求利潤的最大化和市場供應(yīng)的便捷性。本文利用Floyd算法求出各蔬菜采購點到每個菜市場的最短運輸距離，然后用lingo軟件計算蔬菜調(diào)運費用及預(yù)期短缺損失最小的條用方案。最優(yōu)運輸方案為菜市場（A）運往菜市場1蔬菜數(shù)量為8000kg，運往菜市場2蔬菜數(shù)量為4000kg，運往菜市場5蔬菜數(shù)量為6000kg，運往菜市場6蔬菜數(shù)量為7000kg；城鄉(xiāng)路口（B）運往菜市場2蔬菜數(shù)量為30kg，運往菜市場3蔬菜數(shù)量為9000kg，運往菜市場4蔬菜數(shù)量為

2、8000kg；南街口（C）運往菜市場5蔬菜數(shù)量為6000kg，運往菜市場7蔬菜數(shù)量為10000kg，運往菜市場8蔬菜數(shù)量為2000kg。用于蔬菜調(diào)運及預(yù)期的短缺最小損失為10920元。根據(jù)題目要求對算法加以修改得出每個市場短缺率都小于20%的最優(yōu)調(diào)運方案，并求出了最佳的供應(yīng)改進方案。最優(yōu)運輸方案為菜市場（A）運往菜市場1蔬菜數(shù)量為8000kg，運往菜市場2蔬菜數(shù)量為800kg，運往菜市5蔬菜數(shù)量為9200kg，運往菜市6蔬菜數(shù)量為7000kg；城鄉(xiāng)路口（B）運往菜市場2蔬菜數(shù)量為6200kg，運往菜市場3蔬菜數(shù)量為7400kg，運往菜市場4蔬菜數(shù)量為6400kg；南街口（C）運往菜市場5蔬菜數(shù)

3、量為2800kg，運往菜市場7蔬菜數(shù)量為8000kg，運往菜市場8蔬菜數(shù)量為7200kg。用于蔬菜調(diào)運及預(yù)期的短缺最小損失為11128元。增加蔬菜種植面積后根據(jù)結(jié)果知增產(chǎn)的蔬菜向集散點C多供應(yīng)70公斤最經(jīng)濟合理。關(guān)鍵詞：最短路徑；floyd算法；lingo軟件；一、問題重述江平市是一個人口不到20萬人的小城市。根據(jù)該市的蔬菜種植情況，分別在菜市場（A），城鄉(xiāng)路口（B）和南街口（C）設(shè)三個收購點，再由各收購點分送到全市的8個菜市場，該市道路情況，各路段距離（單位：100m）及各收購點，菜市場到的具體位置見圖1。按常年情況，A、B、C三個收購點每天收購量分別為250，200和180（單位：100

4、kg）,各菜市場的每天需求量及發(fā)生供應(yīng)短缺時帶來的損失（元/100kg）見表1。設(shè)從收購點至各菜市場蔬菜調(diào)運費為2元/(100kg.100m)。圖1 蔬菜供應(yīng)網(wǎng)點圖表1 各蔬菜市場需求量表菜市場每天需求（100 kg）短缺損失（元/100kg）80107089058010120107081005908試為該市設(shè)計一個用于蔬菜調(diào)運及預(yù)期的短缺損失為最小的從收購點至各個菜市場的定點供應(yīng)方案；若規(guī)定各菜市場短缺量一律不超過需求量的20%，重新設(shè)計定點供應(yīng)方案；規(guī)劃增加蔬菜種植面積后增產(chǎn)的蔬菜每天應(yīng)分別向A、B、C三個采購點供應(yīng)多少最經(jīng)濟合理。二、問題分析求總的運費最低，可以先求出各采購點到菜市場的最

5、小運費，因為單位重量的運費與距離成正比。第一問可以用Floyd算法求出最短路徑即求出各個采購點都菜市場的最短運輸距離，乘以單位重量單位距離的運輸費用就是單位重量各運輸路線的費用，然后用線性方法即可解得相應(yīng)的最小的調(diào)運費及預(yù)期短缺損失。第二問規(guī)定各菜市場短缺量一律不超過需求量的20%，只需在第一問的基礎(chǔ)上加上新的設(shè)定條件，就可得到新的供應(yīng)方案。第三問建立新的線性問題進行求解。三、問題假設(shè)1、各個收購點、中轉(zhuǎn)站以及菜市場都可以做為中轉(zhuǎn)點。2、各個收購點、中轉(zhuǎn)站以及菜市場的最大容納量為700噸。3、假設(shè)運輸?shù)穆吠局惺卟藳]有任何損耗。4、假設(shè)只考慮運輸費用和短缺費用，不考慮裝卸等其他費用。5、忽略從種

6、菜地點到收購點的運輸費用。四、變量說明a1,b1,c1,d1,e1,f1,g1,h1A收購點分送到全市的8個菜市場的供應(yīng)量a2,b2,c2,d2,e2,f2,g2,h2B收購點分送到全市的8個菜市場的供應(yīng)量a3,b3,c3,d3,e3,f3,g3,h3C收購點分送到全市的8個菜市場的供應(yīng)量a,b,c,d,e,f,g,h8個菜市場的短缺損失量（100kg）五、模型建立根據(jù)問題的分析，必須得求解各采購點到菜市場的最短距離。如果求圖中最短路徑的話則有以下兩種解法：解法一：Dijkstra算法；解法二：Floyd（弗洛伊德）算法。以圖中的每個頂點作為源點，調(diào)用Dijkstra算法。Dijkstra算法

7、是從一個頂點到其余各頂點的最短路徑算法，主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法簡明，可是由于它遍歷計算的點太多了，所說效率很低，占用運算空間大。這里只需要求解圖中任意兩點之間的最短距離，所以可以使用網(wǎng)絡(luò)各點之間的矩陣計算法即Floyd算法。Floyd算法的基本思想：可以將問題分解，先找出最短的距離，然后在考慮如何找出對應(yīng)的行進路線。如何找出最短路徑呢，這里還是用到動態(tài)規(guī)劃的知識，對于任何一個城市而言，i到j(luò)的最短距離不外乎存在經(jīng)過i與j之間的k和不經(jīng)過k兩種可能，所以可以令k=1，2，3，.，n(n是城市的數(shù)目)，在檢查d(ij)與d(ik)+d(kj)

8、的值；在此d(ik)與d(kj)分別是目前為止所知道的i到k與k到j(luò)的最短距離，因此d(ik)+d(kj)就是i到j(luò)經(jīng)過k的最短距離。所以，若有d(ij)>d(ik)+d(kj)，就表示從i出發(fā)經(jīng)過k再到j(luò)的距離要比原來的i到j(luò)距離短，自然把i到j(luò)的d(ij)重寫為d(ik)+d(kj)，每當(dāng)一個k查完了，d(ij)就是目前的i到j(luò)的最短距離。重復(fù)這一過程，最后當(dāng)查完所有的k時，d(ij)里面存放的就是i到j(luò)之間的最短距離了。Floyd算法的基本步驟：定義n×n的方陣序列D-1，D0， Dn1。初始化： D-1C。D-1ij邊<i,j>的長度，表示初始的從i到j(luò)的最

9、短路徑長度，即它是從i到j(luò)的中間不經(jīng)過其他中間點的最短路徑。迭代：設(shè)Dk-1已求出，如何得到Dk（0kn-1）。Dk-1ij表示從i到j(luò)的中間點不大于k-1的最短路徑p：ij，考慮將頂點k加入路徑p得到頂點序列q：ikj，若q不是路徑，則當(dāng)前的最短路徑仍是上一步結(jié)果：Dkij= Dk1ij；否則若q的長度小于p的長度，則用q取代p作為從i到j(luò)的最短路徑。因為q的兩條子路徑ik和kj皆是中間點不大于k1的最短路徑，所以從i到j(luò)中間點不大于k的最短路徑長度為：Dkijmin Dk-1ij, Dk-1ik +Dk-1kj 。 Floyd算法實現(xiàn)：可以用三個for循環(huán)把問題搞定了，但是有一個問題需要注

10、意，那就是for循環(huán)的嵌套的順序。 for(int k=0; k<n; k+)                         for(int i=0; i<n; i+)               

11、;               for(int j=0; j<n; j+)這樣作的意義在于固定了k，把所有i到j(luò)而經(jīng)過k的距離找出來，然后象開頭所提到的那樣進行比較和重寫，因為k是在最外層的，所以會把所有的i到j(luò)都處理完后，才會移動到下一個k，這樣就不會有問題了，看來多層循環(huán)的時候，我們一定要當(dāng)心，否則很容易就弄錯了。接下來就要看一看如何找出最短路徑所行經(jīng)的城市了，這里要用到另一個矩陣P，它的定義是這樣的：p(ij)的值如果為p，就表示i到j(luò)的最短路

12、徑為i->.->p->j，也就是說p是i到j(luò)的最短行徑中的j之前的最后一個城市。P矩陣的初值為p(ij)=i。有了這個矩陣之后，要找最短路徑就輕而易舉了。對于i到j(luò)而言找出p(ij)，令為p，就知道了路徑i->.->p->j；再去找p(ip)，如果值為q，i到p的最短路徑為i->.->q->p；再去找p(iq)，如果值為r，i到q的最短路徑為i->.->r->q；所以一再反復(fù)，到了某個p(it)的值為i時，就表示i到t的最短路徑為i->t，就會的到答案了，i到j(luò)的最短行徑為i->t->.->q-&g

13、t;p->j。因為上述的算法是從終點到起點的順序找出來的，所以輸出的時候要把它倒過來。但是，如何動態(tài)的回填P矩陣的值呢？當(dāng)d(ij)>d(ik)+d(kj)時，就要讓i到j(luò)的最短路徑改為走i->.->k->.->j這一條路，但是d(kj)的值是已知的，換句話說，就是k->.->j這條路是已知的，所以k->.->j這條路上j的上一個城市(即p(kj)也是已知的，當(dāng)然，因為要改走i->.->k->.->j這一條路，j的上一個城市正好是p(kj)。所以一旦發(fā)現(xiàn)d(ij)>d(ik)+d(kj)，就把p(kj)存

14、入p(ij)。在利用Floyd算法求出最短路徑以后，對于問題一可以建立以下lingo程序下的線性規(guī)劃模型：MIN=(4*a1+8*b1+8*c1+19*d1+11*e1+6*f1+22*g1+20*h1+14*a2+7*b2+7*c2+16*d2+12*e2+16*f2+23*g2+17*h2+20*a3+19*b3+11*c3+14*d3+6*e3+15*f3+5*g3+10*h3+10*a+8*b+5*c+10*d+10*e+8*f+5*g+8*h)*2;a1+b1+c1+d1+e1+f1+g1+h1=250;a2+b2+c2+d2+e2+f2+g2+h2=200;a3+b3+c3+d3+

15、e3+f3+g3+h3=180;a+b+c+d+e+f+g+h=70;a1+a2+a3+a=80;b1+b2+b3+b=70;c1+c2+c3+c=90;d1+d2+d3+d=80;e1+e2+e3+e=120;f1+f2+f3+f=70;g1+g2+g3+g=100;h1+h2+h3+h=90;End對于問題二可以建立以下lingo程序下的線性規(guī)劃模型：MIN=(4*a1+8*b1+8*c1+19*d1+11*e1+6*f1+22*g1+20*h1+14*a2+7*b2+7*c2+16*d2+12*e2+16*f2+23*g2+17*h2+20*a3+19*b3+11*c3+14*d3+6*

16、e3+15*f3+5*g3+10*h3+10*a+8*b+5*c+10*d+10*e+8*f+5*g+8*h)*2;a1+b1+c1+d1+e1+f1+g1+h1=250;a2+b2+c2+d2+e2+f2+g2+h2=200;a3+b3+c3+d3+e3+f3+g3+h3=180;a+b+c+d+e+f+g+h=70;a1+a2+a3+a=80;b1+b2+b3+b=70;c1+c2+c3+c=90;d1+d2+d3+d=80;e1+e2+e3+e=120;f1+f2+f3+f=70;g1+g2+g3+g=100;h1+h2+h3+h=90;a<16;b<14;c<18;d

17、<16;e<24;f<14;g<20;h<18;End對于問題三可以建立以下lingo程序下的線性規(guī)劃模型：MIN=(4*a1+8*b1+8*c1+19*d1+11*e1+6*f1+22*g1+20*h1+14*a2+7*b2+7*c2+16*d2+12*e2+16*f2+23*g2+17*h2+20*a3+19*b3+11*c3+14*d3+6*e3+15*f3+5*g3+10*h3)*2;a1+a2+a3=80;b1+b2+b3=70;c1+c2+c3=90;d1+d2+d3=80;e1+e2+e3=120;f1+f2+f3=70;g1+g2+g3=100;h

18、1+h2+h3=90;a1+b1+c1+d1+e1+f1+g1+h1>250;a2+b2+c2+d2+e2+f2+g2+h2>200;a3+b3+c3+d3+e3+f3+g3+h3>180;End六、模型求解Floyd算法的MATLAB代碼如下：function D,path,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1)path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end,end,endfor k=1:n for i=1:n for j=1:n

19、 if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end,end,end,endif nargin=3 min1=D(start,terminal); m(1)=start; i=1; path1=; while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end根據(jù)題目網(wǎng)絡(luò)列出距離的矩陣，在MATLAB中編寫的程序代碼如下：a=0 4 8 8 inf

20、inf 6 inf inf 7 inf 4 inf inf inf; 4 0 7 inf inf inf 5 inf inf inf inf inf inf inf inf; 8 7 0 inf inf inf inf inf inf 3 inf inf inf 7 inf; 8 inf inf 0 inf 5 inf inf inf 5 inf 4 6 7 inf; inf inf inf inf 0 inf inf inf inf inf inf inf 5 inf inf; inf inf inf 5 inf 0 inf inf inf inf 6 7 3 inf 6; 6 5 inf

21、inf inf inf 0 inf inf inf 7 5 inf inf inf; inf inf inf inf inf inf inf 0 11 inf 10 inf inf inf 5; inf inf inf inf inf inf inf 11 0 inf inf inf 6 inf 10; 7 inf 3 5 inf inf inf inf inf 0 inf inf inf 6 inf; inf inf inf inf inf 6 7 10 inf inf 0 inf inf inf 8; 4 inf inf 4 inf 7 5 inf inf inf inf 0 inf in

22、f inf; inf inf inf 6 5 3 inf inf 6 inf inf inf 0 11 inf; inf inf 7 7 inf inf inf inf inf 6 inf inf 11 0 inf; inf inf inf inf inf 6 inf 5 10 inf 8 inf inf inf 0調(diào)用a,運行結(jié)果如下：七、結(jié)果分析1、 菜市場收購點12345678收購量A80406070250B309080200C6010020180短缺量（100 kg）70此方案通過運算結(jié)果得出用于蔬菜調(diào)運及預(yù)期的短缺損失為10920元。2、 菜市場收購點12345678收購量A8089

23、270250B627464200C288072180短缺量（100 kg）16162018此方案通過運算結(jié)果得出用于蔬菜調(diào)運及預(yù)期的短缺損失為11128元。3、 菜市場收購點12345678收購量/100kgA80406070250B309080200C6010090180由上表看出，當(dāng)A，B兩收購點收購和供應(yīng)量相等，增收的7000kg由C收購點收購，這樣下來所有的花費會最小。八、參考文獻1 張志涌，楊祖櫻. MATLAB教程M. 北京：北京航空航天大學(xué)出版社, 2011.2 運籌學(xué)教材編寫組，運籌學(xué)，清華大學(xué)出版社，2011.9、 附錄1、lingo運行結(jié)果1 Global optimal

24、solution found. Objective value: 10920.00 Infeasibilities: 0.000000 Total solver iterations: 12 Variable Value Reduced Cost A1 80.00000 0.000000 B1 40.00000 0.000000 C1 0.000000 0.000000 D1 0.000000 4.000000 E1 60.00000 0.000000 F1 70.00000 0.000000 G1 0.000000 24.00000 H1 0.000000 10.00000 A2 0.000

25、000 22.00000 B2 30.00000 0.000000 C2 90.00000 0.000000 D2 80.00000 0.000000 E2 0.000000 4.000000 F2 0.000000 22.00000 G2 0.000000 28.00000 H2 0.000000 6.000000 A3 0.000000 42.00000 B3 0.000000 32.00000 C3 0.000000 16.00000 D3 0.000000 4.000000 E3 60.00000 0.000000 F3 0.000000 28.00000 G3 100.0000 0.

26、000000 H3 20.00000 0.000000 A 0.000000 26.00000 B 0.000000 14.00000 C 0.000000 8.000000 D 0.000000 0.000000 E 0.000000 12.00000 F 0.000000 18.00000 G 0.000000 4.000000 H 70.00000 0.000000 Row Slack or Surplus Dual Price 1 10920.00 -1.000000 2 0.000000 -16.00000 3 0.000000 -14.00000 4 0.000000 -6.000

27、000 5 0.000000 -2.000000 6 0.000000 8.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 -18.00000 10 0.000000 -6.000000 11 0.000000 4.000000 12 0.000000 -4.000000 13 0.000000 -14.000002、 lingo運行結(jié)果2 Global optimal solution found. Objective value: 11128.00 Infeasibilities: 0.000000 Total solve

28、r iterations: 11 Variable Value Reduced Cost A1 80.00000 0.000000 B1 8.000000 0.000000 C1 0.000000 0.000000 D1 0.000000 4.000000 E1 92.00000 0.000000 F1 70.00000 0.000000 G1 0.000000 24.00000 H1 0.000000 10.00000 A2 0.000000 22.00000 B2 62.00000 0.000000 C2 74.00000 0.000000 D2 64.00000 0.000000 E2

29、0.000000 4.000000 F2 0.000000 22.00000 G2 0.000000 28.00000 H2 0.000000 6.000000 A3 0.000000 42.00000 B3 0.000000 32.00000 C3 0.000000 16.00000 D3 0.000000 4.000000 E3 28.00000 0.000000 F3 0.000000 28.00000 G3 80.00000 0.000000 H3 72.00000 0.000000 A 0.000000 18.00000 B 0.000000 6.000000 C 16.00000

30、0.000000 D 16.00000 0.000000 E 0.000000 4.000000 F 0.000000 10.00000 G 20.00000 0.000000 H 18.00000 0.000000 Row Slack or Surplus Dual Price 1 11128.00 -1.000000 2 0.000000 -16.00000 3 0.000000 -14.00000 4 0.000000 -6.000000 5 0.000000 -10.00000 6 0.000000 8.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 -18.00000 10 0.000000 -6.000000 11 0.000000 4.000000 12 0.000000 -4.000000 13 0.000000 -14.00000 14 16.00000 0.000000 15 14.00000 0.000000 16 2.000000 0.000000 17 0.000000 8.000000 18