文档介绍：第1页匈牙利法求解指派问题第2页指派问题(分配问题)(AssignmentProblem)例5有一份中文说明书,需翻译成英、日、德、俄四种文字,分别记作E、J、G、R,现有甲、乙、丙、丁四人,他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下,问应该如何分配工作,使所需总时间最少?第3页任务人员EJGR甲215134乙1041415丙9141613丁78119第4页类似有:有n项加工任务,怎样分配到n台机床上分别完成;有n条航线,怎样指定n艘船分别去航行…..等。表中数据称为效益矩阵或系数矩阵,其元素大于零,表示分配第i人去完成第j项任务时的效益(或时间、成本等)。第5页引入0-1变量xij=1分配第i人去完成第j项任务,xij=0不分配第i人去完成第j项任务。分配问题的数学模型:MinZ=.xij=1(j=1,2……n)xij=1(i=1,2……n)xij0或1(i=1,2…..n;j=1,2……n)第6页xij=1(j=1,2……n)表示第j项任务只能由一人去完成。xij=1(i=1,2……n)第i人只能完成一项任务。满足约束条件的解称为可行解可写成矩阵形式:X=010000100000001称为解矩阵其各行各列元素之和为1。第7页匈牙利算法依据:对同一工作i来说,所有机床的效率都提高或降低同一常数,不会影响最优分配;同样,对同一机床j来说,做所有工作的效率都提高或降低同一常数,也不会影响最优分配。第8页匈牙利法基本思想:通过变换修改系数矩阵的行和列的元素,使在每一行或每一列中至少有一个0元素,直到在不同行、不同列中至少有一个0元素,从而得到与这些0元素相对应的一个完全分配方案。关键:寻找n个独立0元素。第9页例5有一份中文说明书,需翻译成英、日、德、俄四种文字,分别记作E、J、G、R,现有甲、乙、丙、丁四人,他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下,问应该如何分配工作,使所需总时间最少?第10页任务人员EJGR甲215134乙1041415丙9141613丁78119