题目

给甲、乙二人分配A，B两项工作，他们完成这两项工作所需要的时间如表：

怎样分配工作才能使完成这两项工作所需的总时间最少？

提问时间：2021-10-14

答案

最优方案为乙做A、甲做B
上面的化简过程可表示为：
答：乙做A、甲做B，才能使完成这两项工作所需的总时间最少．

因为不同的人要做不同的工作，所以上表中不同行、不同列的两数之和对应一种方案，共两种：
（1）甲做A、乙做B，需要7+6=13（时）；
（2）甲做B、乙做A，需要4+8=12（时）．
显然后一种方案优于前一种方案．
为了能够处理更复杂的问题，我们将上例的数量关系尽量简化．
如果把表中第一行的两数都减去该行的最小数7，变成0和1，那么上面（1）（2）各式也各减少7，不影响它们之间的大小关系，即不影响最优方案的确定．
同理，第二行都减去该行的最小数4，变成0和2，也不影响最优方案的确定．
经上述变换后，原表变成左下表：


此时，再将第二列都减去该列的最小数1，变成0和1，同样不影响最优方案的确定，原表变为右上表．
不同行、不同列的两个数之和代表一种方案，因为
0+0＜0+1，
所以最优方案为乙做A、甲做B．

本题考点：最优化问题．

考点点评：总结上面的方法：对于n个人n项工作的合理分配问题：
（1）先将各行都减去该行中最小的数；
（2）再将各列都减去该列中最小的数；
（3）最后选择不在同一行，也不在同一列的n个0即可．
在实施上述变换后，如果仍选不出n个不同行也不同列的0，因为我们的目的是选取一组不同行、不同列的n个数，使这n个数之和尽量小，既然得不到n个0，可用表中最小的数代替0．