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

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

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

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

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

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

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

7、是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法簡(jiǎn)明，可是由于它遍歷計(jì)算的點(diǎn)太多了，所說(shuō)效率很低，占用運(yùn)算空間大。這里只需要求解圖中任意兩點(diǎn)之間的最短距離，所以可以使用網(wǎng)絡(luò)各點(diǎn)之間的矩陣計(jì)算法即Floyd算法。Floyd算法的基本思想：可以將問(wèn)題分解，先找出最短的距離，然后在考慮如何找出對(duì)應(yīng)的行進(jìn)路線。如何找出最短路徑呢，這里還是用到動(dòng)態(tài)規(guī)劃的知識(shí)，對(duì)于任何一個(gè)城市而言，i到j(luò)的最短距離不外乎存在經(jīng)過(guò)i與j之間的k和不經(jīng)過(guò)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)過(guò)k的最短距離。所以，若有d(ij)>d(ik)+d(kj)，就表示從i出發(fā)經(jīng)過(guò)k再到j(luò)的距離要比原來(lái)的i到j(luò)距離短，自然把i到j(luò)的d(ij)重寫為d(ik)+d(kj)，每當(dāng)一個(gè)k查完了，d(ij)就是目前的i到j(luò)的最短距離。重復(fù)這一過(guò)程，最后當(dāng)查完所有的k時(shí)，d(ij)里面存放的就是i到j(luò)之間的最短距離了。Floyd算法的基本步驟：定義n×n的方陣序列D-1，D0， Dn1。初始化： D-1C。D-1ij邊<i,j>的長(zhǎng)度，表示初始的從i到j(luò)的最

9、短路徑長(zhǎng)度，即它是從i到j(luò)的中間不經(jīng)過(guò)其他中間點(diǎn)的最短路徑。迭代：設(shè)Dk-1已求出，如何得到Dk（0kn-1）。Dk-1ij表示從i到j(luò)的中間點(diǎn)不大于k-1的最短路徑p：ij，考慮將頂點(diǎn)k加入路徑p得到頂點(diǎn)序列q：ikj，若q不是路徑，則當(dāng)前的最短路徑仍是上一步結(jié)果：Dkij= Dk1ij；否則若q的長(zhǎng)度小于p的長(zhǎng)度，則用q取代p作為從i到j(luò)的最短路徑。因?yàn)閝的兩條子路徑ik和kj皆是中間點(diǎn)不大于k1的最短路徑，所以從i到j(luò)中間點(diǎn)不大于k的最短路徑長(zhǎng)度為：Dkijmin Dk-1ij, Dk-1ik +Dk-1kj 。 Floyd算法實(shí)現(xiàn)：可以用三個(gè)for循環(huán)把問(wèn)題搞定了，但是有一個(gè)問(wè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)過(guò)k的距離找出來(lái)，然后象開(kāi)頭所提到的那樣進(jìn)行比較和重寫，因?yàn)閗是在最外層的，所以會(huì)把所有的i到j(luò)都處理完后，才會(huì)移動(dòng)到下一個(gè)k，這樣就不會(huì)有問(wèn)題了，看來(lái)多層循環(huán)的時(shí)候，我們一定要當(dāng)心，否則很容易就弄錯(cuò)了。接下來(lái)就要看一看如何找出最短路徑所行經(jīng)的城市了，這里要用到另一個(gè)矩陣P，它的定義是這樣的：p(ij)的值如果為p，就表示i到j(luò)的最短路

12、徑為i->.->p->j，也就是說(shuō)p是i到j(luò)的最短行徑中的j之前的最后一個(gè)城市。P矩陣的初值為p(ij)=i。有了這個(gè)矩陣之后，要找最短路徑就輕而易舉了。對(duì)于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ù)，到了某個(gè)p(it)的值為i時(shí)，就表示i到t的最短路徑為i->t，就會(huì)的到答案了，i到j(luò)的最短行徑為i->t->.->q-&g

13、t;p->j。因?yàn)樯鲜龅乃惴ㄊ菑慕K點(diǎn)到起點(diǎn)的順序找出來(lái)的，所以輸出的時(shí)候要把它倒過(guò)來(lái)。但是，如何動(dòng)態(tài)的回填P矩陣的值呢？當(dāng)d(ij)>d(ik)+d(kj)時(shí)，就要讓i到j(luò)的最短路徑改為走i->.->k->.->j這一條路，但是d(kj)的值是已知的，換句話說(shuō)，就是k->.->j這條路是已知的，所以k->.->j這條路上j的上一個(gè)城市(即p(kj)也是已知的，當(dāng)然，因?yàn)橐淖遡->.->k->.->j這一條路，j的上一個(gè)城市正好是p(kj)。所以一旦發(fā)現(xiàn)d(ij)>d(ik)+d(kj)，就把p(kj)存

14、入p(ij)。在利用Floyd算法求出最短路徑以后，對(duì)于問(wèn)題一可以建立以下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對(duì)于問(wèn)題二可以建立以下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對(duì)于問(wèn)題三可以建立以下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,運(yùn)行結(jié)果如下：七、結(jié)果分析1、 菜市場(chǎng)收購(gòu)點(diǎn)12345678收購(gòu)量A80406070250B309080200C6010020180短缺量（100 kg）70此方案通過(guò)運(yùn)算結(jié)果得出用于蔬菜調(diào)運(yùn)及預(yù)期的短缺損失為10920元。2、 菜市場(chǎng)收購(gòu)點(diǎn)12345678收購(gòu)量A8089

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