《《货物配送问题》word版.docx》由会员分享，可在线阅读，更多相关《《货物配送问题》word版.docx（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、题目 货物配送问题 摘 要本文研究某公司猪肉销售问题，构建数学模型，设计生产与配送方案和增设销售连锁店方案，使得销售量最大。问题一要求设计生产与配送方案，使运输成本最低。将最低成本问题转化为最短路径问题，采用算法：利用编程，得到生产基地到所有连锁店的最短路线：生产基地为提供这几家连锁店提供鲜猪肉，所耗费的成本约为元，生产基地为这几家连锁店提供鲜猪肉，所耗费的成本为元，最低总成本为元。问题二要求分析各城镇需求特征并预测需求达到峰值的时间及到峰值时需求达到前位和后位的城镇。对于需求通过特征分析，通过作出城镇需求量与时间的折线图，可知全省的鲜猪肉的需求量从年虽上下波动，但总体上升趋势明显，每年对鲜猪
2、肉的需求量明显升高。对于对未来几年的预测，通过作出的散点图利用进行拟合，根据拟合曲线得出2014年需求量会达到峰值为，前五名分别为号，号，号，号，号城镇，后五名分别为号，号，号，号，号城镇。问题三要求为公司设计增设销售连锁店方案，使全省销售量最大。采用规划算法，构建数学模型：通过求得优化方案：所求城镇6 8 10 18 31 33 50 54 56 64 68 76 100 101 104 110 116 120 123 125 150 154需要增设连锁店，其中城镇分别含有连锁店的个数是。关键词 销售方案 算法 拟合曲线 规划模型 一、问题背景与重述1.1问题背景某公司是一家肉类食品加工与销
3、售公司，主营：鲜猪肉。该公司在全省县级及以上城镇设立销售连锁店。全省县级及以上城镇地理位置及道路连接见数据文件：全省交通网络数据.。目前该公司现有个生产基地、家销售连锁店，生产基地设在号和号城镇，为家连锁店提供鲜猪肉，连锁店的日销售量见附录。通过广告宣传等手段，未来几年公司在全省的市场占有率可增至成左右（各城镇对公司产品每日需求预测数据见文件：公司未来各城镇每日需求预测数据），调查还发现，公司产品的需求量与销售量并不完全一致，若在当地（同一城镇）购买，则这一部分需求量与销售量相同，若在不足公里的其他城镇的销售连锁店购买，则这一部分需求量只能实现一半（成为公司产品销售量，由于距离的原因，另一半需
4、求转向购买其他公司或个体工商户的产品），而在超过公里的其他城镇的销售连锁店购买，销售量只能达到需求量的三成。于是，公司决定在各城镇增设销售连锁店，基于现有条件、成本等的考虑，原有的家销售连锁店销售能力可在现有销售量的基础上上浮，增设的销售连锁店销售能力控制在每日吨至吨内，并且要求增设的销售连锁店的销售量必须达到销售能力的下限。同一城镇可设立多个销售连锁店。1.2问题重述分析数据，并通过数学建模知识回答下述问题：1、若运输成本为，为公司设计生产与配送方案，使运输成本最低。2、根据公司收集的近年全省各城镇的鲜猪肉月度需求数据，分析各城镇需求特征，并预测未来何时全省鲜猪肉需求达到峰值和达到峰值时需求
5、达到前位和后位的城镇。3、为公司设计增设销售连锁店方案，使全省销售量达到最大。二、问题分析2.1问题一的分析要设计生产与配送方案使运输成本最低，即可将最低成本问题转化为最短路径问题，进而得到最优化生产和配送方案。算法2是最具代表性的最短路径的算法，它以起点为中心向外层层拓展直至结点，因此可将连锁店和生产基地看成质点，路基最短即两点之间距离最短,可通过软件画出城镇网络图，并利用结合算法，得到生产基地到所有连锁店的最短路线，从而得到最优分配方案。2.2问题二的分析要分析各城镇需求特征，首先要明白数据的的变化情况，通常对这种题目要求，可以对所给数据进行均值和标准差运算来了解数据的波动情况和离散程度，
6、并通过作出各城镇需求量与时间的折线图。为准确得知公司发展状况，并采取相对应的措施，要求对未来峰值的预测，可通过画出散点图了解总需求量的变化，并利用最小二乘法对散点图进行曲线拟合3，预测出未来走势，利用拟合出的两个函数式估测出出现峰值时的年份，对于需求排名前五和后五情况确定，则可以对年至年这五年间的需求量进行统计并通过排名情况总结。2.3问题三的分析问题三要求设计增设销售连锁店方案，使全省销售量达到最大，要考虑连锁店的销售量、需求量与距离变化的关系以及增设的销售连锁店销售能力控制在每日20吨至40吨内，并且要求增设的销售量必须达到销售能力的下限，且同一城镇可设立多个销售连锁店。根据题意拟采用规划
7、算法，对新增连锁店进行规划，建立目标函数。同一城镇可设立多个销售连锁店，以及连锁店对于每个城镇的供给量的实现，（在公里以内，需求量等于销售量的一半，公里以外，需求量等于销售量的三分之一，且每个店最低销量为吨），由此建立线性约束条件，并利用软件建立优化模型，则可以得出优化方案。三、模型假设结合本题的实际，为了确保模型求解的准确性与合理性，本文排除一些干扰因素，提出以下几点假设：1、假设材料中信息来源可靠真实；2、假设各基地足够地供给鲜猪肉，不出现断货缺货的情况；3、假设运输成本中只考虑距离问题，其他损失忽略不计；4、假设在近期内连锁店不会出现食品安全问题，保证正常运营。四、符号说明为了便于问题的
8、求解，本文给出以下符号说明：符号说明第个数据值所有数据的平均值新增的销售能力不足10公里的其他城镇的连锁店销售能力超过10公里的其他城镇连锁店的销售能力未来第个城镇的需求量原有的连锁店在增设之前的销售能力原有的连锁店在增设后的销售能力五、模型的建立与求解5.1问题一的模型建立与求解模型建立算法是很具有代表性的最短路径的算法，它是以起点为中心向外层层拓展直至结点。在本题中，采用软件求得货物配送的最短路径，进而得到最优生产和配送方案。由于需要解决的问题转化成了最短路径问题，所以解决任意两点间的最短距离问题采用算法。因此建立模型，将每个连锁店和生产基地看成一个质点，按照城镇编号命名为，其中点63和点
9、120是货物运输的起点。设源始点到某一结点的距离为，结点到结点的距离为，则以点63为始点时，表示两者之间有直通车，表示两者之间没有直通车。同理，点120。比较点63和点120到相同点的之间的距离，取最小的那一种情况，来满足最短距离配送问题要求，其中重要步骤如下：，是除了63的其他始点，由此将最低成本问题转化为最短路径问题。模型求解（1）利用软件根据全省交通网络数据表和高速公路连接表中的数据绘制出城镇网络图，如下图：图1 城镇网络图如图所示，我们可以清晰地看出各城镇之间的相对位置，也较为直观地看出货物运输路线。（2）利用软件结合算法，编写程序，很快地得出生产基地到所有连锁店的最短路线，得到最优分
10、配方案表（具体见附录） 根据表中数据可知，生产基地为提供这几家连锁店提供鲜猪肉，所耗费的成本约为元，生产基地120为这几家连锁店提供鲜猪肉，所耗费的成本为，由此得到运输最低成本约为元。5.2问题二的模型建立与求解要求分析各城镇的需求特征，首先，我们分别求出每年每个月所有城镇需求量的平均值，结果如表：表 城镇需求量平均值12345678910111220086956897006947087097067017077197177172009714712719728724729731736741738730736201074074474574573974574875175275974475920117
11、5475875776276175576676576577476017752012764767771763781783769769777770780768由表格数据可得，每年每月所有城镇的需求量的平均值都普遍在呈上升趋势，我们画出该表格的折线统计图：图2 城镇月需求量平均图由图得，城镇每年每月的需求量的平均值呈上升趋势，但趋势趋于平缓，下面我们做出所有月份城镇平均值的的折线图：图3 城市月需求量平均总图由图3可得，全省的鲜猪肉的需求量从2008-2012年虽上下波动，但总体上升趋势明显，每年对鲜猪肉的需求量明显升高。对于未来几年的预测，首先我们求出2008-2012年每年全省鲜猪肉的总需求量，如
12、下：根据前五年全省鲜猪肉的总需求量，我们可以做出散点图如图4：图4 散点图对散点图分析可得2008-2012年的总需求量呈抛物线形式，所以运用最小二乘法对散点图进行曲线拟合。上述过程以求得2008-2012年全省鲜猪肉的需求量，以年份为自变量，总需求量为因变量，所以假设曲线为二次多项式，利用进行拟合求得系数：所以函数方程式为：拟合曲线如图5：图5 2008-2012年总需求量拟合图得出拟合图后发现这五年间大致上呈增长的趋势发展，接着我们对未来几年的鲜猪肉的总需求量做出预测，如图6：图6 未来几年预测图对图6进行分析得，同时将代入函数关系式得第七年全省对鲜猪肉的需求量会达到峰值，即2014年需求
13、量会达到峰值为1437802。在对2014年达到峰值时，对前五名与后五名排名时，我们求出年每个城镇对鲜猪肉的年度总需求量（见附录），其次对每年的每个城镇鲜猪肉的总需求量分别作出折线统计图（其中2008年的折线图见图7，年的折线统计图见附录）。图7 2008年每个城镇鲜猪肉总需求量折线图通过对五张折线图的分析，我们发现每年各城镇对鲜猪肉总需求的排名几乎没有变动，所以推测2014年各城镇对鲜猪肉需求量排名与几乎前几年相同，前五名分别为120号，63号，31号，106号，104号城镇，后五名分别为30号，94号，84号，109号，129号城镇。5.3问题三的模型建立与求解模型建立题目要求设计增设销售
14、连锁店方案，使全省销售量达到最大。而经调查发现，公司产品的需求量与销售量并不完全一致，若在当地（同一城镇）购买，则这一部分需求量与销售量相同，若在不足10公里的其他城镇的销售连锁店购买，则这一部分需求量只能实现一半，而在超过10公里的其他城镇的销售连锁店购买，销售量只能达到需求量的三成。所以建立规划模型，首先建立线性目标函数，其中表示第个城镇增加连锁店，表示第个不增设连锁店。则有目标函数：约束条件：5.3.2 模型求解利用软件结合线性规划，求得结果如下：所求城镇6 8 10 18 31 33 50 54 56 64 68 76 100 101 104 110 116 120 123 125 1
15、50 154需要增设连锁店，其中城镇120，31，64，10，123分别含有连锁店的个数是3，2，2，2，2个。使得全省销售量最大，最大值为919414公斤。六、模型的评价与改进6.1模型的评价模型的优点1、拟合曲线可以得到近似函数方程，比便预测未来数据；2、规划模型与实际紧密联系，将问题简单化，具有很好的通透性和推广性；3、模型的计算采用专业的数学软件，可信度高。模型的缺点1、规划模型约束条件有点简单；2、算法只能解决正权值图，虽是较为成熟、最易接受的一种算法，但始终存在局限。6.2模型的改进6.2.1对于问题一的改进最短路径是图论研究中一个重要课题，传统公认的求得最短路径的最好算法是Dij
16、ketra算法，然而存在时间和空间复杂度，现对此算法进行改进，采用邻接表和堆排序的优化方法。首先，将数组T通过堆排序调整为小顶堆，取数组首元即堆顶节点为中间节点，并将该节点加入到已标记集合S中，再比较更新节点的邻接点集合与已标记集合的差集中任一节点V1的当前最短路径值，然后查找S集合所有节点的邻接点的并集和S集合的差集，同时将这些节点顺次存入数组T中，覆盖原数组中的节点，并设置一个计数器i记录节点个数，最后将数组中的前i个元素按它们当前的最短路径值调整成小顶堆，取堆顶节点为下一个最短路径节点将其个归并到集合S中，如此反复得出理想的最短路径值。对于问题三的改进基于本文的问题，可把0-1非线性规划
17、问题转化为约束优化问题，采用动态双目标的约束处理方法，即粒子群混合算法。首先设置当前迭代代数t=1，确定种群的大小N，搜索空间的维度D，在0，1空间内产生N个粒子的初始位置和速度。第二步将第个粒子的最好位置pbest设置为该粒子的当前位置，如果A=xx,则全局最优位置,第三步根据Sigmoid函数公式、改进式和粒子优化等式更新每个粒子的速度与当前位置，第四步根据前面转化出来的无约束双目标问题得出的公式：minFx=min(x,f(x)更新每个粒子的个体优化位置和全局最优值，按照一定的概率对当前粒子在0，1空间进行随机赋值，最后让t=t+1返回到步骤三，直到获得一个预期的适应值。七、模型的检验将
18、杂乱无序，无相关关系的散点拟合成曲线，用来预测未来情况，但意义不大，因此为了模型的高精确度和曲线的高切合度，有必要对回归方程进行显著性检验4。一般设是已求得的回归方程。是第个试验点代入回归方程所求的回归值。这里称实验值与其平均值的离差平方和为总离差平方和，记为，以此推测出与：已知公式及关系式如下： 定义为复相关系数，显然，越接近1，回归效果就越好。我们对问题二拟合出的方程：进行显著性检验得，明显接近于1，所以该方程的拟合程度较高，预测比较准确。八、模型推广算法是计算最短路径的经典算法，是许多工程解决最短路径问题的理论基础。最短路径问题又可以引申为最快路径问题、最低费用问题等，但他们的核心算法都
19、是最短路径算法经典的最短路径算法算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对算法采用了不同的实现方法。规划模型能够很好的解决本文中的增设销售连锁店问题。也可以将其推广到大面积区域的规划，比如从一个区域推广到多个区域或是一个市、一个省的情形。另外也可以推广到其他服务性行业的选址中的方案的确定。比如物流中心的选址就可以用规划模型来解决，知识此时需要考虑的因素，需要列出的约束条件和目标函数都有所不同。九、参考文献1姜启源 谢金星 叶俊（第三版），数学模型，北京：高等教育出版社，2003；2陈益富 卢潇 丁豪杰，对算法的优化策略研究J，计算机技术与发展,2006，09:73-75+
20、78；3徐海霞 任红松 袁继勇 杨德松 马智群，用及其“规划求解”功能拟合曲线方程J，农业网络信息，2004，02:37-39； 4程郁昕 陶金萍 蔡治华,拟合曲线的显著性检验J,安徽农业技术师范学院学报，2001，02:46-48； 5高更君 黄卫，现代物流中心的货物配送问题J，东南大学学报(自然科学版),2001，06:30-33。附录表1 连锁店的日销售量连锁店编号12345678所在城镇编号1201066331141106579日销售量（公斤）28733382232173323947925884811557038759连锁店编号910111213141516所在城镇编号11203627
21、34429411日销售量（公斤）14744325171150392654519489127736103连锁店编号17181920212223所在城镇编号2463145221612364日销售量（公斤）32512829539653637514783180811840附录利用软件结合算法，得到最优分配方案表：表2 最优分配方案连锁店编号所在城镇编号最短距离日销量（公斤）运输成本（元）基地12011200287330210663382231095514161925825791134147448911012003251701136151115037821334119451241594190127731
22、09319145723965312992116103147836892212351808141基地6336302173304311142394712356101088481413765191557013387928387594911227135926556314421289489550161117961034921724128325118818630282950202216863754842364718406附录年每个城镇对鲜猪肉的年度总需求量： 表3 描述统计量N和VAR00061154117323.40VAR00063154117816.20VAR00062154119325.92VAR00065154118960.80VAR00064154118081.69VAR00066154117690.01VAR00067154120240.93VAR00068154120709.51VAR00069154118502.13VAR00070154118408.05VAR00071154119662.59VAR00072154118745.00VAR00112154120100.94有效的 N（列表状态）154附录年的折线统计图：图1 城镇年需求量统计图图2 城镇年需求量统计图图3 城镇年需求量统计图图4 城镇年需求量统计图