救援人员紧急调运模型

救援人员紧急调运模型 摘要摘要 通过对题目的研究与分析可以知道 在本题中实际要实现的问题就是在 最短的时间内将全部的救援人员从出发地运送至目的地 为了实现这一目标 本 文首先建立了两个比较典型的模型 模型一与模型二 在模型一中车辆运送一部 分救援人员送至出发地与目的地之间的某一处 然后再返回接其余救援人员并将 其运送至出发地与目的地的某一处 直到所有的车辆与所有的救援人员同时到达 目的地 在模型二中 是车辆先运送一部分救援人员到达目的地后 再返回接其 余的救援人员 就这样一直重复直至所有的救援人员全部运送结束 通过对以上 两模型的实际的计算的结果的对比与理论研究证明可知 模型一而完成任务所用 的时间 T1要比模型二完成任务所用的时间 T2小即 T11 五 模型的建立 根据题目中的已知条件 可以合理地建立如下两个模型 同过对比 可以找 出解决问题的最优解决方案 5 1 模型一 在模型一中 车辆与人同时出发 由于车的数量小于救援人员分组后的队数 即 m 小于或等于 p 可以建立这样的一个模型 车辆在将第一组救援人员送至出发 地与目的地的某一位置然后再返回接第二组的救援人员 然后再将第二组救援人 员送至某位置 直至将所有的救援人员与车辆同时到达目的地 则可以进行如下 的假设与计算 不妨设出发地目的地两地的距离为 1 个单位长度 人行军的速度为 1 个速度 单位 车速为 k 个速度单位 且 n pb n mbj 其中 p 是自然数 j 是大于 1 的 整数 因为最优方案中 人与车是同时到达的 所以每个人行军的路程与乘车的 路程必须都是一样的 每辆车前进的路程与后退的路程也是一样的 设人行军的 路程为 y 每辆车前进的路程为 x 后退的路程为 x 1 则有运输过程中的所需 要的时间为 1 1 21 y x kk y 因为 n mbj 车前进时有 mb 个人乘车 车后退时无人乘车 车前进所用的最 短时间为 后退所用的最短时间为 所以最有方案中 平均的乘车人数为 x k 1x K 2 121 21 0 xxxxmb kkkx mb 式 2 给出了车辆的最大利用率 当车辆的利用率达到这个值时 可以得 到团体平均速度的最大值 为v 3 1 212121 1 1 kx xmbxmb xxxj vknn 再根据式 1 得到最优方案的平均速度为 2111 kk xky 代入式 3 得 4 1 12 21 12 kj kj j kj x y 运输任务完成后所用的总时间 21 211 2 1 2 1 1 j jkj kj y ty kk 5 2 模型二 同样 在模型二中 车辆与人同时出发 由于车的数量小于救援人员分组后 的队数 即 m 小于或等于 p 可以先将第一组救援人员送至目的地 然后返回接第 二组救援人员 把他们送至目的地 然后再返回接第三组救援人员 直至把最后 一组救援人员送至目的地 则可以进行如下的假设与计算 不妨设与模型一相同即出发地目的地两地的距离为 1 个单位长度 人行军的 速度为 1 个速度单位 车速为 k 个速度单位 且 n pb n mbj 其中 p 是自然数 j 是大于 1 的整数 则此时可得如下结论 当 j 2 时 将第一组救援人员送至目的地所花费的时间为 此时的第二组救援人员 1 1 t k 与车辆相距的路程为 此时车辆返回接第二组救援人员 相遇时所花费 1 1 1s k 的时间为 21 111 1 11 ts kkk 当车辆将第二组救援人员送至目的地是所花费的时间为 32 111 1 11 tts kkk 此时任务结束后所花费的总时间为 1123 31 1 k Tttt k k 当 j 3 时 由上面的情况可以知道 车辆在运送前两组救援人员是所花费的时间为 1 T 当车来那个返回接第三组救援人员时 人车相距的路程为 由分析可知 21 1 1sT 车辆在接送最后一组救援人员时 所花费的时间为返回接组后一组救援人员的两 倍 则可以求得 121 22 1 1 11 tsT kk 即此情况所用的总时间为 2111 21 11 k TTtT kk 当 j 4 时 由上面的情况可以知道 车辆在运送前两组救援人员是所花费的时间为 2 T 当车来那个返回接第四组救援人员时 此时 2 3 1 1sT 23 2 22 1 1 11 tsT kk 在此种情况下可以求得所花费的总时间为 3 222 1 21 11 2121 1111 k TTtT kk kk T kkkk 同理可以类推出在 j 5 6 7 时的表达式 以下通过对以上 j 2 3 4 数据的所花费的总时间的对比来说明模型的优化性 已知参数中 k 8 当 j 1 时 很容易可以看出 两种模型所花费的时间是一样的即 1 0 25 y ty k 当 j 2 时 在模型一中 21 211 2 1 2 1 125 0 284 88 j jkj kj y ty kk 在模型二中 1123 3123 0 319 172 k Tttt k k 当 j 3 时 在模型一中 21 211 2 1 2 1 1 0 337 j jkj kj y ty kk 在模型二中 2111 21 0 47 11 k TTtT kk 当 j 4 时 在模型一中 21 211 2 1 2 1 1 0 475 j jkj kj y ty kk 在模型二中 3 2221 212121 0 588 111111 kkk TTtTT kkkkkk 将以上数据列表显示如下 模型一模型二 j 10 250 25 j 20 2840 319 j 30 3370 47 j 40 4750 588 将表中数据绘图对比如下图示 两种模型完成任务所用时间的对比 通过以上的对比可以看出 模型一的所花费的时间显然比模型二的时间要短 所以模型一应为可选择的方案 同时 通过理论分析可得如下结论 从问题的本身出发可以知道 无论那部分人先到达 无论救援人员分几 批到达 由于他们的出发时间相同 而到达时间不同 因此所用的时间 不同 在总路程一定的条件下 他们的平均速度不等 可以让平均速度 大的那部分人减少乘车 而让平均速度慢的多乘车 增加这部分人的平 均速度 使他们到达一地的时间提前 因此最优的方案一定是人员同时 到达目的地 因为运输车的速度要大于人行军的速度 由于问题的目标是同时到达目 的地的时间 而这个时间又取决于每个人的平均速度 显然要提高平均 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 j 1j 2j 3j 4 模型一 模型二 速度 必须充分利用车辆的速度优势 也只有前进时尽量满载 后退尽 量空载 才能发挥车辆的速度优势 综合以上两点可以分析得到 在最优方案中 应该是满载的车辆与其余 的行军人员必须同时到达目的地 因此 通过对以上两个模型的对比结果与理论证明可以说明模型一是解决问 题的优化方案 因此选用模型一来解决问题最适合 六 问题的求解 6 1 问题一 6 1 1 建立优化方案 根据题意可建立如下方案 设 n pb n mbj 其中 p 是自然数 j 是大于 1 的整数 对于这种情况 每辆车需要运载 j 组人 所有的车辆可以同时前进或后退 据此可以采用如下方案 开始让车满载 其余的人行军 人与车同时出发 当车开到 1 y 处 让车上的人行军前进 车回头接后面行军的人 当回头的车辆遇到正在行军的人员时 让其中的任意 mb 个人乘车前进 当车辆遇到前面行军的人员时 将车上的人员放下 让他们与前面行军 的人员一起继续行军 车回头接后面行军的人员 当车辆在返回的途中遇到后面行军人员时 再让 mb 个人员上车 其余的 人员继续行军 车辆再次前进 当遇到前面行军的人员时 将车上的人 员放下 让其随前面的行军人一起行军 如此反复 直至最后的 mb 歌人 上车 车载着这些人员一直开到目的地 6 1 2 证明方案的最优性 从方案中 能容易的得到 第一批乘车人员乘车路程为 1 y 行军路程为 y 第二批乘车人员不可能在第一批乘车人员之前到达目的地 第三批乘车人员 不可能在第二批乘车人员之前到达目的地 以此类推 第 j 1 批乘车人员不可 能在第 j 2 批乘车人员之前到达目的地 因此只要证明最后一批乘车人员乘车 的路程为 1 y 行军的路程为 y 就可以得到第一批乘车人员与最后一批乘车人 员同时到达 据此可以推出前面各批乘车人员的乘车路程为 1 y 行军路程为 y 因为车辆回头接最后一批人员的前提是第 y 1 批乘车人员赶上第一批乘车人 员 或者车辆将这批人员送到终点再回头接最后一批乘车人员 对于后一种情况 必然是第一批人员先最后一批人员到达目的地 其乘车路程一定多余最后一批乘 车人员 因此如果证明了最后一批乘车人员乘车的路程也是 1 y 那么一定是第 j 1 批乘车人员在途中赶上了第一批乘车人员 并且与第一批同时到达目的地 据此推出第 j 1 批乘车人员乘车的路程为 1 y 行军的路程为 y 以此类推 便可以证明各个批次的乘车人员乘车的路程为 1 y 行军的路程为 y 下面计算最后一批乘车人员的乘车路程 先计算每次车辆后退街道下一批 救援人员时车辆后退的路程 设 A 点为起点 B 点为第一批乘车人员下车的地点 D 点为车辆后退是与后面救援人员相遇的地点 经计算得到如下关系式 2 1 1 y AD k 1 1 1 k BDy k ADBC 因为第二批乘车人员与地一批乘车人员同时出发 同时到达 所以乘车路程 也为 1 y 将 D 看做新的起点 类似地 可以得到其后退的路程也是 1 y k 1 k 1 以此类推 可以得到车辆每次后退的路程为 1 y k 1 k 1 因此当车 辆让第 j 1 批乘车人员下车时 车辆向前行驶的距离为 j 1 1 y 当车辆 接到第 j 批乘车人员时 共后退了 j 1 k 1 1 y k 1 此时车辆实际前 进的路程为 11 121 1 1 1 11 jkyjy jy kk 将 y 用式子 4 代入得到 21 1 1 jy y k 所以最后一批乘车人员行军的路程为 y 乘车的路程为 1 y 因此与第一批 乘车人员的路程相同 同时到达目的地 方案是最优的 6 1 3 问题解决 在问题一中 可以知道各个参数的具体数值如下 需要运输的救援人员为 n 800 人 军分区与灾区的总路程为 100km 行车的速度为 80 km h 人行的速度为 10km h 军分区共有车辆为 m 10 辆 每辆车能够载人数量为 b 20 系数 k 80 10 8 有 n pb mbj 800 可得 p 40 j 4 将以上的参数带入到 x y 中可得到 8 1 436 70 70240 8 1 815 2 4 16 70 7040 8 1 815 xkm ykm 此时行军所用的时间 40603 44 75 10804 th 由此可知 对于问题一的最佳调运方案是 开始让所有的车满载 其余的人行军 人与车同时出发 当车开到 60km 处 让车上的人行军前进 车回头接后面行军的人 当回头的车辆遇到正在行军的人员时 让其中的任意 10 20 200 个人乘车 前进 当车辆遇到前面行军的人员时 将车上的人员放下 让他们与前面 行军的人员一起继续行军 车回头接后面行军的人员 当车辆在返回的途中遇到后面行军人员时 再让 10 20 200 个人员上车 其余的人员继续行军 车辆再次前进 当遇到前面行军的人员时 将车上 的人员放下 让其随前面的行军人一起行军 如此反复 4 次 直至最后的 10 20 200 个人上车 车载着这些人员一直开到目的地 6 2 问题二 6 2 1 建立优化方案 在问题二的模型中 此时 n pb n mbj 其中 p 是自然数 j 是分数 虽然 j 是 分数 但是式子 4 仍然成立 只要乘车路程满足 x y 的关系式 则该方案仍然 是最佳的 在问题二的条件下 可知个参数的具体数值如下 需要运输的救援人员为 n 800 人 军分区与灾区的总路程为 100km 行车的速度为 80 km h 人行的速度为 10km h 军分区共有车辆为 m 12 辆 每辆车能够载人数量为 b 20 系数 k 80 10 8 有 n pb mbj 800 可得 p 40 10 3 j 此时 p 2m 但却不是 m 的整数倍 此时先考虑 m p 2m m p m i i 是自然 数的情况下的方案 对于这种情况 显然前面的车辆集体行动的方案是行不通的 不妨采用分组行动的方案 将 p m 辆分成车分成一组 每组联合出动 经计算可 以知道 对于 m p2m 时 可以先将情形转化为 m p 2m 的情形 在制定方案时 可以先 运行 mb 个救援人员值 1 y 处 让他们继续行军至目的地 然后返回再接 mb 救援 人员赶上前面的行军队伍 并在返回直至后面的未有乘过车的救援人员小于 2mb 且大于 mb 个为止 当返回车与他们相遇时 情形就与已讨论的情形完全相 同 可用前面的方案对最后一批少于 2mb 救援人员进行调度 6 2 3 问题解决 在问题二的条件下 需要运输的救援人员为 n 800 人 军分区与灾区的总路程为 100km 行车的速度为 80 km h 人行的速度为 10km h 军分区共有车辆为 m 12 辆 每辆车能够载人数量为 b 20 系数 k 80 10 8 由 n pb mbj 800 可得 p 40 10 3 j 此时的 36 40 48 且 j 不是整数 可利用对以上讨论的情形 先将 12 20 240 个救援人员 运送至 1 y 处 让他们继续行军 然后返回再接 12 20 240 个救援人员赶上前面的行军队伍 并返回接后面未乘过车的救援人员 此时救援人员大于 12 20 240 但却小于 2 12 20 480 则也可利用前面的已讨 论的情形 再将它们编队 将车分成 12 40 24 12 3 组 救援人员分成 3 1 组 此时每组车除了完成一组救援人员的乘车任务外 还要共同承担第四队的运输任 务 将 j 10 3 代入到式子 4 计算得到 1 10 2 1 143 100 10034 15 10 41 8 12 3 ykm 由于此时的 当前两组救援人员运送完成时 设所花费的总时间 则根据 s t 可以求得当开始运送开始运送重分组救援人员费的所需要运送的路程 以及再 s t 次路程内的最优化后的结果如下 A B C D E F G 设第一组救援人员到达处所花费的时间为 则可以求得 1 1AEy 1 t 此时的其余的救援人员行军到 AB 处 此时 1 1 1y t k 1 1y k 1 1 1 1 y BEy k 不妨设 BE S 则 因为救援人员行军的速度是相同且不变的 1 1 1 1 y sy k 则前一组与后一组救援人员相差的路程总为 S 当车辆由 E 点返回接第二组救援 人员的时候 车与救援人员在 C 点相遇 车辆在 CE 段多花费的时间 2 1 BE t K 此时车辆继续载着第二组人追逐第一组人知道 F 点追上 则在 CF 所花费的时间 当车辆将第二组救助人员运输结束后 从 F 点返回接其余的救援人员 3 1 s t K 并开始进行新的编组 假设在 D 点与剩余的救援人员相遇 此时所花费的时间 此时的 而此时未乘过车的救援人员多行走的路程为 4 1 s t K 1234s ttttt 1 则这一部分人在 m p 2m 的情形下要完成的运输路程为 1 1 s t s t 根据问题二的已知条件将各个参数的具体数值代入到以上的各个式子中 可 以得到如下结论 1234 120 41 s ttttth 120 100 10100100 41 ss tt 将 i 3 代入到式子 5 计算得到 2 2 100 104 87 8 1 32 s ytkm 设第一批人到达灾区的时间是 则 1 T 11 1 10010034 1534 15 4 24 80108010 yy Th 设最后一批人达到灾区的时间是 则 2 T 22 2 100 10 8010 s s tyy Tt 120 100 104 87 1204 87 41 4 24 804110 h 因为 所以所有的救援人员同时到达灾区 所以给方案是最优化的方 1 T 2 T 案 即问题二的最佳调运方案是先将 12 20 240 个救援人员 运送第一组救援人 员至 100 34 15 65 85km 处 让他们继续行军 然后返回再接第二组 12 20 240 个救援人员赶上前面的行军队伍 并返回接后面未乘过车的救援人员 然后将四 辆车分成一组 剩余的救援人员分成 3 1 4 组 然后具体采用以下方案 三组车辆载满救援人员与另一组救援人员同时出发 车队行驶至 第一组车上的人下车行军 车返回接 120 100 104 87 3 41 后面的行军人员 其他需继续前进 当第一组车辆返回遇到正在行军的救援人员时 让他们乘车直到灾区 与此同时 原来的车队行驶至处 第二组车上的 120 2 100 104 87 3 41 救援人员下车行军 车返回接从第一组车上下来的救援人员直至灾区 车队行驶至处 第三组的乘车人员下车行军 第 120 3 100 104 87 3 41 三组车返回接从第二组车上下来的救援人员 接到后直接让其乘车到灾 区 6 3 问题三 6 3 1 建立优化方案 在问题三中由已知条件可知 n 800 m 10 b 30 k 5 此时 n pb mbj 中 jp 均不为自然数 运输时一定会有乘不满的情况 此时不妨设虚增个救援人 2 p bn 员 其中是大于 的最小自然数 然后可以综合利用问题一与问题二的模型来解 2 ll 决问题三 具体方案如下 开始让车满载 m 组救援人员满载 其余的人行军 人与车同时出发 当车开到处 让车上的人行军前进 车回头接后面行军的人 1 1y 当回头的车辆遇到正在行军的人员时 此时且与 2 2mpmm 2 pm m 得最大公约数是 1 则可以以每辆车为一个单位 开始让满载前进 让其中的 任意 mb 个人乘车前进 车辆每前进 则一辆车上的人下车行军前进 2 1 y a m 车返回先接行军组的人 再按下车先后接正在后面行军的一车人 直至所有的救 援人员到达目的地 6 3 2 证明方案的最优性 以下对上面的方案进行理论推导 第一阶段 当车辆在着第一组的人出发时 由将带入到式子 4 中可以 121 np bmbj 1 j 得到 1 1 1 21 12 j y kj 此时走完时所用的时间 1 1y 1 1 1y t k 在 时间内 后面的救援人员所行军的路程为 1 t 1 1 1y s k 当车辆运送第一组救援人员结束时 车辆返回与后面的救援人员相遇时 在 这期间后面的救援人员所走的路程为 1 21 11 1 1 y sy kk 此期间所花费的时间 1 21 11 1 1 y ty kk 则 1 12 2 1 1 y sss k 在后面的救援人员走完 s 的路程时所花费的时间为 1 312 2 1 1 y ttt k 剩余的路程为 1 2 1 11 1 y as k 第二阶段 从此时开始 车辆每前进 则一辆车上的人下车行军前进 车返回先 2 1y m 接行军组的人 再按下车先后接正在后面行军的一车人 直至所有的救援人员到 达目的地 此时的 将带入到式子 4 中可以得到 2 22 npm bmbj 2 j 2 2 2 21 12 j y kj 在此过程中 对于第 m 辆车进行求解可以得出 在此阶段的的第 m 组救援人员乘车行驶的路程为 所花费的 2 2 1 1 y my m 时间是 下车后第 m 组救援人员在行军的路程后才会 2 1 1y t k 2 2 11 y pm mk 有车辆返回接他们 此期间所花费的时间为 此时他们与 2 22 11 y tpm mk 车相距的路程为 当他们相遇时所花费时间为 2 2 11 yk pm mk 2 32 111 ykk tpm mkk 由以上证明可以求得 在第 m 组救援人员与返回的车辆相遇之前 第 m 救援 人员应经走完了的路程 即 也就是说第 m 组的人在被运送a 223 1sytta 后在行走的路程即可与第一组救援人员同时到达目的地 2 1y 2 y k 6 3 3 解决问题 在第一阶段中救援人员到达目的地所花费的时间是 1 11 1y Ty k 在第二阶段所有的救援人员到达目的地所花费的时间是 2 232 1 y Ttya k 经证明可得 即多有的救援人员同时到达目的地 12 TT 有问题三的已知条件可得如下结论 第一阶段的 121 810np bmbj 第一阶段的 27 1 j 第二阶段的 2 22 510npm bmbj 第二阶段的 17 2 j 在第一与第二阶段中 k 与 m 保持不变即 k 5 m 10 将以上个参数带入到具体是式子后可得如下结果 1 2 137 11 147 y as k 1 1 1 2117 100 10036 17 1247 j ykm kj 1 11 11730123 10 104 89 4747547 y Tyh k 2 2 2 217 100 10018 92 1237 j ykm kj 1 22 2322 2 1 1 10 1 104 89 1 yyy Ttyayah kkk 即 12 4 89TTh 即解决此问题的优化方案是 开始让车满载 10 组救援人员满载 其余的人行军 人与车同时出发 当车开到处 让车上的人行军前进 车回头接后面行军的人 63 83km 当回头的车辆遇到正在行军的人员时 以每辆车为一个单位 开始让 10 辆车满载前进 让其中的任意个人乘车前进 车辆每前进 10 30300 则一辆车上的人下车行军前进 车返回先接行军组的 100 18 9237 6 39 1047 km 人 再按下车先后接正在后面行军的一车人 直至所有的救援人员到达目的地 6 4 问题四 6 4 1 建立优化方案以及问题解决 由已知条件可以看出 该问题的求解可以分解为两个部分 第一部分中可利 用问题一中的模型将所有的救援人员运输至 70km 处即从 A 运送至 C 然后再将然 后再次利用问题一中的模型将所有的救援人员从 70km 处运送至 100km 处 目的 地 即从 C 运送至 B A C B 在第一部分中 可以求得以下结论 需要运输的救援人员为 n 800 人 由 A 到 C 的路程为 70km 行车的速度为 80 km h 人行的速度为 10km h 军分区共有车辆为 m 10 辆 每辆车能够载人数量为 b 20 系数 k 80 10 8 有 n pb mbj 800 可得 p 40 j 4 将以上的参数带入到 x y 中可得到 1 1 8 1 436 70 70168 8 1 815 2 4 16 70 7028 8 1 815 xkm ykm 此期间所用的是 22 2 702842 3 325 10801080 yy th 在第二部分中 可以求得以下结论 需要运输的救援人员为 n 800 人 由 C 到 B 的路程为 30km 行车的速度为 40 km h 人行的速度为 10km h 军分区共有车辆为 m 10 辆 每辆车能够载人数量为 b 20 系数 k 40 10 4 有 n pb mbj 800 可得 p 40 j 4 将以上的参数带入到 x y 中可得到 2 2 4 1 420 30 3054 5 4 1 811 2 4 16 30 3016 4 4 1 811 xkm ykm 此期间所用的是 22 2 3016 413 6 1 98 10401040 yy th 在运送结束后所用的总时间为 12 3 325 1 985 305 z ttth 由此可知 对于问题四的最佳调运方案是 在第一部分时 开始让所有的车满载 其余的人行军 人与车同时出发 当车开到 28km 处 让车上的人行军前进 车回头接后面行军的人 当回头的车辆遇到正在行军的人员时 让其中的任意 10 20 200 个人乘车 前进 当车辆遇到前面行军的人员时 将车上的人员放下 让他们与前面 行军的人员一起继续行军 车回头接后面行军的人员 当车辆在返回的途中遇到后面行军人员时 再让 10 20 200 个人员上车 其余的人员继续行军 车辆再次前进 当遇到前面行军的人员时 将车上 的人员放下 让其随前面的行军人一起行军 如此反复 4 次 直至最后的 10 20 200 个人上车 车载着这些救援人员一直开到 C 地 在第二部分中 开始让所有的车满载 其余的人行军 人与车同时出发 当车开到 12km 处 让车上的人行军前进 车回头接后面行军的人 当回头的车辆遇到正在行军的人员时 让其中的任意 10 20 200 个人乘车 前进 当车辆遇到前面行军的人员时 将车上的人员放下 让他们与前面 行军的人员一起继续行军 车回头接后面行军