蔬菜分配(数学建模)

2016年数学建模论文第二套论文题目：蔬菜供应方案设计组别：第38组姓名：耿晨闫思娜王强提交日期：2016年7月13日题目：蔬菜供应方案设计摘要本次建模探究得是江平市蔬菜市场为满足不同条件的最优调配方案问题，模型求解时使用了Froyd算法，并用线性规划建立了一系列数学规划模型，采用MATLAB和LINGO软件编程计算出模型结果。关于问题一：为了实现蔬菜调运及预期的短缺损失为最小，我们建立了线性规划模型，用Froyd算法在MATLAB中编程，求出收购点至个菜市场的最短距离，并考虑每日各菜市场的需求量条件，用LINGO编程求得蔬菜调运及预期的短缺损失最小值为日均10280元。关于问题二：在模型一的基础增加各菜市场短缺量一律不超过需求量的20%的约束条件，用LINGO编程求得最少日均费用最少为10628元，并设计最优供应方案见正文。关于问题三：在模型一的基础上，条件改为供货充足、需求调运与短缺损失的费用最小值。建立模型三时在模型一的基础上改变条件，并用LINGO编程求得日均最少费用为11200元，增产的蔬菜每天应分给C收购点7000Kg，分析过程见正文。关键词：蔬菜市场调配方案，Floyd算法，线性规划，MATLAB编程，LINGO-1-一、问题重述江平市是一个人口不到20万人的小城市。根据该市的蔬菜种植情况，分别在菜市场（A），城乡路口（B）和南街口（C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位：100m）及各收购点，菜市场①到⑧的具体位置见图1。图1：蔬菜供应网点图按常年情况，A、B、C三个收购点每天收购量分别为250，200和180（单位：100kg）,各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表1。设从收购点至各菜市场蔬菜调运费为2元/(100kg.100m).表1：各蔬菜市场需求量表菜市场每天需求（100kg）短缺损失（元/100kg）①8010②708③905④8010⑤12010⑥708⑦1005⑧908通过这次建模我们解决以下问题：1.为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预期的短缺损失为最小；-2-2.若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案；3.为满足城市居民的蔬菜供应，该市的领导规划增加蔬菜种植面积，试问增产的蔬菜每天应分别向A、B、C三个采购点供应多少最经济合理。二、问题分析2.1问题一的分析要使用于蔬菜调运及预期的短缺损失为最小，即总费用R最小，也就是指调运费用P与缺货损失Q之和最小。首先考虑调运费用P，调运费用与距离与送货量成正比，因此考虑距离问题，我们须先求出A、B、C三个采购点至各个菜市场的最短距离。采用Froyd算法，结合MATLAB编程实现最短距离计算，确定出最短路线。其次考虑缺货造成的损失Q，以题中每天需求量为约束条件，将损失最低作为目标建立线性规划模型，用LINGO编程求解缺货损失最小值。2.2问题二的分析若按规定各菜市场短缺量一律不超过需求量的20%，也就是在模型一的基础上增加一个约束条件，即每个菜市场的供应量必须不低于需求量的80%。则可得到满足条件要求的模型二。2.3问题三的分析本题的目标有二：首先要满足每个菜市场的供货量要充足的条件；其次要使得总费用最低。所以我们在模型一的基础上增加了上述两个限制条件，即得到模型三。使得在供货量充足的情况下日均费用最小化。三、问题假设1、各个路口以及蔬菜销售点都可以作为中转点。2、假设蔬菜种植基地直达某个销售地点，即销售点之间没有卸货的情况。3、假设运输的蔬菜路途中没有损耗，也无意外发生。4、假设只考虑运输费用和短缺费用，不考虑装卸等其它费用。5、假设各蔬菜种植基地供应蔬菜同质且单位运价相同。6、假设新增产的蔬菜能够满足缺货量。7、日需求量与缺货损失费用不变。四、变量说明1,28AiDi……从A到i（各个菜市场）的最短距离1,28BiDi……从B到i（各个菜市场）的最短距离1,28CiDi……从C到i（各个菜市场）的最短距离1,28AiSi……从A到i（各个菜市场）的运货量-3-1,28BiSi……从B到i（各个菜市场）的运货量1,28CiSi……从C到i（各个菜市场）的运货量P总调运费Q短缺损失R总费用五、模型建立5.1问题一模型的建立按照问题的分析，我们知道调运总费用P与调运距离和调运量乘积有关，也就是说总调运费用等于每阶段调运距离和调运量的累计。首先就要求解各采购点到菜市场的最短距离。在图论里面关于最短路径问题比较常用的是Dijkstra算法，Dijkstra算法提供了从网络图中某一点到其他点的最短距离。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。但由于它遍历计算的节点很多，所以效率较低，实际问题中往往要求网络中任意两点之间的最短路距离。如果仍然采用Dijkstra算法对各点分别计算，就显得很麻烦。所以就可以使用网络各点之间的矩阵计算法，即Floyd算法。Floyd算法的基本思想是：从任意节点i到任意节点j的最短路径不外乎两种可能，一种是直接从i到j，另一种是从i经过若干个节点k到j。i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，…，n(n是菜市场的数目)，再检查d(i,j)与d(i,k)+d(k,j)的值，在此d(i,k)与d(k,j)分别是目前为止所知道的i到k与k到j的最短距离。因此d(i,k)+d(k,j)就是i到j经过k的最短距离。所以，若有d(i,j)d(i,k)+d(k,j)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(i,j)重写为d(i,k)+d(k,j)，每当一个k查完了，d(i,j)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(i,j)里面存放的就是i到j之间的最短距离了。5.2问题二模型的建立各菜市场短缺量一律不超过需求量的20%，为满足这一条件，现对方案一进行调整。只需在方案一中加一限制条件：-4-111222333444555666777888800.864700.856900.872800.8641200.896700.8561000.880900.872ABCABCABCABCABCABCABCABCSSSSSSSSSSSSSSSSSSSSSSSS同理可用LINGO编程求出调运方案。5.3问题三模型的建立要足城市居民的蔬菜供应，增加蔬菜种植面积，则需要保证所有的菜市场都满足日需求量，且日均化费用要最小。在问题一得基础上作出以下调整：111222333444555666777888807090801207010090ABCABCABCABCABCABCABCABCSSSSSSSSSSSSSSSSSSSSSSSS同理可用LINGO编程求出调运方案。六、模型求解6.1问题一模型的求解由图1和表格1的信息，建立一个线性规划模型并经过Floyd算法，使得蔬菜调运及预期的短缺损失为最小。调运总费用P为：888111AiAiBiBiCiCiiiiPSDSDSD（1）若使调运总费用最少，则应保证A、B、C三个收购点到8个菜市场的路程最短，最短路线的求解过程如图2：-5-图2：最短路程求解过程图分析上图可知，该路线为无向网络，就该图而言，网络弧集为：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=()nnijw（2）其中：①当（iv,jv）属于E时，ijw=ijl，ijl为弧（iv,jv）的权；②当（iv,jv）不属于E时，ijw=inf。（inf为无穷大，n为网络结点个数）③iiw=0，i=1,2,3……n按上述规定，该网络的权矩阵为：-6-因为上述网络有15个结点，故网络的权矩阵均为15阶矩阵。用Floyd算法求解图2中任意两个顶点的最短路径及其长度，名为Floyd.m的程序文件见附录程序1。最终运行结果为：D=0714541081218121520242223707128312814191319202419147016136117111812181723165121606135915712152117204813607481413111720221910361370951116101617211681211549041012713161815128798540611511121611181411151411106093961451219187131612119068151014151312121110753606911820191815171613119860105142420172120171612615910011112224231722211816141011511019231916201916151151481411190path=1224525554545451231565661666662238668898889891174557771071071071264567884778-7-782235568888888885584587884111181185637567891111119119883888889111111131115441144114111110111211141178877878910111291291011111011111111111011121314119999999999912131491012121012121212121012121314129999999999999915根据上述矩阵，分别找出A、B、C到①、②、③、④、⑤、⑥、⑦、⑧的最短距离，见表2：表2：收购点到菜市场的最短距离最短距离（单位：100千米）①②③④⑤⑥⑦⑧A488191162220B14771612162317C20191114615510调运量的限制：11122233344455566677788880;70;90;80;120;70;100;90;ABCABCABCABCABCABCABCABCSSSSSSSSSSSSSSSSSSSSSSSS短缺损失费为：-8-11122233344455566677788810808705901080101208705100890ABCABCABCABCABCABCABCABCQSSSSSSSSSSSSSSSSSSSSSSSS