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

　　此时，再将第二列都减去该列的最小数1，变成0和1，同样不影响最优方案的确定，原表变为右上表。

　　不同行、不同列的两个数之和代表一种方案，因为

　　0＋0＜0+1，

　　所以最优方案为乙做A、甲做B。上面的化简过程可表示为：

　　总结上面的方法：对于n个人n项工作的合理分配问题：

　　（1）先将各行都减去该行中最小的数；

　　（2）再将各列都减去该列中最小的数；

　　（3）最后选择不在同一行，也不在同一列的n个0即可。

　　在实施上述变换后，如果仍选不出n个不同行也不同列的0，因为我们的目的是选取一组不同行、不同列的n个数，使这n个数之和尽量小，既然得不到n个0，可用表中最小的数代替0（见例6）。

　　例6 给甲、乙、丙三人分配A，B，C三项工作，他们完成这三项工作的时间如下表：

　　完成这三项工作所需总时间最少是多少？

　　分析与解：

　　因为没有三个不同行也不同列的0，我们用右下角的1代替0，此时，○内的三个数就是我们要找的最佳方案，即甲做B、乙做A、丙做C。所需总时间为

　　9＋7＋9=25（时）。

　　练习28

　　1.某种健身球由一个黑球和一个白球组成一套。已知两个车间都生产这种

　　现在两个车间联合起来生产，每月最多能生产多少套健身球？

　　2.某车间有铣床5台、车床3台、自动机床1台，生产一种由甲、乙两种零件各 1个组成的产品。每台铣床每天生产甲零件10个，或者生产乙零件20个；每台车床每天生产甲零件20个，或者生产乙零件30个；每台自动机床每天生产甲零件30个，或者生产乙零件80个。这些机器每天最多可生产多少套产品？

　　3.车过河交渡费3元，马过河交渡费2元，人过河交渡费1元。某天过河的车、马数目的比为2∶9，马、人数目的比为3∶7，共收得渡费945元。问：这天渡河的车、马、人的数目各多少？

　　4.有4辆汽车要派往七个地点运送货物，右图中的数字分别表示这七个地点完成任务需要的装卸工人数。如果装卸工可以跟车，那么最少要安排多少名装卸工才能完成任务？

　　5.有一批长4.3米的条形钢材，要截成0.7米和0.4米的甲、乙两种毛坯，要求截出的甲、乙两种毛坯数量相同。如何下料才能使残料最少？

　　6.用10米长的钢筋做原材料，截取3米和4米长的钢筋各100根，至少要用多少根原材料？

　　7.给甲、乙、丙分配A，B，C三项工作，他们完成这三项工作的时间如下表。怎样分配工作才能使完成这三项工作所需总时间最少？最少用多少时间？