货物配送问题

1、题目货物配送问题摘要本文研究某公司猪肉销售问题，构建数学模型，设计生产与配送方案和增设销售连 锁店方案，使得销售量最大。问题一要求设计生产与配送方案，使运输成本最低。将最低成本问题转化为最短路 径问题，采用Dijkstra算法：D v Min D v , D w l w,v利用Matlab编程，得到生产基地到所有连锁店的最短路线：生产基地63为提供3、467、8、12、4、16、7、8、20、23这几家连锁店提供鲜猪肉，所耗费的成本约为 4559元，生 产基地120为1、2、5、9、1011、315、19、21、22这几家连锁店提供鲜猪肉，所耗费的成本为 6175元，最低总成本为10734元。

2、问题二要求分析各城镇需求特征并预测需求达到峰值的时间及到峰值时需求达到 前5位和后5位的城镇。对于需求通过特征分析，通过 SPSS乍出城镇需求量与时间的折 线图，可知全省的鲜猪肉的需求量从 2008 2012年虽上下波动，但总体上升趋势明显， 每年对鲜猪肉的需求量明显升高。对于对未来几年的预测，通过作出的散点图利用Matlab进行拟合，根据拟合曲线得 出2014年需求量会达到峰值为1437802，前五名分别为120号，63号，31号，106号, 104号城镇，后五名分别为30号，94号，84号，109号，129号城镇。问题三要求为公司设计增设销售连锁店方案，使全省销售量最大。采用0 1规划算法

3、，构建数学模型：154Max 输 yi 1通过 Lin go 求得优化方案：所求城镇 6 8 10 18 31 33 50 54 56 64 68 76 100 101 104 110 116 120 123 125 150 154需要增设连锁店，其中城镇120,31,6410123分别含有连锁店 的个数是3,2,2,2,2。关键词销售方案 Dijkstra算法拟合曲线 0 1规划模型、问题背景与重述1.1 问题背景某公司是一家肉类食品加工与销售公司，主营：鲜猪肉。该公司在全省县级及以上 城镇设立销售连锁店。全省县级及以上城镇地理位置及道路连接见数据文件：全省交通 网络数据 . xlsx 。目

4、前该公司现有 2个生产基地、 23家销售连锁店，生产基地设在 120号 和 63 号城镇，为 23 家连锁店提供鲜猪肉，连锁店的日销售量见附录 I 。通过广告宣传等手段，未来几年公司在全省的市场占有率可增至3 成左右（各城镇对公司产品每日需求预测数据见文件： 公司未来各城镇每日需求预测数据 .txt ），调查还 发现，公司产品的需求量与销售量并不完全一致，若在当地（同一城镇）购买，则这一 部分需求量与销售量相同， 若在不足 10 公里的其他城镇的销售连锁店购买， 则这一部分 需求量只能实现一半（成为公司产品销售量，由于距离的原因，另一半需求转向购买其 他公司或个体工商户的产品） ，而在超过 1

5、0 公里的其他城镇的销售连锁店购买，销售量 只能达到需求量的三成。于是，公司决定在各城镇增设销售连锁店，基于现有条件、成 本等的考虑，原有的 23家销售连锁店销售能力可在现有销售量的基础上上浮 20% ，增 设的销售连锁店销售能力控制在每日 20吨至 40吨内，并且要求增设的销售连锁店的销 售量必须达到销售能力的下限。同一城镇可设立多个销售连锁店。1.2 问题重述分析数据，并通过数学建模知识回答下述问题：1、若运输成本为 0.45元/ 吨公里 ，为公司设计生产与配送方案，使运输成本最低。2、根据公司收集的近 5 年全省各城镇的鲜猪肉月度需求数据， 分析各城镇需求特征， 并 预测未来何时全省鲜猪

6、肉需求达到峰值和达到峰值时需求达到前5位和后 5 位的城镇。3、为公司设计增设销售连锁店方案，使全省销售量达到最大。问题分析2.1 问题一的分析要设计生产与配送方案使运输成本最低， 即可将最低成本问题转化为最短路径问题， 进而得到最优化生产和配送方案。Dijkstra 算法 2是最具代表性的最短路径的算法，它以起点为中心向外层层拓展直 至结点，因此可将连锁店和生产基地看成质点，路基最短即两点之间距离最短 , 可通过 软件画出城镇网络图，并利用 Matlab结合Dijkstra算法，得到生产基地到所有连锁店的 最短路线，从而得到最优分配方案。2.2 问题二的分析要分析各城镇需求特征，首先要明白数

7、据的的变化情况，通常对这种题目要求，可 以对所给数据进行均值和标准差运算来了解数据的波动情况和离散程度，并通过 SPSS 作出各城镇需求量与时间的折线图。为准确得知公司发展状况，并采取相对应的措施，要求对未来峰值的预测，可通过画出散点图了解总需求量的变化，并利用最小二乘法对散点图进行曲线拟合3，预测出未来走势，利用拟合出的两个函数式估测出出现峰值时的年份，对于需求排名前五和后 五情况确定，则可以对2008年至2012年这五年间的需求量进行统计并通过排名情况总 结。2.3问题三的分析问题三要求设计增设销售连锁店方案，使全省销售量达到最大，要考虑连锁店的销 售量、需求量与距离变化的关系以及增设的销

8、售连锁店销售能力控制在每日20吨至40吨内，并且要求增设的销售量必须达到销售能力的下限，且同一城镇可设立多个销售连 锁店。根据题意拟采用0-1规划算法，对新增连锁店进行规划，建立目标函数。同一城镇 可设立多个销售连锁店，以及连锁店对于每个城镇的供给量的实现，（在10公里以内，需求量等于销售量的一半，10公里以外，需求量等于销售量的三分之一，且每个店最低 销量为20吨），由此建立线性约束条件，并利用 Lin go软件建立优化模型，则可以得出 优化方案。三、模型假设结合本题的实际，为了确保模型求解的准确性与合理性，本文排除一些干扰因素, 提出以下几点假设：1、假设材料中信息来源可靠真实；2、假设各

9、基地足够地供给鲜猪肉，不出现断货缺货的情况；3、假设运输成本中只考虑距离问题，其他损失忽略不计；4、假设在近期内连锁店不会出现食品安全问题，保证正常运营。四、符号说明为了便于问题的求解，本文给出以下符号说明:符号说明S第i个数据值S所有数据的平均值ai新增的销售能力bi不足10公里的其他城镇的连锁店销售能力Ci超过10公里的其他城镇连锁店的销售能力di未来第i个城镇的需求量x原有的连锁店在增设之前的销售能力y原有的连锁店在增设后的销售能力五、模型的建立与求解5.1问题一的模型建立与求解模型建立Dijkstra算法是很具有代表性的最短路径的算法，它是以起点为中心向外层层拓展 直至结点。在本题中，

10、采用软件求得货物配送的最短路径，进而得到最优生产和配送方 案。由于需要解决的问题转化成了最短路径问题，所以解决任意两点间的最短距离问题 采用Dijkstra算法。因此建立模型，将每个连锁店和生产基地看成一个质点，按照城镇编号命名为 点,2,3,，54，其中点63和点120是货物运输的起点。设源始点v到某一结点u的距离为 D u，结点v到结点u的距离为I v,u，则以点63为始点时，D u l 63,u表示两者之 间有直通车，D u表示两者之间没有直通车。同理，点120。比较点63和点120到相同点的之间的距离，取最小的那一种情况，来满足最短距离配送问题要求，其中重要步 骤如下：D vMinDv

11、,Dw I w,v ，w是除了 63的其他始点，由此将最低成本问题转化为最短路径问题。模型求解1JI1訂丹祜和直井（1）利用软件根据全省交通网络数据表和高速公路连接表中的数据绘制出城镇网 络图，如下图：200第7300350iDO图1城镇网络图如图所示，我们可以清晰地看出各城镇之间的相对位置，也较为直观地看出货物运 输路线。（2）利用Matlab软件结合Dijkstra算法，编写程序，很快地得出生产基地到所有 连锁店的最短路线，得到最优分配方案表（具体见附录II）根据表中数据可知，生产基地63为提供3、4、6、7、812、141617、8、20、23这几家连锁店 提供鲜猪肉，所耗费的成本约为

12、4559元，生产基地120为1、2、5、9、0、1、31519、21、22这 几家连锁店提供鲜猪肉，所耗费的成本为 6175，由此得到运输最低成本约为10734元。5.2问题二的模型建立与求解要求分析各城镇的需求特征，首先，我们分别求出每年每个月所有城镇需求量的平 均值，结果如表2：表2城镇需求量平均值12345678910111220086956897006947087097067017077197177172009714712719728724729731736P 741738730P 7362010740744745745739745748751752759744759201175475

13、875776276175576676576577476017752012764767771763781783769769777770780768由表格数据可得，每年每月所有城镇的需求量的平均值都普遍在呈上升趋势，我们 画出该表格的折线统计图：图2城镇月需求量平均图由图得，城镇每年每月的需求量的平均值呈上升趋势，但趋势趋于平缓，下面我们 做出所有月份城镇平均值的的折线图：图3城市月需求量平均总图由图3可得，全省的鲜猪肉的需求量从 2008-2012年虽上下波动，但总体上升趋势明显，每年对鲜猪肉的需求量明显升高。对于未来几年的预测，首先我们求出 2008-2012年每年全省鲜猪肉的总需求量，如 下

14、：(1304076 1346541 1382772 1410444 1427072)根据前五年全省鲜猪肉的总需求量，我们可以做出散点图如图4：1 441411鮎1.341.321 I 522 53354*5 S图4散点图对散点图分析可得2008-2012年的总需求量呈抛物线形式，所以运用最小二乘法对 散点图进行曲线拟合。上述过程以求得2008-2012年全省鲜猪肉的需求量，以年份ti(t 1,2,3L)为自变量， 总需求量y为因变量，所以假设曲线为二次多项式 y a2 a?x a3，利用Matlab进行 拟合求得系数：所以函数方程式为：y 4302x2 5680x 1251000得出拟合图后发

15、现这五年间大致上呈增长的趋势发展，接着我们对未来几年的鲜猪 肉的总需求量做出预测，如图 6：对图6进行分析得，同时将i 6、7、89代入函数关系式得第七年全省对鲜猪肉的需 求量会达到峰值，即2014年需求量会达到峰值为。在对2014年达到峰值时，对前五名与后五名排名时，我们求出2008 2012年每个城镇对鲜猪肉的年度总需求量（见附录III），其次对每年的每个城镇鲜猪肉的总需求量 分别作出折线统计图（其中 2008年的折线图见图7，2009 2012年的折线统计图见附录 IV ）。图7 2008年每个城镇鲜猪肉总需求量折线图通过对五张折线图的分析，我们发现每年各城镇对鲜猪肉总需求的排名几乎没有

16、变动，所以推测2014年各城镇对鲜猪肉需求量排名与几乎前几年相同，前五名分别为120号，63号，31号，106号，104号城镇，后五名分别为 30号，94号，84号，109号， 129号城镇。5.3问题三的模型建立与求解模型建立题目要求设计增设销售连锁店方案，使全省销售量达到最大。而经调查发现，公司 产品的需求量与销售量并不完全一致，若在当地（同一城镇）购买，则这一部分需求量 与销售量相同，若在不足10公里的其他城镇的销售连锁店购买，则这一部分需求量只能 实现一半，而在超过10公里的其他城镇的销售连锁店购买，销售量只能达到需求量的三 成。所以建立0 1规划模型，首先建立线性目标函数，其中ti

17、1表示第i个城镇增加连锁店， ti 0表示第 i 个不增设连锁店则有目标函数：154Maxtiai yii1 约束条件：s.t.2000tibiai4000t id ixi2000ticiyi 1.2xi5.3.2 模型求解利用软件 Lingo 结合 0-1线性规划，求得结果如下： 所求城镇 6 8 10 18 31 33 50 54 56 64 68 76 100 101 104 110 116 120 123 125 150 154需要增设连锁店，其中城镇 120， 31， 64，10，123 分别含有连锁店的个数是 3，2，2，2，2 个。使得全省销售量最大，最大 值为 919414 公

18、斤六、模型的评价与改进6.1 模型的评价6.1.1 模型的优点1、拟合曲线可以得到近似函数方程，比便预测未来数据；2、规划模型与实际紧密联系，将问题简单化，具有很好的通透性和推广性；3、模型的计算采用专业的数学软件，可信度高。模型的缺点1、 0-1规划模型约束条件有点简单；2、 Dijkstra 算法只能解决正权值图，虽是较为成熟、最易接受的一种算法，但始终存在 局限。6.2 模型的改进对于问题一的改进 最短路径是图论研究中一个重要课题，传统公认的求得最短路径的最好算法是Dijketra 算法，然而存在时间和空间复杂度，现对此算法进行改进，采用邻接表和堆排 序的优化方法。首先，将数组 T 通过

19、堆排序调整为小顶堆，取数组首元即堆顶节点为中 间节点，并将该节点加入到已标记集合 S 中，再比较更新节点的邻接点集合与已标记集 合的差集中任一节点Vi的当前最短路径值，然后查找S集合所有节点的邻接点的并集和 S集合的差集，同时将这些节点顺次存入数组 T中，覆盖原数组中的节点，并设置一个 计数器 i 记录节点个数，最后将数组中的前 i 个元素按它们当前的最短路径值调整成小 顶堆，取堆顶节点为下一个最短路径节点将其个归并到集合 S 中，如此反复得出理想的 最短路径值 。对于问题三的改进基于本文的问题，可把0-1非线性规划问题转化为约束优化问题，采用动态双目标 的约束处理方法，即粒子群混合算法。首先

20、设置当前迭代代数t=1,确定种群的大小N , 搜索空间的维度D，在0，1空间内产生N个粒子的初始位置和速度。第二步将第个粒 子的最好位置pbest设置为该粒子的当前位置，如果A=x|?(x)工?,则全局最优位置, 第三步根据Sigmoid函数公式、改进式和粒子优化等式更新每个粒子的速度与当前位置， 第四步根据前面转化出来的无约束双目标问题得出的公式：mi nF(x) = min ?(x),f(x)更新每个粒子的个体优化位置和全局最优值，按照一定的概率对当前粒子在0，1空间进行随机赋值，最后让t=t+1返回到步骤三，直到获得一个预期的适应值。七、模型的检验将杂乱无序，无相关关系的散点拟合成曲线，

21、用来预测未来情况，但意义不大，因 此为了模型的高精确度和曲线的高切合度，有必要对回归方程进行显著性检验。一般设$ b° b b?X2 L bmXm是已求得的回归方程。yi是第i个试验点代入回归方程所求的回归值。这里称实验值 yi与其平均值y的离差平方和为总离差平方和，记为S、，以此推测出S回与S剩: 已知公式及关系式如下：s回1 S总总、s总总、n2S总yii 1y定义R21 S剩/&为复相关系数，显然-1 ny二Yini 1n2i 1y屮0 R 1,R越接近1,回归效果就越好。我们对问题二拟合出的方程：y4302x2 56800x 1251000进行显著性检验得R 0.99

22、98,明显接近于1,所以该方程的拟合程度较高，预测比较 准确。八、模型推广Dijkstra算法是计算最短路径的经典算法，是许多工程解决最短路径冋题的理论基 础。最短路径问题又可以引申为最快路径问题、最低费用问题等，但他们的核心算法都 是最短路径算法经典的最短路径算法一一Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法。0 1规划模型能够很好的解决本文中的增设销售连锁店问题。也可以将其推广到大面积区域的规划，比如从一个区域推广到多个区域或是一个市、一个省的情形。另外也 可以推广到其他服务性行业的选址中的方案的确定。比如物流中

23、心的选址就可以用0 1规划模型来解决，知识此时需要考虑的因素，需要列出的约束条件和目标函数都有所不 同。九、参考文献 1 姜启源 谢金星 叶俊（第三版），数学模型，北京：高等教育出版社， 2003； 2 陈益富 卢潇 丁豪杰，对 Dijkstra 算法的优化策略研究 J ，计算机技术与发展 , 2006， 09:73-75+78；3徐海霞 任红松 袁继勇 杨德松 马智群，用EXCEL及其“规划求解”功能拟合曲线 方程J，农业网络信息，2004, 02:37-39; 4 程郁昕 陶金萍 蔡治华 ,拟合曲线的显著性检验 J, 安徽农业技术师范学院学报， 2001， 02:46-48;5高更君 黄卫

24、，现代物流中心的货物配送问题 J ，东南大学学报 （自然科学版）, 2001， 06:30-33。附录I表1连锁店的日销售量连锁店编号12345678所在城镇编号1201066331141106579日销售量（公斤）:287333822321733239479258 :84811557038759连锁店编号910111213141516所在城镇编号1120362734429411日销售量（公斤）：14744 32517115039265451948912773r 6103连锁店编号P 17181920212223所在城镇编号2463145221612364日销售量（公斤）32512829539653637514783180811840附录II利用Matlab软件结合Dijkstra算法，得到最优分配方案表:表2最优分配方案连锁店编号所在城镇编号最短距离日销量（公斤）r运输成本（兀）基地1201120028733021066338223109551416192582579113414744891101200325170113615111503P782133411945124159419012