匈牙利指派问题

1匈牙利指派主讲人：陈元安电话：[phone]E-mail:[e-mail]2一、指派问题的背景及意义数学建模是指根据需要针对实际问题组建数学模型的过程。也就是对某一实际问题，经过抽象、简化、明确变量和参数，并依据某种“规律”建立变量和参数间的一个明确的数学关系(即数学模型)，然后求解该数学问题的过程。数学模型的过程不仅要进行演绎推理而且还要对复杂的现实进行总结、归纳和提炼，这是一个归纳总结与演绎推理相结合的过程。3建模时．必须要对现实问题进行去粗取精、去伪存真、归纳、加工过程，但建模时究竟保留什么因素，忽略什么因素，并没有一定的范式，这要根据建模者对实际问题的理解、研究的目的及其数学背景来完成这个过程，应该说这是一个创造性的过程。而且不同的建模者针对同一实际问题完全可以得到不同的数学模型。4在现实生活中，经常会遇到把几个任务分派给不同的对象去完成，由于每个对象的条件不同，完成任务的效率和效益亦不同，指派问题的目标就是如何分派使所消耗的总资源最少(或总体效益最优)。最常见的应用有：给工人分派工作，给车辆分配道路，给工件分配机床等等。同时许多网络问题(如旅行问题、任务分配问题、运输问题等)都可以演化成指派问题来解决。利用数学建模思想，可以很好地解决指派问题，本次课通过例子，介绍指派问题的匈牙利解法的实际应用。5指派问题又称分配问题，其用途非常广泛，比如某公司指派n个人去做n件事，各人做不同的一件事，如何安排人员使得总费用最少？若考虑每个职工对工作的效率（任务有难易，人员素质有高低)（如熟练程度等），怎样安排会使总效率达到最大？这些都是一个企业经营管理者必须考虑的问题，所以该问题有重要的应用价值.6哪个人应该负责哪项工作？7虽然指派问题可以用0-1规划问题来解，设X(I,J)是0-1变量,用X(I,J)=1表示第I个人做第J件事,X(I,J)=0表示第I个人不做第J件事.设非负矩阵C（I，J）表示第I个人做第J件事的费用，但是由于有N^2个0-1变量,当N很大时，用完全枚举法解题几乎是不可能的.而已有的0-1规划都是用隐枚举法做的，计算量较大.对于指派问题这种特殊的0-1规划，有一个有效的方法——匈牙利算法，是1955年W.W.Kuhn利用匈牙利数学家D.König的二部图G的最大匹配的大小等于G的最小顶点覆盖的大小的定理提出的一种算法，这种算法是多项式算法，8匈牙利算法的基本原理是基于以下两个定理.定理1设C=(Cij)n×n是指派问题的效益矩阵，若将C中的任一行（或任一列）减去该行（或该列）中的最小元素，得到新的效率矩阵C’，则C’对应的新的指派问题与原指派问题有相同的最优解.定理2效率矩阵C中独立的0元素的最多个数等于覆盖所有0元素的最少直线数.当独立零元素的个数等于矩阵的阶数时就得到最优解.9设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。12…j…n12…i…n指派问题模型：jiijijxcZmin1.21inijiixxxxtsi=1,2,…,n121njijjjxxxxj=1,2,…,nnjnixij,,2,1;,,2,11,0解：第i个人做第j人件事Z表示总费用i=1,2,…,n;j=1,2,…,n第i个人不做第j人件事01ijxnnnjnninijiinjnjcccccccccccccccc21212222211112111、指派问题的数学模型10jiijijxcZminnnnnnnnnnnnnxcxcxcxcxcxcxcxcxc2211222222212111121211111.21inijiixxxxts121njijjjxxxxi=1,2,…,nj=1,2,…,n当n=4时，有16变量，8个约束方程111.21222221111211nnnjnnnjnjxxxxxxxxxxxxts11121222212112111nninnnninixxxxxxxxxxxx11例：现有4份工作，4个人应聘，由于各人技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一人承担，试求使总费用最小的分派方案。工作人1234123435456768898101010911解：ijx10第i人做第j件事Z表示总费用i=1,2,3,4;j=1,2,3,4第i人不做第j件事141312115453maxxxxxZ242322218676xxxx3433323110898xxxx444342411191010xxxx1.14131211xxxxts124232221xxxx134333231xxxx144434241xxxx141312111xxxx142322212xxxx143332313xxxx144342414xxxxnjnixij,,2,1,,2,11,0122、费用矩阵设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。12…j…n12…i…nnnnjnninijiinjnjcccccccccccccccc2121222221111211nnnnnncccccccccC212222111211取cij表示第i个人做第j件事的费用费用矩阵13例：现有4份工作，4个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总费用最小的分派方案。工作人1234123435456768898101010911费用矩阵11910101089886765453C0753193506650016532054321C设对应一个5个人5个工作的指派问题第2个人做第4个工作的费用5第4个人做第2个工作的费用014定理：在费用矩阵C=（cij）的任一行（列）中减去一个常数或加上一个常数不改变本问题的最优解。n个人n个工作的指派问题1nnnniniinnccccccccccccC21212222111211-bnnnniniinncccbcbcbcccccccC21212222111211iniicccb,,,min213、匈牙利法n个人n个工作的指派问题215Zminnnnnnnnnininiiiinnnnxcxcxcxcxcxcxcxcxcxcxcxc22112211222222212111121211111.21inijiixxxxts121njijjjxxxxnjnixij,,2,1;,,2,11,0i=1,2,…,nj=1,2,…,nZminnnnnnnnnininiiiinnnnxcxcxcxbcxbcxbcxcxcxcxcxcxc2211221122222221211112121111)()()(nnnniniinnccccccccccccC21212222111211nnnniniinncccbcbcbcccccccC212122221112111.21inijiixxxxts121njijjjxxxxnjnixij,,2,1;,,2,11,0i=1,2,…,nj=1,2,…,n-b16Zminnnnnnnnnininiiiinnnnxcxcxcxbcxbcxbcxcxcxcxcxcxc2211221122222221211112121111)()()()(212211221122222221211112121111iniinnnnnnnnininiiiinnnnxxxbxcxcxcxcxcxcxcxcxcxcxcxcbxcxcxcxcxcxcxcxcxcxcxcxcnnnnnnnnininiiiinnnn221122112222222121111212111117ZminZminnnnnnnnnininiiiinnnnxcxcxcxcxcxcxcxcxcxcxcxc2211221122222221211112121111bxcxcxcxcxcxcxcxcxcxcxcxcnnnnnnnnininiiiinnnn2211221122222221211112121111nnnniniinnccccccccccccC21212222111211nnnniniinncccbcbcbcccccccC21212222111211-b1.21inijiixxxxts121njijjjxxxxnjnixij,,2,1;,,2,11,0i=1,2,…,nj=1,2,…,n1.21inijiixxxxts121njijjjxxxxnjnixij,,2,1;,,2,11,0i=1,2,…,nj=1,2,…,nbZbZ18ZminZmin的最优解是若ZXmin0的最优解也是，则ZXmin0的最优值是若ZZmin0的最优值是，则若ZbZmin0任务：对C的行和列减去某个常数，将C化的尽可能简单，简单到可一眼看出该问题的最优解nnnniniinnccccccccccccC21212222111211nnnniniinncccbcbcbcccccccC21212222111211-bbZbZ19在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务（或所费时间）的效率也不同。于是产生应指派哪个人去完成哪项任务使完成n项任务的总效率最高（或所需总时间最小）。这类问题称为指派问题或分配问题（Assignmentproblem）。二．指派问题的数学模型20任务人员EJGR甲乙丙丁643575191191082842引例：有一份中文说明书，将译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如下表所示。问应指派何人去完成何工作，使所需总时间最少？先通过下面的引例了解指派问题的特征21类似有：有n项加工任务，怎样指派到n台机床上分别完成任务的问题；有n条航线，怎样指定n艘船去航行问题…等等，对应每个指派问题，