数学建模 送货线路设计问题 标准答案 答案仅供参考Word文件下载.docx
- 文档编号:6287441
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:50
- 大小:638.83KB
数学建模 送货线路设计问题 标准答案 答案仅供参考Word文件下载.docx
《数学建模 送货线路设计问题 标准答案 答案仅供参考Word文件下载.docx》由会员分享,可在线阅读,更多相关《数学建模 送货线路设计问题 标准答案 答案仅供参考Word文件下载.docx(50页珍藏版)》请在冰点文库上搜索。
要从O点到16点则要先到23即0-23-16要从O点到23点则要先到17即0-17-23-16要从o点到17点则要先到21即0-21-17-23-16而O可以直接到21所以从0到16的最优路径是0-21-17-23-16最短的距离是w(0,16)=7493m
模型二
—对于问题一的求解
2.1模型的建立
由前30件货物可以到达的地点可以知道i,j=13、14、16、17、18、21、23、24、26、27、31、32、34、36、38、39、40、42、43、45、49。
图2需要达到的点(红点标注的)
其中共经过21个点,运送30件货物
该30件货物
=47.3kg<
50kg
=0.8371
所以可以一次把货物携带进行运送。
由T与W关系可知要使所用的时间最小即所走的距离最短。
即
目标函数是:
T=W÷
V+
×
30
约束条件是:
必须全部遍历回到0点
即求出从O出发遍历这图的21个点的并回到o的最短的距离
要距离最短则每一步也要最短,即从O开始找最短的点到达后继续找未遍历的最短的点则可求出最短的距离。
本题要求出回到O点则可以看到两个开始最短遍历的点在某点重合即可完成最短的遍历。
2.2模型的求解
由图可以明显得出距离O最近的点是21点和26点。
由于32点到38点的距离小于32点到16点的距离为使从21点出来的线遍历右下的点完后再和26点出来的汇合则安排32点到35点断开。
有程序2(附录2.2)可得:
1
31
12
13
2
32
14
3
34
16
4
36
15
17
5
38
18
6
39
21
7
40
23
8
42
19
24
9
43
20
26
10
45
27
11
49
22
遍历节点路线是:
0-21-17-23-32-16-14-18-13-24-34-40-45-49-42-43-38-36-39-27-31-26-0
最优的路线是:
0-21-17-23-32-23-16-14-21-18-13-19-24-31-34-40-45-42-49-42-43-38-36-27-39-27-31-26-0
总路程是:
W=53787m
最优时间是:
T=3.7411h
模型三
—对于问题二的求解
3.1模型的建立
由第一个模型建立的可以求出到达24时所用的时间是:
可知到24点的时间是:
t(24)=2.0880
由表2.1可知必须在9点之前把货物送到24点即t(24)<
1故模型一不适用于问题二的求解.
由下图3可知:
图3.考虑时间的点的位置
由于右边的点的地点需要的时间要比左边的早,所以先分两个阶段,即先走左边后走右边即先走圈内的元素由程序3(附录2.3)可得:
从O出发经过13、18、24、26、27、31、34、39、40到达45
0.1080
0.2220
0.3165
29
0.4407
0.6835
28
0.8954
1.0751
1.4393
1.5573
1.7413
而到13点时必须在9点之前到达但1.0751>
1,到45点时必须在9点半之前到达而1.7412>
1.5故分成两个阶段不成功,所以分四个阶段,求出各个阶段的最短距离和到达时的时间即可。
目标函数:
=
÷
v+
约束条件是:
T到个点的时间最大值
3.2模型的求解
图4.4个阶段的圈图
对四个阶段分别求出到达的时间,由程序4(附录2.4)可知
●分4个阶段
0.0909
0.2706
0.5587
1.从0出发经过13、18到24。
满足t<
1的条件
故路线为:
0-18-13-24
0.7329
0.9297
1.0477
1.2317
2.从24出发经过31、34、40到45。
满足t<
1.5
24-31-34-40-45
1.4297
1.5618
1.7322
1.8913
3.从45出发经过38、42、43到49。
2.25
所以路线为:
45-42-49-43-38
4.从38出发经过14、16、17、21、23、26、27、32、36、39回到O。
2.0054
2.1472
2.3214
2.5540
2.7454
2.8714
2.9953
3.1500
3.4420
3.6007
38-36-27-39-27-31-26-21-17-23-32-16-14-21-0
所以总的遍历点顺序是:
0-18-13-24-31-34-40-45-42-49-43-38-36-27-39-26-21-17-23-32-16-14-0
总时间是T=3.9130h
总距离是W=57912m
最优路线是:
0-18-13-19-24-31-34-40-45-42-49-42-43-38-36-27-39-27-31-26-21-17-23-32-23-16-14-21-0
到每个点的时间见附录1.4
模型四
—对于问题三的求解
4.1.模型的建立
本题中要遍历所有的50个点但由于
=147kg,
=2.8
而M<
50kg,V<
故应该以M<
50kg和V<
判断的标准到达的最远的点后返回。
W=
约束条件:
M<
4.2模型的求解
由O开始逐渐依次找出最近的点后再找出离该点最近的点直到不满足约束条件。
见程序5(附录2.5)
图5.改进后的遍历图
1第一阶段
2.第二阶段
3.第三阶段
4.第四阶段
4.3模型的优化
由于总的
=148kg
=2.8
所以最少要分四个阶段,但由于每次不可能刚好带满50kg而如果只要3次则最多只能带150kg只比原货物多2kg所以不可能是三次就把货物带完,最少要四次。
故只需要把上述的模型进行数据处理就好了。
过程如下:
1.由于到21点时M=49V=0.8757若走过14则M大于了50故直接从21点返回。
最优路线为:
0-26-31-27-39-27-36-38-35-32-23-17-21-0
走的距离W=27122m,花费的时间T=1.7301
2.若按程序给出的从13到8的路线是13-12-11-12-8而当为13-11-12-8时更短故修改之;
同时到达40后如果选择34则45的周围全被遍历过。
到45后M=46.83,V=1.0247不满足要求,故从40到34后沿21-26返回。
最优路线为:
0-18-13-11-12-8-3-1-6-1-7-10-9-14-16-23-32-35-38-43-42-49-50-40-45-36-21-0
走得距离是:
W=83220,所用的时间是T=4.4675
3.当到达45点时若要去20点放货物的话则需要遍历许多已经遍历过的地点,故从45点沿36-21-0返回
0-26-31-24-19-25-29-22-30-28-33-46-48-44-41-37-40-47-40-45-36-21-0
所走的距离为:
W=128970m,所用的时间是:
T=6.1238
4.只余下了5个点,所以由图可知
路线为:
0-26-31-24-19-25-15-22-20-2-5-2-4-3-8-12-13-18-o
W=171510m所用的时间是T=7.3964
由上面的四个阶段可以知道该问的最优路线是:
0-26-31-27-39-27-36-38-35-32-23-17-21-0-18-13-11-12-8-3-1-6-1-7-10-9-14-16-23-32-35-38-43-42-49-50-40-45-36-21-0-26-31-24-19-25-29-22-30-28-33-46-48-44-41-37-40-47-40-45-36-21-0-26-31-24-19-25-15-22-20-2-5-2-4-3-8-12-13-18-o
W=171510m
所用的时间是T=7.3964
5、模型的分析
1误差分析:
对于模型一是使用了精确地Dijkstra算法,故误差可以忽略不计
对于模型二假定了32到38点的断开存在一定的误差,但相对于断开其余的几点得到的数值要小,故该模型可以使用。
对于模型三,由于分区域的方法有很多,故不可避免的存在些许误差,但由于区域越多,路程越多,故选择分成4个区域最合适;
分成的四个不同的时间的到达区域比较紧密故按照时间的不同划分了四个区域,从而大大的消除了误差,此模型可以使用。
对于模型四的误差比较大,由于未考虑货物的拆分可能会有一定的影响同时由于4个阶段的划分也是有一定的不确定性故误差存在。
对于该模型简化了考虑的条件,仅以M和V为判断标准,虽对准确性存在挑战,但该模型相对与其他的分类有明显的优越性。
故该模型适用于该问的求解。
2灵敏度分析
对于模型一、二、三,灵敏度很好,模型的准确性很高。
对于模型四由于质量和体积的制约,使其灵敏度不会很好,但准确性较高,因此模型可以使用。
6、模型评价、改进和推广
6.1模型的评价
优点:
●充分利用了已知数据建立模型,使其具有很高的准确性和可行性
●使用了准确的算法和适当的假设,使模型的准确性和实用性到达统一
●运用功能强大的Matlab工具使数据处理误差达到最小
缺点
●由于数据较多,没法使用工具进行模型的验证,只能一步一步的精化模型
6.2模型的改进
对于模型一和三主要是进行验证。
对于模型二断开的那个点可以去取别的点进行。
主要是模型四的改进,可以考虑到不同的地点送的货物进行拆分,从而渠道最优的解
6.3模型的推广
可充分使用到图的遍历和最短路的一系列问题的求解中。
7、参考文献
1.AFirstCourseinMathenmaticalModerling(ThirdEdition)
FrankR.GiordianoMauriceD.weirWilliamP.Fox
2.图论任韩。
3.数学建模案例选集姜启源谢金星
4.图论第3版德迪斯特尔 著
5.大学生数学建模竞赛辅导教材叶其效
6.基于matlab动态规划中最短路线的实现程序[J]电脑学习
施益昌郑贤斌李自立
7.物流配送问题的混沌优化算法研究中央民族大学学报(自然科学版)2009年11月第18卷第4期
8.Dijkstra算法在企业物流运输网络中的应用湖南农业大学学报(自然科学版)2005年8月第29卷4期
附录
附录1.、表格
1.1各货物号信息表
货物号
送达地点
重量(公斤)
体积(立方米)
不超过时间
2.50
0.0316
9:
00
0.50
0.0354
1.18
0.0240
30
1.56
0.0350
12:
2.15
0.0305
1.72
0.0100
1.38
0.0109
1.40
0.0426
0.70
0.0481
1.33
0.0219
10:
1.10
0.0287
0.95
0.0228
2.56
0.0595
2.28
0.0301
2.85
0.0190
1.70
0.0782
0.25
0.0412
1.79
0.0184
2.45
0.0445
2.93
0.0420
0.80
0.0108
0.0018
1.57
0.0210
2.80
0.0103
25
1.14
0.0155
0.68
0.0382
1.35
0.0144
0.52
0.0020
2.91
0.0487
1.20
0.0429
1.26
0.0250
1.15
0.0501
33
1.63
0.0483
1.23
0.0006
35
1.41
0.0387
0.54
0.0067
37
0.0129
0.76
0.0346
2.14
0.0087
1.07
0.0124
41
1.37
0.0510
2.39
0.0428
0.99
0.0048
44
1.66
0.0491
0.45
0.0209
46
2.04
0.0098
47
1.95
0.0324
48
2.12
0.0554
3.87
0.0262
50
2.01
51
0.0419
52
0.39
0.0001
53
0.0502
54
1.24
0.0534
55
2.41
0.0012
56
0.0059
57
0.42
0.0224
58
0.0580
59
1.34
0.0372
60
0.06
0.0402
61
0.60
0.0274
62
2.19
0.0503
63
1.89
0.0494
64
1.81
0.0325
65
1.00
0.0055
66
0.0177
67
2.51
0.0361
68
0.0110
69
0.0440
70
0.49
0.0329
71
0.51
0.0094
72
0.0455
73
1.31
0.0121
74
0.0005
75
0.98
0.0413
76
0.0241
77
0.0230
78
0.0542
79
1.01
0.0566
80
1.12
0.0284
81
0.79
0.0011
82
0.0492
83
2.77
0.0034
84
2.29
0.0054
85
0.21
0.0490
86
1.29
0.0088
87
0.0249
88
0.90
0.0038
89
2.38
0.0434
90
1.42
91
0.0300
92
0.0133
93
1.17
94
1.82
0.0308
95
0.33
0.0345
96
0.30
0.0172
97
4.43
0.0536
98
0.24
0.0056
99
0.0175
100
1.98
0.0493
1.250个位置点的坐标
位置点
X坐标(米)
Y坐标(米)
9185
500
1445
560
7270
570
3735
670
2620
995
10080
1435
10025
2280
7160
2525
13845
2680
11935
3050
7850
3545
6585
4185
7630
5200
13405
5325
2125
5975
15365
7045
14165
7385
8825
8075
5855
8165
780
8355
12770
8560
2200
8835
14765
9055
7790
9330
4435
9525
10860
9635
10385
10500
565
9765
2580
9865
1565
9955
9395
10100
14835
10365
1250
10900
7280
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学建模 送货线路设计问题 标准答案 答案仅供参考 数学 建模 送货 线路 设计 问题 答案 仅供参考