结冰路面铺沙问题.docx

结冰路面铺沙问题
问题重述
在一个村庄中， 应对路面结冰的措施是向路面上铺沙防滑。 铺沙工作由养路站负责，养路站位于交汇点 1 处，铺沙所使用的卡车就在此养路站内。 卡车的载沙量足够大，能够不需要中途加沙就完成所有路面的铺沙任务。 由于有些街道是单行线，因此有时候可能需要多次经过一条街道。 请为铺沙车选择一条路线， 使得完成所有街道铺沙所需的路程最短。 对于双向的街道， 需要为每个方向的车道分别进行铺沙。
本文将研究以下问题：
1）卡车由养路站出发，以最短的路程完成所有街道的铺沙工作；
2）卡车尽可能少的多次经过一条街道；
问题分析
本题要求我们通过建立模型和计算， 设计出卡车需行走的最短路程， 由题可知卡车为村庄街道都铺沙， 且卡车在养路站内， 卡车载沙量可一次将村庄的街道全部铺沙。卡车铺沙的基本原则只有一个，成本要低。
据题，题目要求设计出最短路线。 因此在此模型中我们需要根据图中线路确定路线，并计算出总路程， 进行比较，得出最短路程。
基本假设
（1）卡车载重量足够大；
（2）沙子量足够；
（3）车子不打滑；
（4）村子路面平整；
（5）工作期间不用换司机；
（6）卡车在工作期间不会坏；
（7）卡车的载重和油耗量无关。
符号说明
符号
路线
距离 (m)
a
1→ 2
150
b
2→ 3
130
c
3→ 2
140
d
3→ 4
100
e
4→ 3
100
f
1→ 5
165
g
5→ 1
165
h
2→ 5
230
i
2→ 6
160
j
6→ 2
170
k
7→ 3
200
l
4→ 8
190
m
8→ 4
180
n
5→ 6
144
o
6→ 5
144
p
6→ 7
128
q
7→ 6
122
r
7→ 8
109
s
9→ 5
194
t
6→ 9
218
u
6→10
174
v
10→6
174
w
10→7
233
x
7→11
185
y
11→7
185
z
8→11
141
A
8→12
190
B
9→10
148
C
11→ 10
135
D
12→ 11
110
L
周长
模型建立与求解
假设卡车不走重复路线，将每一条路走完并铺完沙，最短路程为 4814m。
如题所示，要想得出最短路线，首先要得出此次
铺沙共有多少种铺沙路线。通过二项式，由①出发，
1
共有两条路线，那么就有
2 种方法；假设继续由②
出发，那么就有
1
1
种
3 种选择方法；由③出发会有
2