一、题目要求
江平市是一个人口不到
20
20
20万人的小城市。根据该市的蔬菜种植情况，分别在菜市场
(
A
)
(A)
(A)，城乡路口
(
B
)
(B)
(B)和南街口
(
C
)
(C)
(C)设三个收购点，再由各收购点分送到全市的
8
8
8个菜市场，该市道路情况，各路段距离(单位：
100
m
100m
100m)及各收购点，菜市场
①
①
①到
⑧
⑧
⑧的具体位置见图
1
1
1。按常年情况，
A
、
B
、
C
A、B、C
A、B、C三个收购点每天收购量分别为
250
250
250，
200
200
200和
180
180
180(单位：
100
k
g
100 kg
100kg),各菜市场的每天需求量及发生供应短缺时带来的损失(元/
100
k
g
100kg
100kg)见表
1
1
1。设从收购点至各菜市场蔬菜调运费为
2
2
2元/(
100
k
g
.
100
m
100kg.100m
100kg.100m)。
试解决以下问题：
1.为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预期的短缺损失为最小；
2.若规定各菜市场短缺量一律不超过需求量的
25
25
25%，重新设计定点供应方案；
3.为满足城市居民的蔬菜供应，该市的领导规划增加蔬菜种植面积，试问增产的蔬菜每天应分别向
A
、
B
、
C
A、B、C
A、B、C三个采购点供应多少最经济合理。
本题目需要计算各收购点至各菜市场之间的最短路径，从而建立线性规划模型并进行求解。
2.1 求解两点间最短路径的算法
弗洛伊德算法(Floyd)又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法，也要高于执行|V|次SPFA算法。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。
缺点：时间复杂度比较高，不适合计算大量数据。
算法过程：1.从任意一条单边路径开始，所有两点之间的距离是边的权，用邻接矩阵G表示，如果两点之间没有边相连，则权为无穷大；
2.对于每一对顶点i和j，看看是否存在一个顶点k使得从i到k再到j比已知的路径更短。G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值变小，定义一个矩阵D用来记录所插入点的信息，则D[i][j]=k。
本次练习使用的是Floyd算法计算各收购点至各菜市场的最短路径。除了Floyd算法之外还有其他几种可以求解两点间最短路经的算法，详情可见
→
\rightarrow
→求解两点间最短路径的算法。
2.2 线性规划模型的建立与求解
线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题，一般用于求解最优化问题。因为其目标函数及约束条件均为线性函数，所以被称为线性规划问题。线性规划所研究的对象属于最优化的范畴，本质上是一个极值问题。
本次练习根据题目信息建立线性规划模型，使用MATLAB和Lingo两种方法求解。线性规划模型的建立与求解的相关知识详情可见
→
\rightarrow
→线性规划问题的模型建立与求解。
本次练习主要研究的是蔬菜供应方案的设计，即研究江平市 A 、 B 、 C A、B、C A、B、C三个蔬菜收购点向全市 ① ① ①到 ⑧ ⑧ ⑧八个菜市场供应的蔬菜量分别为多少时，满足蔬菜调运费及预期的短缺损失的总费用最小且最经济合理。题目中给出了蔬菜供应网点图和各蔬菜市场需求量表，需要我们通过建立线性规划模型并求解，得到在不同条件下使蔬菜调运费及预期的短缺损失的总费用为最小的蔬菜供应方案。
四、模型的建立与求解4.1 最短距离模型的建立与求解
首先，对图1的蔬菜供应网点图重新进行编号，结果如图2所示。
其次，建立各个网点的权值邻接矩阵G，如表2所示。
注：(1)[i, j]表示i，j网点直接相连时的距离；
(2)若j = i，表示网点自身和自身的距离为0；
(3)若i、j节点不直接相连，用Inf表示；
(4)表中A、B、C收购点分别对应节点4、6、13；
(5)表中1~8号菜市场分别对应节点1、2、8、12、10、3、15、14。
最后，根据Floyd算法过程可进行MATLAB编程，求得各收购点至各菜市场之间的最短距离如表3所示。
求解各收购点至各菜市场最短距离的代码如下：
- floyd.m
function [dist,mypath]=floyd(G,sb,db)
% 寻找i,j两点最短路径
% 输入：G为邻接矩阵，元素(Gij)是顶点i到j之间的直达距离，可以是有向的
% sb为起点的标号；db为终点的标号
% 输出：dist为最短路的距离；% mypath为最短路的路径
n=size(G,1); path=zeros(n);
for k=1:n
for i=1:n
for j=1:n
if G(i,j)>G(i,k)+G(k,j)
G(i,j)=G(i,k)+G(k,j);
path(i,j)=path(i,k);
end
end
end
end
dist=G(sb,db);
parent=path(sb,:); %从起点sb到终点db的最短路上各顶点的前驱顶点
parent(parent==0)=sb; %path中的分量为0，表示该顶点的前驱是起点
mypath=db; t=db;
while t~=sb % 得到sb到db的路线
p=parent(t); mypath=[p,mypath];
t=p;
end
- distance.m
% 输入基本数据
G=[0 7 5 4 inf inf inf inf inf inf inf inf inf inf inf;
7 0 inf 8 3 7 inf inf inf inf inf inf inf inf inf;
5 inf 0 6 inf inf 5 inf 7 inf inf inf inf inf inf;
4 8 6 0 7 inf 4 8 inf inf inf inf inf inf inf;
inf 3 inf 7 0 inf 5 5 inf inf inf inf inf inf inf;
inf 7 inf inf inf 0 inf 7 inf inf 11 inf inf inf inf;
inf inf 5 4 5 inf 0 4 inf 7 inf inf inf inf inf;
inf inf inf 8 5 7 4 0 inf 5 6 inf inf inf inf;
inf inf 7 inf inf inf inf inf 0 6 inf inf 8 inf 10;
inf inf inf inf inf inf 7 5 6 0 3 inf 6 inf inf;
inf inf inf inf inf 11 inf 6 inf 3 0 5 inf 6 inf;
inf inf inf inf inf inf inf inf inf inf 5 0 inf inf inf;
inf inf inf inf inf inf inf inf 8 6 inf inf 0 10 5;
inf inf inf inf inf inf inf inf inf inf 6 inf 10 0 11;
inf inf inf inf inf inf inf inf 10 inf inf inf 5 11 0]; %各个节点邻接矩阵
store=[80,70,90,80,120,70,100,90]; %各菜市场每天需求量
loss=[10,8,5,10,10,8,5,8]; %各菜市场每天短缺损失单价
storage=[250,200,180]; %各收购点每天收购量
No_ABC=[4,6,13]; %A、B、C三个收购点编号
No_v=[1,2,8,12,10,3,15,14]; %1-8八个菜市场编号
% 寻找收购点到菜市场最短距离
for i=1:8
for j=1:3
sb=No_v(i);db=No_ABC(j);
[dist,mypath]=floyd(G,sb,db);
dis(j,i)=dist;
end
end
dis
4.2 问题一模型的建立与求解
对问题一进行分析，根据使用Floyd算法计算的各收购点至各菜市场之间的最短路径，从而确定调运费函数和短缺损失函数，对调运费函数和短缺损失函数求和得到目标函数，根据题目中的条件写出相应的等式和不等式约束，然后使用MATLAB和Lingo两种方法求得该线性规划问题的最优解。
4.2.1 总费用函数
总费用函数包括调运费函数和短缺损失函数两部分。
调运费函数=调运单价×调运量×调运最短距离
P
=
2
∑
i
=
1
8
(
D
A
i
M
A
i
+
D
B
i
M
B
i
+
D
C
i
M
C
i
)
P=2\sum_{i=1}^{8}\left ( D_{Ai}M_{Ai}+ D_{Bi}M_{Bi} +D_{Ci}M_{Ci} \right )
P=2i=1∑8(DAiMAi+DBiMBi+DCiMCi)
其中，调运单价为
2
2
2元/(
100
k
g
⋅
100
m
100kg·100m
100kg⋅100m)；调运量为未知量，
M
A
i
、
M
B
i
、
M
C
i
M_{Ai}、M_{Bi}、M_{Ci}
MAi、MBi、MCi分别表示
A
、
B
、
C
A、B、C
A、B、C三个收购点到第
i
i
i个菜市场的调运量；调运最短距离由Floyd算法已经得出，
D
A
i
、
D
B
i
、
D
C
i
D_{Ai}、D_{Bi}、D_{Ci}
DAi、DBi、DCi分别表示
A
、
B
、
C
A、B、C
A、B、C三个收购点到第
i
i
i个菜市场的调运最短距离。
短缺损失函数=(需求量-调运量)×短缺损失单价
Q
=
∑
i
=
1
8
[
(
n
e
e
d
i
−
(
M
A
i
+
M
B
i
+
M
C
i
)
)
∗
l
o
s
s
i
]
Q=\sum_{i=1}^{8}\left [ \left (need_{i}-\left ( M_{Ai}+M_{Bi}+M_{Ci} \right ) \right )*loss_{i}\right ]
Q=i=1∑8[(needi−(MAi+MBi+MCi))∗lossi]
其中，各个菜市场的需求量和短缺损失单价可由表1得出，第
i
i
i个菜市场的需求量用
n
e
e
d
i
need_{i}
needi表示、短缺损失单价用
l
o
s
s
i
loss_{i}
lossi表示；调运量为未知量，
M
A
i
、
M
B
i
、
M
C
i
M_{Ai}、M_{Bi}、M_{Ci}
MAi、MBi、MCi分别表示
A
、
B
、
C
A、B、C
A、B、C三个收购点到第
i
i
i个菜市场的调运量。
总费用函数=调运费函数+短缺损失函数
R
=
P
+
Q
=
(
2
D
−
l
o
s
s
)
T
M
+
n
e
e
d
T
l
o
s
s
R=P+Q=\left ( 2D-loss \right )^{T}M+need^{T}loss
R=P+Q=(2D−loss)TM+needTloss
4.2.2 目标函数和约束条件
根据题目要求，A、B、C三个蔬菜收购点向全市①到⑧八个菜市场的总供应量不能超过各菜市场的需求量，且各收购点的供应量不能超过自身的收购量，假设其供应量刚好等于收购量，所以问题一的目标函数和约束函数如下所示。
目标函数：
m
i
n
P
+
Q
minP+Q
minP+Q
约束条件：①到⑧八个菜市场需求量的约束条件如下。 A、B、C三个蔬菜收购点收购量的约束条件如下。
4.2.3 问题一模型的求解
-
使用Lingo求解
使用Lingo求解问题一模型可得供应方案如图3所示，供应量单位为100kg。图3 问题一供应方案
使用Lingo求解问题一模型得到最小蔬菜调运费及预期的短缺损失的总费用为10280元。
使用Lingo求解问题一模型的代码如下：
- problem_1.lg4
model:
min=(80-Ma1-Mb1-Mc1)*10+(70-Ma2-Mb2-Mc2)*8+(90-Ma3-Mb3-Mc3)*5+(80-Ma4-Mb4-Mc4)*10+(120-Ma5-Mb5-Mc5)*10+
(70-Ma6-Mb6-Mc6)*8+(100-Ma7-Mb7-Mc7)*5+(90-Ma8-Mb8-Mc8)*8+(4*Ma1+8*Ma2+8*Ma3+19*Ma4+11*Ma5+6*Ma6+22*Ma7+20*Ma8+
14*Mb1+7*Mb2+7*Mb3+16*Mb4+12*Mb5+16*Mb6+23*Mb7+17*Mb8+20*Mc1+12*Mc2+11*Mc3+14*Mc4+6*Mc5+15*Mc6+5*Mc7+10*Mc8)*2;
Ma1+Mb1+Mc1<=80;
Ma2+Mb2+Mc2<=70;
Ma3+Mb3+Mc3<=90;
Ma4+Mb4+Mc4<=80;
Ma5+Mb5+Mc5<=120;
Ma6+Mb6+Mc6<=70;
Ma7+Mb7+Mc7<=100;
Ma8+Mb8+Mc8<=90;
Ma1+Ma2+Ma3+Ma4+Ma5+Ma6+Ma7+Ma8=250;
Mb1+Mb2+Mb3+Mb4+Mb5+Mb6+Mb7+Mb8=200;
Mc1+Mc2+Mc3+Mc4+Mc5+Mc6+Mc7+Mc8=180;
end
-
使用MATLAB求解
对问题一模型进行MATLAB编程求解得到A、B、C收购点对①-⑧菜市场的供应方案及产生的总费用的结果与使用Lingo求解得到的结果相同。
使用MATLAB求解问题一模型的代码如下： - problem_1.m
%计算损失费用(Problem1)
aim_f=zeros(1,24); %形成目标函数f
for i=1:8
for j=1:3
aim_f(j+3*(i-1))=2*dis(j,i)-loss(i);
end
end
f=aim_f'; %形成目标函数f
aim_eq=zeros(3,24); %形成等式约束Aeq
for i=1:3
for j=1:8
aim_eq(i,3*(j-1)+i)=1;
end
end
aim_st=zeros(8,24); %形成不等式约束A
for i=1:8
for j=1:3
aim_st(i,3*(i-1)+j)=1;
end
end
A=aim_st;
b=store'; %形成不等式约束
Aeq=aim_eq;
beq=storage'; %形成等式约束
lb=zeros(24,1);
[M1,fval1] = linprog(f,A,b,Aeq,beq,lb,[],[]);
M1 %在约束条件成立的情况下，目标函数f最小时的解
LossPrice1=sum(store.*loss)+fval1;
LossPrice1 %
m1=zeros(3,8);
for i=1:8
for j=1:3
m1(j,i)=M1(3*(i-1)+j); %ABC收购点对1-8个菜市场的供应方案
end
end
4.3 问题二模型的建立与求解
问题二研究的是当规定各菜市场短缺量一律不超过需求量的25%时，A、B、C三个蔬菜收购点向全市①到⑧八个菜市场供应的蔬菜量分别为多少，满足蔬菜调运费及预期的短缺损失最小。
4.3.1 问题二模型的建立
根据对问题二的分析，可以得到问题二的模型需在问题一所建立的模型基础上增加一个各菜市场的供应量不低于需求量的75%的约束再去求解即可。
约束条件：增加的①到⑧八个菜市场的供应量不低于需求量的75%的约束条件如下。
4.3.2 问题二模型的求解
-
使用Lingo求解
使用Lingo求解问题二模型可得供应方案如图4所示，供应量单位为100kg。图4 问题二Lingo求解供应方案
使用Lingo求解问题二模型得到最小蔬菜调运费及预期的短缺损失的总费用为10520元。
使用Lingo求解问题二模型的代码如下：
- problem_2.lg4
model:
min=(80-Ma1-Mb1-Mc1)*10+(70-Ma2-Mb2-Mc2)*8+(90-Ma3-Mb3-Mc3)*5+(80-Ma4-Mb4-Mc4)*10+(120-Ma5-Mb5-Mc5)*10+
(70-Ma6-Mb6-Mc6)*8+(100-Ma7-Mb7-Mc7)*5+(90-Ma8-Mb8-Mc8)*8+(4*Ma1+8*Ma2+8*Ma3+19*Ma4+11*Ma5+6*Ma6+22*Ma7+20*Ma8+
14*Mb1+7*Mb2+7*Mb3+16*Mb4+12*Mb5+16*Mb6+23*Mb7+17*Mb8+20*Mc1+12*Mc2+11*Mc3+14*Mc4+6*Mc5+15*Mc6+5*Mc7+10*Mc8)*2;
Ma1+Mb1+Mc1<=80;
Ma2+Mb2+Mc2<=70;
Ma3+Mb3+Mc3<=90;
Ma4+Mb4+Mc4<=80;
Ma5+Mb5+Mc5<=120;
Ma6+Mb6+Mc6<=70;
Ma7+Mb7+Mc7<=100;
Ma8+Mb8+Mc8<=90;
Ma1+Mb1+Mc1>=80*0.75;
Ma2+Mb2+Mc2>=70*0.75;
Ma3+Mb3+Mc3>=90*0.75;
Ma4+Mb4+Mc4>=80*0.75;
Ma5+Mb5+Mc5>=120*0.75;
Ma6+Mb6+Mc6>=70*0.75;
Ma7+Mb7+Mc7>=100*0.75;
Ma8+Mb8+Mc8>=90*0.75;
Ma1+Ma2+Ma3+Ma4+Ma5+Ma6+Ma7+Ma8=250;
Mb1+Mb2+Mb3+Mb4+Mb5+Mb6+Mb7+Mb8=200;
Mc1+Mc2+Mc3+Mc4+Mc5+Mc6+Mc7+Mc8=180;
end
-
使用MATLAB求解
使用Matlab求解问题二模型可得供应方案如图5所示，供应量单位为100kg。图5 问题二Matlab求解供应方案
使用Matlab求解问题二模型得到最小蔬菜调运费及预期的短缺损失的总费用为10520元。
使用MATLAB求解问题二模型的代码如下：
- problem_2.m
%%计算损失费用(Problem2)
aim_f=zeros(1,24); %形成目标函数f
for i=1:8
for j=1:3
aim_f(j+3*(i-1))=2*dis(j,i)-loss(i);
end
end
f=aim_f'; %形成目标函数f
aim_eq=zeros(3,24); %形成等式约束Aeq
for i=1:3
for j=1:8
aim_eq(i,3*(j-1)+i)=1;
end
end
aim_st=zeros(8,24); %形成不等式约束A
for i=1:8
for j=1:3
aim_st(i,3*(i-1)+j)=1;
end
end
z=zeros(8,24);
for i=1:8
for j=1:3
z(i,3*(i-1)+j)=-1;
end
end
A=[aim_st;z];
b=[store';-0.75.*store'];
Aeq=aim_eq;
beq=storage';
lb=zeros(24,1);
[M2,fval2] = linprog(f,A,b,Aeq,beq,lb,[],[]);
LossPrice2=sum(store.*loss)+fval2;
M2
LossPrice2
m2=zeros(3,8);
for i=1:8
for j=1:3
m2(j,i)=M2(3*(i-1)+j);
end
end
经过对比图4和图5的数据发现，使用Lingo求解问题二中A、B、C收购点对①-⑧菜市场的具体供应方案与使用Matlab求解得到的具体供应方案有所差异，但A、B、C收购点对每个菜市场的总供应量相同，蔬菜调运费及预期的短缺损失的总费用也相同，均为10520元。
4.4 问题三模型的建立与求解
问题三研究的为满足城市居民的蔬菜供应，该市的领导规划增加蔬菜种植面积使得供货充足的情况下，A、B、C三个蔬菜收购点向全市①到⑧八个菜市场供应的蔬菜量分别为多少最经济合理。
4.4.1 问题三模型的建立
由题目条件可知原来A、B、C三个蔬菜收购点的总收购量只有63000kg，而①到⑧八个菜市场的总需求量有70000kg，供应不足。因此为满足每日需求，可以通过提高A、B、C三个蔬菜收购点的收购量去弥补菜市场的短缺损失，使其总和大于所有菜市场的需求量。为满足最经济合理，使各个菜市场供应量刚好等于需求量。所以在问题一所建立的模型基础上修改菜市场需求量和蔬菜收购点收购量的约束条件再去求解即可。
约束条件：①到⑧八个菜市场需求量的约束条件如下。 A、B、C三个蔬菜收购点收购量的约束条件如下。
4.4.2 问题三模型的求解
-
使用Lingo求解
使用Lingo求解问题三模型可得供应方案如图6所示，供应量单位为100kg。图6 问题三Lingo求解供应方案
使用Lingo求解问题三模型得到通过增加蔬菜种植面积所增产的蔬菜每天只需向C收购点供应7000kg最经济合理，得到最小蔬菜调运费及预期的短缺损失的总费用为11200元。
使用Lingo求解问题三模型的代码如下：
- problem_3.lg4
model:
min=(80-Ma1-Mb1-Mc1)*10+(70-Ma2-Mb2-Mc2)*8+(90-Ma3-Mb3-Mc3)*5+(80-Ma4-Mb4-Mc4)*10+(120-Ma5-Mb5-Mc5)*10+(70-Ma6
-Mb6-Mc6)*8+(100-Ma7-Mb7-Mc7)*5+(90-Ma8-Mb8-Mc8)*8+(4*Ma1+8*Ma2+8*Ma3+19*Ma4+11*Ma5+6*Ma6+22*Ma7+20*Ma8+14*Mb1
+7*Mb2+7*Mb3+16*Mb4+12*Mb5+16*Mb6+23*Mb7+17*Mb8+20*Mc1+12*Mc2+11*Mc3+14*Mc4+6*Mc5+15*Mc6+5*Mc7+10*Mc8)*2;
Ma1+Mb1+Mc1=80;
Ma2+Mb2+Mc2=70;
Ma3+Mb3+Mc3=90;
Ma4+Mb4+Mc4=80;
Ma5+Mb5+Mc5=120;
Ma6+Mb6+Mc6=70;
Ma7+Mb7+Mc7=100;
Ma8+Mb8+Mc8=90;
Ma1+Ma2+Ma3+Ma4+Ma5+Ma6+Ma7+Ma8>=250;
Mb1+Mb2+Mb3+Mb4+Mb5+Mb6+Mb7+Mb8>=200;
Mc1+Mc2+Mc3+Mc4+Mc5+Mc6+Mc7+Mc8>=180;
Ma1+Ma2+Ma3+Ma4+Ma5+Ma6+Ma7+Ma8+Mb1+Mb2+Mb3+Mb4+Mb5+Mb6+Mb7+Mb8+Mc1+Mc2+Mc3+Mc4+Mc5+Mc6+Mc7+Mc8>=700;
end
-
使用MATLAB求解
使用Matlab求解问题三模型可得供应方案如图7所示，供应量单位为100kg。图7 问题三Matlab求解供应方案
使用Matlab求解问题三模型得到通过增加蔬菜种植面积所增产的蔬菜每天只需向C收购点供应7000kg最经济合理，得到最小蔬菜调运费及预期的短缺损失的总费用为11200元。
使用MATLAB求解问题三模型的代码如下：
- problem_3.m
% 计算增产蔬菜对ABC的供应量(Problem3)
aim_f=zeros(1,24); %形成目标函数f
for i=1:8
for j=1:3
aim_f(j+3*(i-1))=2*dis(j,i)-loss(i);
end
end
f=aim_f'; %形成目标函数f
aim_st=zeros(8,24); %形成不等式约束A
for i=1:8
for j=1:3
aim_st(i,j+3*(i-1))=1;
end
end
y=zeros(3,24); %形成不等式约束A
for i=1:3
for j=1:8
y(i,3*(j-1)+i)=-1;
end
end
A=[y;-ones(1,24)]; %形成不等式约束
b=[-storage';-700]; %形成不等式约束
Aeq=aim_st;
beq=store';
lb=zeros(24,1);
[M3,fval3] = linprog(f,A,b,Aeq,beq,lb,[],[]);
LossPrice3=sum(store.*loss)+fval3;
M3
LossPrice3
m3=zeros(3,8);
for i=1:8
for j=1:3
m3(j,i)=M3(3*(i-1)+j);
end
end
经过对比图6和图7的数据发现，使用Lingo求解问题三中A、B、C收购点对①-⑧个菜市场的具体供应方案与使用Matlab求解得到的具体供应方案有所差异，但A、B、C收购点对每个菜市场的总供应量相同，得到增产的蔬菜供应方案相同，均为每天只向C收购点每天供应7000kg最经济合理，最小蔬菜调运费及预期的短缺损失的总费用也相同，均为11200元。
五、结果分析本次练习通过对江平市A、B、C三个蔬菜收购点向全市①到⑧八个菜市场的蔬菜供应方案的设计问题进行研究，使用Floyd算法计算各收购点至各菜市场之间的最短路径，根据题目信息建立线性规划模型并对不同条件下的三个问题分别用两种方法进行模型求解。对求解结果进行分析可知，即使两种方法对问题二和问题三模型求得的具体供应方案有所差异，但求解的最小蔬菜调运费及预期的短缺损失的总费用是相同的。通过对两种方法的对比分析进一步验证了模型建立及求解的准确性。