指派问题新解法的探讨.pdfVIP

指派问题新解法的探讨 于福贾春玉 [摘要]指派问题新解法省去了匈牙利法的第三步，进行试指派，寻求最优解中间环节。免去 了繁琐的画最少的零复盖线进行造零的步骤。新解法是通过检验是否满足约束条件，即零元素是否够 用。满足约束条件，即零元素够用可得最优解，否则，需进一步造零，以满足约束条件。直至得出最优 解为止。方法简单、便于掌握且计算工作量小、运算速度快。比匈牙利法快而简单，该方法在企业管理 运输问题中的应用效果更为明显。 (关键词】 指派问题匈牙利法约束条件零元素新解法 一、指派问题的数学模型及其理论依据 二、指派问题新解法的探讨 在生产运营管理中有时会遇到这样的问题：有n项 1．匈牙利法简介 任务要完成，恰好有n个人可以去完成其中每一项任务， 匈牙利法是指派问题常用的解法。匈牙利法经过第 由于每项任务的性质和个人专长不同，因此各项任务由 一步，每行减去相应的最小元素，第二步，每列减去相 不同的人完成的效率有所不同。在这种情况下如何分配 应的最小元素。第三步，进行试指派，寻求最优解。当 任务使每人完成一项且仅完成一项，使完成所有n项任 零元素不够用时，得不到最优解需要经第四步进行繁琐 务的总效益最高。这类问题称为指派问题或分配问题。 的画最少的零复盖线进行造零。这样大大降低了运算速 此类问题的解法常用的有线性规划法和匈牙利法。匈牙 度，增加了计算工作量。然后重新回到第三步直到得出 利法相对来说比线性规划法简单一些，运算速度快一些， 最优解为止。 但仍不理想。指派问题的数学模型可描述为： 匈牙利解法步骤为： 第一步，每行减去相应的最小元素。在本例中由表 目标函数为 Min z=∑∑qK i=l 2得表3。 J=1 第二步，每列减去相应的最小元素。在本例中由表 约束条件为：∑xij=1，J=1,2，…，n I=l 3得表4。 第三步，进行试指派。以寻求最优解。在本例中参 ● ～ ．， 见表5。具体步骤为： O X 宴Ⅲ铲 =或 _： “撕 0有 ．，的 m和 (1)从只有一个零元素的行(或列)开始，给只有 一个零元素加小括号()作标记，然后给已作标记加小括 其中目标函数为：Min z=∑∑q～ i；I j=1 号零元素所在那列的其它零元素加中括号[]作标记。中 括号[]表示不能再安排其它任务。 因为Clj／0，～I0，所以有Min z=∑∑cqx。≥0， (2)再给每列(行)只有一个零元素加小括号()作 标记，然后给已作标记加小括号零元素所在那行的其它