第6题-加油站加油排队

第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。练习61某加工厂加工某一批零配件，需要加工后才能送到下一道工序继续加工，否则只能等待。已知各种类型的零件加工时间如下：零件类型：1 2 3 4 5加工时间：55 40 30 80 60 (单位：分)问如何安排加工顺序才能使总的等待时间最短？2如果这5种零件需要先后两种工序加工，加工时间如下表，又应该如何安排加