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

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

立元素是指系数矩阵中既非同行又非同列的元素）下面我们来逐一分析上述矩阵解法的步骤。第一步是利用最小―最大元素法给出初始指派的过程，最小―最大元素法虽然不能保证所选初始指派中的元素之和最小以证接近最小在定程度上减少了计算步骤，简化了求解过程。通过对步骤3的反复操作，保证了二维关系中一对一的关系，即：保证了所给出的初始指派中的元素为独立元素。第二步是检验初始指派的过程的是在保证初始指派中的元素为独立元素的基础上，寻求其元素之和为最小的情况确定了指派问题的解后果存在上述步骤3中的情况，就说明该指派问题一定存在重解，通过步骤）的操作，既保证了不改变所有加（）元素的独立性证新的指派所用时间或效率与原指派相同指也是原指派问题的解。4.例子例1.现有一份中文资料需译成、日、德、俄文字，今让甲、乙、丙、丁4人时去完成，每人译且仅译一种文字。他们对这四种语言皆精通，但个人专长不同，因此翻译同一种语言所用时间有别，具体情况如表1所示试问如果四人同时开始翻译，应如何安排工作可使翻译历时最短［１］？表1解：该指派问题的效率矩阵为：a=21513410491416138119（）据步骤一求初始指派如下：a=［2］1513［4］10［］1415141613711→21541041415914161378（11）→［2］1513［］10［］15916137（）→21513410（）1591416137（）→［］15134］10（）141591478（）9→1513（）10（）141591416138（11→21513（）10（）1415（）16137（11）9（）据步骤二检验初始指派如下：此时=11=a，由于在二阶方阵13（））（）9）（11）中均满足检验条件1题解决，结束。即：甲→译成俄文，乙→译成日文，丙→译成英文，丁→译成德文。例2.求表2所效率矩阵的指派问题的最小解［１表2解：该指派问题的效率矩阵：a=1279798966671712149151461047109（）据步骤一求初始指派如下：a=12［7］97989［］［］［6］7171214915146610［4］107109→（）7989667171214915146610412797989［］7171214915146［］10710912（797989666717129156104107109→12（）97989（）67171214［］15146［］［］107109→12（）97989（）667171214915146→（7）9798（6）6671712（）146［］104］1010（）97989（）67171214（）146（）104107109→（）979896）171214（）146（）10（）107109（）据步骤二检验初始指派如下：此时=9=a由于在二阶方阵6612（（10（9917（）均满足检验条件1题决，结束。观察可见有）66（改6（）6，：存在重解，且可知原指问题的最优指派方案为：甲，乙c，丙e，丁d，戊

→或→，乙→，→，→，戊。5.结语本文主要介绍了求解历时最短或效率最高的指派问题的一