光明市的菜篮子工程.docx
《光明市的菜篮子工程.docx》由会员分享,可在线阅读,更多相关《光明市的菜篮子工程.docx(45页珍藏版)》请在冰点文库上搜索。
光明市的菜篮子工程
光明市的菜篮子工程
摘要
本文研究的是蔬菜市场为满足不同条件的最优调配方案问题,用了Froyd算法、线性规划建立了一系列数学规划模型,并用MATLAB和LINGO软件编程实现。
关于问题一:
用Froyd算法结合MATLAB编程求出收购点至个菜市场的最短距离,以用于蔬菜调运及预期的短缺损失为最小为目标建立线性规划模型。
用LINGO编程求得日均费用最少为4610元。
关于问题二:
在模型一的基础增加各菜市场短缺量一律不超过需求量的20%的约束条件,用LINGO编程求得最少日均费用以及最优供应方案。
费用最少为4806元,供应方安见正文。
关于问题三:
在模型一的基础上,改为以供货充足、费用最小为目标,建立模型三,用LINGO编程求得日均费用为4770元,增产的蔬菜每天应分给C收购点8000Kg。
关键字:
蔬菜市场调配方案Froyd算法线性规划
一、问题的重述
海江市是一个人口不到20万人的小城市。
根据该市的蔬菜种植情况,分别在菜市场(A),菜市场(B)和菜市场(C)设三个收购点,再由各收购点分送到全市的8个菜市场,该市道路情况,各路段距离(单位:
100m)及各收购点,菜市场①
⑧的具体位置见图3.2.按常年情况,A,B,C三个收购点每天收购量分别为30000,25000和20000(单位:
100kg),各菜市场的每天需求量及发生供应短缺时带来的损失(元/100kg)见表3.设从收购点至各菜市场蔬菜调运费为1元/(100kg.100m).
①7②
54837
A76B
⑥685
54711
74③
756
6⑤35④
866
10C10⑧
511
⑦
表3
菜市场
每天需求(100kg)
短缺损失(元/100kg)
1
150
10
2
100
8
3
120
5
4
100
10
5
140
10
6
100
8
7
140
5
8
120
8
(a)为该市设计一个从收购点至个菜市场的定点供应方案,使用于蔬菜调运及预期的短缺损失为最小;
(b)若规定各菜市场短缺量一律不超过需求量的20%,重新设计定点供应方案;
(c)为满足城市居民的蔬菜供应,光明市的领导规划增加蔬菜种植面积,试问增产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。
二、符号说明
从A到i(各个菜市场)的最短距离
从B到i(各个菜市场)的最短距离
从C到i(各个菜市场)的最短距离
从A到i(各个菜市场)的运货量
从B到i(各个菜市场)的运货量
从C到i(各个菜市场)的运货量
总调运费
短缺损失
总费用
三模型假设
1、假设日需求量与缺货损失费用不变。
2、假设在蔬菜调配的过程中无意外发生。
3、假设新增产的蔬菜能够满足缺货量。
四模型的建立与求解
4.1问题一
4.1.1问题的分析:
为了使用于蔬菜调运及预期的短缺损失为最小,即调运费用与缺货损失之和最小。
首先考虑调运费用P,P为距离与送货量的积,因为与送货距离相关,我们必须先求出A、B、C三个采购点至各个菜市场的最短距离。
采用Froyd算法,结合MATLAB编程实现。
其次考虑缺货损失Q,以题中要求为约束条件,损失最低位目标建立线性规划模型,用LINGO编程求解。
4.1.2模型的建立与求解:
由图和表格的信息知,建立一个线性规划模型,使得蔬菜调运及预期的短缺损失为最小。
调运总费用P为:
若使调运总费用最少,则应保证A、B、C三个收购点到8个菜市场的路程最短,最短路线的求解过程如图一:
图一:
求解过程图
分析上图可知,该路线为无向网络,就该图而言,网络弧集为:
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=
其中
=
,当(
)属于E时,
为弧(
)的权
=0,i=1,2,3……n
=inf,当(
)不属于E时。
(inf为无穷大,n为网络结点个数)
按上述规定,该网络的权矩阵为:
07inf54infinfinfinfinfinfinfinfinfinf
707inf83infinfinfinfinfinfinfinfinf
inf70infinf6inf711infinfinfinfinfinf
5infinf06inf5infinf7infinfinfinfinf
48inf60748infinfinfinfinfinfinf
inf36inf70inf5infinfinfinfinfinfinf
infinfinf54inf04infinf7infinfinfinf
infinf7inf85406inf5infinfinfinf
infinf11infinfinfinf60inf3inf6inf5
infinfinf7infinfinfinfinf068inf10inf
infinfinfinfinfinf753606infinfinf
infinfinfinfinfinfinfinfinf860105inf
infinfinfinfinfinfinfinf6infinf10011inf
infinfinfinfinfinfinfinfinf10inf5110inf
infinfinfinfinfinfinfinf5infinfinfinfinf0
因为上述网络有15个结点,故网络的权矩阵均为15阶矩阵。
现在给出网络最短路线的Froyd算法:
(1)d1=w.(w为所给网络的n阶权矩阵)
(2)dk=
k=2,3,…,p.
其中
=min[
+
i,j=1,2,…,n.
计算次数的确定:
当
0时,p由下式确定:
p
ln(n-1)/ln2,这样的dp就确定了网络各点间的最短距离。
此处n=15,解出p
3.8074
故只需要取p=4即可,即算到d4即可。
按照Froyd算法:
d1=d,d2=fld(15,d1),d3=fld(15,d2),
d4=(fld(15,d3),算的d4为:
0714541081218121520242223
707128312814191319202419
14701613611711181218172316
512160613591571215211720
48136074814131117202219
103613709511161016172116
81211549041012713161815
128798540611511121611
18141115141110609396145
1219187131612119068151014
1513121211107536069118
2019181517161311986010514
242017212017161261591001111
2224231722211816141011511019
231916201916151151481411190
d4即为该网络的距离矩阵,距离矩阵的第i行指明了
到其他各点的最短距离。
根据上述矩阵,分别找出A,B,C到①、②、③、④、⑤、⑥、⑦、⑧的最短距离,见表一:
表一:
收购点到菜市场的最短距离
最短距离(单位:
100千米)
①
②
③
④
⑤
⑥
⑦
⑧
A
4
8
8
19
11
6
22
20
B
14
7
7
16
12
16
23
17
C
20
19
11
14
6
15
5
10
调运量的限制:
短缺损失费为:
总费用为:
由以上约束条件,用LINGO软件进行线性规划求解(源程序及完整运行结果见附录),部分运行结果如下:
Globaloptimalsolutionfound.
Objectivevalue:
4610.000
Infeasibilities:
0.000000
Totalsolveriterations:
10
ModelClass:
LP
Totalvariables:
26
Nonlinearvariables:
0
Integervariables:
0
Totalconstraints:
22
Nonlinearconstraints:
0
Totalnonzeros:
124
Nonlinearnonzeros:
0
VariableValueReducedCost
P3890.0000.000000
Q720.00000.000000
SA175.000000.000000
SA20.0000000.000000
SA30.0000000.000000
SA40.0000002.000000
SA570.000000.000000
SA655.000000.000000
SA70.00000012.00000
SA80.0000005.000000
SB10.00000011.00000
SB260.000000.000000
SB380.000000.000000
SB430.000000.000000
SB50.0000002.000000
SB60.00000011.00000
SB70.00000014.00000
SB80.0000003.000000
SC10.00000021.00000
SC20.00000016.00000
SC30.0000008.000000
SC40.0000002.000000
SC530.000000.000000
SC60.00000014.00000
SC790.000000.000000
SC840.000000.000000
从上述运行结果中可以得出调运方案为:
收购点C
菜市场⑤,运量为30
菜市场⑦,运量为90
菜市场⑧,运量为40
在此种方案下,蔬菜调运及预期的短缺损失为最小,最小金额为4610元。
4.1.3模型的评价与分析:
本模型用Froyd算法快捷的求出了A、B、C三个收购点到8个菜市场的最短路程,用线性规划模型使得费用最低,并给出了上图所示的调配方案。
在所得方案中每日只需4610元。
4.2问题二
4.2.1问题的分析:
若按规定各菜市场短缺量一律不超过需求量的20%,则只需要在模型一的基础上在增加一个约束条件:
每个菜市场的供应量必须不低于需求量的80%即可。
即得到满足条件的模型二。
4.2.2模型的建立与求解:
各菜市场短缺量一律不超过需求量的20%,为满足这一条件,现对方案一进行调整。
只需在方案一中加一限制条件:
同理可用LINGO编程(源程序及完整运行结果见附录),部分运行结果如下:
Globaloptimalsolutionfound.
Objectivevalue:
4806.000
Infeasibilities:
0.000000
Totalsolveriterations:
13
ModelClass:
LP
Totalvariables:
26
Nonlinearvariables:
0
Integervariables:
0
Totalconstraints:
30
Nonlinearconstraints:
0
Totalnonzeros:
148
Nonlinearnonzeros:
0
VariableValueReducedCost
P4208.0000.000000
Q598.00000.000000
SA175.000000.000000
SA210.000000.000000
SA30.0000000.000000
SA40.0000002.000000
SA560.000000.000000
SA655.000000.000000
SA70.00000012.00000
SA80.0000005.000000
SB10.00000011.00000
SB250.000000.000000
SB364.000000.000000
SB456.000000.000000
SB50.0000002.000000
SB60.00000011.00000
SB70.00000014.00000
SB80.0000003.000000
SC10.00000021.00000
SC20.00000016.00000
SC30.0000008.000000
SC40.0000002.000000
SC524.000000.000000
SC60.00000014.00000
SC772.000000.000000
SC864.000000.000000
从上述运行结果得知调整后的方案为:
调整后的总损失为:
4806元。
4.2.3模型的评价与分析:
在增加了供货量的限制条件后,只需在模型一的基础上再增加约束条件即得到模型二。
在本模型下日均花费最低为4806元。
新的调配方案如上图所示。
4.3问题三
4.3.1问题的分析:
本题的目标有二:
一、要满足每个菜市场的供货量充足;二、要使得总费用最低。
所以我们在模型一的基础上增加了上述两个限制条件,即得到模型三。
使得在供货量充足的情况下最小化日均费用。
4.3.2模型的建立与求解:
要足城市居民的蔬菜供应,增加蔬菜种植面积,则需要保证所有的菜市场都满足日需求量,在问题一得基础上作出以下调整:
同理,用LINGO编程求解(源程序及完整运行结果见附录),部分运行结果如下:
Globaloptimalsolutionfound.
Objectivevalue:
4770.000
Infeasibilities:
0.000000
Totalsolveriterations:
12
ModelClass:
LP
Totalvariables:
26
Nonlinearvariables:
0
Integervariables:
0
Totalconstraints:
22
Nonlinearconstraints:
0
Totalnonzeros:
124
Nonlinearnonzeros:
0
VariableValueReducedCost
P4770.0000.000000
Q0.0000000.6250000
SA175.000000.000000
SA240.000000.000000
SA30.0000000.000000
SA40.0000002.000000
SA530.000000.000000
SA655.000000.000000
SA70.00000012.00000
SA80.0000005.000000
SB10.00000011.00000
SB220.000000.000000
SB380.000000.000000
SB470.000000.000000
SB50.0000002.000000
SB60.00000011.00000
SB70.00000014.00000
SB80.0000003.000000
SC10.00000021.00000
SC20.00000016.00000
SC30.0000008.000000
SC40.0000002.000000
SC570.000000.000000
SC60.00000014.00000
SC790.000000.000000
SC880.000000.000000
从结果中可以的知:
故新增的蔬菜8000Kg全部运向C地,这样既能满足城市居民的蔬菜供应,又能使总损失最小,最小为:
4770元。
4.3.3模型的评价与分析:
本模型以供货充足和费用最低为目标,利用题中的约束条件解得:
在供货量充足的情况下日均花费最低为4770元。
并得到了全新的调配方案如上图所示,而且新增蔬菜8000Kg,且全部运向C地。
五模型的及评价与改进
5.1模型的评价
5.1.1模型的优点:
模型简单易懂,主要用了Froyd算法与线性规划,使问题的求解变得十分方便,能适应更重新的要求。
5.1.2模型的缺点:
上述模型第三问只考虑了运输费用最小,却没有考虑到供过于求造成的货物积压问题。
5.2模型的改进:
由于上述模型第三问只考虑了运输费用最小,却没有考虑到供过于求造成的货物积压问题。
可将存货损失计算进去,这样会使这个模型更加完善。
六参考文献
[1]姜启源,数学模型,北京,高等教育出版社,2003
[2]黄雍检、赖明勇,MATLAB语言在运筹学中的应用,长沙,湖南大学出版社,2005
七附件
问题一:
MATLAB新建m文件:
functiony=fld(n,x)
forr=1:
n
fori=1:
n
forj=1:
n
p(j)=x(i,j)+x(j,r);
end
y(r,i)=min(p);
end
end
输入命令:
d=[07inf54infinfinfinfinfinfinfinfinfinf;
707inf83infinfinfinfinfinfinfinfinf;
inf70infinf6inf711infinfinfinfinfinf;
5infinf06inf5infinf7infinfinfinfinf;
48inf60748infinfinfinfinfinfinf;
inf36inf70inf5infinfinfinfinfinfinf;
infinfinf54inf04infinf7infinfinfinf;
infinf7inf85406inf5infinfinfinf;
infinf11infinfinfinf60inf3inf6inf5;
infinfinf7infinfinfinfinf068inf10inf;
infinfinfinfinfinf753606infinfinf;
infinfinfinfinfinfinfinfinf860105inf;
infinfinfinfinfinfinfinf6infinf10011inf;
infinfinfinfinfinfinfinfinf10inf5110inf;
infinfinfinfinfinfinfinf5infinfinfinfinf0]
d1=d
d2=fld(15,d1)
d3=fld(15,d2)
d4=fld(15,d3)
运行结果:
d=
Columns1through14
07Inf54InfInfInfInfInfInfInfInfInf
707Inf83InfInfInfInfInfInfInfInf
Inf70InfInf6Inf711InfInfInfInfInf
5InfInf06Inf5InfInf7InfInfInfInf
48Inf60748InfInfInfInfInfInf
Inf36Inf70Inf5InfIn