【摘要】：以上介绍的是标准形式的指派问题,条件是目标函数最小、人员数目与任务数目相等以及效率矩阵中的元素非负。此外,还有可能遇到以下几种非标准形式的指派问题,均可以通过一定的方法将其转换成标准形式的指派问题进行求解。所以,将最大值指派问题转换成标准指派问题的方法,就是在效率矩阵中,用它的最大元素减去各个元素,得到一个标准矩阵,再利用一般的匈牙利解法求最优解。
以上介绍的是标准形式的指派问题,条件是目标函数最小、人员数目与任务数目相等以及效率矩阵中的元素非负。此外,还有可能遇到以下几种非标准形式的指派问题,均可以通过一定的方法将其转换成标准形式的指派问题进行求解。
1.最大值指派问题
所以,将最大值指派问题转换成标准指派问题的方法,就是在效率矩阵（cij ）中,用它的最大元素减去各个元素,得到一个标准矩阵,再利用一般的匈牙利解法求最优解。
例7.9 有甲、乙、丙、丁4人分别完成4项工作,每个人完成不同工作的效益如表7.21所示,如何分配工作可使总效益最大?
表7.21 任务分配效益表
解 求总效益最大,即目标函数是max,由表7.21可知,17是效率矩阵中的最大元素,用17减去各个元素,得到一个新的标准矩阵,再利用匈牙利解法求解,具体过程如下所示。(www.xing528.com)
从而得到该问题的一个最优解,此时甲——D,乙——B,丙——A,丁——C,目标函数为max f(x)=15+7+13+15=50。
2.人员数目与任务数目不相等的指派问题
若人员少任务多,则可以加入一些虚拟的“人”,这些虚拟的“人”做各项工作的费用取值为0;若人员多任务少,则可以加入一些虚拟的“任务”,这些虚拟的“任务”的费用取值也为0。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
