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