B题 配送问题.doc

货物配送问题的研究摘要本文针对是在运输成本最低的情况下生产与配送方案的设计、各城镇需求特征的分析、需求量达到峰值时间的预测、需求量达到峰值时排名前五和后五的城镇的求解、销售量达到最大值时增设连锁店的方案以及运输成本最低时生产基地方案的设计等问题。在求解的过程中我们运用了图论、聚类分析、曲线拟合、分线性规划等知识，建立了无条件约束最优化模型、聚类分析模型、拟合模型、非线性规划等模型，运用Floyd 算法、欧氏距离聚类法、最小二乘法等方法解决了问题，并对模型结果进行了分析与验证。问题一中，要设计生产与配送方案，使运输成本最低。首先欧式算法编程实现154城镇标号和连线，建立154*154的邻接矩阵，然后在MATlAB环境下采用Flody算法求出任意两个点之间的最短距离，从中提取出2*23的矩阵方法,两两对比找出离23个连锁店最短路程的生产基地，建立以运输成本最低为目标的非线性无约束最优化模型，利用MATLAB软件编程求得最优路径，借助EXCEL得到最低运输成本为10540.8539元。问题二中，要分析各城镇需求特征、预测销售峰值时间、求销售量达到峰值时前五和后五的城市。我们运用聚类分析法建立了模糊聚类分析模型，借助SPSS软件运用欧氏距离聚类方法将154个城镇分为4类，再分析各自城镇需求量知道城镇需求量与其经济的发达和与到发达城镇的距离有关；我们运用曲线拟合的方法，建立了曲线拟合模型，得到以时间为自变量、年销售量为应变量的三次多项式，运用最小二乘法原理对曲线进行拟合，求得三次函数，并对结果进行了检验，根据拟合函数预测得2013年年销售量达到最大值；我们先在EXCEL中先对数据进行处理求每个城镇过去的月平均销售量，再根据求出的每个城镇的权重得前五位为城镇31、城镇63、城镇106、城镇108、城镇120，后五位为城镇30、城镇84、城镇94、城镇109、城镇129.问题三中，要为司设计增设销售连锁店方案，使全省销售量达到最大。根据题目要求和已知条件，建立了非线性规划模型，借助LINGO软件求得其增加的连锁店数目为4个。问题四中，要求在增设销售连锁店的基础上为公司设计生产基地增设方案，使运输成本最低，这是一个多目标优化问题。我们根据题设要求建立了多目标优化模型，运用LINGO编程求得增设连锁店数目为5个,最低运输成本为36341,28元。本文最大的特色是对模型的结果分析、评价和改进，综合MATLAB,Lingo,EXCEL,SPSS等软件,运用最短路径算法，最小二乘法原理等对问题进行了求解。问题四中不仅考虑了最低运费还考虑了送货车辆的数量，路径问题，使得问题的求解更加全面。关键词：Floyd 算法 聚类分析 曲线拟合 非线性规划一、问题提出梦想连锁是一家肉类食品加工与销售公司，主营：鲜猪肉。公司在全省县级及以上城镇设立销售连锁店。全省县级及以上城镇地理位置及道路连接见附件1：全省交通网络数据.xls。问题：1、目前公司现有2个生产基地、23家销售连锁店，生产基地设在120号和63号城镇，为23家连锁店提供鲜猪肉，连锁店的日销售量见附录1。若运输成本为0.45元/吨公里，请为公司设计生产与配送方案，使运输成本最低。2、公司收集了近5年全省各城镇的鲜猪肉月度需求数据（附件2：各城镇月度需求数据.txt）请你分析各城镇需求特征，并预测未来数年，何时全省鲜猪肉需求达到峰值，达到峰值时需求达到前5位和后5位的城镇是那些？3、通过广告宣传等手段，未来几年公司在全省的市场占有率可增至3成左右（各城镇对公司产品每日需求预测数据见附件3：公司未来各城镇每日需求预测数据.txt），调查还发现，公司产品的需求量与销售量并不完全一致，若在当地（同一城镇）购买，则这一部分需求量与销售量相同，若在不足10公里的其他城镇的销售连锁店购买，则这一部分需求量只能实现一半（成为公司产品销售量，由于距离的原因，另一半需求转向购买其他公司或个体工商户的产品），而在超过10公里的其他城镇的销售连锁店购买，销售量只能达到需求量的三成。于是，公司决定在各城镇增设销售连锁店，基于现有条件、成本等的考虑，原有的23家销售连锁店销售能力可在现有销售量的基础上上浮20%，增设的销售连锁店销售能力控制在每日20吨至40吨内，并且要求增设的销售连锁店的销售量必须达到销售能力的下限。同一城镇可设立多个销售连锁店。请你为公司设计增设销售连锁店方案，使全省销售量达到最大。4、在增设销售连锁店的基础上，公司决定增加生产基地，地址设立在城镇所在地，每日产品生产必须达到250吨以上，在生产与销售各环节不能有产品积压。请为公司设计生产基地增设方案，使运输成本最低。二、基本假设1、假设本问题中所给的数据是准确的；2、假设在未来数年中不会发生重大灾难或金融危机对该省经济造成影响；3、假设当连锁店和生产基地在同一城镇上时，它们间的距离较短可以不考虑运输成本；4、假设每个生产基地到各连锁店送货路径是不唯一的；5、假设公司送货车辆足够多。三、符号说明符号意义单位备注运输成本元/吨公里已知为0.45元/吨公里第个连锁店第个生产基地总运输成本元第家连锁店日销售量公斤基地向第家连锁店提供的猪肉量公斤生产基地分别到23个连锁店的最短距离公里相邻两点之间的距离公里第个城镇对总销售量的权重第个城镇过去五年的平均年需求量公斤总销售量公斤号城镇对公司产品每日需求预测量公斤见附件3原有连锁店向城镇销售的猪肉量公斤表示连锁店所在城镇号增设连锁店向城镇销售的猪肉量公斤表示连锁店所在城镇号城镇到的最短距离公里城镇向原有连锁店需求的猪肉量公斤表示连锁店所在城镇号城镇向增设连锁店需求的猪肉量公斤表示连锁店所在城镇号城镇的总销售量公斤4、 问题分析本题是以在城镇设立连锁店为背景，进行货物配送问题的研究。确定出合理生产配送方案使得运输成本最低，本在此基础增设连锁店、生产基地，使销售量达最大。实际上就是动态优化问题，我们要做的就是根据具体的情况，为公司建立合理的方案，下面我们就问题具体分析。对于问题一，为了建立起优化模型，我们要找到各个变量和常量与我们目标函数的关系，针对本问，我们发现，总运输成本与单位运输成本、配送猪肉量和基地到连锁店距离有关，我们已经知道单位运输成本、日销售猪肉量，从而只需确定基地到连锁店距离即可得出最低成本。因此我们可以将问题转化为最短路问题来研究，我们模型的建立就将围绕寻找最优路径，得出最短路，然后可借助相关数学软件MATLAB即可得到我们的生产与配送方案。对于问题二，为求各城镇需求特征，对于庞大的数据，我们可以利用SPSS软件，用模糊聚类分析法将各城镇按其月需求量进行分类研究，再结合实际销售分析；要预测峰值我们则先用EXCEL软件对154个城镇各年的需求量进行汇总,再用MATLAB软件采用拟合或灰色预测等进行研究。对于问题三，是为公司设计增设连锁店，使全省销售量达最大的方案，由于题目要求增设连锁店必须达销售每日20吨的能力下线，因此我们整理数据，得出需求量大于20吨的城镇，见表1,猜想很可能增设的销售连锁店就在这些城镇中。我们可以建立多条件限制的优化模型，利用LINGO软件求解即可。 表1 预测需求量大于20吨城镇表城镇需求量（公斤）城镇3145123城镇6339125城镇6820574城镇10121299城镇10634561城镇12087236城镇12120154城镇15020426对于问题四，在问题三的基础上，增设生产基地，在满足每日产品生产必须达250吨以上，且在生产与销售环节不能有产品积压的基础上，使得运输成本最低，这是个多目标非线性规划问题。因此我们可以在一，三问的基础上建立起关于运输成本的优化模型，最后利用LINGO软件求解。 五、模型的建立与求解5.1 问题一模型建立与求解5.1.1 问题一的分析对于问题一，我们假定以各城镇为图1的顶点，两城镇间的直通路为图1相应两顶点间的边，为了更直观的了解该省城市交通网，我们在MATLAB中绘出的二位平面图，见图1。图1 城镇连线图要为公司设计生产与配送方案，使运输成本最低，我们首先假设每日生产基地向各个连锁店提供鲜猪肉量大于等于其日销售量。那么公司的运输成本为： （5-1）约束条件： （5-2）本题并无其它约束条件的限制，由公式知在时，生产基地到每个连锁店的运输成本仅于距离有关，因此我们就将问题转化为求两个基地到23个连锁店的最短路问题，运用MATLAB软件求解最短路，求出的运输成本必然是最低的。5.1.2 问题一模型的建立设图的邻接矩阵为,其中(i 1,2,3, , n);当定点，之间没有边时取，即在程序中以各边的权都不可能达到，且充分大的正数来代替。于是我们用MATLAB编程建立无向量的邻接对称矩阵。对图中的每一边，赋以一个实数两城镇之间的的长度，表示第家连锁店日销售量，为运输成本为0.45元/吨公里，为第家连锁店日销售量，为总运输成本。根据以上问题的分析，我们发现要为公司设计生产与配送方案，我们首先要找出两个生产基地到销售连锁店的最短距离： （5-3）目标函数运输成本的函数: （5-4）5.1.3 问题一模型的求解本问题在求解连锁店到生产基地最短距离时，需要用到Floyd 算法，该算法是一种求解最短路的确定型算法。根据文献【1】里面求解最短距离的方法：1、初值，；2、计算,其中表示从顶点到顶点的路径上所经过的大于的最短路径长度；3、递推产生一个距离矩阵序列；4、当时就得到了最短路径，即矩阵就是各顶点之间的最短距离，否则(为迭代次数)，转到第2步。通过对本问题的分析，结合上述原理求解模型一的步骤如下：Step1:通过MATLAB编程我们分别得到了两个基地到23个连锁店的运输路径及距离，两基地到连锁店的距离见表2。表2 两基地到连锁店的距离表基地距离连锁店123456781200.00 63.70 89.45 169.37 61.72 175.67 108.54 117.62 6389.45 84.51 0.00 114.66 122.56 108.36 19.09 28.17 910111213141516120134.31 0.00 151.19 202.41 119.54 110.58 170.17 239.26 63187.99 89.45 193.72 135.10 162.07 153.11 190.98 179.15 17181920212223120218.39 89.45 72.85 252.61 103.64 5.11 96.76 63128.94 0.00 137.83 168.95 157.32 94.56 7.31 Step2:比较两个基地到23个连锁店的距离,得出运输路径与最短距离，即得到满足运输成本最低的的最优化方案，其中表3、表4分别为设在120号、63号城镇的生产基地向连锁店配送猪肉的方案。 表3 120号基地的配送方案表基地连锁店运输路径最短距离12011200.00 212012513113010663.70 512012512413313214161.72 912012512413313214115142143161134.31 101200.00 1112011913454041423536151.19 131201191345444334119.54 141201191345404142110.58 1512012513113010691902849394170.17 1912012313413914914614572.85 211201251241331321411514214316103.64 221201235.11 表4 63号基地的配送方案表基地连锁店运输路径最短距离633630.00 463651501031114.66 6636515010108.36 763646519.09 8636667928.17 12636515010292827135.10 16636666768693212311179.15 1763666676869324128.94 18630.00 206366667686932122168.95 2363647.31 由表2、3，再联系附录1可知，在120号城镇的基地日生产量至少为230208公斤，分别向1,2,5,9,11,13,14,15,19,21,22号连锁店配送猪肉；在63号城镇的基地日生产量至少为163619公斤，分别向3,4,6,7,8,12,16,17,18,20,23号连锁店配送猪肉。Step3:由第2步比较得出的最短距离带入（5-3），运用EXCEL,即可求出运输的最小成本：（元）5.1.4 问题一结果的分析 本题，我们利用求最短路的方法，运用MATLAB软件，设计出了公司对每个连锁店的配送方案，见表2、3，此时120号基地日生产量至少230208公斤，63号基地日生产量至少为163619公斤，在此生产与配送方案下的运输成本最低为：10540.8935元。由此结果可见，由于120号为省会城市，省会及其周边城镇的人口数量更多，经济状况更好，因此此基地生产量明显多于另一生产基地。5.2 问题二模型建立与求解5.2.1 问题二的分析问题二要求各城镇需求特征，预测未来数年，何时全省鲜猪肉需求达到峰值，达到峰值时需求达到前5位和后5位的城镇。首先，要分析各城镇的需求特征。先将.txt文本中的各城镇月度需求数据数据导入到Excel中，并做了数据的缺失和病态检验，发现均无异常。对于154城镇知道其5年中的月销售量要分析其特点是不太容易的,我们打算先用模糊聚类分析法将各城镇按其月需求量进行分类，再分析各城镇需求量的特点；然后，要预测全省需求量的达到最高峰的时间，需求量是关于时间序列的一些离散变量，先用EXCEL软件对154个城镇各年的需求量进行汇总,用MATLAB软件拟合一个以时间为自变量，总需求量为因变量的多项式，再求导就找到了全省需求量最大的时间。最后，在全省猪肉需求量达到最高峰时，要求找出154个城镇的月度需求量排名前五位和后五位的城镇。由于季度变化或其他的偶然因素，每月猪肉的需求量具有不确定性和波动性。于是我们打算求出每个城镇过去五年的平均年需求量,平均每年该省猪肉总需求量根据它们的权重对总需求量进行排序。5.2.2 问题二模型的建立1、模型建立：Step1:建立如下的数据矩阵：Step2:平移标准差变换对数据进行标准化处理 （5-5） （5-6）经过变换后，每个变量的均值为0，标准差为1，且消除了量纲的影响，得到矩阵。但是再用得到的还不一定在区间上。Step3:采用欧氏距离建立模糊相似矩阵 （5-7） 2、我们做出了以2008年为起始年的五个点的散点图个点的散点图:图2 年需求量散点图对以上描绘的散点图我们建立了下面的三次函数关系式： （5-8）3、由以上问题的分析我们建立求解权重的模型： （5-9）5.2.3 问题二模型的求解1、根据布尔矩阵法进行聚类。其算法原理如下：（1）求模糊相似矩阵的截矩阵；（2）由可得水平上的分类。利用MATLAB软件我们得到城镇按销售量可以分为三类，如下表：2、借助MATLAB软件运用最小二乘法的原理求得各参数分别为： ,该三次多项式为： （5-10）要求全省最大销售量主要有以下两个步骤：Step1:对拟合函数求导： （5-11）Step2:求出的根并检验： 在2013年时全省需求量达到最高峰，最大需求量为1430200吨。3、 通过求解权重模型，需求量达到峰值时，需求量在前五和后五的城镇如下表所示：表5 达峰值需求量排名前五位表排名城镇1城镇1202城镇313城镇634 城镇1065城镇104表6 达峰值需求量排名前五位表排名城镇1城镇302城镇943城镇844城镇1095城镇1295.2.4 问题二结果的分析1、根据以上平方欧氏距离，我们将对将样本进行聚类。Step1：个样本自成一类，计算出相似性测度，将相似性测度较小的任意两个样本合并；Step2：计算出样本之间的欧氏距离,按最小距离准这进行；Step3：每次减小一类，直到最后所有样本归为一类。利用MATLAB软件我们得到城镇按销售量可以分为四类，如下表：第一类：1 2 3 4 5 6 7 8 9 10 11 15 30 32 34 45 47 48 51 52 55 57 62 64 67 69 70 72 75 77 78 80 99 102 103 105 107 109 111 115 122 123 127 127 147 149 151 153第二类：12 33 46 49 50 53 54 56 68 71 76 79 100 101 104 110 116 117到119 121 128 148 150 154第三类：31 63 106第四类：120根据附件中所给数据我们进行对比分析可以得到以下结论：某些经济比较发达，规模较大的城市其月需求量比较大。比如120号城镇，它是该省的省会；另外一个影响需求量的因素是与大城市之间的距离，离省会越远需求量相对较小，它可能只是一个普通的县级单位。 2、对上述三次多项式进行拟合后通过研究对其回归系数、残差平方和、标准差等指标对模型进行了检验。拟合的曲线如下：图3 拟合曲线图 ， （5-12） （5-13）通过上述数据的分析我们发现我们建立的模型是合理有效的。5.3 问题三模型建立与求解5.3.1 问题三的分析本题在同一城镇可设立多个销售连锁店的前提下求解为公司设计增设销售连锁店方案，使全省销售量达到最大。在此问题中，我们可以不考虑产品的储存问题，但产品的销售量与连锁店之间的货物购买、连锁店的销售能力和城镇的需求量之间都存在重大影响。1、连锁店之间的货物购买会由于距离原因导致产品的销售量降低，存在产品积压，这与我们要使销售量最大化矛盾，故我们要尽量避免这种情况的发生；2、产品需求量和连锁店的销售能力决定着是否新增设连锁店，以及增设连锁店的数量。虽在本题中不用考虑增设连锁店的成本问题，但在生活中这是客观存在的，因此我们要将连锁店的增设数量控制到最小。从这些影响因素之间的关系可以判定这是一个动态规划模型，我们可根据这一系列分析建立起目标函数，并列出约束条件，引入0,1变量，最后利用LINGO软件即可计算我们的模型，最终得到最优化的增设销售连锁店的方案。5.3.2 问题三模型的建立经过上面的分析，要求增设连锁店，使产品销售量最大化，现在开始优化模型的建立。首先明确变量：设表示猪肉在全省的总销售量，表示原有连锁店向城镇提供的猪肉量，表示增设连锁店向城镇提供的猪肉量，表示城镇到的最短距离，表示号城镇对公司产品每日需求预测量。 目标函数： （5-14）约束条件：1、城镇的需求预测量等于城镇向原有连锁店的需求量与城镇向增设连锁店的需求量之和： （5-15）2、题中指出：公司产品的需求量与销售量并不完全一致，若在当地（同一城镇）购买，则这一部分需求量与销售量相同，若在不足10公里的其他城镇的销售连锁店购买，则这一部分需求量只能实现一半而在超过10公里的其他城镇的销售连锁店购买，销售量只能达到需求量的三成。则：（1）原有连锁店实际销售量： （5-16）原有连锁店： （5-17）（2）同理，增设连锁店实际销售： （5-18）由于要求增设的销售连锁店销售能力控制在每日20吨至40吨内，则： （5-19）综上所述我们建立了下面非线性规划模型：5.3.3 问题三模型的求解Step1：第个城镇向第个城镇购买,第个城镇向第个城镇购买的比例(本城为1，10公里内0.5，10公里外0.3)；Step2：使城镇的需求预测量满足城镇向原有连锁店的需求量与城镇向增设连锁店的需求量之和；Step3：求出原有连锁店实际销售量与增设连锁店实际销售量；Step:4：对于这个动态优化模型我们采用LINGO进行求解。得到的全局最优解程序见附录4，增设连锁店应该在68,101,121,150城镇，可以使全省销售量达到最大。5.3.4 问题三结果的分析我们通过LINGO计算得到的结果与我们在问题分析中猜想的结果（见表1）基本符合，说明增设的连锁店建在需求量大的城镇，可以在满足销售量最大且可以使建立的连锁店尽量的少，这样就可以减少公司的成本，使利润最大化。5.4 问题四模型建立与求解5.4.1 问题四的分析问题要求在增设销售连锁店的基础上，为公司设计生产基地增设方案，并使运输成本最低，这是个非线性规划求最优解的问题。5.4.2 问题四模型的建立1、目标函数为： （5-20）2、要求各环节不能有产品的积压，那么原有的两个生产基地城镇总运输量应不超过城镇的总销售量： （5-21）3、设各个生产基地最大生产量为,新增连锁店数目为.生产基地到城镇的生产量理论上不大于总运输量： , （5-23） 综上所述我们建立了下列非线性规划模型： 5.4.3 问题四模型的求解我们根据题设要求建立了多目标优化模型，运用LINGO编程求得增设连锁店数目为5个,最低运输成本为36341,28元。5.4.4 问题四结果的分析及验证结果的合理性分析，误差分析，灵敏度分析，结果的验证与方法的检验等。六、模型的评价与推广模型最大的优点在于利用最短路求运输最低成本，我们应用的是floyd算法，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法，容易理解，可以算出任意两个节点之间的最短距离，代码编写也非常简单，但时间复杂度比较高，不适合计算大量数据。在问题三中的模型未考虑增设销售店的成本问题和产品储存费用等问题，与实际情况不相符。最短路问题不仅仅适用于运输网络，在舰船通道路设计、通讯线路的建造和维护、汽车导航系统及各种应急系统都有直接应用价值。七、参考文献1 汪晓银等 数学建模与教学实验（第二版），P7，高等教育出版社，2003年8月；2 ,卓金武，MATLAB在数学建模中的应用P10，北京航空航天大学出版社：2011年4月。 八、附录8.1 附录清单附录1：23家连锁店日销售量附录2：问题一中MATLAB程序及结果附录3：问题二中MATLAB程序及结果附录4：问题三中LINGO程序及结果8.2 附录正文附录1：23家连锁店日销售量连锁店编号12345678所在城镇编号1201066331141106579日销售量（公斤）28733382232173323947925884811557038759连锁店编号910111213141516所在城镇编号1120362734429411日销售量（公斤）14744325171150392654519489127736103连锁店编号17181920212223所在城镇编号2463145221612364日销售量（公斤）32512829539653637514783180811840附录2：问题一中MATLAB程序及结果clcload A.txt figure(1);hold on;A=A;x=A(2,:); y=A(3,:); plot(x,y,.,MarkerSize,10) for i=1:154 text(x(i)-4,y(i)+1,num2str(i)end load B.txtB; n,m=size(B); a=B(:,1); b=B(:,2);c=B(:,3); for i=1:n x3=x(a(i); y3=y(a(i); x4=x(b(i); y4=y(b(i); plot(x3,x4,y3,y4 ,LineWidth,1) endx=137.500000000000;362;410;167;420;376;374;365;354;359;333;276;270;276;282;135;212;240;235;206;193.500000000000;y=462;443;408.500000000000;462;401;406;424;448;495;528;511;419;415;405;398.500000000000;395;443;495;496;466;475;plot(x,y,r*);grid on;xlabel(x),ylabel(y); for i=1:n f(a(i),b(i)=c(i);endf=f;i,j,v=find(f);DG = sparse(i,j,v);for i=1:23 i=120;106;63;31;141;10;65;79;1;120;36;27;34;42;94;11;24;63;145;22;16;123;64;enddist,path,pred = graphshortestpath(DG,63,i) dist = Columns 1 through 10 89.4500 84.5100 0 114.6600 122.5600 108.3600 19.0900 28.1700 187.9900 89.4500 Columns 11 through 20 193.7200 135.1000 162.0700 153.1100 190.9800 179.1500 128.9400 0 137.8300 168.9500 Columns 21 through 23 157.3200 94.5600 7.3100dist = Columns 1 through 10 0 63.7000 89.4500 169.3700 61.7200 175.6700 108.5400 117.6200 134.3100 0 Columns 11 through 20 151.1900 202.4100 119.5400 110.5800 170.1700 239.2600 218.3900 89.4500 72.8500 252.6100 Columns 21 through 23 103.6400 5.1100 96.7600附录3：问题二中MATLAB程序及结果% 散点图程序 x=0 1 2 3 4;y=1304067.34 1346540.65 1382773.01 1410444 1427071.86;plot(x,y,r*);ylabel(年需求量：吨);xlabel(t-2008:年)曲线拟合程序： x=0 1 2 3 4;y=1304067.34 1346540.65 1382773.01 1410444 1427071.86;P=polyfit(x,y,3);xi=0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 3 3.2 3.4 3.6 3.8 4 4.2 4.4 4.6 4.8 5 5.2 5.4 5.6 5.8 6;yi=polyval(P,xi);plot(xi,yi,x,y,r*)xlabel(t-2008:年);ylabel(年需求量：吨);f=fittype(a.*t.3+b.*t.