试述什么是指派问题指派问题可以用什么方法求解
发布网友
发布时间：2022-04-25 12:59
共1个回答
热心网友
时间：2024-10-10 14:35
具体如下：
某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。这类问题称为指派问题或分派问题。
解决方法：
一、做减法（归约）：
行归约：每行元素减去该行最小元素。
列归约：每行元素减去该行最小元素。
归约顺序无所谓，目的就是把所有的数尽可能化的很小，但最小的数不能为负数。
二、圈零划零
找到含零元素最少的行，对零元素打圈，划去打圈零元素所在行和列存在的零元素，重复这个步骤，直到矩阵中所有的零元素都被处理完。
深度解析：
首先描述了区间数、序值、序区间和语言评价等多种信息形式及相关概念;然后通过计算各人员指派信息与正负理想点的距离,得到将某项任务指派给某个人员完成的"机会成本"和"效益"。
从而得到指派问题总"机会成本"矩阵和总"效益"矩阵,在此基础上建立了使总成本最小及总效益最大为目标的指派问题数学模型,并采用匈牙利法进行求解。最后,通过一个算例分析说明了本文给出方法的`可行性和有效性。
