.../光明市的菜籃子工程摘要本文研究的是蔬菜市場為滿足不同條件的最優(yōu)調(diào)配方案問題,用了Froyd算法、線性規(guī)劃建立了一系列數(shù)學(xué)規(guī)劃模型,并用MATLAB和LINGO軟件編程實現(xiàn)。關(guān)于問題一：用Froyd算法結(jié)合MATLAB編程求出收購點至個菜市場的最短距離,以用于蔬菜調(diào)運及預(yù)期的短缺損失為最小為目標(biāo)建立線性規(guī)劃模型。用LINGO編程求得日均費用最少為4610元。關(guān)于問題二：在模型一的基礎(chǔ)增加各菜市場短缺量一律不超過需求量的20%的約束條件,用LINGO編程求得最少日均費用以及最優(yōu)供應(yīng)方案。費用最少為4806元,供應(yīng)方安見正文。關(guān)于問題三：在模型一的基礎(chǔ)上,改為以供貨充足、費用最小為目標(biāo),建立模型三,用LINGO編程求得日均費用為4770元,增產(chǎn)的蔬菜每天應(yīng)分給C收購點8000Kg。關(guān)鍵字：蔬菜市場調(diào)配方案Froyd算法線性規(guī)劃一、問題的重述海江市是一個人口不到20萬人的小城市。根據(jù)該市的蔬菜種植情況,分別在菜市場〔A,菜市場〔B和菜市場〔C設(shè)三個收購點,再由各收購點分送到全市的8個菜市場,該市道路情況,各路段距離〔單位：100m及各收購點,菜市場①⑧的具體位置見圖3.2.按常年情況,A,B,C三個收購點每天收購量分別為30000,25000和20000〔單位：100kg,各菜市場的每天需求量及發(fā)生供應(yīng)短缺時帶來的損失〔元/100kg見表3.設(shè)從收購點至各菜市場蔬菜調(diào)運費為1元/<100kg.100m>.①7②54837A76B⑥6855471174③7566⑤35④86610C10⑧511⑦表3菜市場每天需求〔100kg短缺損失〔元/100kg15010100812051001014010100814051208為該市設(shè)計一個從收購點至個菜市場的定點供應(yīng)方案,使用于蔬菜調(diào)運及預(yù)期的短缺損失為最?。蝗粢?guī)定各菜市場短缺量一律不超過需求量的20%,重新設(shè)計定點供應(yīng)方案；為滿足城市居民的蔬菜供應(yīng),光明市的領(lǐng)導(dǎo)規(guī)劃增加蔬菜種植面積,試問增產(chǎn)的蔬菜每天應(yīng)分別向A,B,C三個采購點供應(yīng)多少最經(jīng)濟合理。二、符號說明從A到i〔各個菜市場的最短距離從B到i〔各個菜市場的最短距離從C到i〔各個菜市場的最短距離從A到i〔各個菜市場的運貨量從B到i〔各個菜市場的運貨量從C到i〔各個菜市場的運貨量總調(diào)運費短缺損失總費用三模型假設(shè)假設(shè)日需求量與缺貨損失費用不變。假設(shè)在蔬菜調(diào)配的過程中無意外發(fā)生。假設(shè)新增產(chǎn)的蔬菜能夠滿足缺貨量。四模型的建立與求解4.1問題一問題的分析：為了使用于蔬菜調(diào)運及預(yù)期的短缺損失為最小,即調(diào)運費用與缺貨損失之和最小。首先考慮調(diào)運費用P,P為距離與送貨量的積,因為與送貨距離相關(guān),我們必須先求出A、B、C三個采購點至各個菜市場的最短距離。采用Froyd算法,結(jié)合MATLAB編程實現(xiàn)。其次考慮缺貨損失Q,以題中要求為約束條件,損失最低位目標(biāo)建立線性規(guī)劃模型,用LINGO編程求解。模型的建立與求解：由圖和表格的信息知,建立一個線性規(guī)劃模型,使得蔬菜調(diào)運及預(yù)期的短缺損失為最小。調(diào)運總費用P為：若使調(diào)運總費用最少,則應(yīng)保證A、B、C三個收購點到8個菜市場的路程最短,最短路線的求解過程如圖一：圖一：求解過程圖分析上圖可知,該路線為無向網(wǎng)絡(luò),就該圖而言,網(wǎng)絡(luò)弧集為：E=[<v1,v2>,<v1,v4>,<v1,v5>,<v2,v1>,<v2,v3>,<v2,v5>,<v2,v6>,<v3,v2>,.<v3,v6>,<v3,v8>,<v3,v9>,<v4,v1>,<v4,v5>.<v4,v7>,<v4,v10>,<v5,v1>,<v5,v2>,<v5,v4>,<v5,v6>,<v5,v7>,<v5,v8>,<v6,v2>,<v6,v3>,<v6,v5>,<v6,v8>,<v7,v4>,<v7,v5>,<v7,v8>,<v7,v11>,<v8,v3>,<v8,v5>,<v8,v6>,<v8,v7>,<v8,v9>,<v8,v11>,<v9,v3>,<v9,v8>,<v9,v11>,<v9,v13>,<v9,v15>,<v10,v4>,<v10,v11>,<v10,v12>,<v10,v14>,<v11,v7>,<v11,v8>,<v11,v9><v11,v10>,<v11,v12>,<v12,v10>,<v12,v11>,<v12,v13>,<v12,v14>,<v13,v9>,<v13,v12>,<v13,v14>,<v14,v10>,<v14,v12>,<v14,v13>,<v15,v9>]下面來確定網(wǎng)絡(luò)權(quán)矩陣：W=其中=,當(dāng)〔,屬于E時,為弧〔,的權(quán)=0,i=1,2,3……n=inf,當(dāng)〔,不屬于E時?！瞚nf為無窮大,n為網(wǎng)絡(luò)結(jié)點個數(shù)按上述規(guī)定,該網(wǎng)絡(luò)的權(quán)矩陣為：07inf54infinfinfinfinfinfinfinfinfinf707inf83infinfinfinfinfinfinfinfinfinf70infinf6inf711infinfinfinfinfinf5infinf06inf5infinf7infinfinfinfinf48inf60748infinfinfinfinfinfinfinf36inf70inf5infinfinfinfinfinfinfinfinfinf54inf04infinf7infinfinfinfinfinf7inf85406inf5infinfinfinfinfinf11infinfinfinf60inf3inf6inf5infinfinf7infinfinfinfinf068inf10infinfinfinfinfinfinf753606infinfinfinfinfinfinfinfinfinfinfinf860105infinfinfinfinfinfinfinfinf6infinf10011infinfinfinfinfinfinfinfinfinf10inf5110infinfinfinfinfinfinfinfinf5infinfinfinfinf0因為上述網(wǎng)絡(luò)有15個結(jié)點,故網(wǎng)絡(luò)的權(quán)矩陣均為15階矩陣。現(xiàn)在給出網(wǎng)絡(luò)最短路線的Froyd算法：d1=w.<w為所給網(wǎng)絡(luò)的n階權(quán)矩陣>dk=,k=2,3,…,p.其中=min[+,i,j=1,2,…,n.計算次數(shù)的確定：當(dāng)0時,p由下式確定：pln<n-1>/ln2,這樣的dp就確定了網(wǎng)絡(luò)各點間的最短距離。此處n=15,解出p3.8074故只需要取p=4即可,即算到d4即可。按照Froyd算法：d1=d,d2=fld<15,d1>,d3=fld<15,d2>,d4=<fld<15,d3>,算的d4為：0714541081218121520242223707128312814191319202419147016136117111812181723165121606135915712152117204813607481413111720221910361370951116101617211681211549041012713161815128798540611511121611181411151411106093961451219187131612119068151014151312121110753606911820191815171613119860105142420172120171612615910011112224231722211816141011511019231916201916151151481411190d4即為該網(wǎng)絡(luò)的距離矩陣,距離矩陣的第i行指明了到其他各點的最短距離。根據(jù)上述矩陣,分別找出A,B,C到①、②、③、④、⑤、⑥、⑦、⑧的最短距離,見表一：表一：收購點到菜市場的最短距離最短距離〔單位：100千米①②③④⑤⑥⑦⑧A488191162220B14771612162317C20191114615510調(diào)運量的限制：短缺損失費為：總費用為：由以上約束條件,用LINGO軟件進行線性規(guī)劃求解〔源程序及完整運行結(jié)果見附錄,部分運行結(jié)果如下：Globaloptimalsolutionfound.Objectivevalue:4610.000Infeasibilities:0.000000Totalsolveriterations:10ModelClass:LPTotalvariables:26Nonlinearvariables:0Integervariables:0Totalconstraints:22Nonlinearconstraints:0Totalnonzeros:124Nonlinearnonzeros:0VariableValueReducedCostP3890.0000.000000Q720.00000.000000SA175.000000.000000SA20.0000000.000000SA30.0000000.000000SA40.0000002.000000SA570.000000.000000SA655.000000.000000SA70.00000012.00000SA80.0000005.000000SB10.00000011.00000SB260.000000.000000SB380.000000.000000SB430.000000.000000SB50.0000002.000000SB60.00000011.00000SB70.00000014.00000SB80.0000003.000000SC10.00000021.00000SC20.00000016.00000SC30.0000008.000000SC40.0000002.000000SC530.000000.000000SC60.00000014.00000SC790.000000.000000SC840.000000.000000從上述運行結(jié)果中可以得出調(diào)運方案為：收購點A收購點A菜市場①,運量為75菜市場⑤,運量為70菜市場⑥,運量為55收購點B收購點B菜市場②,運量為60菜市場③,運量為80菜市場④,運量為30收購點C收購點C菜市場⑤,運量為30菜市場⑦,運量為90菜市場⑧,運量為40在此種方案下,蔬菜調(diào)運及預(yù)期的短缺損失為最小,最小金額為4610元。模型的評價與分析：本模型用Froyd算法快捷的求出了A、B、C三個收購點到8個菜市場的最短路程,用線性規(guī)劃模型使得費用最低,并給出了上圖所示的調(diào)配方案。在所得方案中每日只需4610元。4.2問題二問題的分析：若按規(guī)定各菜市場短缺量一律不超過需求量的20%,則只需要在模型一的基礎(chǔ)上在增加一個約束條件：每個菜市場的供應(yīng)量必須不低于需求量的80%即可。即得到滿足條件的模型二。模型的建立與求解：各菜市場短缺量一律不超過需求量的20%,為滿足這一條件,現(xiàn)對方案一進行調(diào)整。只需在方案一中加一限制條件：同理可用LINGO編程〔源程序及完整運行結(jié)果見附錄,部分運行結(jié)果如下：Globaloptimalsolutionfound.Objectivevalue:4806.000Infeasibilities:0.000000Totalsolveriterations:13ModelClass:LPTotalvariables:26Nonlinearvariables:0Integervariables:0Totalconstraints:30Nonlinearconstraints:0Totalnonzeros:148Nonlinearnonzeros:0VariableValueReducedCostP4208.0000.000000Q598.00000.000000SA175.000000.000000SA210.000000.000000SA30.0000000.000000SA40.0000002.000000SA560.000000.000000SA655.000000.000000SA70.00000012.00000SA80.0000005.000000SB10.00000011.00000SB250.000000.000000SB364.000000.000000SB456.000000.000000SB50.0000002.000000SB60.00000011.00000SB70.00000014.00000SB80.0000003.000000SC10.00000021.00000SC20.00000016.00000SC30.0000008.000000SC40.0000002.000000SC524.000000.000000SC60.00000014.00000SC772.000000.000000SC864.000000.000000從上述運行結(jié)果得知調(diào)整后的方案為：收購點A收購點A菜市場①,運量為75菜市場②,運量為10菜市場⑤,運量為60菜市場⑥,運量為55收購點B收購點B菜市場②,運量為50菜市場③,運量為64菜市場④,運量為56收購點C收購點C菜市場⑤,運量為24菜市場⑦,運量為72菜市場⑧,運量為64調(diào)整后的總損失為：4806元。模型的評價與分析：在增加了供貨量的限制條件后,只需在模型一的基礎(chǔ)上再增加約束條件即得到模型二。在本模型下日均花費最低為4806元。新的調(diào)配方案如上圖所示。4.3問題三問題的分析：本題的目標(biāo)有二：一、要滿足每個菜市場的供貨量充足；二、要使得總費用最低。所以我們在模型一的基礎(chǔ)上增加了上述兩個限制條件,即得到模型三。使得在供貨量充足的情況下最小化日均費用。模型的建立與求解：要足城市居民的蔬菜供應(yīng),增加蔬菜種植面積,則需要保證所有的菜市場都滿足日需求量,在問題一得基礎(chǔ)上作出以下調(diào)整：同理,用LINGO編程求解<源程序及完整運行結(jié)果見附錄>,部分運行結(jié)果如下:Globaloptimalsolutionfound.Objectivevalue:4770.000Infeasibilities:0.000000Totalsolveriterations:12ModelClass:LPTotalvariables:26Nonlinearvariables:0Integervariables:0Totalconstraints:22Nonlinearconstraints:0Totalnonzeros:124Nonlinearnonzeros:0VariableValueReducedCostP4770.0000.000000Q0.0000000.6250000SA175.000000.000000SA240.000000.000000SA30.0000000.000000SA40.0000002.000000SA530.000000.000000SA655.000000.000000SA70.00000012.00000SA80.0000005.000000SB10.00000011.00000SB220.000000.000000SB380.000000.000000SB470.000000.000000SB50.0000002.000000SB60.00000011.00000SB70.00000014.00000SB80.0000003.000000SC10.00000021.00000SC20.00000016.00000SC30.0000008.000000SC40.0000002.000000SC570.000000.000000SC60.00000014.00000SC790.000000.000000SC880.000000.000000從結(jié)果中可以的知：故新增的蔬菜8000Kg全部運向C地,這樣既能滿足城市居民的蔬菜供應(yīng),又能使總損失最小,最小為：4770元。模型的評價與分析：本模型以供貨充足和費用最低為目標(biāo),利用題中的約束條件解得：在供貨量充足的情況下日均花費最低為4770元。并得到了全新的調(diào)配方案如上圖所示,而且新增蔬菜8000Kg,且全部運向C地。五模型的及評價與改進5.1模型的評價模型的優(yōu)點：模型簡單易懂,主要用了Froyd算法與線性規(guī)劃,使問題的求解變得十分方便,能適應(yīng)更重新的要求。模型的缺點：上述模型第三問只考慮了運輸費用最小,卻沒有考慮到供過于求造成的貨物積壓問題。5.2模型的改進:由于上述模型第三問只考慮了運輸費用最小,卻沒有考慮到供過于求造成的貨物積壓問題。可將存貨損失計算進去,這樣會使這個模型更加完善。六參考文獻[1]姜啟源,數(shù)學(xué)模型,北京,高等教育出版社,2003[2]黃雍檢、賴明勇,MATLAB語言在運籌學(xué)中的應(yīng)用,XX,XX大學(xué)出版社,2005七附件問題一：MATLAB新建m文件：functiony=fld<n,x>forr=1:nfori=1:nforj=1:np<j>=x<i,j>+x<j,r>;endy<r,i>=min<p>;endend輸入命令：d=[07inf54infinfinfinfinfinfinfinfinfinf;707inf83infinfinfinfinfinfinfinfinf;inf70infinf6inf711infinfinfinfinfinf;5infinf06inf5infinf7infinfinfinfinf;48inf60748infinfinfinfinfinfinf;inf36inf70inf5infinfinfinfinfinfinf;infinfinf54inf04infinf7infinfinfinf;infinf7inf85406inf5infinfinfinf;infinf11infinfinfinf60inf3inf6inf5;infinfinf7infinfinfinfinf068inf10inf;infinfinfinfinfinf753606infinfinf;infinfinfinfinfinfinfinfinf860105inf;infinfinfinfinfinfinfinf6infinf10011inf;infinfinfinfinfinfinfinfinf10inf5110inf;infinfinfinfinfinfinfinf5infinfinfinfinf0]d1=dd2=fld<15,d1>d3=fld<15,d2>d4=fld<15,d3>運行結(jié)果：d=Columns1through1407Inf54InfInfInfInfInfInfInfInfInf707Inf83InfInfInfInfInfInfInfInfInf70InfInf6Inf711InfInfInfInfInf5InfInf06Inf5InfInf7InfInfInfInf48Inf60748InfInfInfInfInfInfInf36Inf70Inf5InfInfInfInfInfInfInfInfInf54Inf04InfInf7InfInfInfInfInf7Inf85406Inf5InfInfInfInfInf11InfInfInfInf60Inf3Inf6InfInfInfInf7InfInfInfInfInf068Inf10InfInfInfInfInfInf753606InfInfInfInfInfInfInfInfInfInfInf860105InfInfInfInfInfInfInfInf6InfInf10011InfInfInfInfInfInfInfInfInf10Inf5110InfInfInfInfInfInfInfInf5InfInfInfInfInfColumn15InfInfInfInfInfInfInfInf5InfInfInfInfInf0d1=Columns1through1407Inf54InfInfInfInfInfInfInfInfInf707Inf83InfInfInfInfInfInfInfInfInf70InfInf6Inf711InfInfInfInfInf5InfInf06Inf5InfInf7InfInfInfInf48Inf60748InfInfInfInfInfInfInf36Inf70Inf5InfInfInfInfInfInfInfInfInf54Inf04InfInf7InfInfInfInfInf7Inf85406Inf5InfInfInfInfInf11InfInfInfInf60Inf3Inf6InfInfInfInf7InfInfInfInfInf068Inf10InfInfInfInfInfInf753606InfInfInfInfInfInfInfInfInfInfInf860105InfInfInfInfInfInfInfInf6InfInf10011InfInfInfInfInfInfInfInfInf10Inf5110InfInfInfInfInfInfInfInf5InfInfInfInfInfColumn15InfInfInfInfInfInfInfInf5InfInfInfInfInf0d2=Columns1through1407145410812Inf12InfInfInfInf707128312818InfInfInfInfInf1470Inf13611711Inf12Inf17Inf512Inf061359Inf71215Inf17481360748141311InfInfInf103613709511Inf10InfInfInf81211549041012713InfInf12879854061151112InfInf1811Inf1411106093961712InfInf713Inf121190681810InfInf12121110753606911InfInfInf15InfInnfInf17InfInfInfInf12618910011InfInfInf17InfInfInfInf1710115110InfInf16InfInfInfInf115Inf8Inf11InfColumn15InfInf16InfInfInfInf115Inf8Inf11Inf0d3=Columns1through140714541081218121520242270712831281419131920291470161361171118121817235121606135915712152117481360748141311172022103613709511161016172181211549041012713161812879854061151112161814111514111060939614121918713161211906815101513121211107536069112019181517161311986010524201721201716126159100112229231722211816141011511023191620191615115148141119Column15231916201916151151481411190d4=Columns1through140714541081218121520242270712831281419131920241470161361171118121817235121606135915712152117481360748141311172022103613709511161016172181211549041012713161812879854061151112161814111514111060939614121918713161211906815101513121211107536069112019181517161311986010524201721201716126159100112224231722211816141011511023191620191615115148141119Column15231916201916151151481411190LINGO程序：min=P+Q;DA1=4;DA2=8;DA3=8;DA4=19;DA5=11;DA6=6;DA7=22;DA8=20;DB1=14;DB2=7;DB3=7;DB4=16;DB5=12;DB6=16;DB7=23;DB8=17;DC1=20;DC2=19;DC3=11;DC4=14;DC5=6;DC6=15;DC7=5;DC8=10;SA1+SA2+SA3+SA4+SA5+SA6+SA7+SA8=200;SB1+SB2+SB3+SB4+SB5+SB6+SB7+SB8=170;SC1+SC2+SC3+SC4+SC5+SC6+SC7+SC8=160;p=<SA1*DA1+SA2*DA2+SA3*DA3+SA4*DA4+SA5*DA5+SA6*DA6+SA7*DA7+SA8*DA8>+<SB1*DB1+SB2*DB2+SB3*DB3+SB4*DB4+SB5*DB5+SB6*DB6+SB7*DB7+SB8*DB8>+<SC1*DC1+SC2*DC2+SC3*DC3+SC4*DC4+SC5*DC5+SC6*DC6+SC7*DC7+SC8*DC8>;Q=10*<75-<SA1+SB1+SC1>>+8*<60-<SA2+SB2+SC2>>+5*<80-<SA3+SB3+SC3>>+10*<70-<SA4+SB4+SC4>>+10*<100-<SA5+SB5+SC5>>+8*<55-<SA6+SB6+SC6>>+5*<90-<SA7+SB7+SC7>>+8*<80-<SA8+SB8+SC8>>;10*<75-<SA1+SB1+SC1>>>=0;8*<60-<SA2+SB2+SC2>>>=0;5*<80-<SA3+SB3+SC3>>>=0;10*<70-<SA4+SB4+SC4>>>=0;10*<100-<SA5+SB5+SC5>>>=0;8*<55-<SA6+SB6+SC6>>>=0;5*<90-<SA7+SB7+SC7>>>=0;8*<80-<SA8+SB8+SC8>>>=0;SA1+SB1+SC1<=75;SA2+SB2+SC2<=60;SA3+SB3+SC3<=80;SA4+SB4+SC4<=70;SA5+SB5+SC5<=100;SA6+SB6+SC6<=55;SA7+SB7+SC7<=90;SA8+SB8+SC8<=80;end運行結(jié)果：Globaloptimalsolutionfound.Objectivevalue:4610.000Infeasibilities:0.000000Totalsolveriterations:10ModelClass:LPTotalvariables:26Nonlinearvariables:0Integervariables:0Totalconstraints:22Nonlinearconstraints:0Totalnonzeros:124Nonlinearnonzeros:0VariableValueReducedCostP3890.0000.000000Q720.00000.000000DA14.0000000.000000DA28.0000000.000000DA38.0000000.000000DA419.000000.000000DA511.000000.000000DA66.0000000.000000DA722.000000.000000DA820.000000.000000DB114.000000.000000DB27.0000000.000000DB37.0000000.000000DB416.000000.000000DB512.000000.000000DB616.000000.000000DB723.000000.000000DB817.000000.000000DC120.000000.000000DC219.000000.000000DC311.000000.000000DC414.000000.000000DC56.0000000.000000DC615.000000.000000DC75.0000000.000000DC810.000000.000000SA175.000000.000000SA20.0000000.000000SA30.0000000.000000SA40.0000002.000000SA570.000000.000000SA655.000000.000000SA70.00000012.00000SA80.0000005.000000SB10.00000011.00000SB260.000000.000000SB380.000000.000000SB430.000000.000000SB50.0000002.000000SB60.00000011.00000SB70.00000014.00000SB80.0000003.000000SC10.00000021.00000SC20.00000016.00000SC30.0000008.000000SC40.0000002.000000SC530.000000.000000SC6