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