光明市的菜篮子工程Word文件下载.doc
《光明市的菜篮子工程Word文件下载.doc》由会员分享，可在线阅读，更多相关《光明市的菜篮子工程Word文件下载.doc（48页珍藏版）》请在冰点文库上搜索。
756
6⑤35④
866
10C10⑧
511
⑦
表3
菜市场
每天需求（100kg）
短缺损失（元/100kg）
①
150
10
②
100
8
③
120
5
④
⑤
140
⑥
⑦
⑧
（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由下式确定：
pln（n-1）/ln2，这样的dp就确定了网络各点间的最短距离。
此处n=15,解出p3.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
19
11
6
22
20
B
14
7
16
12
23
17
C
15
调运量的限制：
短缺损失费为：
总费用为：
由以上约束条件，用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
从上述运行结果中可以得出调运方案为：
收购点A
菜市场①，运量为75
菜市场⑤，运量为70
菜市场⑥，运量为55
收购点B
菜市场②，运量为60
菜市场③，运量为80
菜市场④，运量为30
收购点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编程（源程序及完整运行结果见附录），部分运行结果如下：
4806.000
13
30
148
P4208.0000.000000
Q598.00000.000000
SA210.000000.000000
SA5
升级会员 