最优指派问题的动态规划模型及算法

摘要

考虑了指派问题:有m项工作和n个人.若m与n是相同的,并且每一项工作只能由一个人来做;同时,每一个人只能做一项工作;符合这一条件的指派问题称为标准指派问题;若m与n不相同, 则称为非标准指派问题.本文在充分考虑了指派问题性质的基础上,建立了求解标准指派问题的动态规划模型,并给出了其求解算法;同时在标准指派问题的动态规划模型的基础上给出了求解非标准指派问题的动态规划模型.最后,通过实例说明了本文提出的方法的基本步骤和计算方法的可靠性.