第6题-加油站加油排队.doc

精选优质文档-----倾情为你奉上第6题 加油站加油排队　　某个加油站每次只能对一种车辆加油各种车辆的加油时间如下：　　车型： 大型卡车 中型卡车 小汽车　　时间(分)： 7 5 4　　如果这三种车辆同时到达加油站加油，问加油站应该怎样安排加油顺序，才能使总共需要的时间(加油及等候时间最省？　　分析：由于加油站一次只能对一种车辆加油，所以三种车辆同时到达，必定产生有两种车辆要等候要节省时间，必须尽量减少等候时间，而让加油时间短的车辆先加油，就能节省总的加油及等候时间我们不妨计算一下按大型卡车、中型卡车、小汽车加油顺序所需总的等候时间：7＋7＋7＋5＋5＋4= 35(分)　　如果按大型卡车、小汽车、中型卡车的加油顺序计算总的等候时间为：7＋7＋7＋4＋4＋5= 34(分)　　显然，第二种方案比第一种方案好一些如果我们把所有的加油方案一一列举出来，通过计算，就能找到最优方案对于这样的问题是否有规律性，利用它还能解决更一般的情形吗？　　解：由于加油时间分别为7分、5分和4分钟，所以合理的方案是安排加油时间短的车辆先加油，这样其他两种车辆的等候时间就较短，因此按小汽车、中型卡车、大型卡车的加油顺序计算总的等候时间为最少。

4＋4＋4＋5＋5＋7= 29(分)　　回顾：如果有几种不同类型的车辆同时到达加油站，加油的时间分别为T1 、T2 …Tn ，则等候的总时间T为：T＝nT1+ (n- 1)T2+ (n- 2)T3＋…+Tn　　要使T最少，只有当T1≤T2≤…≤Tn 时，T取到最小，因此必须安排加油时间短的车辆先加油，加油时间长的车辆放在后面　　下面我们考虑将上述问题从加油站的加油能力方面加以推广：　　如果加油站能够同时对两种车辆加油，对各种车辆的加油所需时间为：　　车型： 重型车 大卡车 中型卡车 小汽车 微型车　　时间(分)： 10 7 5 4 3　　车型：摩托车　　时间(分)： 2　　如果有上述六种不同类型的车辆同时到达，又应该如何安排加油顺序呢？　　首先必须考虑分成二组，分组和编排加油顺序仍然以尽量减少等候时间为原则第一种方案是每组各三辆车设第一组，加油时间分别为T1 、T2 、T3，则总共需要时间为：T1+ (T1＋T2)+ (T1+ T2+ T3)＝ 3T1＋ 2T2＋T3　　同理，另一组为3t1+ 2t2＋t3，六种车辆所需的总时间T为：T= 3(T1 ＋t1 )＋2(T2+t2)＋(T3 ＋t3 )　　从式子中可以看出，T1＋t1尽可能小。

因此，摩托车、微型车安排在最前，小汽车、中型卡车其次，而大卡车及重型车安排在最后即分成的两组为：　　第一组：摩托车、小汽车、大卡车　　第二组：微型车、中型卡车、重型车　　所需总时间T为：　　T= 3(2＋3)+ 2(4＋5)＋(7＋10)= 50(分)　　如果按另一种方案编成四辆和二辆的两组又如何呢？显然时间为：　　(4T1＋3T2 +2T3 ＋T4 )＋(2t1+t2)= T1 ＋3(T1+ T2)　　＋2(T3＋t1)+ (T4＋t2)　　与第一种方案作同样的分析，多了一个T1，不是最节省同样以五辆与一辆为两组的所需时间更不节省了　　注：下面我们不加证明地介绍一个不等式的结论，上述问题也可看作它的一个应用　　假设有两组数： a1 ， a2，…， an； b1 ， b2 ，…， bn，满足：　　a1≤a2 ≤…≤an； b1≤b2 ≤…≤bn，我们称：　　a1b1＋a2b2 +a3 b3 ＋…＋anbn 为顺序和；　　a1bn＋a2 bn－1 + …+ anb1 为逆序和；　　ai1bj1＋ai2bj2＋…＋ainbjn(1≤i1，i2，…， in≤n， 1≤j1，…，　　jn≤n)为乱序和。

　　在不等式中有：顺序和≥乱序和≥逆序和证明从略)　　在上述问题中的总时间T= nT1 ＋(n- 1)T2 ＋…＋Tn的情况下，要使T最小，取其逆序和即可，即有T1≤T2≤…≤Tn练习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 (单位：分)　　完成先后两道工序总用了多少时间呢？专心---专注---专业。