《光明市的菜篮子工程(DOC33页)》由会员分享，可在线阅读，更多相关《光明市的菜篮子工程(DOC33页)（55页珍藏版）》请在金锄头文库上搜索。
1、编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页 共1页光明市的菜篮子工程摘要本文研究的是蔬菜市场为满足不同条件的最优调配方案问题，用了Froyd算法、线性规划建立了一系列数学规划模型，并用MATLAB和LINGO软件编程实现。关于问题一：用Froyd算法结合MATLAB编程求出收购点至个菜市场的最短距离，以用于蔬菜调运及预期的短缺损失为最小为目标建立线性规划模型。用LINGO编程求得日均费用最少为4610元。关于问题二：在模型一的基础增加各菜市场短缺量一律不超过需求量的20%的约束条件，用LINGO编程求得最少日均费用以及最优供应方案。费用最少为4806元，供应方安见
2、正文。 关于问题三：在模型一的基础上，改为以供货充足、费用最小为目标，建立模型三，用LINGO编程求得日均费用为4770元，增产的蔬菜每天应分给C收购点8000Kg。关键字：蔬菜市场调配方案 Froyd算法 线性规划一、问题的重述海江市是一个人口不到20万人的小城市。根据该市的蔬菜种植情况，分别在菜市场（A），菜市场（B）和菜市场（C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位：100m）及各收购点，菜市场的具体位置见图3.2.按常年情况，A,B,C三个收购点每天收购量分别为30000，25000和20000（单位：100 kg）,各菜市场的每天需求量及发
3、生供应短缺时带来的损失（元/100kg）见表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) 为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预期的短缺损失为最小；(b) 若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案；(c) 为满足城市居民的蔬菜供应，光明市的领导
4、规划增加蔬菜种植面积，试问增产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。二、 符号说明 从A到i（各个菜市场）的最短距离 从B到i（各个菜市场）的最短距离 从C到i（各个菜市场）的最短距离 从A到i（各个菜市场）的运货量 从B到i（各个菜市场）的运货量 从C到i（各个菜市场）的运货量 总调运费 短缺损失 总费用三 模型假设1、 假设日需求量与缺货损失费用不变。2、 假设在蔬菜调配的过程中无意外发生。3、 假设新增产的蔬菜能够满足缺货量。四 模型的建立与求解4.1问题一4.1.1问题的分析：为了使用于蔬菜调运及预期的短缺损失为最小，即调运费用与缺货损失之和最小。首先考虑调运费用P
5、，P为距离与送货量的积，因为与送货距离相关，我们必须先求出A、B、C三个采购点至各个菜市场的最短距离。采用Froyd算法，结合MATLAB编程实现。其次考虑缺货损失Q，以题中要求为约束条件，损失最低位目标建立线性规划模型，用LINGO编程求解。4.1.2模型的建立与求解：由图和表格的信息知，建立一个线性规划模型，使得蔬菜调运及预期的短缺损失为最小。调运总费用P为： 若使调运总费用最少，则应保证A、B、C三个收购点到8个菜市场的路程最短，最短路线的求解过程如图一：图一：求解过程图分析上图可知，该路线为无向网络，就该图而言，网络弧集为：E=(v1,v2),(v1,v4),(v1,v5),(v2,v
6、1),(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),(v
7、10,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,3n=inf,当（,）不属于E时。（inf为无穷大，n为网络结点个数）按上述规定，该网络的权矩阵为：0 7 inf 5 4 inf in
8、f inf inf inf inf inf inf inf inf7 0 7 inf 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
9、inf inf 7 inf inf inf infinf inf 7 inf 8 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 i
10、nf inf 10 0 11 infinf inf inf inf inf inf inf inf inf 10 inf 5 11 0 infinf inf inf inf inf inf inf inf 5 inf inf inf inf inf 0因为上述网络有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故只
11、需要取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 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 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
