员工任务的指派方法.doc

《员工任务的指派方法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、员工任务的指派方法——匈牙利法各员工完成任务时间汇总表P96甲乙丙丁戊A10591811B131961214C32445D189121715E116141910下面的方法是最准确的方法，其中画“盖0线”是难点，稍复杂点，但看懂后，再自己做两道题就会应用的非常熟练。若有看不懂的，可联系我。红色部分为考试时写在卷面上的步骤，其他的是自己在草稿纸上算的。1.以时间构造矩阵矩阵一：10591811131961214324451891217151161419102.对行约减：减去本行中的最小数矩阵二：504136713068

2、10223903865081343.A.若矩阵各行各列均有“0”，则跳过此步B.否则，继续约减：此时，每行已有“0”，则对每列进行约减本题属于第二种情况，再对每列进行约减矩阵三：40411361304500200803634081114.画“盖0线”，用最少的线将矩阵（3）中的“0”全部覆盖（这是匈牙利法中最难的部分)方法如下：找出独立的0元素，即每一行或每一列中只有一个0的0元素A.对矩阵三中每一行中只含有一个0的画上*，同时将画*的0所在列的其他0画#，从第一行找起，然后第二行，第三行，第四行B.每一行找完后，

3、若还有0未标示“*”“#”，则再从列中寻找，方法同AC.所有0标记完毕后，有几个独立0元素（标为*的0），则说明有几条“盖0线”矩阵四64*4113613*45*#2##8#3634#8111详细过程：第一行有一个单独的0元素，标为*，同时该0所在的第二列中其他0标为#；然后看第二行，也有一个独立0元素，标为*，该0所在第三列中没有其他0；继续第三行，第三行有4个0，则先跳过；看第四行，有一个0，但已被划掉，所以没有独立0元素；第五行同第四行则第三行中的0还没有处理，接下来再看列；第一列中有一个独立0元素，标为*，

4、该0所在行中的其他0标为#；此时，所有0均已标记完毕，有三个标为*的0，则说明有最少的“盖0线”3条5.如何画“盖0线”：（1）将非独立0元素（画#的0）所在的行打√——即矩阵四中的第四行和第五行打√（2）看打√行中的0所在的列是否有独立0元素（标*的0），若有，则在独立0元素所在列打√——第四行和第五行中的0所在第二列中有独立0元素，则第二列打√（3）将打√的列中的独立0元素所在的行打√——即第二列中独立0元素所在的第一行打√（4）将未打√的行画“盖0线”，打√的列画“盖0线”——即第二行和第三行划“盖0线”，第

5、二列画“盖0线”4*4113√613*45*#2##8#363√4#8111√√4*4113613*45*#2##8#3634#8111矩阵五40411361304500200803634081116.A.若盖“0”线=矩阵维数，则跳到第（7）步B.若盖“0”线<矩阵维数，则进行数据转换：6（1）找出未被“盖0线”覆盖的数中最小值（2）将未被“盖0线”覆盖住的数减去（3）将“盖0线”交叉点的数加上本题属于后者，=13031023*3102√303102614045614*4561404501200*12##0120

6、0702527#252√702523071003#710*307100√=2（下面的运算得出4个独立0数，说明还要继续变换数据）101801*18#√10180616045616*45√61604503200*32##03200500305##3#√5003032710032710*√327100√√√=100170*#17#516035516*3504301#43*1400204*#2#227902279*由上面得知有五个独立0数，等于矩阵维数，所以接下来求最优解，随意画五条覆盖0的“盖0线”（7）求最优解A.先

7、找出只含有一个“0”的行（或列），将该行（或列）中的“0”打“√”B.将带“√”的“0”所在列（或行）中的“0”打“×”C.重复（1）（2）步至结束，若所有行列均含有多个“0”，则从“0”数目最少的列或行中任选一个“0”打“√”00170√×17×516035516√3504301×43√1400204√×2×227902279√(注：考试的时候将上面√和×的0补上，这里不好画，所以直接用的√和×）所以，A任务由甲担任，B任务由丙担任，C任务由丁担任，D任务由乙担任，E任务由戊担任。二、匈牙利方法的推广1.当员工数

8、目>任务数目时6增添虚任务，使二者数目一致，增添的虚任务的工作时间、利润为“0”由于上面有详细的讲解和过程，此处只列计算过程，不再写详细甲乙丙丁戊A10591811B131961214C32445D116141910（1）构造时间矩阵(2)对行约减：减去本行中的最小数1059181150413613196121471306832445102231161419