一类指派问题的改进矩阵解法.docx

摘 要: 本文介绍了求历时最短的指派问题,给出了改进矩阵解法的求解步骤,论述了这种
解法的合理性,最后举例说明了这种解法的方便可行性。
关键词: 指派问题 改进矩阵解法 整数规划 效率矩阵
1. 引言
我们经常遇到这样的问题: 某单位需要完成某 n 项任务,恰好有 n 个人可承担这些任务。
由于每个人的专长不同,每个人完成某项任务的效率也不同,于是产生了应指派哪个人去完
成哪项任务,才能使完成这 n 项任务的总效率最高,或者说是所用总时间最短的问题,这类
问题被称为指派问题或分派问题 [1―2]。根据这类指派问题的特点, 我们可以用匈牙利法
等方法求解,但其过程非常复杂,容易出现错误。以下介绍一种求解这类指派问题的较为简
便的方法――改进矩阵解法。
2. 改进矩阵解法的步骤
指派问题是整数规划, 是 0― 1 规划的特例, 也是运输问题的特例, 因此当然可以用整数
规划、 0― 1 规划或运输问题的解法求解,即可用枚举法和表上作业法等方法求解,但这就如
同用单纯形法求解运输问题一样是不划算的。 我们通常利用指派问题的特点来求解指派问题,
即匈牙利法。但这种方法的过程太过于繁琐,且容易出错。下面给出一种求解历时最短的指
派问题的新解法,即矩阵解法。具体的方法和步骤如下[ 3― 5]。
第一步:利用最小―最大元素法给出初始指派。
1)找出效率矩阵中每一列元素的最小元素,记为, a,j=1 ,2,…, m,若有不止一个最
小元素,可任选其一试行;
2)找出效率矩阵中每一列元素的最小元素中的最大者, 记为 θ ,若有不止一个最大元素,
亦可任选其一试行;
3)给元素 θ 加( ?摇),同时将效率矩阵中其所在的行和列划去;
4)重复以上三步, 分别可得到 θ ,θ ,…,θ 。此时所有加 ()者便构成一个初始指派。
第二步:检验初始指派,具体方法如下。
找出所有加()中的最大者,记为 θ ,为了说明方便,我们不妨假设 θ =θ , θ =a( a 为
效率矩阵中对角线上的元素, j=1 ,2,…, m),分别将 θ 与 θ( j=2 ,…, m)所位于的行和
列中交叉位置的四个元素取出构成一个二阶方阵。
即:( a) aa ( a)
1)若 a≤max{a ,a} ( j=2 ,…,m),则初始指派即为所求指派, 问题解决, 结束。 否则,
进入下一步。
2)若 a> max{a,a} ( j=2 ,…, m),则 a 将 a 和的括号去掉,并给对应的 a 和 a 加()。
返回第二步,重新检验,直到结束为止。
3)若通过检验条件 1),确定了指派问题的解,此时如果所有加()的元素中存在这样
两个处于对角线位置的元素,其和与另一侧对角线上的两个元素之和相等,则可以去掉这两
个加()元素的() ,并给另一侧对角线上的两个元素加() ,所得的新指派问题也是原指派
问题的解。
另外,第二步中的 3)是检验指派问题存在重解的一种情况。当条件满足时,所求指派
问题一定存在重解,且按照 3)的方法即可求得一个重解,但当条件不满足时,所求指派问
题也有可能存在重解。
3. 论述
求解历时最短的指派问题,实质就是要解决两个问题: ( 1)在 n 阶系数矩阵中确定 n 个
独立元素;( 2)保证所