第6题-加油站加油排队word版本494.pdf

第 6 题 加油站加油排队 某个加油站每次只能对一种车辆加油。各种车辆的加油时间如下：车型：大型卡车 中型卡车 小汽车 时间(分)：7 5 4 如果这三种车辆同时到达加油站加油，问加油站应该怎样安排加油顺序，才能使总共需要的时间(加油及等候时间最省？分析：由于加油站一次只能对一种车辆加油，所以三种车辆同时到达，必定产生有两种车辆要等候。要节省时间，必须尽量减少等候时间，而让加油时间短的车辆先加油，就能节省总的加油及等候时间。我们不妨计算一下按大型卡车、中型卡车、小汽车加油顺序所需总的等候时间：777554=35(分)如果按大型卡车、小汽车、中型卡车的加油顺序计算总的等候时间为：777445=34(分)显然，第二种方案比第一种方案好一些。如果我们把所有的加油方案一一列举出来，通过计算，就能找到最优方案。对于这样的问题是否有规律性，利用它还能解决更一般的情形吗？解：由于加油时间分别为 7 分、5 分和 4 分钟，所以合理的方案是安排加油时间短的车辆先加油，这样其他两种车辆的等候时间就较短，因此按小汽车、中型卡车、大型卡车的加油顺序计算总的等候时间为最少。444557=29(分)回顾：如果有几种不同类型的车辆同时到达加油站，加油的时间分别为 T1、T2 Tn，则等候的总时间 T 为：TnT1+(n-1)T2+(n-2)T3+Tn 要使 T 最少，只有当 T1T2Tn 时，T 取到最小，因此必须安排加油时间短的车辆先加油，加油时间长的车辆放在后面。下面我们考虑将上述问题从加油站的加油能力方面加以推广：如果加油站能够同时对两种车辆加油，对各种车辆的加油所需时间为：车型：重型车 大卡车 中型卡车 小汽车 微型车 时间(分)：10 7 5 4 3 车型：摩托车 时间(分)：2 如果有上述六种不同类型的车辆同时到达，又应该如何安排加油顺序呢？首先必须考虑分成二组，分组和编排加油顺序仍然以尽量减少等候时间为原则。第一种方案是每组各三辆车设第一组，加油时间分别为 T1、T2、T3，则总共需要时间为：T1+(T1T2)+(T1+T2+T3)3T1 2T2T3 同理，另一组为 3t1+2t2t3，六种车辆所需的总时间 T 为：T=3(T1 t1)2(T2+t2)(T3 t3)从式子中可以看出，T1t1尽可能小。因此，摩托车、微型车安排在最前，小汽车、中型卡车其次，而大卡车及重型车安排在最后。即分成的两组为：第一组：摩托车、小汽车、大卡车 第二组：微型车、中型卡车、重型车 所需总时间 T 为：T=3(23)+2(45)(710)=50(分)如果按另一种方案编成四辆和二辆的两组又如何呢？显然时间为：(4T13T2+2T3 T4)(2t1+t2)=T1 3(T1+T2)2(T3t1)+(T4t2)与第一种方案作同样的分析，多了一个 T1，不是最节省。同样以五辆与一辆为两组的所需时间更不节省了。注：下面我们不加证明地介绍一个不等式的结论，上述问题也可看作它的一个应用。假设有两组数：a1，a2，an；b1，b2，bn，满足：a1a2 an；b1b2 bn，我们称：a1b1a2b2+a3 b3 anbn 为顺序和；a1bna2 bn1+anb1 为逆序和；ai1bj1ai2bj2ainbjn(1i1，i2，inn，1j1，jnn)为乱序和。在不等式中有：顺序和乱序和逆序和。(证明从略)在上述问题中的总时间 T=nT1(n-1)T2 Tn的情况下，要使T 最小，取其逆序和即可，即有 T1T2Tn。练习 6 1某加工厂加工某一批零配件，需要加工后才能送到下一道工序继续加工，否则只能等待。已知各种类型的零件加工时间如下：零件类型：1 2 3 4 5 加工时间：55 40 30 80 60(单位：分)问如何安排加工顺序才能使总的等待时间最短？2如果这 5 种零件需要先后两种工序加工，加工时间如下表，又应该如何安排加工顺序呢？零件类型：1 2 3 4 5 加工工序 1：50 40 30 20 40 加工工序 2：30 20 60 80 60(单位：分)完成先后两道工序总用了多少时间呢？