题目描述
本题为吉林大学数学学院2020级数学模型期末大作业
长春市的伊通河自南向北穿城而过,是长春人民的“母亲河”。伊通河全长342.5公里,假设长春市政府要在其中风景最为优美的225公里河段建设漂流露营区,建成之后游客们可以选择以乘船的方式畅游伊通河的这一河段。
目前的规划是每一次旅行都是从最开始的下水点出发到最终的结束点,开始点到结束点的河流长度为225公里,且是顺流而下的。游客可选择的交通工具总共有两种,一种是平均4公里每小时的脚踏公园游船,另一种是平均8公里每小时的螺旋桨电动游船。整个漂流旅行的总时长从6到18个夜晚不等,为了确保游客们在旅行过程中的安全,负责管理的政府机构希望每一艘游船在漂流的过程中都尽可能地避免遇到其他的游船。
目前的规划还包括在每年的五月到十一月可以进行全程的漂流旅行,在这六个月期间,共有X次旅行,225公里的伊通河游玩路线上共有50处露营区,露营区均匀地分布在游玩路线的河岸边。由于景区的知名度不断提升,前来游玩的游客数量也逐渐增加,因此管理机构计划增加每年的旅行次数以满足游客们的需求。
为了能够接纳尽可能多的游客,完成尽可能多的旅行次数,政府现在向你们征集一个最优的混合旅行方案,可以改变不同的旅行时间(单位为夜)与不同种类的游船,同时最大限度地利用露营区(两组游客不能同一时间在同一露营区里过夜)。
问题一
请制定一个最佳的乘船旅行计划,以最大限度地增加六个月中的旅行次数,假设在旅行的第25天,管理部门计划让四个游客团体从开始点出发,他们乘坐的游船种类和旅行时间分别为
g
1
g_1
g1 :电动游船,
t
1
=
6
t_1=6
t1=6;
g
2
g_2
g2 :脚踏游船,
t
2
=
18
t_2=18
t2=18;
g
3
g_3
g3:电动游船,
t
3
=
12
t_3=12
t3=12;
g
4
g_4
g4:脚踏游船,
t
4
=
12
t_4=12
t4=12。
请运用建立的模型分别为这四组游客设计旅行计划表。
问题二
管理部门计划未来将漂流河段的长度扩建到226公里,并将露营区数量增加到235个,请计算出在这样的条件下河流的承载能力,即六个月时间内最大的可能旅行次数。
问题三
请分析第二问的结果对于每天下⽔的脚踏游船与电动游船的⽐率和河流上露营地数量变化的敏感性。
背景介绍
长春市的伊通河自南向北穿城而过,是长春人民的“母亲河”。伊通河全长342.5公里,假设长春市政府要在其中风景最为优美的225公里河段建设漂流露营区,建成之后游客团体们可以选择以乘船的方式畅游伊通河的这一河段。
目前的规划是每一次旅行都是从最开始的下水点出发到最终的结束点,开始点到结束点的河流长度为225公里,且是顺流而下的。游客团体可选择的交通工具总共有两种,一种是平均4公里每小时的脚踏公园游船,另一种是平均8公里每小时的螺旋桨电动游船。整个漂流旅行的总时长从6到18个夜晚不等,为了确保游客团体们在旅行过程中的安全,负责管理的政府机构希望每一艘游船在漂流的过程中都尽可能地避免遇到其他的游船。
目前的规划还包括在每年的五月到十一月可以进行全程的漂流旅行,在这六个月期间,共有X次旅行,225公里的伊通河游玩路线上共有50处露营区,露营区均匀地分布在游玩路线的河岸边。由于景区的知名度不断提升,前来游玩的游客团体数量也逐渐增加,因此管理机构计划增加每年的旅行次数以满足游客团体们的需求。
为了能够接纳尽可能多的游客团体,完成尽可能多的旅行次数,政府现在向你们征集一个最优的混合旅行方案,可以改变不同的旅行时间(单位为夜)与不同种类的游船,同时最大限度地利用露营区(两组游客团体不能同一时间在同一露营区里过夜)。
模型假设
首先,假设每个游客团体团每天最多旅行 12 12 12个小时,那么电动游船每天最多旅行 96 k m 96km 96km,脚踏游船最多旅行 48 k m 48km 48km。
其次,假设出发点和终点不算露营点,则每两个露营点以及露营点距离出发点或终点之间相距 225 / 51 225/51 225/51。
又因为游客团体每天要在露营点暂停,所以电动游船每天最多旅行 [ 96 / ( 225 / 51 ) ] × ( 225 / 51 ) ≈ 92.65 k m [96/(225/51)]\times(225/51)\approx92.65km [96/(225/51)]×(225/51)≈92.65km,即每天最多到第 [ 96 / ( 225 / 51 ) ] = 21 [96/(225/51)]=21 [96/(225/51)]=21个露营点;脚踏游船每天最多旅行 [ 48 / ( 225 / 51 ) ] × ( 225 / 51 ) ≈ 44.12 k m [48/(225/51)]\times (225/51)\approx44.12km [48/(225/51)]×(225/51)≈44.12km,即每天最多到第 [ 48 / ( 225 / 51 ) ] = 10 [48/(225/51)]=10 [48/(225/51)]=10个露营点。 [ ⋅ ] [\cdot] [⋅]表示高斯函数,向下取整。
假设每天游客团体都必须去至少下一个露营点,即保证游客团体除了最后一天需要保证到达终点外,距离终点的剩余露营区数必须大于等于剩余天数。
问题一的模型
为了确保每一艘游船在漂流的过程中都尽可能地避免遇到其他的游船,我们需要确定游客团体漂流的优先级,保证优先级低的游客团体不能超过优先级高的游客团体,同时确保了不同优先级的游客团体每天不在同一露营区停留。
为了确保优先级低的游客团体不能超过优先级高的游客团体,我们需要根据游客团体走完全程平均每天需要经过的露营区数,当平均每天需要经过的露营区数相同时,我们就考虑游客团体的速度:
游客团体 | 平均每天需要经过的露营区数(个) | 速度 ( k m / h ) (km/h) (km/h) |
---|---|---|
g 1 g_1 g1 | 50 / 6 ≈ 8.33 50/6\approx 8.33 50/6≈8.33 | 8 8 8 |
g 2 g_2 g2 | 50 / 18 ≈ 2.78 50/18\approx 2.78 50/18≈2.78 | 4 4 4 |
g 3 g_3 g3 | 50 / 12 ≈ 4.17 50/12\approx 4.17 50/12≈4.17 | 8 8 8 |
g 4 g_4 g4 | 50 / 12 ≈ 4.17 50/12\approx 4.17 50/12≈4.17 | 4 4 4 |
由上表我们可以得到游客团体优先级: g 1 > g 3 > g 4 > g 2 g_1>g_3>g_4>g_2 g1>g3>g4>g2
显然,优先级最高的游客团体会最早完成旅程,假如优先级最高的游客团体要开始下一次旅程,那么为了保证其不会遇到其他游船,则该游客团体不能超过其他团体,那么该游客团体的优先级就应当被设为最低。
决策树模型
为了找到最佳方案,显然最简单粗暴的方法就是列举所有情况进行比较,而由于我们把游客团体每天的旅行路程转化成经过的露营区数,将连续的变量转化成了离散的变量,因此我们可以使用决策树来列举所有的情形。
我们从优先级高到优先级低的游客团体的第一天行程开始列举,优先级最高的游客第一天可以选择到达的露营区有 21 21 21种,下一优先级的游客团体每天到达的可选露营区是前一优先级当天到达露营区和自己所在露营区之间的露营区。
当优先级最高的游客完成旅程后,假如其还有旅行次数,则重置其剩余的旅行天数,将其位置移动到出发点,并且剩余旅行次数减一。以下代码展示了假如每个游客团体都只有一次旅程的决策树,并且当完成第一种方案时会抛出异常以强制退出程序:
def travel(k, T, P, priority, times, max):
global count
global G, T0
if sum(P) == 204 and sum(times) == 0:
count += 1
if count == 1:
print(count)
raise Exception("done")
if sum(T) >= 1:
if T[priority[k]] >= 1:
for i in range(1, max):
p = P[priority[k]] + i # 用于记录下一天可能到的位置
T1 = T.copy()
P1 = P.copy()
times1 = times.copy()
priority1 = priority.copy()
if 51 - p >= T1[priority1[k]] - 1: # 如果剩余天数每天都至少有下一个营地能够到达
if p + (T1[priority1[k]] - 1) * G[priority1[k]] >= 51: # 确保旅行结束能到终点
if T1[priority1[k]] > 1:
P1[priority1[k]] = p
else:
P1[priority1[k]] = 51 # 最后一天必须到终点
T1[priority1[k]] -= 1
print(priority1[k], i, T1, P1, priority1, times1)
if T1[priority1[(k + 1) % 4]] == 0 and times1[priority1[(k + 1) % 4]] > 0:
times1[priority1[(k + 1) % 4]] -= 1
T1[priority1[(k + 1) % 4]] = T0[priority1[(k + 1) % 4]]
P1[priority1[(k + 1) % 4]] = 0
# 调整优先级,降为最低
priority1 = priority1[:(k + 1) % 4] + priority1[(k + 1) % 4 + 1:] + [priority1[(k + 1) % 4]]
k -= 1 # 回退
print(k)
if k != 3:
if P1[priority1[k]] < 51:
travel((k + 1) % 4, T1, P1, priority1, times1,
min([G[priority1[(k + 1) % 4]] + 1,
abs(P1[priority1[k]] - P1[priority1[k + 1]])])) # 不能超过优先级高的
else:
travel((k + 1) % 4, T1, P1, priority1, times1,
min([G[priority1[(k + 1) % 4]] + 1,
abs(51 - P1[priority1[k + 1]] + 1)]))
else:
travel((k + 1) % 4, T1, P1, priority1, times1, G[priority1[0]] + 1)
'''
else:
print("方案失败," + str(priority1[k]) + "无法到达终点,p=" + str(p))
print(priority1[k], i, T1, P1, priority1, times1)
print()
else:
print("方案失败" + str(priority1[k]) + ",51-p < T[k]-1,p=" + str(p))
print(priority1[k], i, T1, P1, priority1, times1)
print()
continue
'''
else:
if T[priority[(k + 1) % 4]] == 0 and times[priority[(k + 1) % 4]] > 0:
times[priority[(k + 1) % 4]] -= 1
T[priority[(k + 1) % 4]] = T0[priority[(k + 1) % 4]]
P[priority[(k + 1) % 4]] = 0
# 调整优先级,降为最低
priority = priority[:(k + 1) % 4] + priority[(k + 1) % 4 + 1:] + [priority[(k + 1) % 4]]
k -= 1 # 回退
if k != 3:
if P[priority[k]] < 51:
travel((k + 1) % 4, T, P, priority, times,
min([G[priority[(k + 1) % 4]] + 1,
abs(P[priority[k]] - P[priority[k + 1]])])) # 不能超过优先级高的
else:
travel((k + 1) % 4, T, P, priority, times,
min([G[priority[(k + 1) % 4]] + 1,
abs(51 - P[priority[k + 1]] + 1)]))
else:
travel((k + 1) % 4, T, P, priority, times, G[priority[0]] + 1)
if __name__ == "__main__":
T0 = [6, 18, 12, 12] # 旅行天数
T = [6, 18, 12, 12] # 记录旅行天数
times0 = [0, 0, 0, 0] # 旅行次数
times = [0, 0, 0, 0] # 记录旅行次数
G = [21, 10, 21, 10] # 每天经过的最多营地数/最大速度
P = [0] * 4 # 用于记录每组到达的位置
priority = [0, 2, 3, 1] # 出发优先级
k = 0 # 用于记录游客团体优先级的下标
count = 0
travel(k, T, P, priority, times, G[priority[0]] + 1)
上面这段代码首先定义了一个名为travel
的函数,它接受一些参数,包括游客团体的优先级、旅行天数、到达位置、旅行次数等。代码中使用了全局变量count
、G
和T0
,用于记录计数、每天经过的最多营地数和旅行天数。
在函数内部,通过判断累计到达位置的总和是否为204并且旅行天数的总和是否为0,来确定是否已经找到一个可行的方案。如果是,将计数器count
加1,并且输出计数器的值。然后抛出一个异常,以中断代码的执行。
如果旅行天数的总和大于等于1,进入下一个判断条件。这个条件判断当前优先级对应的旅行天数是否大于等于1。如果是,使用循环遍历每一天可能到达的位置,并进行一系列操作。
首先,根据下一天可能到达的位置,创建副本变量T1
、P1
、times1
和priority1
,用于记录可能的变化。然后判断剩余天数每天都至少有下一个营地能够到达,并确保旅行结束时能够到达终点。如果满足条件,进行一系列的操作,包括更新到达位置、旅行天数、优先级等信息,并打印相关信息。
接下来,检查下一个优先级对应的旅行天数是否为0,并且旅行次数大于0。如果满足条件,进行一系列的操作,包括更新旅行天数、到达位置、优先级等信息,并回退到上一个优先级。如果不满足条件,则继续进行下一步操作。
在判断条件的最后,根据不同的情况选择不同的递归调用方式,继续进行下一个游客团体的优先级的计算。根据当前优先级和下一个优先级的位置差异,确定最小的旅行步长。
最后,在main
函数中初始化一些参数,并调用travel
函数来进行求解。
总体来说,这段代码使用递归和条件判断来遍历不同的方案,通过调整旅行天数、到达位置和优先级等参数,寻找满足条件的最优解。
由此,我们得到各游客团体前6天的一种满足条件的可能的旅行计划(其中第51个露营区表示终点):
天数 | g 1 g_1 g1到达的露营区数 | g 2 g_2 g2到达的露营区数 | g 3 g_3 g3到达的露营区数 | g 4 g_4 g4到达的露营区数 |
---|---|---|---|---|
1 | 4 | 1 | 3 | 2 |
2 | 5 | 2 | 4 | 3 |
3 | 6 | 3 | 5 | 4 |
4 | 9 | 4 | 6 | 5 |
5 | 30 | 5 | 7 | 6 |
6 | 51 | 6 | 8 | 7 |
决策树模型如果给予足够多的时间,就能列出所有的可能性并基于这些结果能够选出合适的方案,然而,该模型有两个明显的缺陷:
- 由于我们每天都要从高到低遍历所有优先级的游客团体,每天决策树的深度都会增加4,那么,即便我们只考虑前6天的所有情形,其数量级也在大约 1 0 24 10^{24} 1024,这是无法接受的。
- 假如在第一次旅行中拥有最高优先级的游客团体 g 1 g_1 g1能够立即进行第二次旅程,容易发现当 g 1 g_1 g1完成旅程后, g 2 g_2 g2还有 12 12 12天的旅程,而 g 1 g_1 g1完成一次旅程只需 6 6 6天,因此 g 1 g_1 g1和 g 2 g_2 g2必然会相遇,而决策树限制了两者的相遇,就会一直遍历直到找到能够避免两者相遇的解,而事实上这样的解是不存在的。这也引出了另一个问题:游客安全最大化与旅行次数最大化之间存在矛盾。
游客安全最大化与旅行次数最大化模型
为了使游客安全最大化,则优先级低的游客团体必须不能超越优先级高的游客团体;而为了使旅行次数最大化,就需要让优先级最高的游客完成旅程的第二天开始新的旅程。然而,由上述分析可得,如果游客团体 g 1 g_1 g1能够立即进行第二次旅程,那么 g 1 g_1 g1和 g 2 g_2 g2必然会相遇,游客安全最大化与旅行次数最大化之间存在矛盾。
我们以四组旅行天数的最大公约数36天为一个周期进行考虑,假如不考虑游客安全,那么显然最多能够进行14次旅行。我们以每6天为单位进行考虑,则 g 1 g_1 g1与其他小组的最小相遇次数及其说明如下:
单位(每6天) | 最小相遇次数 | 说明 |
---|---|---|
1 | 0 | 保证优先级,就不会相遇 |
2 | 1 | g 1 g_1 g1和 g 2 g_2 g2必然会相遇;若 g 1 g_1 g1在前几天速度较快,后几天速度较慢,而 g 3 , g 4 g_3,g_4 g3,g4在保证优先级顺序的情况下可以以最快速度先于 g 1 g_1 g1到达终点 |
3 | 2 | g 1 g_1 g1和 g 3 , g 4 g_3,g_4 g3,g4必然会相遇;若 g 1 g_1 g1在前几天速度较快,后几天速度较慢,而 g 2 g_2 g2可以以最快速度先于 g 1 g_1 g1到达终点 |
4 | 1 | g 1 g_1 g1和 g 2 g_2 g2必然会相遇;若 g 1 g_1 g1在前几天速度较快,后几天速度较慢,而 g 3 , g 4 g_3,g_4 g3,g4在保证优先级顺序的情况下可以以最快速度先于 g 1 g_1 g1到达终点 |
5 | 3 | g 1 g_1 g1和其他组必然会相遇,因为当 g 1 g_1 g1出发时,其他组都还有12天旅程 |
6 | 0 | 若 g 1 g_1 g1在前几天速度较快,后几天速度较慢,而其他组在保证优先级顺序的情况下可以以最快速度先于 g 1 g_1 g1到达终点 |
由上表可得,一个周期内 g 1 g_1 g1与其他小组之间至少会相遇7次;而如果进行合理安排, g 2 g_2 g2和 g 3 , g 4 g_3,g_4 g3,g4就不会相遇。因此,无论怎么安排,各小组之间至少会相遇7次。
而假如我们要使游客安全最大化,首先考虑 g 1 g_1 g1,则必须在其他组都剩余少于6天旅程时才能再次出发;其次考虑 g 3 g_3 g3和 g 4 g_4 g4,则必须在 g 2 g_2 g2还剩少于12天旅程时才能再次出发。在保证优先级的情况下,为了使各组之间不会相遇,我们以每6天为单位进行考虑,则各小组的出发情况如下:
单位(每6天) | 6天开始时出发小组 | 6天结束时各小组情况 |
---|---|---|
1 | g 1 , g 2 , g 3 , g 4 g_1,g_2,g_3,g_4 g1,g2,g3,g4 | g 1 g_1 g1到达终点, g 2 g_2 g2还剩12天, g 3 , g 4 g_3,g_4 g3,g4还剩6天 |
2 | 无 | g 1 g_1 g1无法行动, g 2 g_2 g2还剩6天, g 3 , g 4 g_3,g_4 g3,g4到达终点 |
3 | g 3 , g 4 g_3,g_4 g3,g4 | g 1 g_1 g1无法行动, g 2 g_2 g2到达终点, g 3 , g 4 g_3,g_4 g3,g4还剩6天 |
4 | g 2 g_2 g2 | g 1 g_1 g1无法行动, g 2 g_2 g2还剩12天, g 3 , g 4 g_3,g_4 g3,g4到达终点 |
5 | g 3 , g 4 g_3,g_4 g3,g4 | g 1 g_1 g1无法行动, g 2 g_2 g2还剩6天, g 3 , g 4 g_3,g_4 g3,g4还剩6天 |
6 | g 1 g_1 g1 | 全部到达终点 |
因此,在保证各组之间不相遇的情况下,一个周期总共可以进行10次旅行。
统筹考虑游客安全与旅行次数的模型
由上述分析可得,保证游客安全最大化时,每个周期最多旅行10次;而保证旅行次数最大化时,每个周期最多旅行14次。两种模型每个周期的旅行次数只相差3次,其区别在于第2到第5个六天 g 1 g_1 g1无法出发。 g 1 g_1 g1第2个六天出发至少与其他组相遇1次, g 1 g_1 g1第3个六天出发至少与其他组相遇2次, g 1 g_1 g1第4个六天出发至少与其他组相遇1次,而 g 1 g_1 g1第5个六天出发至少与其他组相遇3次,因此,我们统筹考虑游客安全和旅行次数,令 g 1 g_1 g1在第2和4个六天出发但不在第3和第5个六天出发,则每个周期能够进行12次旅行,且至少只相遇2次。
由此我们制定一个周期内一种可能的旅行计划如下(其中第51个露营区表示终点,第0个露营区表示出发点):
天数 | g 1 g_1 g1到达的露营区数 | g 2 g_2 g2到达的露营区数 | g 3 g_3 g3到达的露营区数 | g 4 g_4 g4到达的露营区数 |
---|---|---|---|---|
1 | 4 | 1 | 3 | 2 |
2 | 5 | 2 | 4 | 3 |
3 | 6 | 3 | 5 | 4 |
4 | 9 | 4 | 6 | 5 |
5 | 30 | 5 | 7 | 6 |
6 | 51 | 6 | 8 | 7 |
7 | 1 | 7 | 9 | 8 |
8 | 10 | 8 | 12 | 11 |
9 | 20 | 9 | 22 | 21 |
10 | 30 | 10 | 32 | 31 |
11 | 40 | 11 | 42 | 41 |
12 | 51 | 12 | 51 | 51 |
13 | 0 | 13 | 2 | 1 |
14 | 0 | 14 | 3 | 2 |
15 | 0 | 21 | 4 | 3 |
16 | 0 | 31 | 5 | 4 |
17 | 0 | 41 | 6 | 5 |
18 | 0 | 51 | 10 | 9 |
19 | 2 | 1 | 11 | 10 |
20 | 11 | 2 | 12 | 11 |
21 | 21 | 3 | 22 | 21 |
22 | 30 | 4 | 32 | 31 |
23 | 40 | 5 | 42 | 41 |
24 | 51 | 6 | 51 | 51 |
25 | 0 | 7 | 2 | 1 |
26 | 0 | 8 | 3 | 2 |
27 | 0 | 9 | 4 | 3 |
28 | 0 | 10 | 5 | 4 |
29 | 0 | 11 | 6 | 5 |
30 | 0 | 12 | 7 | 6 |
31 | 1 | 13 | 8 | 7 |
32 | 2 | 14 | 12 | 11 |
33 | 3 | 23 | 22 | 21 |
34 | 9 | 33 | 32 | 31 |
35 | 30 | 43 | 42 | 41 |
36 | 51 | 51 | 51 | 51 |
按照上述计划, g 1 g_1 g1与 g 2 g_2 g2在第7到8天和第18到19天必然会相遇。
模型对比
第一问在旅行的第25天开始旅行到11月结束,总共 6 + 31 + 31 + 30 + 31 + 30 = 159 6+31+31+30+31+30=159 6+31+31+30+31+30=159天,因此,能够完成 [ 159 / 36 ] = 4 [159/36]=4 [159/36]=4个周期,而第5个周期还剩15天,在第5个周期可以令 g 1 g_1 g1完成两次旅行, g 3 , g 4 g_3,g_4 g3,g4各完成一次旅行且三组不会相遇。
则各模型可以完成的旅行次数与最小相遇次数如下:
模型 | 旅行次数 | 最小相遇次数 |
---|---|---|
旅行次数最大化模型 | 14 × 4 + 3 = 59 14\times 4+3=59 14×4+3=59 | 7 × 4 = 28 7\times 4=28 7×4=28 |
游客安全最大化模型 | 10 × 4 + 3 = 43 10\times 4+3=43 10×4+3=43 | 0 0 0 |
统筹游客安全与旅行次数模型 | 12 × 4 + 3 = 51 12\times 4+3=51 12×4+3=51 | 2 × 4 = 8 2\times 4=8 2×4=8 |
第二问的模型
管理部门计划未来将漂流河段的长度扩建到226公里,并将露营区数量增加到235个,所以电动游船每天最多到第 [ 96 / ( 226 / 235 ) ] = 99 [96/(226/235)]=99 [96/(226/235)]=99个露营点;脚踏游船每天最多到第 [ 48 / ( 226 / 235 ) ] = 49 [48/(226/235)]=49 [48/(226/235)]=49个露营点。
为了使六个月时间内最大的可能旅行次数最多,那么就需要使得河流最快达到满载状态,所谓的满载状态,就是一天内所有露营区都有游客团体停留;并且达到满载状态后,一直保持到最后一批游客出发为止。
为了使河流最快达到满载状态,并且旅行过程中尽可能不相遇,则游客团体每天旅行的速度要尽可能快且旅行时间尽可能短,于是我们令所有游客团体都乘坐电动游船,并且旅行时间都设为6天,并且使第一个出发的游客团体行程安排如下(其中第236个露营区表示终点):
天数 | 到达露营区数 |
---|---|
1 | 99 |
2 | 198 |
3 | 233 |
4 | 234 |
5 | 235 |
6 | 236 |
为了使河流最快达到满载状态,每天都必须有游客团体出发,那么前六天的河流载荷情况如下:
天数 | 河流载荷情况 |
---|---|
1 | 99/235 |
2 | 198/235 |
3 | 233/235 |
4 | 234/235 |
5 | 235/235 |
6 | 235/235 |
上表中,第一天第一批99个游客团体出发;
第二天,第一批游客团体占有第100到198个露营区,第二批99个游客团体出发到达第1到99个露营区;
第三天,为了使最早出发的游客团体剩余的天数都有露营区停留,则第一批游客团体占有第135到233个露营区,第二批游客团体占有第36到133个露营区,第三批35个游客团体出发到达第1到35个露营区;
第四天,第一批游客团体占有第136到234个露营区,第二批游客团体占有第37到135个露营区,第三批游客团体占有第2到36个露营区,第四批1个游客团体出发到达第1个露营区;
第五天,第一批游客团体占有第137到235个露营区,第二批游客团体占有第38到136个露营区,第三批游客团体占有第3到37个露营区,第四批游客团体占有第2个露营区,第五批1个游客团体出发到达第1个露营区,此时河流达到满载;
第六天,第一批游客全部到达终点,第二批游客团体占有第137到235个露营区,第三批游客团体占有第102到136个露营区,第四批游客团体占有第101个露营区,第五批占有第100个露营区,第六批99个游客团体出发到达第1到99个露营区,河流保持满载;
此后每天,河流保持满载状态,以每5天为一个周期,河流上共有5批游客团体,其数量分别为99,99,35,1,1。
六个月总天数为 30 × 3 + 31 × 3 = 183 30\times 3+31\times 3=183 30×3+31×3=183,考虑第180天,则情况与第五天相同,但此时旅行天数仅剩3天,则前三批游客团体能够在最后一天之前到达终点,那我们假设后两批没有出发,则最大的可能旅行次数为 [ 183 / 5 ] × ( 99 + 99 + 35 + 1 + 1 ) − 2 = 8458 [183/5]\times(99+99+35+1+1)-2=8458 [183/5]×(99+99+35+1+1)−2=8458。
每天下水的脚踏游船与电动游船的比率的敏感性分析
全是电动游船的情形
如第二问所述,当全是电动游船时,可以达到的最大可能旅行次数为8458次。
全是脚踏游船的情形
类似于第二问的分析,为了使河流最快达到满载状态,并且旅行过程中尽可能不相遇,则游客团体每天旅行的速度要尽可能快且旅行时间尽可能短,于是我们将旅行时间都设为6天,并且使第一个出发的游客团体行程安排如下(其中第236个露营区表示终点):
天数 | 到达露营区数 |
---|---|
1 | 49 |
2 | 98 |
3 | 147 |
4 | 196 |
5 | 235 |
6 | 236 |
为了使河流最快达到满载状态,每天都必须有游客团体出发,那么前六天的河流载荷情况如下:
天数 | 河流载荷情况 |
---|---|
1 | 49/235 |
2 | 98/235 |
3 | 147/235 |
4 | 196/235 |
5 | 235/235 |
6 | 235/235 |
上表中,第一天第一批49个游客团体出发;
第二天,第一批游客团体占有第50到98个露营区,第二批49个游客团体出发到达第1到49个露营区;
第三天,第一批游客团体占有第99到147个露营区,第二批游客团体占有第50到98个露营区,第三批49个游客团体出发到达第1到49个露营区;
第四天,第一批游客团体占有第148到196个露营区,第二批游客团体占有第99到147个露营区,第三批游客团体占有第50到98个露营区,第四批49个游客团体出发到达第1到49个露营区;
第五天,为了使最早出发的游客团体剩余的天数都有露营区停留,则第一批游客团体占有第187到235个露营区,第二批游客团体占有第138到186个露营区,第三批游客团体占有第89到137个露营区,第四批游客团体占有第40到88个露营区,第五批39个游客团体出发到达第1到39个露营区,此时河流达到满载;
第六天,第一批游客全部到达终点,第二批游客团体占有第187到235个露营区,第三批游客团体占有第138到186个露营区,第四批游客团体占有第89到137个露营区,第五批占有第50到88个露营区,第六批49个游客团体出发到达第1到49个露营区,河流保持满载;
此后每天,河流保持满载状态,以每5天为一个周期,河流上共有5批游客团体,其数量分别为49,49,49,49,39。
六个月总天数为 30 × 3 + 31 × 3 = 183 30\times 3+31\times 3=183 30×3+31×3=183,考虑第180天,则情况与第五天相同,但此时旅行天数仅剩3天,则前三批游客团体能够在最后一天之前到达终点,那我们假设后两批没有出发,则最大的可能旅行次数为 [ 183 / 5 ] × ( 49 + 49 + 49 + 49 + 39 ) − 49 − 39 = 8372 [183/5]\times(49+49+49+49+39)-49-39=8372 [183/5]×(49+49+49+49+39)−49−39=8372。
与全部采用电动游船的区别在于最后两天,这是由于前五天到达河流满载需要的时间不同。
每天下水的脚踏游船与电动游船成比率的情形
假设脚踏游船与电动游船的比率为
k
k
k,若第一天下水
n
n
n个电动游船,则第一天下水
k
n
kn
kn个脚踏游船,为了使游客团体不相遇且每天不使用相同露营区,并且使旅行次数最大,也就需要使河流最快达到满载,需要满足以下关系:
{
k
n
≤
49
k
n
+
n
≤
99
\begin{cases} kn\le 49\\ kn+n\le 99 \end{cases}
{kn≤49kn+n≤99
显然,
n
,
n
k
∈
N
∗
n,nk\in\N^*
n,nk∈N∗,当
k
k
k最大时,
n
=
1
,
k
=
49
n=1,k=49
n=1,k=49;当
n
n
n最大时,
n
=
49
,
k
=
1
n=49,k=1
n=49,k=1。
为了使河流最快到达满载,我们设定每个游客团体尽可能按最大速度旅行且旅行时间尽可能短,则第一批出发的游客团体占用露营区安排如下(其中第236个露营区表示终点):
天数 | 脚踏游船 | 电动游船 |
---|---|---|
1 | 49 ∼ 50 − k n 49\sim 50-kn 49∼50−kn | 99 ∼ 100 − n 99\sim 100-n 99∼100−n |
2 | 98 ∼ 99 − k n 98\sim 99-kn 98∼99−kn | 198 ∼ 199 − n 198\sim 199-n 198∼199−n |
3 | 147 ∼ 148 − k n 147\sim 148-kn 147∼148−kn | 233 ∼ 234 − n 233\sim 234-n 233∼234−n |
4 | 196 ∼ 197 − k n 196\sim 197-kn 196∼197−kn | 234 ∼ 235 − n 234\sim 235-n 234∼235−n |
5 | 234 − n ∼ 235 − ( k + 1 ) n 234-n\sim 235-(k+1)n 234−n∼235−(k+1)n | 235 ∼ 236 − n 235\sim 236-n 235∼236−n |
6 | 236 或 236 ∼ 284 − ( k + 1 ) n 或 284 − n ∼ 284 − ( k + 1 ) n 236或236\sim 284-(k+1)n或284-n\sim 284-(k+1)n 236或236∼284−(k+1)n或284−n∼284−(k+1)n | 236 236 236 |
与全部都是脚踏游船的情形不同,当 ( k + 1 ) n > 48 (k+1)n>48 (k+1)n>48时,则 236 − [ 235 − ( k + 1 ) n ] > 49 236-[235-(k+1)n]>49 236−[235−(k+1)n]>49超出了最后一个游客团体的最大速度,因此第六天最后一个游客团体可能只能到第 284 − ( k + 1 ) n 284-(k+1)n 284−(k+1)n个露营区;当 236 − ( 235 − n ) > 49 236-(235-n)>49 236−(235−n)>49,即 n > 48 n>48 n>48时,第一个乘脚踏游船的游客团体也不能到达终点,只能到达第 284 − n 284-n 284−n个露营区,此时只能有 k = 1 , n = 49 k=1,n=49 k=1,n=49。
若前一天,河流上所有游客团体在当天能到达的最小露营区数为 p p p,则当天最多可以下水 ( k + 1 ) [ p − 1 k + 1 ] (k+1)\left[\dfrac{p-1}{k+1}\right] (k+1)[k+1p−1]艘游船。
显然,当每天下水的脚踏游船与电动游船成比率时,河流可能无法到达满载状态,原因是在前几天,脚踏游船无法追上电动游船。
由于我们进行敏感性分析,只考虑 k k k对最大可能旅行次数的影响,我们要使 n n n最大化,取 n = min { [ 49 k ] , [ 99 k + 1 ] } n=\min\left\{\left[\dfrac{49}{k}\right],\left[\dfrac{99}{k+1}\right]\right\} n=min{[k49],[k+199]}。
显然,对于上述情况,必然有 ( k + 1 ) n > 49 (k+1)n>49 (k+1)n>49,那么在第六天,最后一个乘脚踏游船的乘客团体必然不能到达终点。
首先考虑第二批出发的游客团体,则其数量为 ( k + 1 ) [ 50 − k n − 1 k + 1 ] (k+1)\left[\dfrac{50-kn-1}{k+1}\right] (k+1)[k+150−kn−1],对于其中的电动游船,由于不能超过第一组的脚踏游船,所以其每天只能到第49个露营区,则第二天第二批乘电动游船的游客团体最快以49个露营区的速度也只能到第 49 − k n 49-kn 49−kn个露营区,最慢应当到达第1个露营区;而乘脚踏游船的游客团体最快速度也是49个露营区,因此第三天,第二批游客团体最快只能到第 98 − k n 98 -kn 98−kn个露营区,最慢应当到达第50个露营区,则第三天出发的第三批游客团体数量也为 ( k + 1 ) [ 50 − k n − 1 k + 1 ] (k+1)\left[\dfrac{50-kn-1}{k+1}\right] (k+1)[k+150−kn−1]。
由此可得,每天出发的游客团体数量为 s = ( k + 1 ) [ 50 − k n − 1 k + 1 ] s=(k+1)\left[\dfrac{50-kn-1}{k+1}\right] s=(k+1)[k+150−kn−1],然而,取某些 k k k时,我们发现 s = 0 s=0 s=0,于是第二批游客的出发时间后延 t t t天,直到 s ′ = ( k + 1 ) [ 50 + 49 t − k n − 1 k + 1 ] s'=(k+1)\left[\dfrac{50+49t-kn-1}{k+1}\right] s′=(k+1)[k+150+49t−kn−1]大于0。
因此,最大的可能旅行次数为
(
k
+
1
)
n
+
[
183
−
6
t
]
s
′
(k+1)n+ \left[\dfrac{183-6}{t}\right]s'
(k+1)n+[t183−6]s′,由此可以得到最大的可能旅行次数随
k
k
k的变化为:
当 k = 32 k=32 k=32时,取到最大值5809;当 k = 49 k=49 k=49时,取最小值2951。
绘图代码如下:文章来源:https://www.toymoban.com/news/detail-499358.html
import matplotlib.pyplot as plt
plt.rcParams["font.sans-serif"] = ["SimHei"] # 设置字体
plt.rcParams["axes.unicode_minus"] = False # 该语句解决图像中的“-”负号的乱码问题
# 折线图
s = []
for k in range(1, 50):
n = min([int(49 / k), int(99 / (k + 1))])
t = 0
while int((50 + 49 * t - k * n - 1) / (k + 1)) == 0:
t += 1
s.append(n + int((183 - 6) / (t + 1)) * (k + 1) * int((50 + 49 * t - k * n - 1) / (k + 1)))
print(s)
# 绘制折线图
plt.plot(range(1, 50), s, marker='o', linestyle='-', color='r')
'''
# 标出每个点的坐标
for i in range(len(range(1, 50))):
plt.text(range(1, 50)[i], s[i], f'({range(1, 50)[i]}, {s[i]})', ha='center', va='bottom')
'''
plt.xlabel("最大的可能旅行次数") # 横坐标名字
plt.ylabel("s") # 纵坐标名字
plt.title("最大的可能旅行次数随k的变化")
plt.show()
对河流上露营区数量变化的敏感性分析
显然,当河流上露营区数量变化时,则游客每天经过的最大露营区也会变化,但是,游客每天可以经过的最大路程是不变的,区别只在于进行取整计算时有可能会相差1,因此,露营区数量对最大的可能旅行次数的影响可以忽略。文章来源地址https://www.toymoban.com/news/detail-499358.html
到了这里,关于优化伊通河漂流旅行方案的模型——JLU数学学院2020级数学模型期末大作业的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!