网站地图
【www.arisingsemi.com--热门资讯】
3333333 2010年宝鸡文理学院数学建模竞赛编 号 专 用 页
评阅编号（由组委会评阅前进行编号）：
参赛队信息（由参赛队进行填写）：
姓名
专业班级
学 号
手机
备注
（如E-mail等）
指导教师信息（有指导教师的队填写）：
宝鸡文理学院大学生数学建模竞赛
承 诺 书
我们仔细阅读了宝鸡文理学院大学生数学建模竞赛的竞赛规则。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：
所属学校（请填写完整的全名）：
参赛队员 (打印并签名) ：1.
2.
3.
日期： 2010 年 06 月 06 日
阅卷使用页
l 阅卷编号：（阅卷组填写）
l 阅卷组长：
l 阅卷表格：
序
号
摘要
（15分）
模型分析
及建立
（40分）
求解及结
果分析
（35分）
其余及
特色
（10分）
总分
阅卷老师
签名
1
2
3
4
5
6
总 分
组长签名： 年 月 日
最优送货路线设计问题
摘 要
当今社会，网购已成为一种常见的消费方式.随着物流行业的兴盛，如何用最短的时间，最节约成本的方案，完成送货任务显得尤为重要.针对本案例，我们采用了大量的科学分析方法，并进行了多次反复验证，得出如下结果：
1：根据所给问题及有关数据，我们将题目中给出的城市，及其之间的线路可看成一个赋权连通简单无向图，采用了求这个图最小生成树的办法，求出最优线路.在此基础上，我们通过观察分析计算对上述结果进行修正，得出最终结果.
2：根据所给问题，我们发现当货物不能一次送完时，中途需返回取货，而返回路径当然越短越好，可通过求途中两点最短路径的方法求出.
关键字：送货线路优化，赋权连通简单无向图， Excel，最小生成树.
一、问题重述
现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，现有实业公司，该实业公司生产专业生产某专用设备产品，专用设备产品该每件重达5吨（其长5米，宽4米，高6米），该实业公司库房设在北京，所有货物均由一货机送货，该机种飞机翼展88.40米（机身可用宽20米），机长84米（可用长50米），机高18.2米（可用14米），最多可装载250吨货物，起飞全重达600吨，平均速度为900公里/小时）将货物送至全国各个省辖市（图1所示红色圆点，除北京之外共19个省辖市），假定货机只能沿这些连通线路飞行，而不能走其它任何路线；但由于受重量和体积限制，货机可中途返回取货.经过的各个省市都要一定的停靠费用和停靠时间（停靠时间为常量2小时），假设经过某个省市的停靠费用为：
停靠费用=5000元×该省市的消费指数；
问题
1：若图示中19个省辖市每个省辖市只要一件产品请设计送货方案，使所用时间最少， 标出送货线路.
问题
2：若图示中19个省辖市需求量见表1，请设计送货方案，使所用时间最少.
问题
3：若该实业公司为了花费最少，针对问题1和问题2分别求出花费、标出送货线路.
表1
省辖市
新疆
青海
宁夏
云南
北京
湖南
海南
福建
台湾
吉林
需求量（件）
1
3
5
4
0
10
3
4
9
8
消费
指数
1.2
1.1
1.05
1.3
1.9
1.4
1.7
1.6
1.9
1.2
省辖市
甘肃
西藏
重庆
内蒙古
河南
广西
香港
江苏
上海
黑龙江
需求量（件）
7
9
12
5
4
5
6
9
7
3
消费
指数
1.3
1.0
1.5
1.2
1.3
1.2
1.8
1.5
1.8
1.3
二、基本假设
1.假设货物在存放中，货物与货物之间无空隙.
2.飞机在出行送货期间，无天气突变等突发状况.
3.飞机自身无任何故障，并且在空中始终以平均速度为900公里/小时.
4.假定货机只能沿着图中的连通路线飞行，而不走其他的路线.
三、符号说明
在地图上城市可以用点表示如北京可用A4表示，详细见下表.
符号
城市
符号
城市
A1
黑龙江
A11
青海
A2
吉林
A12
重庆
A3
内蒙古
A13
湖南
A4
北京
A14
福建
A5
上海
A15
台湾
A6
江苏
A16
香港
A7
河南
A17
海南
A8
宁夏
A18
广西
A9
甘肃
A19
云南
A10
新疆
A20
西藏
AiAj ：点Ai到点Aj的线段
权
（1） ：表示题目中给出的两城市之间的权，如北京—上海（A1A5）的权
（1）为9.
权
（2） ：表示通过两城市之间路程所花费的时间，如北京—上海（A1A5）的权
（2）为9*100/900+2=3（小时）
权
（3） ：表示通过两城市之间路程的花费，如北京—上海（A1A5）的权
（3）为9*2500+1.85*5000=31750（小时），1.85为两城市指数的平均值.
V ：A1，A2，A3，A4，A5，A6，A7，A8，A9，A10，A11，A12，A13，A14，A15，A16，A17，A18，A19，A20的集合.
E ：A1A2，A1A3，A1A5，A1A6，A2A4，A3A10，A4A10，A4A12，A4A13，A4A16，A4A5，A4A7，A5A14，A5A15，A6A14，A6A8，A7A10，A7A12，A7A19，A8A9，A9A11，A10A11，A10A19，A10A20，A11A12A，12A18，A13A16，A13A17，A17A18，A19A20的集合.
W ：V中点之间的权
（2）的集合，则G=（V，E，W）表示赋权连通简单无向图
M ：V中点之间的权
（3）的集合，则F=（V，E，M）表示赋权连通简单无向图
四、问题的分析
当今社会，网购已成为一种常见的消费方式.随着物流行业的兴盛，如何用最短的时间，最节约成本的方案，完成送货任务显得尤为重要.
针对本案例，城市可以看成点，而他们之间的连线既可以看成是时间，也可以看成成本，那么就构成了两个赋权连通简单无向图，这个问题就转化成求这两种情况下，两种图的最小生成树问题.
五、模型的建立
问题
1：
根据题目意思，两城市之间的时间=权
（1）*100/速度+2（单位：小时）
例如北京到上海A4A5权
（1）是17，则
北京到上海A4A5关于时间的权为9*100/900+2=3（小时），其他见下表
线路
权
（1）
权
（2）（时间）
线路
权
（1）
权
（2）（时间）
A8A9
2
2.22222222
A6A8
10
3.11111111
A1A2
2
2.22222222
A10A19
11
3.22222222
A17A18
2
2.22222222
A1A3
11
3.22222222
A13A16
2
2.22222222
A19A20
12
3.33333333
A13A17
3
2.33333333
A7A12
12
3.33333333
A5A14
3
2.33333333
A4A7
12
3.33333333
A5A15
4
2.44444444
A7A19
15
3.66666667
A10A11
6
2.66666667
A1A6
15
3.66666667
A12A18
7
2.77777778
A1A5
17
3.88888889
A6A14
7
2.77777778
A3A10
20
4.22222222
A2A4
8
2.88888889
A4A12
20
4.22222222
A10A20
8
2.88888889
A4A13
21
4.33333333
A9A11
8
2.88888889
A7A10
22
4.44444444
A11A12
8
2.88888889
A4A10
23
4.55555556
A4A5
9
3
A4A16
24
4.66666667
定义V为A1，A2，A3，A4，A5，A6，A7，A8，A9，A10，A11，A12，A13，A14，A15，A16，A17，A18，A19，A20的集合，定义E为A1A2，A1A3，A1A5，A1A6，A2A4，A3A10，A4A10，A4A12，A4A13，A4A16，A4A5，A4A7，A5A14，A5A15，A6A14，A6A8，A7A10，A7A12，A7A19，A8A9，A9A11，A10A11，A10A19，A10A20，A11A12A，12A18，A13A16，A13A17，A17A18，A19A20的集合，定义W为V中点之间的权
（2）的集合，则G=（V，E，W）表示图.
根据最小生成树的求法可以求出改图G的最小生成树如图
沿着最小生成树的路线相对较短，为：A4—A5—A15—A5—A14—A6—A8—A9—A11—A10—A20—A10—A19—A10—A11—A12—A18—A17—A13—A16—A4—A7—A4—A2—A1—A3—A1—A2—A4
经过观察上面下划线的部分A11—A10—A20—A10 —A19—A10—A11并不是最短的，经计算这个路线A11—A10—A20—A19—A10—A11比上一个段，所以用之替换，得到最短的线路为：
A4—A5—A15—A5—A14—A6—A8—A9—A11—A10—A20—A19—A10—A11—A12—A18—A17—A13—A16—A4—A7—A4—A2—A1—A3—A1—A2—A4
可以将相邻两点的权
（2）相加，和即为花费，经过计算上述线路所花时间是76.44444小时，为最短时间.
问题
2：
根据题目意思，两城市之间运输的价格=权
（1）*2500+平均指数*5000（单位：价格）
例如北京到上海A4A5权
（1）是17，北京的指数为1.9，上海为1.8，则先求出平均指数（1.9+1.8）/2=1.85，根据公式可得。