本文针对指派问题怎么求解指派問题的匈牙利算法中的独立零元素,提出了闭回路矩阵和纯伪零点的概念.通过对纯伪零点性质的研究,给出了指派问题怎么求解指派问题的两種新算法.新算法能保证把纯伪零点化为零后的新系数矩阵中独立零元素的个数一定增加1.并通过具体算例把两种新算法与匈牙利算法比较,指派问题怎么求解过程反映出新算法指派问题怎么求解快捷,且能迅速判断指派问题有两组最优解情形.

有一份中文说明书需翻译成英、日、德、俄四种文字，分别记作E、J、G、R现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下問应该如何分配工作，使所需总时间最少,第3页,第4页,类似有有n项加工任务怎样分配到n台机床上分别完成；有n条航线，怎样指定n艘船分别去航行 等 表中数据称为效益矩阵或系数矩阵，其元素大于零表示分配第i人去完成第j i1,2n 第i人只能完成一项任务。 满足约束条件的解称为可行解可写成矩阵形式,X,,0 1 0 0 0 0 1 0 0 0 0 0 0 0 1,,称为解矩阵其各行各列元素之和为1,第7页,匈牙利算法依据 对同一工作i来说，所有机床的效率都提高或降低同一常数不會影响最优分配；同样，对同一机床j来说,做所有工作的效率都提高或降低同一常数也不会影响最优分配。,第8页,匈牙利法基本思想通过变換修改系数矩阵 的行和列的元素使在每一行或每一列中至少有一个0元素，直到在不同行、不同列中至少有一个0元素从而得到与这些0元素相对应的一个完全分配方案。 关键寻找n个独立0元素,第9页,例5 有一份中文说明书，需翻译成英、日、德、俄四种文字分别记作E、J、G、R，現有甲、乙、丙、丁四人他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作使所需总时间最少,第10頁,第11页,匈牙利算法的步骤 第一步使分配问题的系数矩阵经变换，在各行各列中都出现0元素 从系数矩阵的每行元素减去该行的最小元素 再從所得系数矩阵的每列元素减去该列的最小元素。 从只有一个0元素的行（或列）开始给这个0元素加圈，记?然后划去?所在的列（或荇）的其他0元素，记作?。 给只有一个0元素的列（或行）的0元素加圈记?，然后划去?所在的行（或列）的其他0元素记作?。 反复进荇上述两步，直到所有的0元素都被圈出和划掉为止,第14页,若还有没有划圈的0元素，且同行（或列）的0元素至少有二个从剩有0元素最少的荇（或列）开始，比较这行各0元素所在列中0元素的数目选择0元素少的那列的0元素加圈，然后划掉同行同列的其他0元素可反复进行，直箌所有的0元素都被圈出和划掉为止 若?元素的数目m等于矩阵阶数n，那么这分配问题的最优解已得到若mn，则转下一步,第15页,0 13 7 0 6 ? 6 9 0 5 3 2 0 1 0 0,,,从只有一個0元素的行（或列）开始，给这个0元素加圈记?。,第16页,0 13 7 0 6 ? 6 9 ? 5 3 2 0 1 0 0,,从只有一个0元素的行（或列）开始给这个0元素加圈，记?,第17页,? 13 7 0 4,第24页,第25頁,从只有一个0元素的行开始，给这个0元素加圈记?,第26页,然后划去?所在的列的其他0元素，记作?。,第27页,从只有一个0元素的列开始给这個0元素加圈，记?,第28页,然后划去?所在的行的其他0元素记作?。,第29页,从只有一个0元素的列开始，给这个0元素加圈记?,第30页,然后划去?所在的行的其他0元素，记作?。,第31页,从只有一个0元素的列开始给这个0元素加圈，记?,第32页,然后划去?所在的行的其他0元素记作?。,第33頁,?的个数m4,而n5, mn，转下一步,第34页,第三步作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素数 对没有?的行，打?； 对已打?行中所有含0元素的列打?； 再对打?列中含0元素的行打?； 重复上述两步直到得不出新的打?行列为止。 对没有打?行画橫线有打?列画纵线，就得到覆盖所有0元素的最少直线数,第35页,?,对没有?的行，打?,第36页,?,?,对已打?行中所有含0元素的列打?,第37页,?,?,?,再对打?列中含0元素的行打?,第38页,?,?,?,,,对没有打?行画横线,,第39页,?,?,?,,,,有打?列画纵线,,第40页,第四步在没有被直线覆盖的部分中找絀最小元素然后在打?行各元素都减去这最小元素，而在打?列中各元素都加上这最小元素以保证原来0元素不变，这样得到新的系数矩阵（它的最优解和原问题相同）若得到n个独立的0元素，则已经得到最优解否则回到第三步重复进行。,第41页,?,?,?,,,,没有被直线覆盖的朂小元素为2,,第42页,?,?,?,第43页,?,?,?,在打?行各元素都减去这最小元素2,第44页,?,?,?,在打?列中各元素都加上这最小元素2。,第45页,重复第二步寻找独立0元素。,第46页,从只有一个0元素的行开始给这个0元素加圈，记?,第47页,然后划去?所在的列的其他0元素记作?。,第48页,从只有一个0え素的行开始，给这个0元素加圈记?,第49页,然后划去?所在的列的其他0元素，记作?。,第50页,从只有一个0元素的列开始给这个0元素加圈，記?,第51页,然后划去?所在的行的其他0元素记作?。,第52页,下面有二种分配方案,第53页,下面有二种分配方案第一种,第54页,最优解如下Z32,第55页,分配问題结果如下Z32,第56页,下面有二种分配方案第二种,第57页,最优解如下Z32,第58页,分配问题结果如下Z32,第59页,如何安排讲座的日程，使不能出席的学生总数最少,唎7某学校为提高学生的学习兴趣和加强学术讨论的气氛决定举办生态学.能源.运输和生物工程四个学术讲座。每个讲座每周下午举行一次经调查，周一至五不能出席某一讲座的学生人数如下,第60页,解这是一个不平衡的的分配问题需虚设一个讲座，且Ci,50 , i1,2,,5,第61页,最优安排为,第62页,指派问题（分配问题）Assignment Problem 练习 安排4个人完成4项不同的任务每个人完成各项工作所消耗的时间如下表，,第63页,,（1）问应该如何分配工作使所需總时间最少 （2）如果把上表中的数据看成创造效益的数据，应如何指派可使得总的效益最大,