蔬菜供應(yīng)方案設(shè)計(jì)摘要由于人們生活水平發(fā)展，開(kāi)始講求天然產(chǎn)品，這使蔬菜產(chǎn)品有了遼闊市場(chǎng)。商業(yè)公司規(guī)定最佳銷(xiāo)售和利潤(rùn)最大化，于是要設(shè)定適當(dāng)蔬菜供應(yīng)方案力求利潤(rùn)最大化和市場(chǎng)供應(yīng)便捷性。本文運(yùn)用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ù)量為8000kg；南街口（C）運(yùn)往菜市場(chǎng)5蔬菜數(shù)量為6000kg，運(yùn)往菜市場(chǎng)7蔬菜數(shù)量為10000kg，運(yùn)往菜市場(chǎng)8蔬菜數(shù)量為kg。用于蔬菜調(diào)運(yùn)及預(yù)期短缺最小損失為10920元。依照題目規(guī)定對(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ù)量為2800kg，運(yùn)往菜市場(chǎng)7蔬菜數(shù)量為8000kg，運(yùn)往菜市場(chǎng)8蔬菜數(shù)量為7200kg。用于蔬菜調(diào)運(yùn)及預(yù)期短缺最小損失為11128元。增長(zhǎng)蔬菜種植面積后依照成果知增產(chǎn)蔬菜向集散點(diǎn)C多供應(yīng)70公斤最經(jīng)濟(jì)合理。核心詞：最短途徑；floyd算法；lingo軟件；一、問(wèn)題重述江平市是一種人口不到20萬(wàn)人小都市。依照該市蔬菜種植狀況，分別在菜市場(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)①到⑧詳細(xì)位置見(jiàn)圖1。按常年?duì)顩r，A、B、C三個(gè)收購(gòu)點(diǎn)每天收購(gòu)量分別為250，200和180（單位：100kg）,各菜市場(chǎng)每天需求量及發(fā)生供應(yīng)短缺時(shí)帶來(lái)?yè)p失（元/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)每天需求（100kg）短缺損失（元/100kg）①8010②708③905④8010⑤12010⑥708⑦1005⑧908試為該市設(shè)計(jì)一種用于蔬菜調(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ī)劃增長(zhǎng)蔬菜種植面積后增產(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)最小運(yùn)費(fèi)，由于單位重量運(yùn)費(fèi)與距離成正比。第一問(wèn)可以用Floyd算法求出最短途徑即求出各個(gè)采購(gòu)點(diǎn)都菜市場(chǎng)最短運(yùn)送距離，乘以單位重量單位距離運(yùn)送費(fèi)用就是單位重量各運(yùn)送路線(xiàn)費(fèi)用，然后用線(xiàn)性辦法即可解得相應(yīng)最小調(diào)運(yùn)費(fèi)及預(yù)期短缺損失。第二問(wèn)規(guī)定各菜市場(chǎng)短缺量一律不超過(guò)需求量20%，只需在第一問(wèn)基本上加上新設(shè)定條件，就可得到新供應(yīng)方案。第三問(wèn)建立新線(xià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)送路途中蔬菜沒(méi)有任何損耗。4、假設(shè)只考慮運(yùn)送費(fèi)用和短缺費(fèi)用，不考慮裝卸等其她費(fèi)用。5、忽視從種菜地點(diǎn)到收購(gòu)點(diǎn)運(yùn)送費(fèi)用。四、變量闡明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）五、模型建立依照問(wèn)題分析，必要得求解各采購(gòu)點(diǎn)到菜市場(chǎng)最短距離。如果求圖中最短途徑話(huà)則有如下兩種解法：解法一：Dijkstra算法；解法二：Floyd（弗洛伊德）算法。以圖中每個(gè)頂點(diǎn)作為源點(diǎn)，調(diào)用Dijkstra算法。Dijkstra算法是從一種頂點(diǎn)到別的各頂點(diǎn)最短途徑算法，重要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法簡(jiǎn)要，可是由于它遍歷計(jì)算點(diǎn)太多了，所說(shuō)效率很低，占用運(yùn)算空間大。這里只需規(guī)定解圖中任意兩點(diǎn)之間最短距離，因此可以使用網(wǎng)絡(luò)各點(diǎn)之間矩陣計(jì)算法即Floyd算法。Floyd算法基本思想：可以將問(wèn)題分解，先找出最短距離，然后在考慮如何找出相應(yīng)行進(jìn)路線(xiàn)。如何找出最短途徑呢，這里還是用到動(dòng)態(tài)規(guī)劃知識(shí)，對(duì)于任何一種都市而言，i到j(luò)最短距離不外乎存在通過(guò)i與j之間k和不通過(guò)k兩種也許，因此可以令k=1，2，3，...，n(n是都市數(shù)目)，在檢查d(ij)與d(ik)+d(kj)值；在此d(ik)與d(kj)分別是當(dāng)前為止所懂得i到k與k到j(luò)最短距離，因而d(ik)+d(kj)就是i到j(luò)通過(guò)k最短距離。因此，若有d(ij)>d(ik)+d(kj)，就表達(dá)從i出發(fā)通過(guò)k再到j(luò)距離要比本來(lái)i到j(luò)距離短，自然把i到j(luò)d(ij)重寫(xiě)為d(ik)+d(kj)，每當(dāng)一種k查完了，d(ij)就是當(dāng)前i到j(luò)最短距離。重復(fù)這一過(guò)程，最后當(dāng)查完所有k時(shí)，d(ij)里面存儲(chǔ)就是i到j(luò)之間最短距離了。Floyd算法基本環(huán)節(jié)：定義n×n方陣序列D-1，D0，…Dn－1。初始化：D-1＝C。D-1[i][j]＝邊<i,j>長(zhǎng)度，表達(dá)初始從i到j(luò)最短途徑長(zhǎng)度，即它是從i到j(luò)中間不通過(guò)其她中間點(diǎn)最短途徑。迭代：設(shè)Dk-1已求出，如何得到Dk（0≤k≤n-1）。Dk-1[i][j]表達(dá)從i到j(luò)中間點(diǎn)不不不大于k-1最短途徑p：i…j，考慮將頂點(diǎn)k加入途徑p得到頂點(diǎn)序列q：i…k…j，若q不是途徑，則當(dāng)前最短途徑仍是上一步成果：Dk[i][j]=Dk－1[i][j]；否則若q長(zhǎng)度不大于p長(zhǎng)度，則用q取代p作為從i到j(luò)最短途徑。由于q兩條子途徑i…k和k…j皆是中間點(diǎn)不不不大于k－1最短途徑，因此從i到j(luò)中間點(diǎn)不不不大于k最短途徑長(zhǎng)度為：Dk[i][j]＝min{Dk-1[i][j]，Dk-1[i][k]+Dk-1[k][j]}。Floyd算法實(shí)現(xiàn)：可以用三個(gè)for循環(huán)把問(wèn)題搞定了，但是有一種問(wèn)題需要注意，那就是for循環(huán)嵌套順序。for(intk=0；k<n；k++)

for(inti=0；i<n；i++)

for(intj=0；j<n；j++)這樣作意義在于固定了k，把所有i到j(luò)而通過(guò)k距離找出來(lái)，然后象開(kāi)頭所提到那樣進(jìn)行比較和重寫(xiě)，由于k是在最外層，因此會(huì)把所有i到j(luò)都解決完后，才會(huì)移動(dòng)到下一種k，這樣就不會(huì)有問(wèn)題了，看來(lái)多層循環(huán)時(shí)候，咱們一定要當(dāng)心，否則很容易就弄錯(cuò)了。接下來(lái)就要看一看如何找出最短途徑所行經(jīng)都市了，這里要用到另一種矩陣P，它定義是這樣：p(ij)值如果為p，就表達(dá)i到j(luò)最短途徑為i->...->p->j，也就是說(shuō)p是i到j(luò)最短行徑中j之前最后一種都市。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í)，就表達(dá)i到t最短途徑為i->t，就會(huì)到答案了，i到j(luò)最短行徑為i->t->...->q->p->j。由于上述算法是從終點(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)值是已知，換句話(huà)說(shuō)，就是k->...->j這條路是已知，因此k->...->j這條路上j上一種都市(即p(kj))也是已知，固然，由于要改走i->...->k->...->j這一條路，j上一種都市正好是p(kj)。因此一旦發(fā)現(xiàn)d(ij)>d(ik)+d(kj)，就把p(kj)存入p(ij)。在運(yùn)用Floyd算法求出最短途徑后來(lái)，對(duì)于問(wèn)題一可以建立如下lingo程序下線(xiàn)性規(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+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程序下線(xiàn)性規(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+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<16;e<24;f<14;g<20;h<18;End對(duì)于問(wèn)題三可以建立如下lingo程序下線(xiàn)性規(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;h1+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);fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;end,end,endfork=1:nfori=1:nforj=1:nifD(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,endifnargin==3min1=D(start,terminal);m(1)=start;i=1;path1=[];whilepath(m(i),terminal)~=terminalk=i+1;m(k)=path(m(i),terminal);i=i+1;endm(i+1)=terminal;path1=m;end依照題目網(wǎng)絡(luò)列出距離矩陣，在MATLAB中編寫(xiě)程序代碼如下：a=[0488infinf6infinf7inf4infinfinf;407infinfinf5infinfinfinfinfinfinfinf;870infinfinfinfinfinf3infinfinf7inf;8infinf0inf5infinfinf5inf467inf;infinfinfinf0infinfinfinfinfinfinf5infinf;infinfinf5inf0infinfinfinf673inf6;65infinfinfinf0infinfinf75infinfinf;infinfinfinfinfinfinf011inf10infinfinf5;infinfinfinfinfinfinf110infinfinf6inf10;7inf35infinfinfinfinf0infinfinf6inf;infinfinfinfinf6710infinf0infinfinf8;4infinf4inf75infinfinfinf0infinfinf;infinfinf653infinf6infinfinf011inf;infinf77infinfinfinfinf6infinf110inf;infinfinfinfinf6inf510inf8infinfinf0]調(diào)用a,運(yùn)營(yíng)成果如下：七、成果分析1、菜市場(chǎng)收購(gòu)點(diǎn)12345678收購(gòu)量A80406070250B309080200C6010020180短缺量（100kg）70此方案通過(guò)運(yùn)算成果得出用于蔬菜調(diào)運(yùn)及預(yù)期短缺損失為10920元。2、菜市場(chǎng)收購(gòu)點(diǎn)12345678收購(gòu)量A8089270250B627464200C288072180短缺量（100kg）16162018此方案通過(guò)運(yùn)算成果得出用于蔬菜調(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é)出版社，.[2]《運(yùn)籌學(xué)》教材編寫(xiě)組，運(yùn)籌學(xué)，清華大學(xué)出版社，.附錄1、lingo運(yùn)營(yíng)成果1Globaloptimalsolutionfound.Objectivevalue：10920.00Infeasibilities：0.000000Totalsolveriterations：12VariableValueReducedCostA180.000000.000000B140.000000.000000C10.0000000.000000D10.0000004.000000E160.000000.000000F170.000000.000000G10.00000024.00000H10.00000010.00000A20.00000022.00000B230.000000.000000C290.000000.000000D280.000000.000000E20.0000004.000000F20.00000022.00000G20.00000028.00000H20.0000006.000000A30.00000042.00000B30.00000032.00000C30.00000016.00000D30.0000004.000000E360.000000.000000F30.00000028.00000G3100.00000.000000H320.000000.000000A0.00000026.00000B0.00000014.00000C0.0000008.000000D0.0000000.000000E0.00000012.00000F0.00000018.00000G0.0000004.000000H70.000000.000000RowSlackorSurplusDualPrice110920.00-1.00000020.000000-16.0000030.000000-14.0000040.000000-6.00000050.000000-2.00000060.0000008.00000070.0000000.00000080.0000000.00000090.000000-18.00000100.000000-6.000000110.0000004.000000120.000000-4.000000130.000000-14.00000lingo運(yùn)營(yíng)成果2Globaloptimalsolutionfound.Objectivevalue：11128.00Infeasibilities：0.000000Totalsolveriterations：11VariableValueReducedCostA180.000000.000000B18.0000000.000000C10.0000000.000000D10.0000004.000000E192.000000.000000F170.000000.000000G10.00000024.00000H10.00000010.00000A20.00000022.00000B262.000000.000000C274.000000.000000D264.000000.000000E20.0000004.000000F20.00000022.00000G20.00000028.00000H20.0000006.000000A30.00000042.00000B30.00000032.00000C30.00000016.00000D30.0000004.000000E328.000000.000000F30.00000028.00000G380.000000.000000H372.000000.000000A0.00000018.00000B0.0000006.000000C16.000000.000000D16.000000.000000E0.0000004.000000F0.00000010.00000G20.000000.000000H18.000000.000000RowSlackorSurplusDualPrice111128.00-1.00000020.000000-16.0000030.000000-14.0000040.000000-6.00000050.000000-10.0000060.0000008.00000070.0000000.00000080.0000000.00000090.000000-18.00000100.000000-6.000000110.0000004.000000120.000000-4.000000130.000000-14.000001416.000000.0000001514.000000.000000162.0000000.000000170.0000008.0000001824.000000.0000001914.000000.000000200.0000004.000000210.0000008.000000lingo運(yùn)營(yíng)成果3Globaloptimalsolutionfound.Objectivevalue：11200.00Infeasibilities：0.000000Totalsolveriterations：12VariableValueReducedCostA180.000000.000000B140.000000.000000C10.0000000.000000D10.0000004.000000E160.000000.000000F170.000000.000000G10.00000024.00000H10.00000010.00000A20.00000022.00000B230.000000.000000C290.000000.000000D280.000000.000000