货物配送问题 - 图文

2013高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模夏令营竞赛的竞赛规则。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 （打印并签名）：1. 2. 3. 指导教师或指导教师组负责人（打印并签名）：

日期： 2013 年 8 月 21 日

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

2013高教社杯全国大学生数学建模竞赛

编 号 专 用 页

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

赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

货物配送问题

摘要

梦想连锁是一家主营鲜猪肉的销售公司。为了更好的提高该公司的销售量。本文建立了相关数学模型，研究鲜猪肉销售问题，并给出了相关方案。

问题一：首先用Matlab作出了全省各个城镇位置的分布图，再用floyd算法求得各个城镇间的最短距离，从而得出2家生产基地到23家连锁店的最短距离，最后用lingo优化模型得到2家生产基地分别分配给23家连锁店的销售量，由公式Min(??xijcij)?450?1.054?1010(元)得到最低运输成本。

i?1j?1221问题二：分析各个城镇需求特征，用曲线拟合的线性最小二乘法得到销售量的曲线方程y??4300?x2?56800x?1251100，并预测了未来的增长趋势，发现在2014年销售量达到峰值是1438吨。得到销售量排名前5的城镇是城镇（120）>城镇（31）>城镇（63）>城镇（106）>城镇>（104）；销售量排名后5位的是：城镇（94）<城镇（30）<城镇（84）<城镇（109）<城镇（129）。

问题三：建立0-1整数规划的优化数学模型，满足题目要求的条件下，得出需要再增加24家连锁店。才能使全省销售量达到最大。

问题四：在第三问的基础上，可以发现，有5个连锁店的销售量超过40吨，其中两个就有生产基地，为此，在其余3个城镇建立生产基地。运用线性规划模型得出：总运输成本=单位运输成本?生产基地与连锁店的距离?运输重量， 且最低运输费用为3.7633.7636?109元。

问题五：用floyd算法将高速公路都转化为普通公路来进行计算，并运用floyd算法求得每个城镇间的普通公路的最短距离，再用优化方案得出5个生产基地送给40个连锁店所在城镇的最优分配，建立优化模型可得最小货车数量是167辆。

【关键词】floyd算法 lingo优化模型 曲线拟合 0-1整数规划

1

一、问题重述

随着经济的发展，人民的消费水平提高，需要的物质增加。为了满足人民

的需求，这就要求连锁销售公司对各连锁店进行重新分配调整。

为此，我们就梦想连锁公司的销售情况，回答以下问题：

问题一：目前公司现有2个生产基地，23家销售连锁店，生产基地设在120号和63号城镇，为23家连锁店提供鲜猪肉。若运输成本为0.45元/吨公里。请你为公司设计生产与配送方案，使运输成本最低。

问题二：请运用相关数学知识分析各城镇需求特征，并预测未来数年，何时全省鲜猪肉需求达到峰值，达到峰值时需求达到前5位和后5位的城镇是那些？

问题三：请你为公司设计增设销售连锁店方案，使全省销售量达到最大。 问题四：在增设销售连锁店的基础上，公司决定增加生产基地，地址设立在城镇所在地，每日产品生产必须达到250吨以上，在生产与销售各环节不能有产品积压。请你为公司设计生产基地增设方案，使运输成本最低。

问题五：公司产品若采用载重1.5吨的小货车从生产基地运往销售连锁店，小货车在高速公路上限速100公里/小时（高速公路见附录2），在普通公路上限速60公里/小时，销售连锁店需要的产品必须当日送达。假设每日车辆使用时间不超过8小时，小货车装满或卸完1.5吨的货物均需要半小时，本市运输车辆行驶时间可忽略不计。

在公司增设销售连锁店、增加生产基地后，为完成每日运输任务，请你为公司确定小货车的最小需求量及各车辆的调运方案。

二、问题分析

问题1：目前公司有2个生产基地，分别在120号和63号城镇，有23家销售连锁店，运输成本为0.45元/吨公里。为了使运输成本最低，则需要生产基地运输到销售店的距离最短。建立lingo优化模型，可得出合理分配给各个销售店的量，且同时满足运输成本最低。

问题2:根据公司近5年的全省各城镇的鲜猪肉月度需求数据，经过分析，建立曲线拟合的线性最小二乘法得到了销售量的销售曲线，就可以预测未来数年的销售量，并根据曲线方程可知销售量在某一年能达到峰值，同时可以预测达到峰值时前5位和后5为的城镇。

问题3：是要求在原有连锁店的基础上再增设连锁店，使增加最少的连锁店来改变现有的供需状况，因此我们既要考虑连锁店距离城镇的位置，又要考虑供应与销售能力，紧接第一问，运用Matlab,lingo软件将23个城镇化分为几个区域，然后分别在每个区域增设连锁店。在十公里以内，需求量等于销售量的二分之一，在十公里之外，需求量为销售量的三成，来表达销售量，并且每个店的销售量要大于且等于20吨，然后求解。

2

问题4：在第三问的基础上，还是用同样的方法划分区域，然后分别算出每个区域需要增设的生产基地，约束条件是每日生产为250吨，销售量要大于等于生产基地的产量。

问题5：用线性规划来做，假设在高速公路运输需要S1辆小货车来运输，而在普通公路上需要S2辆小货车来运输。求S1+S2的最小值。约束条件为每日的使用时间不超过8小时，每辆货车运输所需的时间加上装货卸货的时间不得超过8小时，然后用Matlab软件求解。

三、基本假设

（1）假设搜集的数据真实有效； （2）假设没有其他因素的干扰；

（3）假设销售公司制度没有重大改革。

四、符号说明

符号 含义 各个城镇间的道路距离 销地的需求量 销地 甲基地 每年的总需求量 多项式系数 符号 含义 产地到销地的距离 产地 乙基地 年份序号 多项式系数 多项式系数 aij dj Bi A2 cij Ai A1 xi yi b a c f?i? 新增的所有连锁店的销售能力 H?i? 23家连锁店现有的销售能力 Y?i? x?j? g?j? yij

未来j号城镇的需求 在超过10公里的其他城镇的销售连锁店购买 j号城镇是否增设销售点 z?j? s?j? ki 在不足10公里的其他城镇的销售连锁店购买 原有的23家店在新增连锁店前的销售能力 第i个生产基地运输货物重量 每个连锁店所在城镇的销售能力 生产基地与连锁店的距离 Pj 五、模型的构建与求解

5.1 问题一模型的构建与求解

总运输成本=单位运输成本?产地和销地的距离?运输总重量

3

题中已给出单位运输成本，运输总重量也可由附录中的各个连锁店的销售量的总和来确定，因此仅有一项未知的因子，即产地和销地的距离。

由给出的附录全省交通网络数据，用Matlab程序绘出该省的主要城镇图，并将主要公路和连锁店的位置重点标出，如下图：

图1 主要城镇路线图

该省的主要城镇有154个，运用floyd算法求得各个城镇间的最短距离。 建立一个矩阵a，矩阵种元素aij为各个城镇间的道路距离，没有道路相连城镇之间的数值设为无穷大，编程求解。

从程序结果中挑选出两个生产基地到各个连锁店所在城市的最短距离如下表：

表1 两个生产基地到各个连锁店所在城市的最短距离表 连锁店所在城1 10 11 16 22 24 27 31 镇编号 63号城镇到187.99 108.36 179.15 157.32 168.95 128.94 135.1 114.66 其距离 120号城镇到134.31 175.67 239.26 103.64 252.61 218.39 202.41 169.37 其距离 连锁店34 36 42 63 63 64 65 79 4

所在城镇编号 63号城镇到162.07 193.72 153.11 0 0 7.31 19.09 28.17 其距离 120号城镇到119.54 151.19 110.58 89.45 89.45 96.76 108.54 117.62 其距离 连锁店所在城94 106 120 120 123 141 145 镇编号 63号城镇到190.98 84.51 89.45 89.45 94.56 122.56 137.83 其距离 120号城镇到170.17 63.7 0 0 5.11 61.72 72.85 其距离 根据附录1中连锁店所在的城市编号对连锁店编号及销售量进行重新排序，如下表：

表2 连锁店所在的城市编号及日销售量 城镇编号 1 10 11 16 22 24 27 31 连锁店编号 1 2 3 4 5 6 7 8 日销售量（公斤） 14744 8481 6103 14783 6375 3251 9265 23947 城镇编号 34 36 42 63 63 64 65 79 连锁店编号 9 10 11 12 13 14 15 16 日销售量（公斤） 451 11503 9489 21733 28295 1840 15570 38759 城镇编号 94 106 120 120 123 141 145 连锁店编号 17 18 19 20 21 22 23 日销售量（公斤） 12773 38223 28733 32517 18081 9258 39653 由上表可以得出给每个连锁店所在城镇派送的总的鲜猪肉的重量，并将需要派送鲜猪肉的城镇进行重新编号如下：

表3 每个连锁店所在城镇派送的总的鲜猪肉的重量 城镇编号 1 10 11 16 22 24 27 派送编号 1 2 3 4 5 6 7 派送货物（公斤） 14744 8481 6103 14783 6375 3251 9265 城镇编号 31 34 36 42 63 64 65 派送编号 8 9 10 11 12 13 14 派送货物（公斤） 23947 451 11503 9489 50028 1840 15570 城镇编号 79 94 106 120 123 141 145 派送编号 15 16 17 18 19 20 21 派送货物（公斤） 38759 12773 38223 61250 18081 9258 39653 5

题中要求设计最优生产与配送方案使得总运输费用最小，每个生产基地派送的总货物为其生产的重量，假设Ai分别为63号和120号两个生产基地(i?1,2)，

Bj分别为上面21个需要派送鲜猪肉的城镇(j?1,2,?21)，设xij(i?1,j2?;Ai运到销地Bj的量，cij表示产地Ai到销地Bj的?1,2表示产地,距离，dj表示销地Bj的需求量。由运输成本为0.45元/吨公里，即450元/公斤公里，建立该问题的数学模型为

目标函数 min(??xijcij)?450 （1）

i?1j?1221约束条件为

?2??xij?dj,j?1,2,?21?i?1 （2）

?x?0,i?1,2;j?1,2,?21?ij在lingo里输入相应的程序，解得：

Global optimal solution found.

Objective value: 0.1054089E+11 目标函数值约为1.054?1010元，具体派送方案如下表：

表4 具体派送方案表 派 送 重 销 地 量 0 8481 6103 0 6375 3251 9265 14744 0 0 14783 0 0 0 产 地 A1 A2 B1 B2 B3 B4 B5 B6 B7 6

B8 B9 23947 0 0 0 50028 1840 15570 38759 0 0 0 0 0 0 0 451 11503 9489 0 0 0 0 12733 38223 61250 18081 9258 39653 B10 B11 B12 B13 B14 B15 B16 B17 B18 B19 B20 B21 即按上表中的派送方案进行运输运输费最小，最小约为1.054?1010元。 由上表可知，A1代表乙基地，A2代表甲基地，B1,?,B21代表每个连锁店所在城镇编号对应的派送编号，因此，乙基地分别派送到城镇10、11、22、24、27、31、63、64、65、79，派送的总重量为163619公斤即163.619吨；甲基地分别派送到城镇1、16、34、36、42、94、106、120、123、141、145，派送的总重量为230168公斤即230.168吨。又由于每个基地的生产总量相当于每个基地派送给城镇的总重量，因此，甲基地的生产量为230.168吨，乙基地的生产量为163.619吨。

5.2 问题二模型的构建与求解：

根据附录中给出的数据进行画图分析：

7

1200 1000 800 600 400 200 0 2008年城镇1需求量需求量1月2月3月4月5月6月月份7月8月9月10月11月12月 5000 4000 3000 2000 1000 0 6000城镇10城镇9城镇8城镇7城镇6城镇5城镇4城镇3城镇2城镇11月2月3月4月5月6月7月8月9月10月11月12月2008年图2 2008年城镇1需求量 由2008城镇1需求量的走势图可知：在1月至8月鲜猪肉需求量保持呈现缓慢增长，但八月后需求量增加，到十月中旬达到最大值。再结合其他城镇在这一年销售可知与城镇1的变化情况基本一致，这说明154个城镇的销售情况也是如此。 8

1600 1400 12001000 800600 400 200 0 8000 7000 6000 5000 4000 3000 2000 1000 0 需求量城镇12008-2012年需求量图3 城镇1 2008-2012年需求量 对比城镇1与其他城镇的消费情况可得结论：销售量都是呈递增形式，在2008年至2010年，销售量增加的比较快，到2012年，销售量的虽然增加，但增加的比较缓慢。整年过程都出现波动，这符合实际情况。

1月2月3月4月5月6月7月8月9月10月11月12月1月2月3月4月5月6月7月8月9月10月11月12月1月2月3月4月5月6月7月8月9月10月11月12月1月2月3月4月5月6月7月8月9月10月11月12月1月2月3月4月5月6月7月8月9月10月11月12月1月2月3月4月5月6月7月8月9月10月11月12月1月2月3月4月5月6月7月8月9月10月11月12月1月2月3月4月5月6月7月8月9月10月11月12月1月2月3月4月5月6月7月8月9月10月11月12月1月2月3月4月5月6月7月8月9月10月11月12月2008年2009年2010年时期2011年2012年城镇11城镇10城镇9城镇8城镇7城镇6城镇5城镇4城镇3城镇2城镇12008年2009年2010年2011年2012年9

125000 120000 115000 110000 105000 100000 95000 1600000 1400000 1200000 1000000 800000 600000 400000 200000 0 需求量2008-2012年月总需求量折线图需求量14710131619222528313437404346495255582008-2012月份排序需求量年份12345图4 2008-2012年月总需求量折线图 以月份的销售量作得销售图可得出：总销售量是递增的，而且在前34个月销售量增加比较快，在以后的销售量却增加缓慢。这与年销售量得出结果基本符合。 从以上销售图可知，虽然销售量出现局部波动，但总体呈现上升趋势，在2011年销售量趋于平缓。 对附录中的数据进行处理可得全省从2008年到2012年对该公司的总需求量，如下表：

表5 全省从2008年到2012年对该公司的总需求量 年份 1 2 3 4 5 序号 2008 2009 2010 2011 2012 年份 总需求1304076.36 1346540.65 1382773.01 1410444 1427071.86 量（吨） 对数据做散点图如下： 10

1.44x 1061.421.41.381.361.341.321.311.522.533.544.55

图5 全省2008-2012年总需求量的散点图

从图中可以看出，全省从2008年到2012年对该公司的总需求量近似呈抛物线的形式，因此用最小二乘法对其进行曲线拟合。

上表中已求得全省从2008年到2012年对该公司的鲜猪肉的需求量，以年份序号为xi(i?1,2,3,?，)以每年的总需求量为yi，假设曲线为二次多项式

y?a1x2?a2x?a3。

运用Matlab程序对上面的数据曲线进行拟合，求出二次多项式的系数为：

a1??4300,a2?56800,a3?1251100

所以，对上面数据进行曲线拟合所得到的曲线表达式为：

y??4300?x2?56800x?1251100 （3）

曲线拟合的图像如下：

1.44x 1061.421.41.381.361.341.321.311.522.533.544.55

图6 曲线拟合图

由上图可以看出，曲线拟合的效果与原数据较为吻合，因此可以用拟合出

11

的曲线表达式及二次多项式y??4300?x2?56800x?1251100对未来的需求量进行预测，运用Matlab将数值代入，对未来的需求量的预测图如下：

1.441.421.41.381.361.341.321.31.281.26x 10602468101214

图7 未来需求量的预测图

因题中将2008年序号编为第一年，预测图中未来的需求量的峰值出现在第七年，类推即可得出，未来需求量的峰值将会出现在2014年。

根据预测，达到峰值时，销售量排名前5的城镇是：城镇（120）>城镇（31）>城镇（63）>城镇（106）>城镇>（104）；销售量排名后5位的是：城镇（94）<城镇（30）<城镇（84）<城镇（109）<城镇（129）。

5.3 问题三模型的构建与求解

为公司设计增设销售连锁店方案，使全省销售量达到最大，根据题中所给的已知条件，设f(i)表示新增的所有连锁店的销售能力；

H(i)表示23家连锁店现有的销售能力（即增设连锁店后原有的23家连锁

店的销售能力）；

Y(j)表示未来j号城镇的需求；

z(j)表示在不足10公里的其他城镇的销售连锁店购买，则这一部分需求量

只能实现一半（成为公司产品销售量，由于距离的原因，另一半需求转向购买其他公司或个体工商户的产品）；

x(j)表示超过10公里的其他城镇的销售连锁店购买，销售量只能达到需求

量的三成；

s(j)表示原有的23家店在新增连锁店前的销售能力。

12

?1g(j)???0j号城镇增设有销售点j号城镇不增设销售点154

由以上可知，目标函数为： Max??f(i)g(i)?H(i) （4）

i?1?Y(j)?z(j)?x(j)?s(j)?20000?f(j)?40000g(j)??f(j)?20000g(j)t?约束条件为 s.. （5）

H(j)?1.2s(j)??H(j)?Y(j)?z(j)?x(j)??f(j)g(j)?H(j)?Y(j)?z(j)?x(j)将其编入lingo程序并求解得：

在该省的6，8，10，18，31，33，50，54，56，64，68，76，100，101，104，110，116，120，123，125，150，154号城镇增设连锁店，将会使全省的总销售量最低，最大值为919414公斤。

5.4 问题四模型的构建与求解

在增设销售连锁店的基础上，即原有的23个连锁店以及现增设的连锁店的基础上，连锁店所在的城市分别为1，6，8，10，11，16，18，22，24，27，31，33，34，36，42，50，54，56，62，63，64，65，68，76，79，94，100，101，104，106，110，116，120，121，123，125，141，145，150，154号城镇，总共有40个城镇开设有连锁店，这40个城镇的销售能力分别为： 17692.8，23453，27491.8，35406，7323.6，1761.1，20673，7650，3901.2，11118，55474.1，20304.6，541.2，11459，5330.2，21972.8，22079.7，25328.2，23053.5，46489，25866.1，7035.5，25122，21909.5，19577.5，5134.6，21208.5，27736.1，20478，42360，22389，20382，94147.4，，40000，45370，29010.7，10270.8，3832，27089.3，22002.2公斤。

表6 每个连锁店的销售能力 城镇编号 序号 城镇编号 序号 销售能力 城镇编号 序号 销售能力 城镇编号 1 1 22 8 7650 42 15 65 6 2 24 9 3901.2 50 16 68 8 3 27 10 54 17 76 10 4 31 11 56 18 79 11 5 33 12 62 19 94 16 6 34 13 63 20 100 18 7 20673 36 14 11459 64 21 101 销售能力 17692.8 23453 27491.8 35406 7323.6 1761.1 11118 55474.1 20304.6 541.2 5330.2 21972.8 22079.7 25328.2 23053.5 46489 25866.1 13

序号 销售能力 城镇编号 序号 销售能力 城镇编号 序号 22 7035.5 104 29 20478 125 36 23 106 30 42360 141 37 24 110 31 22389 145 38 3832 25 116 32 150 39 26 120 33 154 40 27 121 34 28 123 35 45370 25122 21909.5 19577.5 5134.6 21208.5 27736.1 20382 94147.4 40000 销售能力 29010.7 10270.8 27089.3 22002.2 为公司设计生产基地增设方案，使运输成本最低，总运输成本=单位运输成本?生产基地与连锁店的距离?运输重量，第三问中已求出增设连锁店之后，每个连锁店所在城镇的销售能力，排序得出销售能力大于40000公斤的有31，63，106，120，123号城镇，因63号和120号城镇已经设立有生产基地，所以假设在31，106，123号城镇新增生产基地使运输成本最低。将31，106，123号生产基地分别记为A1,A2,A3,要向40个开设有连锁店的城镇进行运输，记为

B1,B2,B3,?,B40。

设第i个生产基地运输货物ki公斤(i?1,2,3)，生产基地与连锁店的距离为

yij(j?1,2,?40),Pj为每个连锁店所在城镇的销售能力， 将总运输成本设为目标函数，

目标函数为 minz?450?(k1?k2?k3)?y （6）

?k1?k2?k3?Pj,j?1,2,?40??k1?250000约束条件为 s.. （7） t?k?250000?2?k?250000?3编写Matlab程序并求解得：

在上面三个城镇都建立生产基地，即在31，106，123号城镇增设生产基地，

使运输费用最低，最低运输费用为3.7633.7636?109元。

5.5 问题五模型的构建与求解

本题在公司增设连锁店和生产基地之后，求货车运货的最优方案，采用载重1.5吨的小货车从生产基地运往销售连锁店，小货车在高速公路上限速100公里/小时，在普通公路上限速60公里/小时，高速公路经过的城镇附录中已给出。

为了将思路简单化，这里将高速公路都转化为普通公路来进行计算，由题中

5所给条件可知，每公里高速公路相当于的普通公路，将附录中所给的各城镇间

314

的距离数据进行转化，并运用floyd算法求得每个城镇间的普通公路的最短距离。

小货车每日车辆使用时间不超过8小时，小货车装满或卸完1.5吨的货物均需要半小时，本市运输车辆行驶时间可忽略不计。增设连锁店和生产基地后，共有5个生产基地，分别位于31，63，106，120，123号城镇，

求出每个生产基地与每个连锁店所在城市的距离，根据小货车的速度可以求出小货车从每个生产基地到每个城镇所用的时间，根据最短时间原则确定每个生产基地送货的城镇如下：城镇序号即为第四问中按连锁店所在城镇重新排列的序号：

31号生产基地送货的城镇有：4，5，7，8，9，10，11，12，13，14； 所需的时间分别为0.1050，1.3722，0.6265，1.5947，0.8637，0.5507，0，0.3678，1.3842，1.9553。

63号生产基地送货的城镇有：2，3，16，17，18，19，20，21，22，23，24，25；

所需的时间分别为0.3594，1.0738，0.8507，0.5622，0.9795，0.0933，0，0.1218，0.31821.0767，0.6570，0.4903。

106号生产基地送货的城镇有：1，26，27，28，29，30，37，38；

所需的时间分别为1.8840，1.7745，1.8957，1.3897，0.5386，0，0.8878，1.0453。

120号生产基地送货的城镇有：15，32，33，34； 所需的时间分别为1.9165，0.6128，0，0.3355。

123号生产基地送货的城镇有：6，31，35，36，39，40；

所需的时间分别为1.6620，0.8102，0，0.2355，0.9273，1.2102。 每个连锁店所在城镇重新编号，所用时间及运输情况如下：

表7 每个连锁店的运输情况 城镇编号 序号 单程时间 运货次数 城镇编号 序号 销售能力 单程时间 运货次数 城镇编号 序号 销售能力 1 1 6 2 8 3 10 4 11 5 16 6 18 7 20673 14 36 14 11459 8 64 21 销售能力 17692.8 23453 27491.8 35406 12 22 8 7650 6 42 15 16 24 9 3901.2 3 50 16 19 27 10 24 31 11 0 37 56 18 7323.6 1761.1 5 33 12 2 34 13 1.8840 0.3594 1.0738 0.1050 1.3722 1.6620 0.6265 11118 55474.1 20304.6 541.2 8 54 17 14 62 19 1 63 20 1.5947 0.8637 0.5507 0.3678 1.3842 1.9553 5330.2 21972.8 22079.7 25328.2 23053.5 46489 25866.1 15

单程时间 运货次数 城镇编号 序号 销售能力 单程时间 运货次数 城镇编号 序号 销售能力 单程时间 运货次数 城镇编号 序号 单程时间 运货次数 1.9165 0.8507 0.5622 0.9795 0.0933 4 65 22 7035.5 5 104 29 20478 0.5386 14 125 36 15 68 23 15 76 24 17 79 25 16 94 26 0 31 100 27 0.1218 18 101 28 25122 21909.5 19577.5 5134.6 21208.5 27736.1 17 106 30 42360 0 29 141 37 15 110 31 22389 15 145 38 3832 3 14 116 32 4 120 33 0 63 154 40 15 121 34 0.3345 27 19 123 35 45370 0 31 0.3182 1.0767 0.6570 0.4903 1.7745 1.8957 1.3897 20382 94147.4 40000 14 150 39 0.8102 0.6128 销售能力 29010.7 10270.8 20 7 27089.3 22002.2 19 15 0.2355 0.8878 1.0453 0.9273 1.2102 假设小货车按上述方式进行运输，因每辆货车使用时间不超过8小时，假设t为小货车的使用时间

小货车在运货物时单程时间已知，装载和卸货各需0.5小时，再返回生产基地进行下次运输才算一次完整的运输，因此单位时间为单程时间的2倍加上1小时，因此根据小货车运输单位时间来进行计算，每个小货车使用时间不超过8小时作为约束条件

上面已确定各个生产基地派出的小货车运输的城镇，根据上述条件，编写Matlab程序并求解得,即在公司增设销售连锁店、增加生产基地后，为完成每日运输任务，请你为公司确定小货车的最小需求量为167辆。具体运输方案如下：

31号生产基地派出30辆小货车，运往4，5，7，8，9，10，11，12，13，14号城镇；

63号生产基地派出51辆小货车，运往2，3，16，17，18，19，20，21，22，23，24，25号城镇；

106号生产基地派出39辆小货车，运往1，26，27，28，29，30，37，38号城镇；

120号生产基地派出20辆小货车，运往15，32，33，34号城镇；

123号生产基地派出27辆小货车，运往6，31，35，36，39，40号城镇； 由以上可得最小货车数量是167辆。

六、模型评价及推广

1.模型的优点

16

（1）弗洛伊德算法容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；

（2）曲线拟合可以得到近似函数方程，以便预测未来数据。 （3）线性规划有统一算法，任何线性规划问题都能求解。 2.模型的缺点

（1）0-1规划模型的约束条件简单；

（2）线性规划只能处理线性关系的问题。 3.模型推广

线性规划模型可以解决货物配送，能得到最佳的优化分配方案。

七、参考文献

[1]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出

版社，2001. [2]赵瑞安，吴方.非线性最优化理论和方法[M].北京：浙江科学技术出版社. [3]赵瑞安,吴方.非线性最优化理论和方法[M].浙江：浙江科学技术出版社，

1992：1-41. [4]董颖，唐加福，许宝栋，汪定伟.东北大学学报（自然科学版）[J]，2003，

2-6.

[5]姜启源.数学模型[M].北京：高等教育出版社，2003. [6]李志林，欧宜贵.数学建模及典型案例分析.北京：化学工业出版社，2006. [7]刘承平.数学建模方法.北京：高等教育出版社，2002.

17

八、附录

1）Floyd算法代码：

function [D,path,min1,path1]=floyd(a,start,terminal) D=a;n=size(D,1);path=zeros(n,n); for i=1:n for j=1:n

if D(i,j)~=inf path(i,j)=j;

end end end

for k=1:n for i=1:n for j=1:n

if D(i,k)+D(k,j)

end

end end end

if nargin==3

min1=D(start,terminal); m(1)=start; i=1;

path1=[ ];

while path(m(i),terminal)~=terminal

k=i+1; m(k)=path(m(i),terminal); i=i+1; end

m(i+1)=terminal; path1=m; end

2）求最短路径floyd程序： clear,clc

n=248; a=zeros(n); y(1,1)=0 y(2,2)=0 y(3,3)=0 y(4,4)=0 y(5,5)=0

18

end

4）拟合的Matlab代码： x=1:1:5;

y=[1304076.36 1346540.65 1382773.01 1410444 1427071.86]; A=polyfit(x,y,2) z=polyval(A,x);

plot(x,y,'k+',x,z,'r') %作出数据点和拟合曲线的图形 x=1:13;

y=-4300*x.^2+56800*x+1251100 plot(x,y,'*r') 5）0-1整数规划代码：

model: sets:

num/1,2..154/:f,H,ld,sd,Y,s,g; endsets data:

y=12808 1389 1740 1817 1600 8847 3090 10116 9359 7006 10133 16187 8614 7407 3656 1378 1248 6606 1767 7745 6580 4800 6411 4190 3823 3929 11435 3276 1461 1090 45123 11677 15042 1355 10086 5903 2333 4197 3775 5122 5900 1801 1678 11726 2241 15316 1509 1614 15370 15260 1850 5652 14728 14661 1997 16947 9293 5818 2195 1696 4760 1946 39125 5520 2612 3887 1986 20574 9096 4599 12986 3734 3218 1120 1981 16836 10147 4695 17634 4189 6320 1560 7802 1067 1897 11595 6809 1594 1475 6051 5760 1938 1620 1282 3420 1439 9615 1876 1610 18324 21299 1053 3703 19704 1548 34561 10558 4444 1174 17545 9688 1738 7141 1954 5191 16255 8254 1240 6783 87236 20154 1356 1752 10171 1597 4143 9236 14061 1094 2640 1640 3086 6955 1652 10400 7413 1402 6207 11873 11944 9345 3480 1277 5792 1374 1436 11398 15576 8766 20426 1860 4181 4762 16916;

ld=0 948.5 2095 0 848 2868.5 0 16780 998.5 28400 0 0 0 0 6412.5 0 0 0 0 0 0 3872.5 5066.5 1911.5 0 5717.5 1638 0 1638 730.5 5838.5 0 0 0 0 0 0 0 0 0 900.5 0 0 0 0 754.5 807 0 0 0 0 0 4371 0 0 998.5 0 1097.5 0 5289 1097.5 21107.5 7364 19562.5 4423.5 0 10287 4548 0 9606 1867 2299.5 0 0 0 5073.5 2347.5 10123 1943.5 0 7168 0 0 0 0 0 0 990.5 0 0 969 0 533.5 0 0 1710 0 0 0 0 526.5 0 0 774 969 5279 624 0 8772.5 4844 869 4190.5 8772.5 6166 8996.5 4127 620 0 0 0

29

678 0 43618 798.5 0 9104.5 7030.5 624 16927.5 4618 0 0 1543 0 3706.5 0 6810 5200 826 0 0 0 0 6386 2458 5972 718 4383 5936.5 4033.5 701 2381 0 0;

sd=5910.6 1815.3 0 0 583.8 11737.5 4398.3 595.8 484.2 0 1970.1 0 2707.2 1595.1 4047.6 383.1 1333.2 14067 2323.5 1974 522 1974 1974 3430.5 1178.7 0 0 0 2101.8 15460.2 4512.6 0 5262.6 3025.8 1770.9 5556 0 1832.4 4120.8 2442.3 0 3529.2 406.5 2273.4 8112.6 0 0 4611 0 6712.8 6273.6 0 0 7418.7 452.7 7382.7 4928.7 0 2807.7 0 927 0 0 783.6 0 595.8 0 0 522 0 0 965.4 336 4072.8 5050.8 0 0 0 0 9781.8 5518.8 4598.7 3798.6 416.7 5521.2 2042.7 478.2 442.5 545.1 1728 0 0 1026 3852.6 0 2884.5 878.7 914.7 0 2884.5 5910.6

2926.2 5911.2 0 10368.3 2520 0 5530.8 1333.2 0 480 0 0 0 0 0 0 0 2476.2 6911.4 28562.4 525.6 0 525.6 27413.7 0 2222.1 352.2 0 492 2701.2 492 3051.3 2612.1 495.6 406.8 0 3561.9 0 3561.9 925.8 5911.2 3892.5 0 0 0 4672.8 0 430.8 2629.8 0 2300.1 11202.6 5086.2;

s=14744 0 0 0 0 0 0 0 0 8481 6103 0 0 0 0 14783 0 0 0 0 0 6375 0 3251 0 0 9265 0 0 0 23947 0 0 451 0 11503 0 0 0 0 0 9489 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 50028 1840 15570 0 0 0 0 0 0 0 0 0 0 0 0 0 38759 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12773 0 0 0 0 0 0 0 0 0 0 0 38223 0 0 0 0 0 0 0 0 0 0 0 0 0 61250 0 0 18081 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9258 0 0 0 39653 0 0 0 0 0 0 0 0 0; enddata

max=@sum(num(i):f(i)*g(i)+H(i));

@for(num(j)|Y(j)+ld(j)+sd(j)-s(j)#GE#20000:g(j)=1;); @for(num(j):f(j)<=40000*g(j);); @for(num(j):f(j)>=20000*g(j);); @for(num(j):H(j)<=1.2*s(j););

@for(num(j):H(j)<=Y(j)+ld(j)+sd(j););

@for(num(j):f(j)*g(j)+H(j)<=Y(j)+ld(j)+sd(j)); @for(num(j):@bin(g(j)));

6）线性规划代码： m=ones(1,40)

s=[ 301.3200 103.4800 130.3900 101.7200 97.4500 107.5000 132.8300 128.5600 138.6100 6.3000 191.5400 180.7800 69.8900 263.6600 244.3700 270.6500 72.8100 99.7200 37.5900 235.4300 212.0700

30

83.2400 253.4600 257.7200 51.8200 213.4500 223.5000 33.0400 218.2800 207.5200 0 197.8400 174.4800 13.2400 211.0800 161.2400 49.8300 183.2400 124.6500 84.1000 214.8900 156.3000 86.4600 174.2800 115.6900 64.2600 133.5800 143.6300 105.1600 105.2800 115.3300 119.1000 103.9200 108.7100 118.0200 81.1500 91.2000 114.6600 84.5100 94.5600 121.9700 91.8200 101.8700 110.7900 103.6000 113.6500 127.5400 123.2700 133.3200 131.1200 84.1200 115.5800 116.9500 108.4400 122.7300 290.9300 106.4700 173.7900 283.3100 85.4700 150.7200 252.9500 55.1100 120.3600 217.2300 19.3900 86.7100 197.8400 0 67.3200 167.9700 51.3400 48.6100 178.4200 60.4500 27.1700 169.3700 63.7000 5.1100 180.8500 83.7700 23.5800 174.4800 67.3200 0 179.8800 53.1900 14.1300 231.0900 44.6500 57.8000 242.2200 53.3200 67.7400 230.1200 86.5100 55.6400 247.0900 102.9900 72.6100] c=m*s A=[1 1 1] b=[919424] Aeq=[] beq=[]

vlb=[250000,250000,250000] vub=[]

[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)7)求最小车辆

t=[ 5.1413 3.3977 1.8840 2.2583 2.1732 1.6953 0.3594 1.8920 2.4728 2.416331

2.4323 1.0738 2.1840 2.7648 2.7083 0.1050 1.8167 3.1923 3.7581 3.7017 1.3722 3.2938 4.6695 5.2353 5.1788 4.6302 2.8865 1.3728 1.7472 1.6620 0.6265 2.5482 3.9238 4.4896 4.4332 1.5947 3.3276 4.4726 5.0533 4.9969 0.8637 2.5753 3.8057 4.3865 4.3301 0.5507 2.2623 3.6380 4.2038 4.1473 0 1.9217 3.2973 3.8631 3.8067 0.3678 2.2894 3.6651 3.6646 3.7231 1.3842 3.2331 4.0547 2.6482 2.7067 1.9553 3.2660 4.0284 2.5933 2.6518 2.1158 2.5892 3.3516 1.9165 1.9750 1.0710 0.8507 2.2263 2.7921 2.7357 1.7527 0.5622 1.7547 2.3204 2.2640 1.9850 0.9795 1.7320 2.1657 2.2413 1.9923 0.0933 1.4603 2.0261 1.9697 1.9217 0 1.5537 2.1194 2.0630 2.0428 0.1218 1.6755 2.2413 2.1848 1.8465 0.3182 1.7408 2.3216 2.2652 2.4126 1.0767 2.2216 2.8024 2.7459 2.1853 0.6570 1.4020 1.9828 1.9263 2.0187 0.4903 1.8073 2.3881 2.3317 4.8488 3.3205 1.7745 3.2096 3.1532 5.1930 3.4493 1.8957 2.5972 2.5120 4.6870 2.9433 1.3897 2.0912 2.0060 3.8359 2.0923 0.5386 1.6722 1.5870 3.2973 1.5537 0 1.4351 1.3787 2.9965 1.2528 0.8557 0.8666 0.8102 3.4138 1.6701 1.0075 0.6128 0.6318 3.8631 2.1194 1.4351 0 0.0852 3.6978 2.3358 1.7696 0.3345 0.3930 3.8067 2.0630 1.3787 0.0852 0 3.5712 1.8275 1.1432 0.2919 0.2355 3.9315 2.1878 0.8878 1.0485 0.9633 4.3027 2.5590 1.0453 1.2142 1.1290 4.3562 2.6125 1.5985 1.0125 0.9273 4.6390 2.8953 1.8732 1.2953 1.2102] y=t.*2+1

a=[12 16 19 24 5 2 14 6 3 8 37 14 1 8 4 15 15 17 16 31 18 5 17 15 14 4 15 19 14 29 15 14 63 27 31 20 7 3 19 15] y1=y(:,1) y2=y(:,2) y3=y(:,3)

32

y4=y(:,4) y5=y(:,5)

y11=y1([4 5 7 8 9 10 11 12 13 14])

y12=y2([2 3 16 17 18 19 20 21 22 23 24 25]) y13=y3([1 26 27 28 29 30 37 38]) y14=y4([15 32 33 34]) y15=y5([6 31 35 36 39 40]) a11=a([4 5 7 8 9 10 11 12 13 14])

a12=a([2 3 16 17 18 19 20 21 22 23 24 25]) a13=a([1 26 27 28 29 30 37 38]) a14=a([15 32 33 34]) a15=a([6 31 35 36 39 40]) y21=y11.*a11' y22=y12.*a12' y23=y13.*a13' y24=y14.*a14' y25=y15.*a15' m1=sum(y21)/8 m2=sum(y22)/8 m3=sum(y23)/8 m4=sum(y24)/8 m5=sum(y25)/8

33

a(46,47)=3.22; a(47,48)=4.14; a(48,49)=10.81; a(50,49)=23.17; a(50,10)=57.96; a(51,50)=27.73; a(51,52)=12.84 a(53,52)=5.02; a(53,7)=5.03; a(54,49)=17.73; a(54,9)=10.45; a(55,47)=15.19; a(56,46)=13.5; a(56,55)=6.92; a(56,57)=25.9; a(57,55)=23.85; a(57,13)=38.19; a(57,58)=12.78; a(58,59)=4.07; a(59,9)=25.52; a(60,58)=7.59; a(60,61)=7.15; a(61,59)=5.7; a(61,7)=18.16; a(62,7)=4.66; a(62,63)=3.36; a(63,53)=5.45; a(64,63)=7.31; a(64,65)=11.78; a(65,6)=9.07; a(66,67)=12.05; a(67,68)=6.16; a(68,69)=7.3; a(69,3)=76.68; a(70,69)=9.38; a(70,8)=5.45; a(71,72)=5.45; a(72,70)=6.96; a(72,73)=29.86; a(73,74)=26.56; a(74,75)=34.86; a(75,76)=21.38; a(76,77)=7.95; a(77,78)=9.21;

24

a(78,65)=3.17; a(78,79)=7.16; a(79,66)=7.62; a(80,79)=12.75; a(80,67)=14.25; a(80,71)=15.47; a(81,76)=15.25; a(81,77)=9.3; a(81,80)=9.41; a(81,82)=30.09; a(82,72)=23.74; a(82,86)=113.17; a(74,86)=81.41; a(83,86)=39.54; a(83,84)=24.8; a(84,2)=12.84; a(85,86)=28.31; a(85,87)=30.43; a(86,87)=12.68; a(87,88)=58.27; a(88,75)=9.85; a(88,89)=40.2; a(89,4)=23.38; a(90,91)=31.41; a(91,92)=9.6; a(93,84)=6.62; a(93,95)=10.2; a(94,93)=16.53; a(94,83)=18.09; a(94,95)=14.94; a(96,95)=7.47; a(96,97)=17.32; a(97,98)=19.92; a(97,102)=29.66; a(98,96)=28; a(98,99)=15.04; a(100,97)=12.44; a(101,16)=20.64; a(101,100)=30.36;a(101,102)=7.75; a(102,90)=33.26; a(102,103)=17.53;a(103,104)=10.44;a(104,105)=6.46;

25

a(105,92)=8.67; a(105,106)=12.93; a(106,91)=10.96; a(106,107)=8.08; a(106,130)=21.63; a(107,17)=5.23; a(108,5)=17.39; a(108,76)=48.23; a(109,108)=11.91; a(109,110)=6.83; a(110,111)=5.68; a(111,5)=17.73; a(111,112)=6.21; a(112,113)=7.15; a(112,118)=7.28; a(113,110)=6.81; a(114,113)=5.9; a(114,115)=8.03; a(115,112)=6.61; a(115,116)=5.61; a(116,117)=8.18; a(117,118)=8.86; a(119,117)=16.69; a(120,119)=15.82; a(120,116)=22.06; a(121,120)=20.07; a(121,39)=30.16; a(121,38)=32.14; a(121,122)=5.09; a(122,123)=18.49; a(123,120)=5.11; a(124,123)=10.36; a(124,125)=3.77; a(125,120)=10.51; a(125,126)=15.96; a(126,116)=7.82; a(126,114)=5.81; a(127,14)=13.22; a(127,128)=6.79; a(128,17)=8.21; a(128,109)=22.99; a(129,127)=9.05; a(129,128)=6.04; a(129,107)=8.68;

26

a(130,127)=8; a(130,131)=14.78; a(131,14)=10.17; a(131,125)=16.78; a(132,131)=18.62; a(133,124)=22.71; a(133,132)=6.53; a(134,133)=10.1; a(134,123)=28.59; a(135,134)=12.24; a(135,136)=8.4; a(136,122)=31.92; a(137,136)=6.66; a(137,138)=7.31; a(138,135)=6.04; a(138,139)=10.87; a(139,134)=9.1; a(140,139)=13.46; a(141,132)=18.2; a(142,104)=24.54; a(143,142)=10.98; a(143,103)=24.92; a(143,144)=11.95; a(144,145)=9.64; a(144,147)=9.02; a(145,142)=9.39; a(145,146)=9.18; a(146,140)=7.51; a(147,146)=9.33; a(147,148)=13.55; a(148,149)=9.12; a(149,146)=13.22; a(149,139)=7.65; a(150,138)=8.77; a(150,149)=10.79; a(150,151)=7.65; a(151,137)=8.18; a(152,99)=100.69; a(152,38)=94.21; a(152,151)=23.56; a(152,153)=9.88; a(153,150)=24.11; a(153,154)=12.38; a(154,16)=34.66;

27

a(154,148)=18.15;

a=a+a'; M=max(max(a))*n^2; a=a+((a==0)-eye(n))*M; path=zeros(n); for k=1:n for i=1:n for j=1:n

if a(i,j)>a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; end end end end a, path m=a(63,:) n=a(120,:)

m1=m([1 10 11 16 22 24 27 31 34 36 42 63 64 65 79 94 106 120 123 141 145]) n1=n([1 10 11 16 22 24 27 31 34 36 42 63 64 65 79 94 106 120 123 141 145]) c=path(63,:) d=path(120,:)

c1=c([1 10 11 16 22 24 27 31 34 36 42 63 64 65 79 94 106 120 123 141 145]) d1=d([1 10 11 16 22 24 27 31 34 36 42 63 64 65 79 94 106 120 123 141 145])

3）lingo程序求解运费最小代码：

model: !运输派送问题; sets:

warehouses/wh1..wh2/: ;

vendors/v1..v21/: demand;

links(warehouses,vendors): s, volume; endsets

!目标函数;

min=@sum(links: s*volume)*450; !需求约束;

@for(vendors(J):@sum(warehouses(I): volume(I,J))=demand(J)); !这里是数据; data:

demand=38759 12773 38223 61250 18081 9258 39653 23947 451 11503 9489 50028 1840 15570 14744 8481 6103 14783 6375 3251 9265;

s=187.9900 108.3600 179.1500 157.3200 168.9500 128.9400 135.1000 114.6600 162.0700 193.7200 153.1100 0 7.3100 19.0900 28.1700 190.9800 84.5100 89.4500 94.5600 122.5600 137.8300

134.3100 175.6700 239.2600 103.6400 252.6100

218.3900 202.4100 169.3700 119.5400 151.1900 110.5800 89.4500 96.7600 108.5400 117.6200 170.1700 63.7000 0 5.1100 61.7200 72.8500;

enddata

28

本文来源：https://www.bwwdw.com/article/ibtd.html