《一类指派问题的改进矩阵解法.doc》由会员分享，可在线阅读，更多相关《一类指派问题的改进矩阵解法.doc（6页珍藏版）》请在金锄头文库上搜索。
1、 一类指派问题的改进矩阵解法孙静，何斌，安娜 (广东工业大学经济管理学院 ，广东广州，510520) 86-13631406540摘 要：介绍了求历时最短的指派问题，给出了改进矩阵解法的求解步骤，论述了这种解法的合理性，最后举例说明了这种解法的方便可行性。关键词：指派问题；改进矩阵解法；整数规划；效率矩阵 Improvement Matrix solution about a kind of Assignment ProblemJingSun，BinHe，NaAn（Dept. of Information Management and Engineering, Guangzhou, Guang
2、dong,510520）Abstract：The paper describes the lasted shortest or the efficiency highest assignment problem, and mainly introduceds one kind of new method - improvement matrix solution to solve this kind of assignment problem, meanwhile, it discusses the rationality of this solution. Finally, it illus
3、trates the feasibility of convenience of matrix solution.Key words：Assignment Problem，Improvement Matrix Solution，Integer Programming，Efficiency Matrix1.引言我们经常遇到这样的问题，某单位需要完成某n项任务，恰好有n个人可承担这些任务。由于每个人的专长不同，每个人完成某项任务的效率也不同，于是产生了应指派哪个人去完成哪项任务，才能使完成这n项任务的总效率最高，或者说是所用总时间最短的问题，这类问题被称为指派问题或分派问题1-2。根据这类指派问题
4、的特点，我们可以用匈牙利法等方法求解，但其过程非常复杂，容易出现错误。以下将介绍一种求解这类指派问题的较为简便的方法改进矩阵解法。2.改进矩阵解法的步骤指派问题是整数规划，是0-1规划的特例，也是运输问题的特例，因此当然可以用整数规划、0-1规划或运输问题的解法求解，即可用枚举法和表上作业法等方法求解，但这就如同用单纯形法求解运输问题一样是不划算的。我们通常利用指派问题的特点来求解指派问题，即：匈牙利法。但这种方法的过程太过于繁琐，容易出错。下面给出一种求解历时最短的指派问题的新解法，即：矩阵解法。具体的方法和步骤如下3-5：第一步：利用最小-最大元素法给出初始指派1）找出效率矩阵中每一列元素
5、的最小元素，记为，j=1，2，m,若有不止一个最小元素，可任选其一试行；2）找出效率矩阵中每一列元素的最小元素中的最大者，记为，若有不止一个最大元素，亦可任选其一试行；3）给元素加（），同时将效率矩阵中其所在的行和列划去；4）重复以上三步，分别可得到，。此时所有加（）者便构成一个初始指派。第二步：检验初始指派，具体方法如下：找出所有加（）中的最大者，记为，为了说明方便，我们不妨假设=，=（为效率矩阵中对角线上的元素，j=1，2，m），分别将与（j=2，m）所位于的行和列中交叉位置的四个元素取出构成一个二阶方阵，即：。1）若 max ，（j=2，m），则初始指派即为所求指派，问题解决，结束。否则
6、，进入下一步。2）若 max ，（j=2，m），则将和的括号去掉，并给对应的和加（）。返回第二步，重新检验，直到结束为止。3）若通过检验条件1），确定了指派问题的解，此时如果所有加（）的元素中存在这样两个处于对角线位置的元素，其和与另一侧对角线上的两个元素之和相等，则可以去掉这两个加（）元素的（），并给另一侧对角线上的两个元素加（），所得的新指派也是原指派问题的解。另外，第二步中的3）是检验指派问题存在重解的一种情况。当条件满足时，所求指派问题一定存在重解，且按照3）的方法即可求得一个重解，但当条件不满足时，所求指派问题也有可能存在重解。3.论述求解历时最短的指派问题，实质就是要解决两个问题：
7、（1）在n阶系数矩阵中确定n个独立元素；（2）保证所确定的指派中的的n个独立元素之和是所有情况中最小的。（这里的独立元素是指系数矩阵中既非同行也非同列的元素）下面我们来逐一分析一下上述矩阵解法的步骤：第一步是利用最小-最大元素法给出初始指派的过程，最小-最大元素法虽然不能保证所选初始指派中的元素之和最小，但却可以保证接近最小，这就在一定程度上减少了计算步骤，简化了求解过程。通过对步骤3）的反复操作，保证了二维关系中一对一的关系，即：保证了所给出的初始指派中的元素为独立元素；第二步是检验初始指派的过程，其目的是在保证初始指派中的元素为独立元素的基础上，寻求其元素之和为最小的情况。当确定了指派问题
8、的解后，如果存在上述步骤3）中的情况，说明该指派问题一定存在重解，通过步骤3）的操作，既保证了不改变所有加（）元素的独立性，又保证了新的指派所用时间或效率与原指派相同，因此新指派也是原指派问题的解。4.例子例1.现有一份中文资料需译成英、日、德、俄4种文字，今让甲、乙、丙、丁4人同时去完成，每人译且仅译一种文字。他们对这四种语言皆精通，但个人专长不同，因此翻译同一种语言所用时间有别，具体情况如表1所示，试问如果四人同时开始翻译，应如何安排工作可使翻译历时最短1？表1 任务人员 译成英文译成日文译成德文译成俄文甲215134乙1041415丙9141613丁78119解：该指派问题的效率矩阵为：
9、A= （1）首先依据步骤一求初始指派如下：A= （2）依据步骤二检验初始指派如下：此时=11=，由于在二阶方阵、和中均满足检验条件1），问题解决，结束。即：甲译成俄文，乙译成日文，丙译成英文，丁译成德文。例2.求表2所示效率矩阵的指派问题的最小解1。表2 任务人员ABCDE甲127979乙89666丙71712149丁15146610戊4107109 解：该指派问题的效率矩阵为：A= (1)首先依据步骤一求初始指派如下：A= (2) 依据步骤二检验初始指派如下：此时= 9=，由于在二阶方阵、和中均满足检验条件1），问题解决，结束。观察可见有，可改为，即：存在重解，且可知原指派问题的最优指派方案
10、为：甲B，乙C，丙E，丁D，戊A或甲B，乙D，丙E，丁C，戊A。5.结束语本文主要介绍了求解历时最短或效率最高的指派问题的一种新解法改进矩阵解法，给出了它的具体步骤，并论述了这种方法的正确性，最后用例子说明了它的简便可行性。它是一种较为简单、快捷的求解历时最短指派问题的方法，极大程度地简化了求解过程，而且步骤清晰，容易操作。为从事这类问题的研究提供了极大的方便，也为促进相关问题的发展奠定了基础。参考文献：1运筹学教材编写组.运筹学M.北京：清华大学出版社，2005.2吴振奎，王全文.运筹学M.北京：中国人民大学出版社，2006.3王延臣，王全文，吴振奎.一个特殊指派问题及其解法J.天津商学院学报，2007(06):26-27.4王全文，吴育华，吴振奎.整数规划的一个线性规划解法J.系统工程，2005(07):35-36.5吴振奎，王全文，刘振航.运筹学中的转化思想J.运筹与管理，2003(01):6-8.- 6 -
