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

　　摘 要： 本文介绍了求历时最短的指派问题，给出了改进矩阵解法的求解步骤，论述了这种解法的合理性，最后举例说明了这种解法的方便可行性。
　　关键词： 指派问题 改进矩阵解法 整数规划 效率矩阵
　　
　　1.引言
　　我们经常遇到这样的问题：某单位需要完成某n项任务，恰好有n个人可承担这些任务。由于每个人的专长不同，每个人完成某项任务的效率也不同，于是产生了应指派哪个人去完成哪项任务，才能使完成这n项任务的总效率最高，或者说是所用总时间最短的问题，这类问题被称为指派问题或分派问题［１—２］。根据这类指派问题的特点，我们可以用匈牙利法等方法求解，但其过程非常复杂，容易出现错误。以下介绍一种求解这类指派问题的较为简便的方法——改进矩阵解法。
　　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）保证所确定的指派中的的n个独立元素之和是所有情况中最小的。（这里的独立元素是指系数矩阵中既非同行又非同列的元素）
　　下面我们来逐一分析上述矩阵解法的步骤。
　　第一步是利用最小—最大元素法给出初始指派的过程，最小—最大元素法虽然不能保证所选初始指派中的元素之和最小，却可以保证接近最小，这就在一定程度上减少了计算步骤，简化了求解过程。通过对步骤3）的反复操作，保证了二维关系中一对一的关系，即：保证了所给出的初始指派中的元素为独立元素。
　　第二步是检验初始指派的过程，其目的是在保证初始指派中的元素为独立元素的基础上，寻求其元素之和为最小的情况。当确定了指派问题的解后，如果存在上述步骤3）中的情况，就说明该指派问题一定存在重解，通过步骤3）的操作，既保证了不改变所有加（）元素的独立性，又保证了新的指派所用时间或效率与原指派相同，因此新指派也是原指派问题的解。
　　4.例子
　　例1.现有一份中文资料需译成英、日、德、俄4种文字，今让甲、乙、丙、丁4人同时去完成，每人译且仅译一种文字。他们对这四种语言皆精通，但个人专长不同，因此翻译同一种语言所用时间有别，具体情况如表1所示，试问如果四人同时开始翻译，应如何安排工作可使翻译历时最短［１］？
　　表1
　　解：该指派问题的效率矩阵为：
　　A= 2 1513 410 4 1415 9 141613 7 8 11 9
　　（1）依据步骤一求初始指派如下：
　　A=［2］ 15 13 ［4］10 ［4］ 14 15 9 14 16 13 7 8 ［11］ 9→ 215 13 41041415 914 1613 7 8 （11）9→［2］ 15 13 ［4］10［4］14 15 9 14 16 13 7 8 （11）9→ 215 13410（4）14 15 914 16 13 7 8（11）9→［2］15 13 ［4］10 （4）1415 9 14 1613 78 （11）9→ 2 15 13 （4）10（4） 14 15 9 14 16 13 7 8 （11）9→215 13 （4）10 （4）1415（9）14 16137 8（11） 9
　　（2）依据步骤二检验初始指派如下：
　　此时θ=11=a，由于在二阶方阵13（4）（11）9、（4）148（11）和（9）167（11）中均满足检验条件1），问题解决，结束。即：甲→译成俄文，乙→译成日文，丙→译成英文，丁→译成德文。
　　例2.求表2所示效率矩阵的指派问题的最小解［１］。
　　表2解：该指派问题的效率矩阵为：
　　A=12 7 9 7 9 8 9 6 6 6 7 171214 91514 6 6 10 4 10 7 10 9
　　（1）依据步骤一求初始指派如下：
　　A=12［7］ 97 9 89 ［6］ ［6］ ［6］ 7 17 1214915 14 6 610［4］ 10 7 109→12（7）9 7 9 8 96 6 6 7 17 12 14915146 610 4 107109→12（7） 97 9 89 ［6］［6］［6］ 7 17 12 14 915 14 6 610［4］ 10 7109→12（7）9 79 8 96 66 71712 14 915 14（6）6 10 410 710 9→12（7） 97 9 89 （6） 6 6 7 17 12 14 ［9］15 14 6 ［6］ 10［4］ 10 7109→12（7） 979 8 9 （6） 6 6 717 12 14（9）15 146 610 4107109→12 （7） 9 79 8 9 （6）66 71712 14（9）15 14 6 ［6］ 10［4］10 7 10 9→12（7） 97 9 8 9 （6）6 6 717 12 14 （9）15 146（6）10 4107 109→12（7）9 79 89（6）66 7 171214（9）15 14 6（6）10（4） 10 7 10 9
　　（2）依据步骤二检验初始指派如下：
　　此时θ=9=a，由于在二阶方阵（6）612（9）、14 （9）（6）10、7（9）（4）9和（7）917（9）中均满足检验条件1），问题解决，结束。观察可见有（6）66（6），可改为6（6）（6）6，即：存在重解，且可知原指派问题的最优指派方案为：甲→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.