光明市的菜篮子工程.docx
《光明市的菜篮子工程.docx》由会员分享，可在线阅读，更多相关《光明市的菜篮子工程.docx（64页珍藏版）》请在冰点文库上搜索。
光明市的菜篮子工程
光明市的菜篮子工程
摘要
本文研究的是蔬菜市场为满足不同条件的最优调配方案问题，用了Froyd算法、线性规划建立了一系列数学规划模型，并用MATLAB和LINGO软件编程实现。
关于问题一：
用Froyd算法结合MATLAB编程求出收购点至个菜市场的最短距离，以用于蔬菜调运及预期的短缺损失为最小为目标建立线性规划模型。
用LINGO编程求得日均费用最少为4610元。
20%
关于问题二：
在模型一的基础增加各菜市场短缺量一律不超过需求量的
的约束条件，用LINGO编程求得最少日均费用以及最优供应方案。
费用最少为
4806元，供应方安见正文。
关于问题三：
在模型一的基础上，改为以供货充足、费用最小为目标，建立模型三，用LINGO编程求得日均费用为4770元，增产的蔬菜每天应分给C收购点8000Kg。
关键字：
蔬菜市场调配方案Froyd算法线性规划
一、问题的重述
海江市是一个人口不到20万人的小城市。
根据该市的蔬菜种植情况，分别在菜市场（A），菜市场（B）和菜市场（C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位：
100m）及各收购点，菜市场①L⑧的具体位置见图32按常年情况，A,B,C三个收购点每天收购量分别为30000，25000和20000（单位：
100kg），各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表3.设从收购点至各菜市场蔬菜调运费为1元/（100kg.100m）.
①7②
11
11
表3
菜市场
每天需求（100kg）
短缺损失（元/100kg）
①
150
10
②
100
8
③
120
5
④
100
10
⑤
140
10
⑥
100
8
⑦
140
5
⑧
120
8
（a）为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预
期的短缺损失为最小；
（b）若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案;
（c）为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增
产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。
二、符号说明
DBii
1,2…
…8
从B到i
（各个菜市场）
DCii
1,2…
…8
从C到i
（各个菜市场）
SAii
1,2…
…8
从A到i
（各个菜市场）
SBii
1,2…
…8
从B到i
（各个菜市场）
SCii
1,2…
…8
从C到i
（各个菜市场）
P
总调运费
Q
短缺损失
R
总费用
的最短距离的最短距离的运货量的运货量的运货量
3模型假设
1、假设日需求量与缺货损失费用不变。
2、假设在蔬菜调配的过程中无意外发生。
3、假设新增产的蔬菜能够满足缺货量。
4模型的建立与求解
4.1问题一
4.1.1问题的分析：
为了使用于蔬菜调运及预期的短缺损失为最小，即调运费用与缺货损失之和最小。
首先考虑调运费用P，P为距离与送货量的积，因为与送货距离相关，我们必须先求出A、B、C三个采购点至各个菜市场的最短距离。
采用Froyd算法，结合MATLAB编程实现。
其次考虑缺货损失Q，以题中要求为约束条件，损失最低位目标建立线性规划模型，用LINGO编程求解。
4.1.2模型的建立与求解：
由图和表格的信息知，建立一个线性规划模型，使得蔬菜调运及预期的短缺损失为最小。
调运总费用P为：
图一：
求解过程图
分析上图可知，该路线为无向网络，就该图而言，网络弧集为：
E=[（v1,v2）,（v1,v4）,（v1,v5）,（v2,v1）,（v2,v3）,（v2,v5）,（v2,v6）,（v3,v2）,.（v3,v6）,（v
3,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,v
9）,（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,v
13）,（v12,v14）,（v13,v9）,（v13,v12）,（v13,v14）,
（v14,v10）,（v14,v12）,（v14,v13）,（v15,v9）]
面来确定网络权矩阵：
W=（wij）nn
其中
Wii=lj，当（Vi,Vj）属于E时，lij为弧（Vi,Vj）的权
Wi=0,i=1,2,3n
Wj=inf,当（v,Vj）不属于E时。
（inf为无穷大，n为网络结点个数）
按上述规定，该网络的权矩阵为：
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
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
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
0
因为上述网络有15个结点，故网络的权矩阵均为15阶矩阵。
现在给出网络最短路线的Froyd算法：
（1）d1=w.（w为所给网络的n阶权矩阵）
（2）dk=（dkj）nn,k=2,3,…,p.
其中dkj=min[d（k1h+d（k1）司，i,j=1,2,….
计算次数的确定：
当wij0时，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为：
0
7
14
5
4
10
8
12
18
12
15
20
24
22
23
7
0
7
12
8
3
12
8
14
19
13
19
20
24
19
14
7
0
16
13
6
11
7
11
18
12
18
17
23
16
5
12
16
0
6
13
5
9
15
7
12
15
21
17
20
4
8
13
6
0
7
4
8
14
13
11
17
20
22
19
10
3
6
13
7
0
9
5
11
16
10
16
17
21
16
8
12
11
5
4
9
0
4
10
12
7
13
16
18
15
12
8
7
9
8
5
4
0
6
11
5
11
12
16
1
1
18
14
11
15
14
11
10
6
0
9
3
9
6145
12
19
18
7
13
16
12
11
9
0
6
8
15
10
14
15
13
12
12
11
10
7
5
3
6
0
6
9
11
8
20
19
18
15
17
16
13
11
9
8
6
0
10
5
14
24
20
17
21
20
17
16
12
6
15
9
10
0
11
11
22
24
23
17
22
21
18
16
14
10
11
5
11
0
19
23
19
16
20
19
16
15
11
5
14
8
14
11190
d4即为该网络的距离矩阵，距离矩阵的第i行指明了Vi到其他各点的最短距离。
根据上述矩阵，分别找出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
调运量的限制:
短缺损失费为：
Q1075SA1SB1SC1
860SA2SB2SC2
580SA3SB3SC3
1070SA4SB4SC4
10100SA5SB5SC5
855Sa6Sb6Sd6
590SA7SB7SC7
880SA8SB8SC8
总费用为：
R
PQ
由以上约束条件，用LINGO软件进行线性规划求解（源程序及完整运行结果见
附录），部分运行结果如下：
Globaloptimalsolutionfound.
Totalsolveriterations:
10
ModelClass:
LP
Totalvariables:
26
Nonlinearvariables:
0
Integervariables:
0
Totalconstraints:
22
Nonlinearconstraints:
0
Totalnonzeros:
124
Nonlinearnonzeros:
0
Variable
Value
ReducedCost
P
3890.000
0.000000
0.000000
Q
720.0000
0.000000
SA1
75.00000
0.000000
SA2
0.000000
0.000000
SA3
0.000000
SA4
0.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
SB8
0.000000
3.000000
SC1
0.000000
21.00000
SC2
0.000000
16.00000
SC3
0.000000
2.000000
SC5
0.000000
SC6
14.00000
SC7
0.000000
SC8
0.000000
30.00000
0.000000
90.00000
40.00000
从上述运行结果中可以得出调运方案为:
在此种方案下，蔬菜调运及预期的短缺损失为最小，最小金额为4610元。
4.1.3模型的评价与分析：
本模型用Froyd算法快捷的求出了A、B、C三个收购点到8个菜市场的最短路程，用线性规划模型使得费用最低，并给出了上图所示的调配方案。
在所得方案中每日只需4610元。
4.2问题二
4.2.1问题的分析：
若按规定各菜市场短缺量一律不超过需求量的20%，则只需要在模型一的
基础上在增加一个约束条件：
每个菜市场的供应量必须不低于需求量的80%即
4.2.2模型的建立与求解：
各菜市场短缺量一律不超过需求量的20%，为满足这一条件，现对方案一
进行调整。
只需在方案一中加一限制条件：
SA1
SB1
SC1
75
0.8
60
SA2
SB2
SC2
60
0.8
48
SA3
SB3
SC3
80
0.8
64
SA4
SB4
SC4
70
0.8
56
SA5
SB5
SC5
100
0.8
80
SA6
SB6
SC6
55
0.8
44
SA7
SB7
SC7
90
0.8
72
SA8
SB8
SC8
80
0.8
64
同理可用LINGO编程（源程序及完整运行结果见附录），部分运行结果如
下：
Globaloptimalsolutionfound.
Objectivevalue:
4806.000
Infeasibilities:
0.000000
13
Totalsolveriterations:
Totalvariables:
26
Nonlinearvariables:
0
Integervariables:
0
Totalconstraints:
30
Nonlinearconstraints:
0
Totalnonzeros:
148
Nonlinearnonzeros:
0
Variable
Value
ReducedCost
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.00000
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
64.00000
0.000000
从上述运行结果得知调整后的方案为:
调整后的总损失为：
4806元
423模型的评价与分析：
在增加了供货量的限制条件后，只需在模型一的基础上再增加约束条件即得
到模型二。
在本模型下日均花费最低为4806元。
新的调配方案如上图所示。
4.3问题三
4.3.1问题的分析：
本题的目标有二：
一、要满足每个菜市场的供货量充足；二、要使得总费用最低。
所以我们在模型一的基础上增加了上述两个限制条件，即得到模型三。
使得在供货量充足的情况下最小化日均费用。
4.3.2模型的建立与求解：
要足城市居民的蔬菜供应，增加蔬菜种植面积，则需要保证所有的菜市场都
满足日需求量，在问题一得基础上作出以下调整：
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
同理，用LINGO编程求解（源程序及完整运行结果见附录），部分运行结果
如下:
Globaloptimalsolutionfound.
Totalsolveriterations:
12
ModelClass:
LP
Totalvariables:
26
Nonlinearvariables:
0
Integervariables:
0
Totalconstraints:
22
Nonlinearconstraints:
0
Totalnonzeros:
124
Nonlinearnonzeros:
0
Variable
Value
ReducedCost
P
4770.000
0.000000
0.6250000
Q
0.000000
0.000000
SA1
75.00000
0.000000
SA2
40.00000
0.000000
SA3
0.000000
SA4
0.000000
SA5
30.00000
0.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.000000
2.000000
SC4
0.000000
0.000000
SC5
70.00000
14.00000
SC6
0.000000
0.000000
SC7
90.00000
0.000000
SC8
80.00000
从结果中可以的知：
SA1
SA2
SA5
SA6200
SB2
SB3
SB4
170
SC5
SC7
SC8
240
故新增的蔬菜8000Kg全部运向C地，这样既能满足城市居民的蔬菜供应，
4.3.3模型的评价与分析：
本模型以供货充足和费用最低为目标，利用题中的约束条件解得：
在供货量充足的情况下日均花费最低为4770元。
并得到了全新的调配方案如上图所示，而且新增蔬菜8000Kg，且全部运向C地。
5模型的及评价与改进
5.1模型的评价
5.1.1模型的优点：
模型简单易懂，主要用了Froyd算法与线性规划，使问题的求解变得十分方便，能适应更重新
升级会员 