六年级奥数专题二十八：运筹学初步（2）(2)

　　加工甲、乙、丙三种部件应分别安排12人、5人和60人。

　　例3 有4辆汽车要派往五个地点运送货物，右图○中的数字分别表示五个地点完成任务需要的装卸工人数，五个地点共需装卸工20人。如果有些装卸工可以跟车走，那么应如何安排跟车人数及各点的装卸工人数，使完成任务所用的装卸工总人数最少？

　　分析与解：可用试探法。因为五个地点中需装卸工最多的是5个人，所以如果每辆车跟5个工人，那么每辆车到达任何一个地点，都能正常进行装卸。由此得到，跟车人数的试探范围是1～5个人。

　　若每车跟车5人，则各点不用安排人，共需20人；

　　若每车跟车4人，则原来需5人的点还需各安排1人，共需18人；

　　若每车跟车3人，则原来需5人的点还需各安排2人，原来需4人的点还需各安排1人，共需17人；

　　同理可求出，每车跟车2人，共需18人；每车跟车1人，共需19人。

　　可见，安排每车跟车3人，原来需5人的两个点各安排2人，原来需4人的点安排1人，这时所用的装卸工总人数最少，需17人。

　　在例3中，我们采用试探法，逐一试算，比较选优。事实上，此类题目有更简捷的解法。假设有m个地点n辆车（n≤m），m个地点需要的人数按从多到少排列为

　　A1≥A2≥A3≥…≥Am，

　　则需要的最少总人数就是前n个数之和，即

　　A1＋A2＋…＋An。

　　这时每车的跟车人数可以是An＋1 至An 之间的任一数。具体到例3，5个点4辆车，5个点中需要人数最多的4个数之和，即5＋5＋4＋3=17（人）就是需要的最少总人数，因为A4=A5=3，所以每车跟车3人。若在例3中只有2辆车，其它条件不变，则最少需要 5＋5=10（人），因为A2=5，A3=4，所以每车跟车5人或4人。当每车跟车5人时，所有点不再安排人；当每车跟车4人时，需要5人的两个点各安排1人，其余点不安排人。

　　注：如果车辆数大于地点数，即n＞m，则跟车人数是0，各点需要人数之和就是总共需要的最少人数。