光明市的菜籃子工程

1、光明市的菜籃子工程摘要本文研究的是蔬菜市場為滿足不同條件的最優(yōu)調(diào)配方案問題，用了Froyd算法、線性規(guī)劃建立了一系列數(shù)學(xué)規(guī)劃模型，并用MATLAB和LINGO軟件編程實(shí)現(xiàn)。關(guān)于問題一：用Froyd算法結(jié)合MATLAB編程求出收購點(diǎn)至個菜市場的最短距離，以用于蔬菜調(diào)運(yùn)及預(yù)期的短缺損失為最小為目標(biāo)建立線性規(guī)劃模型。用LINGO編程求得日均費(fèi)用最少為4610元。關(guān)于問題二：在模型一的基礎(chǔ)增加各菜市場短缺量一律不超過需求量的20%的約束條件，用LINGO編程求得最少日均費(fèi)用以及最優(yōu)供應(yīng)方案。費(fèi)用最少為4806元，供應(yīng)方安見正文。 關(guān)于問題三：在模型一的基礎(chǔ)上，改為以供貨充足、費(fèi)用最小為目標(biāo)，建立模型三

2、，用LINGO編程求得日均費(fèi)用為4770元，增產(chǎn)的蔬菜每天應(yīng)分給C收購點(diǎn)8000Kg。關(guān)鍵字：蔬菜市場調(diào)配方案 Froyd算法 線性規(guī)劃一、問題的重述海江市是一個人口不到20萬人的小城市。根據(jù)該市的蔬菜種植情況，分別在菜市場（A），菜市場（B）和菜市場（C）設(shè)三個收購點(diǎn)，再由各收購點(diǎn)分送到全市的8個菜市場，該市道路情況，各路段距離（單位：100m）及各收購點(diǎn)，菜市場的具體位置見圖3.2.按常年情況，A,B,C三個收購點(diǎn)每天收購量分別為30000，25000和20000（單位：100 kg）,各菜市場的每天需求量及發(fā)生供應(yīng)短缺時(shí)帶來的損失（元/100kg）見表3.設(shè)從收購點(diǎn)至各菜市場蔬菜調(diào)運(yùn)費(fèi)為

3、1元/(100kg.100m). 7 5 4 8 3 7 A 7 6 B 6 8 5 5 4 7 11 7 4 7 5 6 6 3 5 8 6 6 10 C 10 5 11 表3菜市場每天需求（100 kg）短缺損失（元/100kg）15010100812051001014010100814051208(a) 為該市設(shè)計(jì)一個從收購點(diǎn)至個菜市場的定點(diǎn)供應(yīng)方案，使用于蔬菜調(diào)運(yùn)及預(yù)期的短缺損失為最?。?b) 若規(guī)定各菜市場短缺量一律不超過需求量的20%，重新設(shè)計(jì)定點(diǎn)供應(yīng)方案；(c) 為滿足城市居民的蔬菜供應(yīng)，光明市的領(lǐng)導(dǎo)規(guī)劃增加蔬菜種植面積，試問增產(chǎn)的蔬菜每天應(yīng)分別向A,B,C三個采購點(diǎn)供應(yīng)多少最經(jīng)

4、濟(jì)合理。二、 符號說明 從A到i（各個菜市場）的最短距離 從B到i（各個菜市場）的最短距離 從C到i（各個菜市場）的最短距離 從A到i（各個菜市場）的運(yùn)貨量 從B到i（各個菜市場）的運(yùn)貨量 從C到i（各個菜市場）的運(yùn)貨量 總調(diào)運(yùn)費(fèi) 短缺損失 總費(fèi)用三 模型假設(shè)1、 假設(shè)日需求量與缺貨損失費(fèi)用不變。2、 假設(shè)在蔬菜調(diào)配的過程中無意外發(fā)生。3、 假設(shè)新增產(chǎn)的蔬菜能夠滿足缺貨量。四 模型的建立與求解4.1問題一4.1.1問題的分析：為了使用于蔬菜調(diào)運(yùn)及預(yù)期的短缺損失為最小，即調(diào)運(yùn)費(fèi)用與缺貨損失之和最小。首先考慮調(diào)運(yùn)費(fèi)用P，P為距離與送貨量的積，因?yàn)榕c送貨距離相關(guān)，我們必須先求出A、B、C三個采購點(diǎn)至

5、各個菜市場的最短距離。采用Froyd算法，結(jié)合MATLAB編程實(shí)現(xiàn)。其次考慮缺貨損失Q，以題中要求為約束條件，損失最低位目標(biāo)建立線性規(guī)劃模型，用LINGO編程求解。4.1.2模型的建立與求解：由圖和表格的信息知，建立一個線性規(guī)劃模型，使得蔬菜調(diào)運(yùn)及預(yù)期的短缺損失為最小。調(diào)運(yùn)總費(fèi)用P為： 若使調(diào)運(yùn)總費(fèi)用最少，則應(yīng)保證A、B、C三個收購點(diǎn)到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,

6、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),(v1

7、1,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時(shí)，為?。?）的權(quán)=0，i=1,2,3n=inf,當(dāng)（,）不屬于E時(shí)。（inf為無窮大，n為網(wǎng)絡(luò)結(jié)點(diǎn)個數(shù)）按上述規(guī)定，該網(wǎng)絡(luò)的權(quán)矩陣為：0 7 inf 5 4 inf inf inf inf inf inf inf inf inf inf7 0 7 i

8、nf 8 3 inf inf inf inf inf inf inf inf infinf 7 0 inf inf 6 inf 7 11 inf inf inf inf inf inf5 inf inf 0 6 inf 5 inf inf 7 inf inf inf inf inf4 8 inf 6 0 7 4 8 inf inf inf inf inf inf inf inf 3 6 inf 7 0 inf 5 inf inf inf inf inf inf infinf inf inf 5 4 inf 0 4 inf inf 7 inf inf inf infinf inf 7 inf 8

9、 5 4 0 6 inf 5 inf inf inf infinf inf 11 inf inf inf inf 6 0 inf 3 inf 6 inf 5inf inf inf 7 inf inf inf inf inf 0 6 8 inf 10 infinf inf inf inf inf inf 7 5 3 6 0 6 inf inf infinf inf inf inf inf inf inf inf inf 8 6 0 10 5 infinf inf inf inf inf inf inf inf 6 inf inf 10 0 11 infinf inf inf inf inf in

10、f inf inf inf 10 inf 5 11 0 infinf inf inf inf inf inf inf inf 5 inf inf inf inf inf 0因?yàn)樯鲜鼍W(wǎng)絡(luò)有15個結(jié)點(diǎn)，故網(wǎng)絡(luò)的權(quán)矩陣均為15階矩陣。現(xiàn)在給出網(wǎng)絡(luò)最短路線的Froyd算法：（1） d1=w.(w為所給網(wǎng)絡(luò)的n階權(quán)矩陣)（2） dk=,k=2,3,p.其中=min+,i,j=1,2,n.計(jì)算次數(shù)的確定：當(dāng)0時(shí)，p由下式確定：pln(n-1)/ln2，這樣的dp就確定了網(wǎng)絡(luò)各點(diǎn)間的最短距離。此處n=15,解出p3.8074故只需要取p=4即可，即算到d4即可。按照Froyd算法：d1=d,d2=fld(1

11、5,d1),d3=fld(15,d2),d4=(fld(15,d3),算的d4為：0 7 14 5 4 10 8 12 18 12 15 20 24 22 237 0 7 12 8 3 12 8 14 19 13 19 20 24 1914 7 0 16 13 6 11 7 11 18 12 18 17 23 165 12 16 0 6 13 5 9 15 7 12 15 21 17 204 8 13 6 0 7 4 8 14 13 11 17 20 22 1910 3 6 13 7 0 9 5 11 16 10 16 17 21 168 12 11 5 4 9 0 4 10 12 7 13

12、16 18 1512 8 7 9 8 5 4 0 6 11 5 11 12 16 1118 14 11 15 14 11 10 6 0 9 3 9 6 14 512 19 18 7 13 16 12 11 9 0 6 8 15 10 1415 13 12 12 11 10 7 5 3 6 0 6 9 11 820 19 18 15 17 16 13 11 9 8 6 0 10 5 1424 20 17 21 20 17 16 12 6 15 9 10 0 11 1122 24 23 17 22 21 18 16 14 10 11 5 11 0 1923 19 16 20 19 16 15 11

13、 5 14 8 14 11 19 0d4即為該網(wǎng)絡(luò)的距離矩陣，距離矩陣的第i行指明了到其他各點(diǎn)的最短距離。根據(jù)上述矩陣，分別找出A,B,C到、的最短距離，見表一：表一：收購點(diǎn)到菜市場的最短距離最短距離（單位：100千米）A488191162220B14771612162317C20191114615510調(diào)運(yùn)量的限制：短缺損失費(fèi)為：總費(fèi)用為：由以上約束條件，用LINGO 軟件進(jìn)行線性規(guī)劃求解（源程序及完整運(yùn)行結(jié)果見附錄），部分運(yùn)行結(jié)果如下：Global optimal solution found. Objective value: 4610.000 Infeasibilities: 0.00

14、0000 Total solver iterations: 10 Model Class: LP Total variables: 26 Nonlinear variables: 0 Integer variables: 0 Total constraints: 22 Nonlinear constraints: 0 Total nonzeros: 124 Nonlinear nonzeros: 0 Variable Value Reduced Cost P 3890.000 0.000000 Q 720.0000 0.000000 SA1 75.00000 0.000000 SA2 0.00

15、0000 0.000000 SA3 0.000000 0.000000 SA4 0.000000 2.000000 SA5 70.00000 0.000000 SA6 55.00000 0.000000 SA7 0.000000 12.00000 SA8 0.000000 5.000000 SB1 0.000000 11.00000 SB2 60.00000 0.000000 SB3 80.00000 0.000000 SB4 30.00000 0.000000 SB5 0.000000 2.000000 SB6 0.000000 11.00000 SB7 0.000000 14.00000

16、SB8 0.000000 3.000000 SC1 0.000000 21.00000 SC2 0.000000 16.00000 SC3 0.000000 8.000000 SC4 0.000000 2.000000 SC5 30.00000 0.000000 SC6 0.000000 14.00000 SC7 90.00000 0.000000 SC8 40.00000 0.000000從上述運(yùn)行結(jié)果中可以得出調(diào)運(yùn)方案為：收購點(diǎn)A菜市場，運(yùn)量為75菜市場，運(yùn)量為70菜市場，運(yùn)量為55收購點(diǎn)B菜市場，運(yùn)量為60菜市場，運(yùn)量為80菜市場，運(yùn)量為30收購點(diǎn)C菜市場，運(yùn)量為30菜市場，運(yùn)量為90菜

17、市場，運(yùn)量為40在此種方案下，蔬菜調(diào)運(yùn)及預(yù)期的短缺損失為最小，最小金額為4610元。4.1.3模型的評價(jià)與分析： 本模型用Froyd算法快捷的求出了A、B、C三個收購點(diǎn)到8個菜市場的最短路程，用線性規(guī)劃模型使得費(fèi)用最低，并給出了上圖所示的調(diào)配方案。在所得方案中每日只需4610元。4.2問題二4.2.1問題的分析：若按規(guī)定各菜市場短缺量一律不超過需求量的20%，則只需要在模型一的基礎(chǔ)上在增加一個約束條件：每個菜市場的供應(yīng)量必須不低于需求量的80%即可。即得到滿足條件的模型二。4.2.2模型的建立與求解：各菜市場短缺量一律不超過需求量的20%，為滿足這一條件，現(xiàn)對方案一進(jìn)行調(diào)整。只需在方案 一中加

18、一限制條件：同理可用LINGO 編程（源程序及完整運(yùn)行結(jié)果見附錄），部分運(yùn)行結(jié)果如下：Global optimal solution found. Objective value: 4806.000 Infeasibilities: 0.000000 Total solver iterations: 13 Model Class: LP Total variables: 26 Nonlinear variables: 0 Integer variables: 0 Total constraints: 30 Nonlinear constraints: 0 Total nonzeros: 148

19、 Nonlinear nonzeros: 0 Variable Value Reduced Cost P 4208.000 0.000000 Q 598.0000 0.000000 SA1 75.00000 0.000000 SA2 10.00000 0.000000 SA3 0.000000 0.000000 SA4 0.000000 2.000000 SA5 60.00000 0.000000 SA6 55.00000 0.000000 SA7 0.000000 12.00000 SA8 0.000000 5.000000 SB1 0.000000 11.00000 SB2 50.0000

20、0 0.000000 SB3 64.00000 0.000000 SB4 56.00000 0.000000 SB5 0.000000 2.000000 SB6 0.000000 11.00000 SB7 0.000000 14.00000 SB8 0.000000 3.000000 SC1 0.000000 21.00000 SC2 0.000000 16.00000 SC3 0.000000 8.000000 SC4 0.000000 2.000000 SC5 24.00000 0.000000 SC6 0.000000 14.00000 SC7 72.00000 0.000000 SC8

21、 64.00000 0.000000從上述運(yùn)行結(jié)果得知調(diào)整后的方案為：收購點(diǎn)A菜市場，運(yùn)量為75菜市場，運(yùn)量為10菜市場，運(yùn)量為60菜市場，運(yùn)量為55收購點(diǎn)B菜市場，運(yùn)量為50菜市場，運(yùn)量為64菜市場，運(yùn)量為56收購點(diǎn)C菜市場，運(yùn)量為24菜市場，運(yùn)量為72菜市場，運(yùn)量為64調(diào)整后的總損失為：4806元。4.2.3模型的評價(jià)與分析： 在增加了供貨量的限制條件后，只需在模型一的基礎(chǔ)上再增加約束條件即得到模型二。在本模型下日均花費(fèi)最低為4806元。新的調(diào)配方案如上圖所示。4.3問題三4.3.1問題的分析：本題的目標(biāo)有二：一、要滿足每個菜市場的供貨量充足；二、要使得總費(fèi)用最低。所以我們在模型一的基礎(chǔ)上

22、增加了上述兩個限制條件，即得到模型三。使得在供貨量充足的情況下最小化日均費(fèi)用。4.3.2模型的建立與求解： 要足城市居民的蔬菜供應(yīng)，增加蔬菜種植面積，則需要保證所有的菜市場都滿足日需求量，在問題一得基礎(chǔ)上作出以下調(diào)整： 同理，用LINGO編程求解(源程序及完整運(yùn)行結(jié)果見附錄)，部分運(yùn)行結(jié)果如下: Global optimal solution found. Objective value: 4770.000 Infeasibilities: 0.000000 Total solver iterations: 12 Model Class: LP Total variables: 26 Nonl

23、inear variables: 0 Integer variables: 0 Total constraints: 22 Nonlinear constraints: 0 Total nonzeros: 124 Nonlinear nonzeros: 0 Variable Value Reduced Cost P 4770.000 0.000000 Q 0.000000 0.6250000 SA1 75.00000 0.000000 SA2 40.00000 0.000000 SA3 0.000000 0.000000 SA4 0.000000 2.000000 SA5 30.00000 0

24、.000000 SA6 55.00000 0.000000 SA7 0.000000 12.00000 SA8 0.000000 5.000000 SB1 0.000000 11.00000 SB2 20.00000 0.000000 SB3 80.00000 0.000000 SB4 70.00000 0.000000 SB5 0.000000 2.000000 SB6 0.000000 11.00000 SB7 0.000000 14.00000 SB8 0.000000 3.000000 SC1 0.000000 21.00000 SC2 0.000000 16.00000 SC3 0.

25、000000 8.000000 SC4 0.000000 2.000000 SC5 70.00000 0.000000 SC6 0.000000 14.00000 SC7 90.00000 0.000000 SC8 80.00000 0.000000從結(jié)果中可以的知： 故新增的蔬菜8000Kg全部運(yùn)向C地，這樣既能滿足城市居民的蔬菜供應(yīng)，又能使總損失最小，最小為：4770元。4.3.3模型的評價(jià)與分析：本模型以供貨充足和費(fèi)用最低為目標(biāo)，利用題中的約束條件解得：在供貨量充足的情況下日均花費(fèi)最低為4770元。并得到了全新的調(diào)配方案如上圖所示，而且新增蔬菜8000Kg，且全部運(yùn)向C地。五 模型的及評

26、價(jià)與改進(jìn)5.1模型的評價(jià)5.1.1模型的優(yōu)點(diǎn)： 模型簡單易懂，主要用了Froyd算法與線性規(guī)劃，使問題的求解變得十分方便，能適應(yīng)更重新的要求。5.1.2模型的缺點(diǎn)： 上述模型第三問只考慮了運(yùn)輸費(fèi)用最小，卻沒有考慮到供過于求造成的貨物積壓問題。5.2模型的改進(jìn): 由于上述模型第三問只考慮了運(yùn)輸費(fèi)用最小，卻沒有考慮到供過于求造成的貨物積壓問題?？蓪⒋尕洆p失計(jì)算進(jìn)去，這樣會使這個模型更加完善。六 參考文獻(xiàn)1姜啟源，數(shù)學(xué)模型，北京，高等教育出版社，20032黃雍檢、賴明勇，MATLAB語言在運(yùn)籌學(xué)中的應(yīng)用，長沙，湖南大學(xué)出版社，2005七 附件問題一：MATLAB新建m文件：function y=fl

27、d(n,x)for r=1:n for i=1:n for j=1:n p(j)=x(i,j)+x(j,r); end y(r,i)=min(p); endend輸入命令：d=0 7 inf 5 4 inf inf inf inf inf inf inf inf inf inf;7 0 7 inf 8 3 inf inf inf inf inf inf inf inf inf;inf 7 0 inf inf 6 inf 7 11 inf inf inf inf inf inf; 5 inf inf 0 6 inf 5 inf inf 7 inf inf inf inf inf;4 8 inf

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

29、 inf inf 7 5 3 6 0 6 inf inf inf;inf inf inf inf inf inf inf inf inf 8 6 0 10 5 inf;inf inf inf inf inf inf inf inf 6 inf inf 10 0 11 inf;inf inf inf inf inf inf inf inf inf 10 inf 5 11 0 inf;inf inf inf inf inf inf inf inf 5 inf inf inf inf inf 0d1=dd2=fld(15,d1)d3=fld(15,d2)d4=fld(15,d3)運(yùn)行結(jié)果：d = C

30、olumns 1 through 14 0 7 Inf 5 4 Inf Inf Inf Inf Inf Inf Inf Inf Inf 7 0 7 Inf 8 3 Inf Inf Inf Inf Inf Inf Inf Inf Inf 7 0 Inf Inf 6 Inf 7 11 Inf Inf Inf Inf Inf 5 Inf Inf 0 6 Inf 5 Inf Inf 7 Inf Inf Inf Inf 4 8 Inf 6 0 7 4 8 Inf Inf Inf Inf Inf Inf Inf 3 6 Inf 7 0 Inf 5 Inf Inf Inf Inf Inf Inf Inf I

31、nf Inf 5 4 Inf 0 4 Inf Inf 7 Inf Inf Inf Inf Inf 7 Inf 8 5 4 0 6 Inf 5 Inf Inf Inf Inf Inf 11 Inf Inf Inf Inf 6 0 Inf 3 Inf 6 Inf Inf Inf Inf 7 Inf Inf Inf Inf Inf 0 6 8 Inf 10 Inf Inf Inf Inf Inf Inf 7 5 3 6 0 6 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 8 6 0 10 5 Inf Inf Inf Inf Inf Inf Inf Inf 6 Inf Inf 10 0 11 Inf Inf Inf Inf Inf Inf Inf Inf Inf 10 Inf 5 11 0 Inf Inf Inf Inf Inf Inf Inf Inf 5 Inf Inf Inf Inf Inf Column 15 Inf Inf Inf Inf Inf Inf Inf Inf 5 Inf Inf Inf Inf Inf 0d1 = Columns 1 through 14 0 7 Inf 5 4 Inf Inf Inf Inf Inf Inf Inf Inf Inf 7 0 7 Inf 8 3 Inf In