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

1、遼寧益海&里地爾樂斯淀粉科技有限公司蔬菜供應(yīng)方案設(shè)計(jì)摘要由于人們生活水平的發(fā)展，開始講求天然產(chǎn)品，這使蔬菜產(chǎn)品有了廣闊的市場。商 業(yè)企業(yè)要求最好的銷售和利潤的最大化，于是要設(shè)定合適的蔬菜供應(yīng)方案力求利潤的最 大化和市場供應(yīng)的便捷性。本文利用尹算法求出各蔬菜采購點(diǎn)到每個(gè)菜市場的最短運(yùn)輸距離，然后用 lingo軟件計(jì)算蔬菜調(diào)運(yùn)費(fèi)用及預(yù)期短缺損失最小的條用方案。最優(yōu)運(yùn)輸方案為菜市場 （久）運(yùn)往菜市場1蔬菜數(shù)量為8000如 運(yùn)往菜市場2蔬菜數(shù)量為4000任g,運(yùn)往菜 市場5蔬菜數(shù)量為6ooo切,運(yùn)往菜市場6蔬菜數(shù)量為7000翊;城鄉(xiāng)路口（E）運(yùn)往 菜市場2蔬菜數(shù)量為30翊,運(yùn)往菜市場3蔬菜數(shù)量

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

3、菜數(shù)量為6400畑;南街口（ C）運(yùn)往 菜市場5蔬菜數(shù)量為2800畑,運(yùn)往菜市場/蔬菜數(shù)量為8ooo翊,運(yùn)往菜市場8蔬 菜數(shù)量為7200如用于蔬菜調(diào)運(yùn)及預(yù)期的短缺最小損失為11128元。增加蔬菜種植面積后根據(jù)結(jié)果知增產(chǎn)的蔬菜向集散點(diǎn)C多供應(yīng)70公斤最經(jīng)濟(jì)合 理。關(guān)鍵詞：最短路徑；他屮f算法；弘00軟件;一、問題重述江平市是一個(gè)人口不到20萬人的小城市。根據(jù)該市的蔬菜種植情況，分別在菜市 場（久），城鄉(xiāng)路口（£）和南街口（C）設(shè)三個(gè)收購點(diǎn)，再由各收購點(diǎn)分送到全市的8 個(gè)菜市場，該市道路情況，各路段距離（單位：loom）及各收購點(diǎn)，菜市場到的 具體位置見圖I。按常年情況，久、遲、C三個(gè)收

4、購點(diǎn)每天收購量分別為250, 200和 280（單位:1OO如,各菜市場的每天需求量及發(fā)生供應(yīng)短缺時(shí)帶來的損失（元力00幼） 見表io設(shè)從收購點(diǎn)至各菜市場蔬菜調(diào)運(yùn)費(fèi)為2 7t/（ioog.ioom）o圖2蔬菜供應(yīng)網(wǎng)點(diǎn)圖表1各蔬菜市場需求量表菜市場每天需求（100庖0）短缺損失（元/ioo仕g）801O708905801O1201O7081OO59。8試為該市設(shè)計(jì)一個(gè)用于蔬菜調(diào)運(yùn)及預(yù)期的短缺損失為最小的從收購點(diǎn)至各個(gè)菜市 場的定點(diǎn)供應(yīng)方案；若規(guī)定各菜市場短缺量一律不超過需求量的20%,重新設(shè)計(jì)定點(diǎn) 供應(yīng)方案；規(guī)劃增加蔬菜種植面積后增產(chǎn)的蔬菜每天應(yīng)分別向久、宏、Q三個(gè)采購點(diǎn)供 應(yīng)多少最經(jīng)濟(jì)合理。遼

5、寧益海孩里地爾樂斯淀粉科技冇限公司二、問題分析求總的運(yùn)費(fèi)最低，可以先求出各采購點(diǎn)到菜市場的最小運(yùn)費(fèi)，因?yàn)閱挝恢亓康倪\(yùn)費(fèi) 與距離成正比。第一問可以用算法求出最短路徑即求出各個(gè)采購點(diǎn)都菜市場的 最短運(yùn)輸距離，乘以單位重量單位距離的運(yùn)輸費(fèi)用就是單位重量各運(yùn)輸路線的費(fèi)用，然 后用線性方法即可解得相應(yīng)的最小的調(diào)運(yùn)費(fèi)及預(yù)期短缺損失。第二問規(guī)定各菜市場短缺量一律不超過需求量的20%,只需在第一問的基礎(chǔ)上加 上新的設(shè)定條件，就可得到新的供應(yīng)方案。第三問建立新的線性問題進(jìn)行求解。三、問題假設(shè)K各個(gè)收購點(diǎn)、中轉(zhuǎn)站以及菜市場都可以做為中轉(zhuǎn)點(diǎn)。2、各個(gè)收購點(diǎn)、中轉(zhuǎn)站以及菜市場的最大容納量為700噸。3、假設(shè)運(yùn)輸?shù)穆吠?/p>

6、中蔬菜沒有任何損耗。4、假設(shè)只考慮運(yùn)輸費(fèi)用和短缺費(fèi)用，不考慮裝卸等其他費(fèi)用。5、忽略從種菜地點(diǎn)到收購點(diǎn)的運(yùn)輸費(fèi)用。四、變量說明(U 血久收購點(diǎn)分送到全市的8個(gè)菜市場的供應(yīng)量a2,02, C2, C(2,02彳2禺2, ft2亦收購點(diǎn)分送到全市的8個(gè)菜市場的供應(yīng)量仇3®3,C3,處,與3禺3,仕3C收購點(diǎn)分送到全市的8個(gè)菜市場的供應(yīng)量8個(gè)菜市場的短缺損失量（100翊）五、模型建立根據(jù)問題的分析，必須得求解各采購點(diǎn)到菜市場的最短距離。如果求圖中最短路徑 的話則有以下兩種解法：解法一：VyHstra算法；解法二：于0屮口弗洛伊德）算法。 以圖中的每個(gè)頂點(diǎn)作為源點(diǎn)，調(diào)用Tfijstra算法。

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

8、+砌的值；在此必詢與必幼分別是目前 為止所知道的i到叵與伍到j(luò)的最短距離，因此羽詢七儺p就是i到丿經(jīng)過叵的最短 距離。所以，若有殉)>d(i©+d(幼,就表示從i出發(fā)經(jīng)過丘再到j(luò)的距離要比原來 的到J距離短，自然把f到)的砌重寫為詢+砌，每當(dāng)一個(gè)£査完了，d(y) 就是目前的到J的最短距離。重復(fù)這一過程，最后當(dāng)査完所有的£時(shí)，砌里面存放 的就是i到j(luò)之間的最短距離了。恥y/算法的基本步驟：定義nxn的方陣序列Q-丄，Qo, Qn-丄。初始化：Tf-i=Co T>-iij= 邊<坊>的長度，表示初始的從E到J的最短路徑長度，即它是從f到J的中

9、間不經(jīng)過其 他中間點(diǎn)的最短路徑。迭代：設(shè)QQr己求出，如何得到。Q切訓(xùn)表示從/到J的中間點(diǎn)不大于6的最短路徑/： $考慮將頂點(diǎn)丘加 入路徑戸得到頂點(diǎn)序列年 Hj,若q不是路徑，則當(dāng)前的最短路徑仍是上一步結(jié) 果：Q任國印=©仕一迅©；否則若q的長度小于戸的長度，則用Q取代戸作為從i 到J的最短路徑。因?yàn)閝的兩條子路徑v-k和皆是中間點(diǎn)不大于k-i的最短路 徑，所以從f到J中間點(diǎn)不大于k的最短路徑長度為：Vij=min -iijL Qli醫(yī)I +Qi創(chuàng)印。于硼算法實(shí)現(xiàn):可以用三個(gè)0循環(huán)把問題搞定了，但是有一個(gè)問題需要注意，那就是0循環(huán)的 嵌套的順序。forfint 心o; H&

10、lt;n;仕+）forfint i=o; i<n; i+）for（int j=o; j<n; j+）這樣作的意義在于固定了念 把所有i到）而經(jīng)過任的距離找出來，然后象開頭所 提到的那樣進(jìn)行比較和重寫，因?yàn)槲槭窃谧钔鈱拥模詴?huì)把所有的i到j(luò)都處理完后, 才會(huì)移動(dòng)到下一個(gè)念這樣就不會(huì)有問題了，看來多層循環(huán)的時(shí)候，我們一定要當(dāng)心， 否則很容易就弄錯(cuò)了。接下來就要看一看如何找出最短路徑所行經(jīng)的城市了，這里要用到另一個(gè)矩陣P 它的定義是這樣的：尹仞的值如果為戸，就表示E到）的最短路徑為也就 是說尹是i到/的最短行徑中的j之前的最后一個(gè)城市。夕矩陣的初值為y（y）=i.有了 這個(gè)矩陣之后，要

11、找最短路徑就輕而易舉了。對于i到j(luò)而言找出尹（妙，令為p就知 道了路徑再去找戸（砂）,如果值為Q, f到戸的最短路徑為 再去找y（iq）f如果值為獷，f到Q的最短路徑為i->.>r->q；所以一再反復(fù)，到了某 個(gè)7（優(yōu)丿的值為f時(shí)，就表示到t的最短路徑為就會(huì)的到答案了，力到j(luò)的最短 行徑為因?yàn)樯鲜龅乃惴ㄊ菑慕K點(diǎn)到起點(diǎn)的順序找出來的，所以輸 出的時(shí)候要把它倒過來。但是，如何動(dòng)態(tài)的回填夕矩陣的值呢？為殉仮）+0（阿） 時(shí)，就要讓T到J的最短路徑改為走/這一條路，但是必切的值是已知 的，換句話說，就是6>.勺 這條路是已知的，所以6>.勺 這條路上的上一個(gè)城 市但卩幼丿

12、也是已知的，當(dāng)然，因?yàn)橐淖?>.>6>.勺 這一條路，j的上一個(gè)城 市正好是尹（幼。所以一旦發(fā)現(xiàn)0（書）>0（仮）+取規(guī),就把p（幼存入卩®。在利用弘y/算法求出最短路徑以后，對于問題一可以建立以下期o程序下的遼寧益海&里地爾樂斯淀粉科技有限公司線性規(guī)劃模型：如+8 呱+8 ci+19 力 +n *£2+6 護(hù) +22 0gi+2O0fii+i4 0a2+702+70C2+i 6 0d2+i2 *e2+16 咒+23'g2+17，fi2+2o(l3+19 壽亦+1 廣 C3+14旳+6性3+】5 方+503+1。仇3+1O 象 a+

13、8 吒+5 康 c+1 o (£+1 o 性+8 節(jié)+5 條0+8 棗 ft)條2；ai+6i+ci+di+eii+0i+fii=25o;<Z2+62+C2+d2+e2f2+02+(12=200Q3+63+C3+血+03 歩+03+3=180；a+6+c+c(+e+f+g+fv=7o;ai+a2+a3+aSo;61+62+63+6=70；ci+c2+c3+c=9。；cCi +d2+d3+d=8o;ei+e2+e3+=i2o;fi+f2+f3+f=7O；01+02+03+000；fti+fi2+fi3+f=9O；Tncf對于問題二可以建立以下 0程序下的線性規(guī)劃模型:MI=(4

14、*«U +8 *61 +8*Cl +19 棗 cd +115+6 怛+22 協(xié)+20 豪 fil +14 豪Q2+7 楽 02+7 豪 C2+16 楽心+12 性 2 +16予+23 來02+X7 濛仇2+20 攣仇3+19 吒3+1 廣 C3+14%6+6 豪C3+X5 怛+5乜3+1。豪仇3+io拳a+8%+5崇c+io楽昴io濛e+8于+5崇g+8奉ft)海2；ai+6i+ci+di+ei+fi+gi+fii=25O；Q3+63+C3+(6+e3 歩+03+仇3=18o;a+6+c+旅 &tf+g+心70； ai +CL2+03+0=80;61+62+63+6=70；C

15、】+C2+C3+C=9O； di +d2+ds+=So;ei+e2+e3+e=i2O；flf2+f3+f=7O；01+02+03+0=100；fil+fi2+fi3+&9O；a<i6;6vi4；c<18;d<16；e<24；f<14；0<2O；fi<18;對于問題三可以建立以下。程序下的線性規(guī)劃模型：+8 *61 +8C1+19 力 +215+6 護(hù) +22 01+20 fil+14 %2+7%2+7 叱6 也+12 陀2+16 2+23 02+17%2+2 O 仇3+19,63+11，C3+】4，必+6 畑3+15方+5乜3+lO*fl3)*

16、2；ai+a2+a3-8o;61+62+63=70；C】+C2+C3=9O；cC1+C(2+cC3=8O；ei+e2+e3=i2o;fi+f2+f37O；01+02+03=100；(11+(12+(13=90;ai+6i+ci+di+ei+fi+0i+fii>25O；CL2+62+C2+d2+e2+f2+g2+fl2>2OO；Q3+63+C3+c+e3 出+03+仇3>】80；Tnd六、模型求解9遼寧益海&里地爾樂斯淀粉科技有限公司珈屮f算法的代碼如下：function Q護(hù)少atfii寸afstartHerminoO D=a;n=size(Q“)尹仇坯=Z£

17、;QS仇處for v=imfarj=im礦 Q(紉 =ir yatfi(ij)=j;encQend,encCfor H=imfor v=imforj=im礦Q憶Q+Q(切0(紉Q(iJ)S(玨)+©(財(cái));ycdfKij)=patfi(玨);eruCeniCetuteniftfnargirv=3mim=V (start, terminaQ;m(i)=start;v=l;yaifii=;yfiiCe yatfi(m(i), terrninaOterminaC=i+i;m(H)=yatfi(m(i), terminaO；v=i+i;endm(i+i)=tertninal;end#遼寧益海

18、&里地爾樂斯淀粉科技有限公司根據(jù)題目網(wǎng)絡(luò)列出距離的矩陣，在中編寫的程序代碼如下: ao 488 vnfinf6 inf inf 7 吋 4 infwfinf;407 inf wf inf 5870 inf inf inf inf inf inf 3 inf inf inf 7 inf；8 inf inf o infs inf inf inf 5 inf 4 6 7 infiinf inf wf inf o inf inf inf wfwf inf 5 wfwf;inf inf inf 5 info inf inf inf wf 6 7 3 inf 6;65 inf inf inf in

19、f o wfwfinfz 5 tnfinfinf;祝f 盹f 龜f 魂f 龜f 龜fo 11 inf 10 wf inf inf 5：irrf irf inf irrf infinf h o inf inf inf 6 inf 10;7 inf 3 5 inf inf inf inf inf o wf inf inf 6 infii?tf inf inf inf inf 6 710 inf inf o 吋 inf inf 8;4 inf inf 4 inf 7 5 irtfwfirinfo inf inf inf;wf inf inf 6 5 3 inf inf 6 inf inf inf o

20、 11 infiinf inf 7 76 inf inf 11 o infiinf inf inf inf inf 6 infs 10 infs inf inf inf o調(diào)用仇，運(yùn)行結(jié)果如下：» D, path=f loyd(a)n =150488191162220*113414131740J I12231552224101281814208Ai0819131224203191214fl11981280119161211461111923191108201911161415516141115138012119106tI31266129201201721131151615222224

21、161911170112110181423L2024201211921110171516617101I103161013211701691161613121911146£ I10151601291884812415r518169120101113141814653151461191001191314I16121623176181111018172019111461510168139180IOpath =1234412112410>11241012123111111113i113I11231010102101010211014101110413612613106121314613

22、13131351313131313131313131312124413612151341112134151221212121111211112121211151115151515118915111515151513131313131313891313131313151334441441044414466686611i6615111446i6441i12446444456469464131461033413444131044131446116666118961166615七、結(jié)果分析1>菜市收購點(diǎn)12345678收購量804。6o702503。9080200C6o10020180短缺量（I

23、OO 切）70此方案通過運(yùn)算結(jié)果得出用于蔬菜調(diào)運(yùn)及預(yù)期的短缺損失為10920元。2>菜市收購點(diǎn)12345678收購量808927。250遼寧益海&里地爾樂斯淀粉科技有限公司627464200c288072180短缺量（1OO 切）16162018此方案通過運(yùn)算結(jié)果得出用于蔬菜調(diào)運(yùn)及預(yù)期的短缺損失為11128元。3、菜市收購點(diǎn)12345678收購量/look080406o70250宏309080200C6o1OO9。180由上表看岀，當(dāng)久 2兩收購點(diǎn)收購和供應(yīng)量相等，增收的7000財(cái)由Q收購點(diǎn) 收購，這樣下來所有的花費(fèi)會(huì)最小。八、參考文獻(xiàn)1 張志涌，楊祖櫻.如處久®教程仇

24、J.北京：北京航空航天大學(xué)出版社，2?？? 運(yùn)籌學(xué)教材編寫組，運(yùn)籌學(xué)，清華大學(xué)出版社，2OU九、附錄2、伉屯0運(yùn)行結(jié)果丄QCobaC optima£ solution fauruCIrtfeasiSiGiies:0.000000"Totaf softer iterations:12Objective value:10920.0013Variableya(ue"Reduced Cost0000010000000£OOOOO9ZI0000000J00000000000009a0000003000000900000刃000000900000*9?OOO0OO9

25、0000000000009 乙0000000OOOO9OOI%oooocrg 乙0000000££0000000000009oooooo000000*0£aOOOOO49T0000000OOOOONW000000900000乙片0000009O0O00090000009乙HooooozOOOOOO9O乙500000乙乙OOOOOO9O乙£ooooooOOOOOO9O0000000OOOOOOS乙QOOOOOO9O00000060000000oooooo£00000乙乙000000900000010000009OOOO0比0000009i5000

26、00090000O9Z00000000000099Eoooooo00000000000000000000*0Q0000000000000000000*0oooooognrQo.oooooo400000070.000000.000000110920.00-1.00000020.000000-16.0000030.000000-14-0000040.0000006.OOOOOOdw Stacfi or Stirpdus"DuaC Trice0.000000-2.0000000.0000008.00000070.0000000.00000080,0000000.00000090.00000

27、0-18.00000100.0000006.OO00000,0000000.0000000.0000004.000000-4000000-14.000002、血矽0運(yùn)行結(jié)果2QCobaC optimaC soCutwnfiniruCObjective value:11128.00IrxfeasibKxties:0.000000"TotaCsoCver iterations:11Variahteyalue"ReducedCost80.000000.0000008.0000000.000000Ci0.0000000.000000Di0.0000004.00000092.0000

28、00.00000000000*91-0000000OOUT000000T-呵（£m$ M）2/dvjsmz如0000009ooooor0000000000009750000050000009£OOOOOO0000000J0000000000001a00000000000091DooooooOOOOOO9O色OOOOOT000000*00000000ooooozZ00000090000008£5oooooz0000009££000000900000$ 乙££OOOOOO90000009oooooa0000000O0O0O乙 &

29、#163;OO0OOO9oooooOOOOOO9O£匕oooooog0000000000008 乙0000000乙5ooooozz0000000oooooo片000000900000000000090000009OOOOOZ9OOOOOO9O00000乙 9OOOO0乙乙000000000000*010000000%oooooz0000000磚0000009ooooooZ30.00000014.0000040.000000-6.00000050.000000-10.0000060.0000008.00000070.0000000.00000080.0000000.00000090.000000-18.00000100.0000006.00O000110.0000004000000120.000000-4.000000130.000000-14.000001416.0