五项任务需要分配到四种不同型号的机器上来执行。四种型号的机器分别有25、30、20和30台。五项任务的工作量分别是20、20、30、10和25，不能把第四类机器分配到第四项任务上。每项任务当中的每个工作量在执行时需占用任意型号的1台机器。各类机器分配到各项

admin2018-10-14 71

问题五项任务需要分配到四种不同型号的机器上来执行。四种型号的机器分别有25、30、20和30台。五项任务的工作量分别是20、20、30、10和25，不能把第四类机器分配到第四项任务上。每项任务当中的每个工作量在执行时需占用任意型号的1台机器。各类机器分配到各项任务时所发生的单位成本如下表所示。

任务分配的最优分配方案中，总成本是( )。

选项 A、500
B、605
C、560
D、520

答案C

解析这是一道复杂的分配问题(Assignment Problem)。
本题可以使用边际收益法(变动成本法、差值法)，也叫伏格尔法(VogelMethod)，其主要思路是：求运费最便宜和次便宜之间的差，先满足运费差值大的。
该方法原理是，某产地的产品如不能按最小运费就近供应，就考虑次小运费，这就有一个差额；差额越大，说明不能按最小运费调运时，运费增加越多；因而对差额最大的产地，就应当采用最小运费调运。
首先为原表格增加一行变动成本，即每列最小成本与次小成本的差值。