4.2-分配问题和匈牙利法.ppt

整数规划,整数规划的数学模型设置逻辑变量建立整数规划模型分配问题与匈牙利法分支定界法、割平面法应用举例,分配问题的标准形式及其数学模型分配问题也称指派问题(assignmentproblem),在我们现实生活中,常有各种性质的分配问题.例如：应如何分配若干项工作给若干个人(或部门)来完成,以达到总体的最佳效果等等.由于分配问题的多样性,我们有必要定义分配问题的标准形式.匈牙利解法一般的分配问题,3分配问题与匈牙利法,分配问题的标准形式及其数学模型,分配问题的标准形式（以人和任务为例）假定有n项任务分配给n个人去完成,并指定每人完成其中一项,每项只交给其中一人去完成,设第i人完成第j项任务费用为Cij(i,j=1,2,n),应如何分配使总费用最少。,因此,我们可得分配问题的系数矩阵,效率矩阵,分配问题的标准形式及其数学模型,为了建立标准分配问题的数学模型,我们引入n个01变量,并且得到该问题的数学模型.,例1.四个外语学院学生组成翻译公司,接到一项业务:把一个产品说明书翻译成A、B、C、D四种语言,应指派何人做何种工作,能使总的时间最少？,分配问题的标准形式及其数学模型,需时(h),语种,学生,解:这是一个标准的分配问题.若设01变量,分配问题的标准形式及其数学模型,可用表上作业法求解,匈牙利法,匈牙利法的基本思想如果效率矩阵C中存在n个位于不同行不同列的零元素,则只要令对应于这些零元素位置的决策变量xij=1,其余的决策变量xij=0,则可取到最小值0,即该分配方案最优.如：,匈牙利法,匈牙利法的计算步骤第一步:找出效率矩阵每行的最小元素,并分别从每行中减去;如例1中效率矩阵为,u1=4u2=7u3=5u4=9,定理1如果从分配问题效率矩阵C每一行元素中分别减去(或加上)常数ui,从每一列分别减去(或加上)常数vj,得到新的效率矩阵C,C与C具有相同的最优解.,匈牙利法,匈牙利法的计算步骤第二步:找出效率矩阵每列的最小元素,再分别从每列中减去;接上,例1中效率矩阵转换为,C与C具有相同的最优解,v1=4v2=0v3=0v4=0,匈牙利法,匈牙利法的计算步骤第三步:确定能否找出n个位于不同行不同列的零元素集合来.根据定理2,该问题转化为:要覆盖上面矩阵中的所有零元素,至少需要多少条直线;怎么得到覆盖零元素的最少直线数？从第一行开始,若该行只有一个零元素,就对这个零元素打上()号,将打()号零元素所在列画一条直线.若该行没有零元素或有两个以上零元素(已划去的不计在内),则转下一行,依次进行到最后一行;从第一列开始,若该列只有一个零元素就对这个零元素打上()号(同样不考虑已划去的零元素),再对打()号零元素所在行画一条直线.若该列没有零元素或有两个以上零元素,则转下一列,依次进行到最后一列;重复1和2两个步骤,可能出现三种情况：,定理2若矩阵A的元素可分成“0”和非“0”两部分,则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素的最大个数.,匈牙利法,第一种情况覆盖零元素的最少直线数(或打()号的零元素个数)等于n,Z=4+11+5+9=29h,匈牙利法,第二种情况打()号的零元素个数小于n,但未被划去的零元素之间存在闭回路,这时可顺着闭回路的走向,对每个间隔的零元素打一()号,然后对所有打()号的零元素,或所在行,或所在列画一条直线.,此问题有多个最优解,匈牙利法,第三种情况矩阵中所有零元素或被划去,或打上()号,但打()号的零元素个数仍小于n.,匈牙利法,匈牙利法的计算步骤第四步:为设法使每一行都有一个打()号零元素,需继续按定理1对矩阵进行变换：从矩阵未被直线覆盖的数字中找出一个最小的数k;对矩阵的每行,当该行有直线覆盖时,令ui=0,无直线覆盖时,令ui=k;每行元素减去ui；对矩阵中有直线覆盖的列,令vj=-k,对无直线覆盖的列,令vj=0;每列元素减去vj；得到一个新矩阵；第五步:回到第三步,反复进行,一直到矩阵的每一行都有一个打()号零元素为止,即找到了最优分配方案.,匈牙利法,上述例子完成一、二、三步之后如右：转向第四步：回到第三步：,k=2,u1=2u2=2u3=0u4=2,v1=-2v2=-2v3=0v4=0,匈牙利法,匈牙利法,第四步：,最优解所对应的最小值Z=3+2+4+3+9=21.,一般分配问题,1、人数和工作任务不相等的分配问题(不平衡的分配问题)（1）人少任务多（2）人多任务少类似产销不平衡问题(虚设假想的人,增添假想任务)2、某项任务一定不能由某人做的分配问题将相应的费用系数取作足够大的数M3、一个人可做几项任务的分配问题4、目标函数为求最大值(最大化的分配问题)效率矩阵中元素全为负数,根据定理1,让效率矩阵中所有元素变成非负数,再利用匈牙利法求解.,例1.已知下列五名运动员各种姿势的游泳成绩(各为50m)如下表.试问如何从中选拔一个450m混合泳的接力队,使预期的比赛成绩为最好？,需时(s),队员,项目,不平衡的分配问题,解:非标准的分配问题,先转化成标准分配问题.,一般分配问题,需时(s),队员,项目,不平衡的分配问题,不平衡的分配问题,不平衡的分配问题,某任务一定不能由某人做的分配问题,例2.分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务。每个人完成各项任务的时间如表所示。由于任务数多于人数，考虑任务E必须完成，其它4项可任选3项完成。试确定最优分配方案，使完成任务的总时间最少。,某任务一定不能由某人做的分配问题,解：1)这是不平衡的分配问题，首先转换为标准型，再用匈牙利法求解。2)由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作E必须完成，故设戊完成E的时间为M(M是非常大的数)，其余效率系数为0，则标准型效率矩阵表为：,某任务一定不能由某人做的分配问题,解续：用匈牙利法求出最优分配方案为：即甲-B，乙-D，丙-E，丁-A，任务C放弃，最少时间为105h。,一个人可做几项任务的分配问题,若某人可同时做几项任务,则将该人化作相同的几个“人”来接受分配,且费用系数取值相同.例如：丙可以同时任职A和C工作，求最优分配方案。,一个人可做几项任务的分配问题,例2.分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务。每个人完成各项任务的时间如表所示。由于任务数多于人数，考虑其中一人完成两项，其他每人完成一项。试确定最优分配方案，使完成任务的总时间最少。,一个人可做几项任务的分配问题,解：虚拟戊，它完成任务的效率由每列最小效率构成，则标准型效率矩阵表为：,例2续,分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务。每个人呢完成各项任务的