大学生数学建模竞赛—菜篮子工程中蔬菜种植问题.docx

2015年吉林省大学生数学建模竞赛

承 诺 书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D/E中选择一项填写）：
我们的报名参赛队号为（8位数字组成的编号）：

所属学校（请填写完整的全名）：
参赛队员 (打印并签名) ：1.
2.
3.
指导教师或指导教师组负责人 (打印并签名)：
（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）
日期： 年 月 日

赛区评阅编号（由赛区组委会评阅前进行编号）：

18 / 18
2015年吉林省大学生数学建模竞赛

编 号 专 用 页

赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

评
阅
人

评
分

备
注

菜篮子工程中的蔬菜种植问题

摘要
菜篮子工程中的蔬菜种植问题研究了如何利用现有的交通运输条件制定出一套调运方案，使得政府的短缺补偿和运费补贴最少。本文首先介绍了什么是最短路问题，设计最短路问题的基本思路等。然后介绍了运输问题的线性规划模型以及线性规划问题的解法。最后提出了菜篮子工程中的蔬菜种植问题，进行了问题分析、模型建立、模型求解以及结果分析等一系列过程。最后对模型进行优化，提出菜篮子工程相关问题的改进方案。

关键字：运输问题，最短路径，线性规划，模型建立

一 问题背景及重述

1.1问题背景
JG市的人口近90万，该市在郊区和农区建立了8个蔬菜种植基地，承担全市居民的蔬菜供应任务，每天将蔬菜运送到市区的35个蔬菜销售点，市区有15个主要交通路口，在蔬菜运送的过程中从蔬菜种植基地可以途经这些交通路口再到达蔬菜销售点。如果蔬菜销售点的需求量不能满足，则市政府要给予一定的短缺补偿，同时市政府还按照蔬菜种植基地供应蔬菜的数量以及路程，发放相应的运费补贴，以此提高蔬菜种植的积极性，运费补贴标准为0.04元/（1吨.1公里）。为了使二者之和最小，应提出一个经济合理的定点供应方案。此外，根据蔬菜的需求量等实际问题的改变，适当调整种植计划和蔬菜运输方案。

1.2 问题重述
具体问题如下：
1、(1) 设计蔬菜运送方案，使政府的短缺补偿和运费补贴最少；
(2) 规定各蔬菜销售点的短缺量一律不超过需求量的30%，重新设计蔬菜运送方案。
2、扩大蔬菜种植基地规模，增加蔬菜种植面积。建立问题的数学模型，确定8个蔬菜种植基地的新增蔬菜种植量，并重新设计蔬菜运送方案，使总短缺补偿和运费补贴最少。
3、 每个蔬菜种植基地可种植12种蔬菜，在问题（3）得到的各个蔬菜种植基地日蔬菜供应量的基础上，建立数学模型，给出问题的求解算法，确定每个蔬菜种植基地的种植计划，并重新设计蔬菜运送方案，使总短缺补偿和运费补贴最少。
4、 政府如何进一步完善和制定相应的扶持政策，使得菜农有种植蔬菜的积极性，居民可以得到质优价低的新鲜蔬菜，同时还能够逐渐减少或者不用政府投入补贴，形成问题的描述，并建立数学模型，给出数值结果。

二 问题分析和模型的建立
2.1 问题分析
对于上述问题，为了研究以及求解的方便，做出如下的基本假设：
（1）只考虑运输补贴和短缺补偿的费用，不考虑装卸、人工等其他费用；
（2）假设日需求量与缺货损失费用不变；
（3）假设运输的蔬菜路途中没有损耗且无任何意外发生；
（4）假设各市场蔬菜只来源于8个蔬菜种植基地，而无其他额外的来源；
（5）假设各收购站供应蔬菜品质相同且单位运价相同；
（6）假设各收购站可以作为中转站；
（7）假设新增产的蔬菜能够满足缺货量；
2.2变量说明

x(i,j)
从蔬菜种植基地i到销售点j运送蔬菜的数量
b(j)
销售点j每天对蔬菜的需求量
C(j)
销售点j的短缺损失
d(i)
蔬菜种植基地i每天的蔬菜收购量
A(i,j)
从蔬菜种植基地i到销售点j的最短路程
2.3 模型建立
菜篮子工程中的蔬菜种植问题，研究的是如何利用现有的交通运输条件，使蔬菜由蔬菜基地分配到各蔬菜种植基地的短缺补偿以及运费补贴最小。要解决菜篮子运输问题，首先需要求出从各个蔬菜基地到各蔬菜种植基地的最短路径，然后利用线性规划的思想设计出最优的运输方案。
（1）最短路径的求解利用Floyd算法(又称弗洛伊德算法)，该算法是解决给定的加权图中顶点间的最短路径的一种算法，可正确处理有向图或负权的最短路径问题。它是通过一个图的权值矩阵求出它的每两点间的最短路径的矩阵，从带权邻接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新，即由矩阵D(0)=A按一个公式，构造出矩阵D(1)，又用同样地公式由D(1)构造出D(2)，依次进行，最后可由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，还可引入一个后继节点矩阵path来记录两点间的最短路径。
（2）要想设计出最优运输方案，需运用线性规划的思想。
用x(i,j)代表从种植地i到销售点j运送蔬菜的数量；用b(j)代表销售点j每天对蔬菜的需求量；C(j)代表销售点j的短缺损失；d(i)代表蔬菜种植基地i每天的蔬菜收购量；A(i,j)代表从蔬菜种植基地i到销售点j的最短路程。目标函数总费用Z来表示,总费用包括两部分: 蔬菜运费补贴R和各市场供给量小于需求量的短缺补偿D，即：Z=R+D
其中R=；销售点j的短缺量为；
则 D=，
所以目标函数为 Z = +
2.4 模型求解
2.4.1问题一(1)模型建立与求解
为了使蔬菜运送过程中的短缺补偿以及运费补贴最小，首先采用Froyd算法求出8个种植基地至各个销售点的最短距离，然后再以题中要求为约束条件、损失最低为目标建立线性规划模型，用LINGO编程求解。约束条件为：
（1）从蔬菜种植基地i运送到销售点j的蔬菜量小于等于蔬菜种植基地i的收购数量，即
（2）从蔬菜种植基地i运送到销售点j的蔬菜量小于等于销售点j的需求数量，即
（3）变量非负性限制
综合以上结论，得出该问题的模型如下：

根据Floyd算法【6】可以确定各个种植基地到各个销售量的最短距离如图1所示：

图1 各蔬菜种植基地到各销售点的最短距离A(i,j)

根据建立的模型，利用LINGO软件进行线性规划求解，输入目标函数和约束条件，求解模型的最优解，从其运行结果中可以整理得出运输方案如下：

在此种方案下，蔬菜运送过程中的短缺补偿以及运费补贴最小，最小金额为
42836.28元。
2.4.2问题一(2)的模型建立及求解

若规定各蔬菜销售点的短缺量一律不超过需求量的30%，该问题的目标函数没有变化，总费用仍然是运费补贴以及短缺补偿，只是在原问题的基础上加上各销售点短缺量一律不超过需求量的30%这一约束条件即可，具体要求如下：
（1）8个蔬菜基地的蔬菜全部供给35个销售点 （i=1,2,L8）
（2）每个销售点短缺量不超过需求量的30%
（j=1,…,35）
(3)变量非负性限制（i=1,2,L8；j=1,…,35）
综合以上结论，得出问题二的约束条件为：
（i=1,2,L8）
（j=1,…,35）
（i=1,2,L8，j=1,…,35）
根据建立的模型，利用LINGO软件，输入目标函数和约束条件，可求解模型的最优解，具体运输方案如下：

在此种方案下，蔬菜运送过程中的短缺补偿以及运费补贴最小，最小金额为
50190.20元。

2.4.3 问题二模型的建立及求解
为满足居民的蔬菜供应，决定扩大蔬菜种植基地规模以增加蔬菜种植面积。因此要实现两个目标：要保证每个菜市场的供货量充足；要使得总费用最低。
因此可在模型一的基础上增加限制条件，使得在供货量充足的情况下获得最小的短缺补偿及运费补贴。建立模型为：

限制条件为：
（i=1,2,L8）
（j=1,…,35）
（i=1,2,L8，j=1,…,35）
t0（i=1,2,L8）
根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。具体运输方案如下：

A、C、D、E、G、H的供应量不变，增加量为0吨；B的供应量由原来的45吨变为74.4吨，增加了29.4吨；E的供应量由原来的29吨变为39.2吨，增加了10.2吨；F的供应量由原来的35吨变为85.5吨，增加了50.5吨。总的增加量为29.4+10.2+50.5=90.1吨，最后供需量平衡。此时不需要支付短缺补偿了，只有运费补贴，需补贴206.776元。

2.4.4 问题三的模型建立及求解
为了提高居民的生活质量，市政府要求蔬菜种植基地不仅要保证蔬菜供应总量，还要满足居民对蔬菜种类的需求。每个蔬菜种植基地可种植12种蔬菜，各个蔬菜销售点对每种蔬菜有确定的需求量，在保证供需量平衡的基础上，需确定每个蔬菜种植基地的种植计划及新的蔬菜运送方案。
模型的建立：
设8个蔬菜基地分别为A,B,C,D,E,F,G,H
设基地A种植的12种蔬菜面积依次为：aa1,aa2,aa3…aa12
设基地B种植的12种蔬菜面积依次为：bb1,bb2,bb3…bb12
设基地C种植的12种蔬菜面积依次为：cc1,cc2,cc3,…cc12
设基地D种植的12种蔬菜面积依次为：dd1,dd2,dd3…dd12
设基地E种植的12种蔬菜面积依次为：ee1,ee2,ee3…ee12
设基地F种植的12种蔬菜面积依次为：ff1,ff2,ff3…ff12
设基地G种植的12种蔬菜面积依次为：gg1,gg2,gg3…gg12
设基地H种植的12种蔬菜面积依次为：hh1,hh2,hh3…hh12
在问题三保证供应总量的基础上，各个蔬菜种植基地到各个销售点的运输方案已经确定，根据其具体的配送方案，设定如下：
设基地A运送到销售点4的12种蔬菜依次为：a11,a12,a13…a112
设基地A运送到销售点5的12种蔬菜依次为：a21,a22,a23…a212
设基地A运送到销售点12的12种蔬菜依次为：a31,a32,a33…a312
设基地A运送到销售点14的12种蔬菜依次为：a41,a42,a43…a412
以同样的方式设定基地B,C,D,E,F,G,H分别到各自的销售点的12种蔬菜运送量，其范围依次为：b11---b812, c11---c412, d11---d412, e11---e412, f11---f1012, g11---g312, h11---h312
约束条件为：
(1)每个蔬菜种植基地种植的12种蔬菜总和等于该基地运出蔬菜量的值；
(2)每个蔬菜种植基地运出的某种蔬菜总量小于等于该基地该种蔬菜种植量；
(3)每个蔬菜种植基地对某一销售点运送的12种蔬菜之和等于带基地运送到该销售点的蔬菜量，结果已在问题三种给出；
(4)每个蔬菜种植基地运送到某一销售点的某一种蔬菜量要大于等于其需求量，
具体约束方程见附录；
根据建立的模型，利用LINGO软件，输入目标函数和约束条件，求解模型的最优解。每个基地的蔬菜种植计划如图2所示，每个基地向各销售点运送12种蔬菜的运送方案如图3所示：

图2 每个基地的蔬菜种植计划

此时供需量平衡，不需要支付短缺补偿了，只有运费补贴，需补贴203.016元。

图3 每个基地向各销售点运送12种蔬菜的运送方案

2.4.5 问题四模型的建立及求解
要求根据收集到的信息，进一步完善和制定相应的扶持政策，使得菜农有种植蔬菜的积极性，居民可以得到质优价低的新鲜蔬菜，同时还能够逐渐减少或者不用政府投入补贴。 
通过以上问题的研究，已经完善了对短缺补偿的研究，即在保证供大于求的情况下，短缺补偿为零，但运费补贴仍然存在，为了使国家逐渐减少或者不用投入补贴，可采取以下多种措施：
1、 可以将运费进行分档，用excel对已算出的数据进行整合，设蔬菜基地到销售点的距离不大于15公里的运费补贴为0.02元/(吨*公里)，距离大于15公里的运费补贴为0.04元/(吨*公里)，在问题三的基础上，算出总的运费补贴为181.8元，比之前算出的206.776元减少了24.976元，实现了最初目的。具体运输方案如下：

2、可以从现实问题出发，即可以优化配送方案【4】。由于我国的配送模式复杂、环节多导致了蔬菜价格高，配送网络规划不合理大大提高了配送的成本，通过模拟网络规划问题建立LRP模型，利用遗传算法对此方面进行求解。具体思路如下，首先进行模型的假设：
(1)每个销售点的需求只由一辆车配送;每个销售点对蔬菜配送的到达时间的要求是在某个时间段。
(2)基地生产的蔬菜量可以完全满足销售点的需求。因为配送网络模式对各个站点的配送的蔬菜量是根据销售点的订单需求计划好的
(3)运输工具数量为多车辆，且每台配送的车辆只为一个销售点服务。
然后建立模型：
  目标1:按照销售点订货的时间要求准时将蔬菜送到指定地点。消费者对蔬菜的第一要求就是蔬菜的新鲜，而且客户订购的蔬菜一般都是用于当天的消费，所以客户对蔬菜配送的及时性要求很高。如何安排配送，以达到客户对时间的要求，是建立模型的首要目标。
  目标2:合理优化物流配送路线以实现总成本最低。
3、可以适当减少销售点个数目，逆向思维，具体减少方式是将1到35个销售点分别算出到8个蔬菜生产基地的运费最小值，然后再将花销的运费补贴进行排序，去掉运费补贴较高的一些，折合到其他的销售点，从而达到减少运费补贴的目的。
三、优缺点和改进方向
3.1优缺点：
①所建立的模型简洁明了，便于使用数学工具。如Lingo,降低了编程求解的难度，缩短了运行时间，提高了工作效率。
②对同一个问题从不同的角度进行了考虑，建立了多个模型，并进行了结果的比较分析，既结合题目要求，又考虑了实际意义。
③从社会效益和经济效益对问题进行了分析，也表现出现实生活中政府在寻求两者之间的平衡中做出的努力。
④本模型还存在一些缺点，即现实中还是遇到一些实际的问题，是上述问题所无法解决的，
3.2改进方向
基于生活中的实际情况，我们做了如下的政策以改进和充实我们的模型：
（1）让菜农自己当老板，自产自销，即提高了菜农的积极性，又可以降低中间 环节的消费，降低菜价；
（2）可以提高仓储能力；
（3）可以设置一些保险以提高菜农的保障以提高积极性；
（4）设定奖励发展基金，减少运费补偿；
（5）鼓励菜农兴建蔬菜大棚和日光温度；
（6）实现蔬菜的产业化、规模化和标准化；
（7）建立专门的运输组织，减低运费成本以及国家的运费补偿；
（8）还可以设定相应的国家政策，如每一个销售点销售量提高1吨，则运费补偿提高到2元/吨/公里，这样，国家通过额外获得的税收即可弥补运费补偿，同时又有一定的剩余。
四 参考文献
[1]楚天科技，MATLAB科学计算实例教程P376—P384，北京市东城区青年湖南街13号，化学工业出版社，2009年6月
[2]吴建国，数学建模案例精编P360—P362，北京市三里河路6号，中国水利水电出版社，2005年5月
[3]王庚，王敏生，现代数学建模方法P92—P99，北京东黄城北街16，
科学出版社，2008年2月
[4] 我国城市蔬菜配送模式及网络规划问题研究P42—P52，2008年5月

[5] 王丽丽，光明市菜篮子工程问题研究，
，2015年4月29日
[6] 运筹学、菜篮子、炼油厂的生产计划，
，2015年4月29日
[7]最短路径—Dijkstra算法和Floyd算法，
，
2015年5月1日
[8]光明市的菜篮子工程，，
2015年5月1日
[9]数学模型光明市的菜篮子工程的答案，
，2015年5月1日
[10] 光明市的菜篮子工程，
，2015年5月1日