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

《一类指派问题的改进矩阵解法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一类指派问题的改进矩阵解法孙静，何斌，安娜(广东工业大学经济管理学院，广东广州，510520)sunjing860620@163.com86-13631406540摘要：介绍了求历时最短的指派问题，给出了改进矩阵解法的求解步骤，论述了这种解法的合理性，最后举例说明了这种解法的方便可行性。关键词：指派问题；改进矩阵解法；整数规划；效率矩阵ImprovementMatrixsolutionaboutakindofAssignmentProblemJingSun，BinHe，NaAn（Dept.ofInformationManagementandEngineering,Guangzho

2、u,Guangdong,510520）Abstract：Thepaperdescribesthelastedshortestortheefficiencyhighestassignmentproblem,andmainlyintroducedsonekindofnewmethod-improvementmatrixsolutiontosolvethiskindofassignmentproblem,meanwhile,itdiscussestherationalityofthissolution.Finally,itillustratesthefeasibilityofconve

3、nienceofmatrixsolution.Keywords：AssignmentProblem，ImprovementMatrixSolution，IntegerProgramming，EfficiencyMatrix1.引言我们经常遇到这样的问题，某单位需要完成某n项任务，恰好有n个人可承担这些任务。由于每个人的专长不同，每个人完成某项任务的效率也不同，于是产生了应指派哪个人去完成哪项任务，才能使完成这n项任务的总效率最高，或者说是所用总时间最短的问题，这类问题被称为指派问题或分派问题[1-2]。根据这类指派问题的特点，我们可以用匈牙利法等方法求解，但其过程非常复杂，容易出

4、现错误。以下将介绍一种求解这类指派问题的较为简便的方法——改进矩阵解法。-6-2.改进矩阵解法的步骤指派问题是整数规划，是0-1规划的特例，也是运输问题的特例，因此当然可以用整数规划、0-1规划或运输问题的解法求解，即可用枚举法和表上作业法等方法求解，但这就如同用单纯形法求解运输问题一样是不划算的。我们通常利用指派问题的特点来求解指派问题，即：匈牙利法。但这种方法的过程太过于繁琐，容易出错。下面给出一种求解历时最短的指派问题的新解法，即：矩阵解法。具体的方法和步骤如下[3-5]：第一步：利用最小-最大元素法给出初始指派1）找出效率矩阵中每一列元素的最小元素，记为，j=1，2，…，

5、m,若有不止一个最小元素，可任选其一试行；2）找出效率矩阵中每一列元素的最小元素中的最大者，记为，若有不止一个最大元素，亦可任选其一试行；3）给元素加（），同时将效率矩阵中其所在的行和列划去；4）重复以上三步，分别可得到，，…，。此时所有加（）者便构成一个初始指派。第二步：检验初始指派，具体方法如下：找出所有加（）中的最大者，记为，为了说明方便，我们不妨假设=，=（为效率矩阵中对角线上的元素，j=1，2，…，m），分别将与（j=2，…，m）所位于的行和列中交叉位置的四个元素取出构成一个二阶方阵，即：。1）若max{，}（j=2，…，m），则初始指派即为所求指派，问题解决，结束。否

6、则，进入下一步。2）若>max{，}（j=2，…，m），则将和的括号去掉，并给对应的和加（）。返回第二步，重新检验，直到结束为止。3）若通过检验条件1），确定了指派问题的解，此时如果所有加（）的元素中存在这样两个处于对角线位置的元素，其和与另一侧对角线上的两个元素之和相等，则可以去掉这两个加（）元素的（），并给另一侧对角线上的两个元素加（），所得的新指派也是原指派问题的解。-6-另外，第二步中的3）是检验指派问题存在重解的一种情况。当条件满足时，所求指派问题一定存在重解，且按照3）的方法即可求得一个重解，但当条件不满足时，所求指派问题也有可能存在重解。3.论述求解历时最短的指派问

7、题，实质就是要解决两个问题：（1）在n阶系数矩阵中确定n个独立元素；（2）保证所确定的指派中的的n个独立元素之和是所有情况中最小的。（这里的独立元素是指系数矩阵中既非同行也非同列的元素）下面我们来逐一分析一下上述矩阵解法的步骤：第一步是利用最小-最大元素法给出初始指派的过程，最小-最大元素法虽然不能保证所选初始指派中的元素之和最小，但却可以保证接近最小，这就在一定程度上减少了计算步骤，简化了求解过程。通过对步骤3）的反复操作，保证了二维关系中一对一的关系，即：保证了所给出的初始指