多目标广义指派问题的模糊匈牙利算法求解

摘要在企业、公司的运营与管理中，管理者总是希望把人员最佳分派以发挥其最大工作效率，从而降低成本、提高效益。

然而，如果没有科学的方法是很难实现优化管理的，由此我们引入了指派问题。

指派问题多是求项目的工时最少，而很多情况下人们并不关心项目总工时的多少，而只关心项目能否在最短的时间内完成，即历时最少的指派问题。

这类问题研究的是n个人执行n项任务，执行每项任务的人数以及总的指派人项数均有限制，要求最优指派。

在运筹学中求解整数规划的指派问题通常是通过匈牙利算法来求解，但指派问题也可以归结为一个0-1整数规划问题，本文先对指派问题进行陈述，引出对实际问题的求解。

在指派问题的背景、描述中充分理解该问题，先运用匈牙利算法实现指派问题，然后再建立一个0-1整数规划模型，并运用matlab和lingo编译程序对问题进行编译，运用软件解决模型问题，最终实现指派问题在实际问题中的运用。

通过运用匈牙利算法和0-1整数规划同时对指派问题求解，我们发现用0-1整数规划的方法来求解可以更简单，也更方便程序的阅读和理解。

与此同时，我们还对0-1整数规划问题由整数数据深入研究到小数数据。

最后通过实例来说明运用matlab，lingo编译程序来解决整数规划问题的简便和有效性。

关键词：指派问题；匈牙利算法；0-1整数规划；matlab模型；lingo模型AbstractIn business, the company's operations and management, managers always want the best distribution of the staff to maximize their efficiency, reduce costs and improve efficiency. However, if there is no scientific method is difficult to achieve optimal management, which we introduced the assignment problem. Multi-assignment problem is to get the project working hours at least, and in many cases people do not care about how much the total project work, but only care about whether the project can be completed within the shortest possible time, that lasted for at least the assignment problem. Such problems is the n individual execution of tasks n, the number of people to perform each task and assign the total number of items are restricted to two people, requiring the optimal assignment. Integer programming in operations research for solving the assignment problem is usually solved by Hungarian algorithm, but the assignment problem can be reduced to a 0-1 integer programming problem, this paper first to make a statement on the assignment problem, leads to the solution of practical problems. Assignment problem in the background to fully understand the problem description, the first assignment problem using Hungarian algorithm, and then a 0-1 integer programming model and compiler using matlab and the lingo of the problem to be compiled using the software solution model problem Ultimately in the assignment of the application in practical problems. By using the Hungarian algorithm and the 0-1 integer programming to solve assignment problems simultaneously, we found that 0-1 integer programming method to solve a more simple and easier to read and understand the program. At the same time, we also 0-1 integer programming problem in-depth study by the integer data to a decimal data. Finally, an example to illustrate the use of matlab, lingo compiler to solve the integer programming problem is simple and effective.Keywords:assignment problem; Hungarian algorithm; 0-1 integer programming;matlab model; lingo model目录1. 问题陈述 (1)2. 指派问题的背景 (1)3. 指派问题的描述 (1)3.1 指派问题的一般形式 (1)3.2 问题的数学模型一般形式 (2)3.3 目标函数极大化的指派问题 (2)4．指派问题实现 (3)4.1 匈牙利算法 (3)4.1.1 匈牙利算法的理论基础 (3)4.1.2 匈牙利算法的实现步骤 (3)4.1.3 匈牙利算法实现指派问题 (4)4.2 0-1整数规划 (5)4.2.1 模型假设 (6)4.2.2 模型建立 (6)4.2.3 模型求解 (7)5. 问题的深入（0-1整数规划） (10)5.1 模型建立 (10)5.2 模型求解 (11)5.2.1 用matlab求解问题 (11)5.2.2 用lingo求解问题 (12)6. 结论 (14)6.1 总结概论 (14)6.2 具体分工.................................. 错误！未定义书签。

匈牙利算法是一种求解指派问题的算法，其步骤如下：对指派问题的系数矩阵进行变换，使每行每列至少有一个元素为“0”。

具体做法是让系数矩阵的每行元素去减去该行的最小元素，再让系数矩阵的每列元素减去该列的最小元素。

从第一行开始，若该行只有一个零元素，就对这个零元素加括号，对加括号的零元素所在的列画一条线覆盖该列。

若该行没有零元素或者有两个以上零元素（已划去的不算在内），则转下一行，依次进行到最后一行。

从第一列开始，若该列只有一个零元素。

就对这个零元素加括号（同样不、考虑已划去的零元素）。

再对加括号的零元素所在行画一条直线覆盖该列。

若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列为止。

重复上述步骤（1）和（2）可能出现3种情况：（5）按定理进行如下变换：①从矩阵未被直线覆盖的数字中找出一个最小的k；②当矩阵中的第i行有直线覆盖时，令；无直线覆盖时。

3.2 求解指派问题的匈牙利算法由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig 提出的更为简便的解法—匈牙利算法。

算法主要依据以下事实：如果系数矩阵)(ij c C =一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵)(ij b B = ，则以C 或B 为系数矩阵的指派问题具有相同的最优指派。

利用上述性质，可将原系数阵C 变换为含零元素较多的新系数阵B ，而最优解不变。

若能在B 中找出n 个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为零，则所得该解是以B 为系数阵的指派问题的最优解，从而也是原问题的最优解。

由C 到B 的转换可通过先让矩阵C 的每行元素均减去其所在行的最小元素得矩阵D ，D 的每列元素再减去其所在列的最小元素得以实现。

下面通过一例子来说明该算法。

例7 求解指派问题，其系数矩阵为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=16221917171822241819211722191516C 解 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=06310157124074011B 再将第3列元素各减去1，得⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=****20531005711407301B 以2B 为系数矩阵的指派问题有最优指派⎪⎪⎭⎫ ⎝⎛43124321 由等价性，它也是例7的最优指派。

有时问题会稍复杂一些。

例8 求解系数矩阵C 的指派问题⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=61071041066141512141217766698979712C 解：先作等价变换如下∨∨∨⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡→⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡----- 2636040*08957510*00*0032202*056107104106614151214121776669897971246767 容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但5=n ，最优指派还无法看出。

指派问题的求解方法嘿，咱今儿就来聊聊指派问题的求解方法。

你说这指派问题啊，就好像是给一群小伙伴分任务，得让每个人都能分到最合适的事儿，这可不容易嘞！咱先来说说啥是指派问题。

就好比有一堆工作，有几个人可以去做，每个人对不同工作的效率或者效果不一样。

那咱就得想办法，怎么把这些工作分配给这些人，才能让总的效果达到最好呀。

那咋求解呢？有一种方法叫匈牙利算法。

这就好比是一把神奇的钥匙，能打开指派问题的大门。

咱就把那些工作和人当成一个个小格子，通过一些计算和摆弄，找到最合适的搭配。

你想想啊，如果随便分，那可能就浪费了某些人的特长，或者让一些工作没被最合适的人去做，那不就亏大啦？用了这个匈牙利算法，就能一点点地把最合适的工作和人配对起来。

就像你去拼图，得找到每一块的正确位置，才能拼成一幅完整漂亮的图。

这匈牙利算法就是帮咱找到那些正确位置的好帮手呀！它能让那些工作和人都找到自己的“最佳搭档”。

还有啊，咱在生活中也经常会遇到类似的指派问题呢。

比如说，家里要打扫卫生，每个人擅长打扫的地方不一样，那怎么分配任务才能又快又好地打扫完呢？这不就是个小小的指派问题嘛。

或者说在公司里，有几个项目要分给不同的团队，哪个团队最适合哪个项目，这也得好好琢磨琢磨，才能让项目都顺利完成，取得好成果呀。

总之呢，指派问题的求解方法可重要啦，就像我们走路需要一双好鞋一样。

掌握了这些方法，咱就能在面对各种指派问题的时候，不慌不忙，轻松应对，找到那个最优解。

你说是不是很厉害呀？所以啊，可别小瞧了这指派问题的求解方法哦，说不定啥时候就能派上大用场呢！。

匈牙利算法是解决二分图最大匹配问题的经典算法。

以下是匈牙利算法的步骤：
初始化：创建一个二分图，并将所有边的匹配状态初始化为未匹配。

选择一个未匹配的左侧顶点作为起始点，开始进行增广路径的寻找。

在增广路径的寻找过程中，首先选择一个未访问的左侧顶点作为当前路径的起点。

针对当前路径的起点，依次遍历与其相邻的右侧顶点。

对于每个右侧顶点，如果该顶点未被访问过，则标记为已访问，并判断该顶点是否已匹配。

如果该右侧顶点未匹配，则找到了一条增广路径，结束路径的寻找过程。

如果该右侧顶点已匹配，将其与之匹配的左侧顶点标记为已访问，并继续寻找与该左侧顶点相邻的右侧顶点，构建新的路径。

如果当前路径无法找到增广路径，则回溯到上一个路径的起点，并继续寻找其他路径。

当所有的路径都无法找到增广路径时，算法结束。

根据最终得到的匹配结果，即可得到二分图的最大匹配。

这些步骤描述了匈牙利算法的基本流程。

具体实现时，可以采用递归或迭代的方式来寻找增广路径，通过标记顶点的访问状态来进行路径的选择和回溯。

算法的时间复杂度为O(V*E)，其中V是顶点的数量，E是边的数量。

指派问题匈牙利算法最大值
匈牙利算法(匈牙利算法,也被称为“插入-删除算法”或“排序算法”)是一种整数排序算法,在指派问题中可以将一个整数数组按照一定规则排序,使得所有指派中最大的元素出现的位置都不相同。

以下是匈牙利算法在解决指派问题的最大值问题的步骤:
1. 将数组分为两个部分,左半部分尽可能地小,右半部分尽可能地大。

2. 从右半部分开始,将一个元素与它的指派对象的最大值进行
比较。

如果两个元素之间的指派关系不符合要求,就将它们交换位置。

3. 接下来,从左边半部分开始,将一个元素与它的指派对象的最大值进行比较。

如果两个元素之间的指派关系不符合要求,就将它们交换位置。

4. 重复步骤2和步骤3,直到左半部分的最大值与右半部分的最大值相等。

5. 在最右半部分找到最大的元素,将它与左半部分的最大值交换。

6. 重复步骤1到步骤5,直到数组中的所有元素都被排序。

匈牙利算法的时间复杂度为O(nlogn),其中n为数组的长度。

在实际应用中,该算法通常用于小规模数据的排序,对于大规模数据的
排序则需要使用更高效的算法。

多目标C-A指派问题的模糊差值法求解李敏【摘要】A multi-objective C-A assignment problem is proposed and discussed in this paper. Firstly, its multi-objective integer linear programming model is presented. Then, it is converted to a fuzzy C-A assignment problem by applying the fuzzy relationship synthetic matrix, and its optimal solution can be found through difference value method. Finally, a practical example is given to illustrate the method.%提出一类多目标的C-A指派问题，给出了它的多目标整数线性规划数学模型，运用模糊关系合成矩阵将其转化为模糊C-A指派问题，采用差值法求解。

最后给出一个应用实例。

【期刊名称】《湖北文理学院学报》【年(卷),期】2016(037)011【总页数】3页(P10-12)【关键词】多目标;C-A指派问题;模糊隶属度;差值法【作者】李敏【作者单位】湖北文理学院数学与计算机科学学院，湖北襄阳 441053【正文语种】中文【中图分类】O221.6标准指派问题的一般提法为:有n项工作要安排n个人去做，每个人只能安排一项工作，每一项工作只需要安排一个人.若已知第i个人做第j项工作的效率为cij(i,j=1,2,…,n),求使总效率最优的指派方案.解决这一问题的著名方法是匈牙利法[1].该问题是个单目标的决策问题，但在实际生活及各类管理决策过程中，决策者需要考虑的因素往往很多，如时间、效益、安全等等，因此面对的多是各类非标准形式[2]的或多目标[3-4]的指派问题.基于此,本文讨论了一类多目标的C-A指派问题，给出了它的多目标整数线性规划数学模型，运用模糊关系合成矩阵将其转化为模糊意义下的C-A指派问题[5]，并采用差值法求解，为决策者提供了可靠的科学依据.多目标C-A指派问题：从m个人中选择k(0<k<min{m,n})个人去做n项工作中的k项工作，要求一人只能做一件事且一件事只需要一个人完成.在选择中有l个需要考虑的目标，若在第t个目标下，记第i人做第j项工作的相应目标属性值为ctij(i=1,2,…,m;j=1,2,…,n;t=1,2,…,l)，试确定使各目标均最优的指派方案.它的数学模型为：其中对值越大越优的目标而言，max′表示取最大值 (max)；对值越小越优的目标而言，max′表示取最小值(min).2.1 多目标模糊关系合成矩阵由于在第t个目标下第i人做第j项工作的目标属性值为，因此可得相应于目标t的属性值矩阵，再由矩阵Ct计算出目标t下的各属性值对“优”的模糊相对隶属度，对目标值越小越优的用公式(1)计算，对目标值越大越优的用公式(2)计算[6].其中分别是矩阵中元素的最大和最小值.记(t=1,2,…,l)为属性值矩阵Ct在目标t下的关于“优”的模糊关系矩阵，再根据层次分析法或德尔斐法(Delphi)等方法来规定各目标的权向量w= (ω1,ω2,…,ωt).记bij为综合l个目标后的各属性值对“优”的合成相对隶属度，计算公式如下：则以bij为元素的m×n矩阵B称为多目标模糊关系合成矩阵.2.2 多目标C-A指派问题的模糊差值法在多目标模糊关系合成矩阵中B=(bij)m×n，若把bij看作是第i人做第j项工作的模糊综合效益，其值越大越优，可把B看作是多目标C-A指派问题的模糊效益矩阵，则原多目标C-A指派问题已被转化成一个模糊意义下目标函数求最大的C-A 指派问题，当然可用匈牙利法求解，但将其转换成标准指派问题后，其规模会变得很大，大大增加了计算难度.对此，由文献[3]可知，用差值法求解目标函数最小化的C-A指派问题非常方便，故先将多目标C-A指派问题转化为模糊意义下目标函数求最小的C-A指派问题，再用差值法求解.若记转化后的模糊效益矩阵为，其中为所有bij(i=1,2,…,m;j=1,2,…,n)中的最大值，其数学模型为：例已知某单位现要从5个人中选择3个人去完成4项工作中的某3项工作，已知每个人做不同工作的效益矩阵、时间矩阵、安全性矩阵分别为C1,C2,C3，请确定使得三个目标都最优的指派方案.解由于效益目标值和安全性目标值属于越大越优型，故它们的模糊相对隶属度选用公式 (2)计算，而时间目标值属于越小越优型，故它的模糊相对隶属度选用公式(1)计算，则得到三个目标下关于“优”的模糊关系矩阵，再取三个目标的权向量为,根据(3)式给出bij(i=1,2,…, m;j=1,2,…,n)，则可得模糊关系合成矩阵为：由于以矩阵B为模糊效益矩阵的指派问题是最大化问题,因此必须将B转化为B′,再按差值法求解，得解矩阵X=(xij)5×4.从求解矩阵可以看出，选择后3个人去做后3项工作，虽然不是使得3个目标各自单独考虑时都达到最优的指派方案，但从C1,C2,C3数据来看，要同时平衡这3个目标，该指派方案是完全合理的.本文根据管理决策的实际需要,提出了一类多目标C-A指派问题,运用模糊关系合成矩阵将其转化成模糊C-A指派问题,并用差值法来求解.算例表明该转化及求解方法巧妙、简便有效，能够为决策者提供可靠的决策依据.【相关文献】[1]李敏.运筹学基础及应用[M].武汉:武汉大学出版社,2014.[2]张劲松,李红.求解非标准形式指派问题的行调整法[J].统计与决策,2008(14):155-156.[3]郭倩倩,吴开信,郝光.一类模糊多目标指派问题的解法及应用[J].西华大学学报:自然科学版,2006,25(2):70-71,87.[4]李仁传,张合勇.变权多目标指派问题及其求解[J].军事运筹与系统工程,2012,26(4):58-61.[5]李敏.求解C-A指派问题的差值法[J].襄樊学院学报,2011,32(8):21-24.[6]宋昭峰,刘付显.基于模糊指派的阵地选址决策[J].火力与指挥控制,2006,31(7):34-36.。

匈牙利法解决人数与任务数不等的指派问题于凯重庆科技学院经济管理学院物流专业重庆沙坪坝区摘要：本文将讨论运筹学中的指派问题，而且属于非标准指派问题，即人数与任务数不相等的指派问题，应当视为一个多目标决策问题，首先要求指派给个人任务数目两两之间相差不能超过1，其次要求所需总时间最少，并且给出了该类问题的求解方法。

关键词：运筹学指派问题匈牙利算法系数矩阵解矩阵引言：在日常的生产生活中常遇到这样的问题：有n项任务，有n个人员可以去承担这n 项任务，但由于每位人员的特点与专长不同，各对象完成各项任务所用的时间费用或效益不同；有因任务性质要求和管理上需要等原因，每项任务只能由一个人员承担来完成，这就涉及到应该指派哪个人员去完成哪项任务，才能使完成n项任务花费总时间最短，总费用最少，产生的总效益最佳。

我们把这类最优匹配问题称为指派问题或分配问题。

1.指派问题的解法——匈牙利法早在1955年库恩（，该方法是以匈牙利数学家康尼格（koning）提出的一个关于矩阵中0元素的定理为基础，因此得名匈牙利法（The Hungonrian Method of Assignment）1.1匈牙利解法的基本原理和解题思路直观的讲，求指派问题的最优方案就是要在n阶系数矩阵中找出n个分布于不用行不同列的元素使得他们的和最小。

而指派问题的最优解又有这样的性质：若从系数矩阵C（ij）的一行（列）各元素都减去该行（列）的最小元素，得到新矩阵CB（ij），那么以CB（ij）为系数矩阵求得的最优解和原系数矩阵C（ij）求得的最优解相同。

由于经过初等变换得到的新矩阵CB（ij）中每行（列）的最小元素均为“○”，因此求原指派问题C（ij）的最优方案就等于在新矩阵CB（ij）中找出n个分布于不同行不同列的“○”元素（简称为“独立○元素”），这些独立○元素就是CB（ij）的最优解，同时与其对应的原系数矩阵的最优解。

1.2匈牙利法的具体步骤第一步：使指派问题的系数矩阵经过变换在各行各列中都出现○元素。

匈牙利法解决人数与任务数不等的指派问题于凯重庆科技学院经济管理学院物流专业重庆沙坪坝区摘要：本文将讨论运筹学中的指派问题，而且属于非标准指派问题，即人数与任务数不相等的指派问题，应当视为一个多目标决策问题，首先要求指派给个人任务数目两两之间相差不能超过1，其次要求所需总时间最少，并且给出了该类问题的求解方法。

关键词：运筹学指派问题匈牙利算法系数矩阵解矩阵引言：在日常的生产生活中常遇到这样的问题：有n项任务，有n个人员可以去承担这n 项任务，但由于每位人员的特点与专长不同，各对象完成各项任务所用的时间费用或效益不同；有因任务性质要求和管理上需要等原因，每项任务只能由一个人员承担来完成，这就涉及到应该指派哪个人员去完成哪项任务，才能使完成n项任务花费总时间最短，总费用最少，产生的总效益最佳。

我们把这类最优匹配问题称为指派问题或分配问题。

1.指派问题的解法——匈牙利法早在1955年库恩（w.w.ku.hn）就提出了指派问题的解法，该方法是以匈牙利数学家康尼格（koning）提出的一个关于矩阵中0元素的定理为基础，因此得名匈牙利法（The Hungonrian Method of Assignment）1.1匈牙利解法的基本原理和解题思路直观的讲，求指派问题的最优方案就是要在n阶系数矩阵中找出n个分布于不用行不同列的元素使得他们的和最小。

而指派问题的最优解又有这样的性质：若从系数矩阵C（ij）的一行（列）各元素都减去该行（列）的最小元素，得到新矩阵CB（ij），那么以CB（ij）为系数矩阵求得的最优解和原系数矩阵C（ij）求得的最优解相同。

由于经过初等变换得到的新矩阵CB（ij）中每行（列）的最小元素均为“○”，因此求原指派问题C（ij）的最优方案就等于在新矩阵CB（ij）中找出n个分布于不同行不同列的“○”元素（简称为“独立○元素”），这些独立○元素就是CB（ij）的最优解，同时与其对应的原系数矩阵的最优解。

浅析指派问题的匈牙利解法胡小芹数学科学学院数学与应用数学学号:040414057指导教师:苏孟龙摘要:对于指派问题,可以利用许多理论进行建模并加以解决,但匈牙利解法是解决指派问题的一种非常简单有效的方法,并且可以解决多种形式的指派问题,但匈牙利算法本身存在着一些问题,本文主要介绍了匈牙利算法的基本思想,基本步骤,以及它的改进方法.在匈牙利算法的基础上,本文还介绍了两种更简便实用的寻找独立零元素的方法——最小零元素消耗法和对角线法.关键词:指派问题;匈牙利解法;最小零元素消耗法;对角线法0 引言在现实生活中经常会遇到把几个任务分派给几个不同的对象去完成,由于每个对象的条件不同,完成任务的效率和效益亦不同.指派问题的目标就是如何分派使所消耗的总资源最少（或总效益最优）,如给工人分派工作,给车辆分配道路,给工人分配机床等等,同时许多网络问题（如旅行问题,任务分配问题,运输问题等）,都可以演化成指派问题来解决.在现实生活中,指派问题是十分常见的问题,而匈牙利解法是解决指派问题的一种非常简单有效的方法.本文主要介绍匈牙利解法的基本原理及思想,解题步骤,不足与改进,以使匈牙利法更能有效地解决指派问题.1 指派问题及其数学模型指派问题是指由m项任务,需要n个人来承担,每人只能承担一项任务,且每项任务只能有一人来承担,由于各人的专长不同,各人完成的任务不同,导致其效率也各不相同.因此,就产生怎样科学地指派任务,才能使完成各项任务所消耗的总资源最少（或总成本最低等）,由于n m ,不同,指派问题可分为以下三种情况:第一、当n m =时,即为每人指派一项任务.第二、当n m >时,即任务数〉人数,这时可虚设)(n m -个人构成m m ⨯的 效率矩阵,并且这)(n m -个人在执行这m 项任务时的效率应该是效率最高. 第三、当n m <时,即配置人数〉任务数,这时应虚设)(m n -项任务,并且这n 个人在执行这)(m n -项任务时的成本最低.通过虚设任务或人,指派问题的效率矩阵都可以转化成方阵.匈牙利解法要求指派问题最小化,其数学模型为设用0ij c >(,1,2,,)i j n =表示指派第i 个人去完成第j 项任务时所用的时间,定义决策变量 10ij i j x i j ⎧=⎨⎩表示第个人完成第项任务, 表示不指派第个人完成第项任务.则问题可转化为0-1线性规划问题:∑∑===n j ij n i c Z 11mint s ⋅ 111,1,2,,,1,1,2,,,01,i,j 1,2,,n nij i nij j ijx j n x i n x ==⎧==⎪⎪⎪==⎨⎪⎪==⎪⎩∑∑或.如果指派问题要求的是最大化问题如F max ,则可以转化为最小化问题,一般方法是:取max (,1,2),ij M c i j n ==令(,1,2,)ij ij b M c i j n =-=,则11min ,n n ij i j f b ===∑∑,max F nM f F =-有从而求. 2 指派问题的解法——匈牙利解法“匈牙利解法”最早是由匈牙利数学家 D.Konig 用来求矩阵中0元素的一种方法,由此他证明了“矩阵中独立0元素的最大个数等于能覆盖所有0元素的最少直线数”.1955年由W.W.Knhu 在求解著名的指派问题时引用了这一结论,并对具体解法做了改进,仍称为匈牙利解法.2.1 匈牙利解法的基本原理和解题思想从根本上讲,求指派问题的最优解就是要在n 阶方阵中找到n 个这样的元素,它们分布在不同行不同列上,并且这些元素之和为最小,而要使这些元素之和为最小,就要使其中的每一个元素尽可能的小——最好这些元素都是其所在行所在列上的最小元素.而指派问题的最优解又具有这样的性质（定理1）:若从系数矩阵)(ij c 的每行（列）各元素中分别减去该行（列）的最小元素,得到的新矩阵()ij b ,那么以()ij b 为系数矩阵求得的最优解与用()ij c 求得最优解相同.由于新矩阵()ij b 中每行每列都有最小元“0”,因此,求原指派问题的最优解转化为在()ij b 中指出n 个分布在不同行不同列上的“0”元素（简称为独立0元素）,而根据考尼格（Konig ）证明的定理（定理2）:矩阵中独立元素的0最多个数等于能覆盖所有零元素的最少直线数,利用这一定理,就可以通过寻找“能覆盖所有零元素的最少直线数”来确定()ij b 中独立元0素的具体数量.若()ij b 中独立0元素的个数少于矩阵的阶数n ,就要继续对矩阵()ij b 进行化简,直到找到n 个独立0元素为止,这就是匈牙利解法的基本原理和解题思想.2.2 匈牙利解法的解题步骤第一步:变换效益矩阵,使新矩阵中的每行每列至少有一个0.（1）行变换:找出每行最小元素,再从该行各元素中减去这个最小元素.（2）列变换:从所得新矩阵中找出每列中的最小元素,再从该列各元素中减去这个最小元素.第二步:进行试指派,以寻找最优解.（1）逐行检查从第一行开始,如果该行只有一个零元素,就对这个零元素打上括号,划去与打括号零元素同在一列的其他零元素,如果该行没有零元素,或有两个或多个零元素（已划去的不计在内）,则转下行.打括号的意义可理解为该项任务已分配给某人.如果该行只有一个0,说明只能有唯一分配.划掉同列括号零元素可理解为该任务已分配,此后不再考虑分配给他人.当该行有两个或更多的零元素时,不计括号内的,其理由是至少有两个分配方案,为使以后分配时具有一定的灵活性,故暂不分配.（2）逐列检查在行检查的基础上,由第一列开始检查,如果该列只有一个零元素,就对这个零元素打括号,再划去与打括号零元素同行的其它零元素.若该列没有零元素或有两个以上零元素,则转下一列.（3）重复（1）、（2）两步后,可能出现以下三种情况:①每行都有一个零元素标出括号,显然打括号的零元素必然位于不同行不同列,因此得到最优解.②每行每列都有两个或两个以上的零,这表示对这个人可以分配不同任务中的任意一个.这时可以从所剩零元素最少的行开始,比较这行各零元素所在列中元素的个数,选择零元素少的那列这个零元素打括号,划掉同行同列的其他它零元素,然后重复前面的步骤,直到所有0都作了标记.③矩阵中所有零都作了标记,但标有(0)的元素个数少于m个,则转下步.第三步:做最少的直线覆盖所有零元素,以确定该系数矩阵中能找到最多的独立0元素.·对没有（）的行打√;·对打√的行上所有含0元素的列打√;·再对打√的列上有（）的行打√;·重复上两步,直到过程结束;·对没有打√的行划横线,对所有打√的列划垂线.这就得到了能覆盖矩阵中所有0元素的最少直线数.第四步:非最优阵的变换——零元素的移动.（1）在没有被直线覆盖的所有元素中,找出最小元素;（2）所有未被直线覆盖的元素都减去这个最小元素;（3）覆盖线十字交叉处的元素都加上这个最小元素;（4）只有一条直线覆盖的元素的值保持不变.第五步:回到第二步,反复进行,直到矩阵中每行每列都有一个打（）的0元素为止,即找到最优解.2.3 匈牙利算法的一点注记（1）匈牙利算法第一步变换效益矩阵使每行每列都出现零元素,一般方法是先行变换,再列变换,但先列变换再行变换最优解不变.（2）有些时候先行后列变换后不能得到最优解,但先列后行变换时却能直接找到最优解,从而减少了计算步骤,使计算简明.如下所示:先行变换,再列变换得2109715414813141611415139B ⎡⎤⎢⎥⎢⎥=→⎢⎥⎢⎥⎣⎦(0)82511(0)5423(0)001145B ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦只找到三个独立0元素,不是最优解.那么先列变换,后行变换得2109715414813141611415139B ⎡⎤⎢⎥⎢⎥=→⎢⎥⎢⎥⎣⎦06(0)013(0)51763(0)(0)920B ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦ 每行每列都有“(0)”,得到最优解.3 匈牙利法的不足与改进3.1 不足和改进（一）以上是匈牙利法的常规解题方法,虽然能有效地解决指派问题,但是其解题过程中还存在以下两点不足:第一、在匈牙利算法的第二步中用“试指派”的方法寻找独立0元素,道理简单,也能很快找到独立0元素,但对于一个n 阶方阵,这些独立0元素在矩阵中可能有n 种排列方式,这样在矩阵中标出来的独立0元素排列很乱,没有规律.另外,对于某些矩阵0元素排列的比较有规律,本可以用别的更简单的方法寻找独立0元素,而用这种“一般性”的方法比较麻烦.第二、在匈牙利算法的第三步“做最少的直线覆盖所有0元素”过程中,一会儿针行,一会儿针对列,一会儿对没有（）的打√,一会儿又对有（）的打√,一会对没有打√号的（行）划线,一会又对打√号的（列）划线,这样变来变去令人晕头转向,稍不注意就会出错,特别是对于这种画法每一步的意图以及内在原理,大多数人难以理解,具体步骤很难记住,难以掌握,这就影响了这一理论在实际工作中的应用.算法的改进:第一、寻找独立0元素的一种新方法——对角线法.对角线法的原理:根据要在指派问题化简后的系数矩阵(ijb)中找出n个独立0元素,而这些独立0元素又分布在方阵的不同行不同列上,利用这一特点,我们可以对矩阵(ijb)的行（或列）进行某种调换,就一定可以使这些独立0元素按矩阵的对角线排列,这样凡是出现在对角线上的零元素一定是独立0元素,而非对角线上的零元素也一定是非独立0元素,这样我们既能很快找到所有独立0元素,又能直观地发现矩阵中独立0元素的个数.方法:从0元素数量最少的行开始,选择该列第一个0元素,根据该0元素所在行的位置确定该列元素在新矩阵中列的位置（若该0元素所在行是第i行,那么就将该0元素所在列放在新矩阵的第i列）,并在原矩阵中划去这一列,并划掉同行其它0元素,再在剩下的矩阵中重新比较各列0元素的数量,并按前面方法进行,直至完成.这样就可以将所有独立0元素集中放在新矩阵的对角线上,当对角线上全为0时,就得到了指派问题的最优解,如果对角线上某一处不为0,说明该矩阵中独立0元素数量不足,这时需要对矩阵作进一步化简.应用示例: 寻找矩阵B中的独立0元素B=5050200304400401⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦→B=5050200304400401⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦→10505003244004010B⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦（第一列与第四列交换）或25050 2300 0044 0104B⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦（第二列与第四列交换）第二、最少直线的一种简单画法.画法原理:根据定理“矩阵中独立0元素的最多个数恰好等于能覆盖所有0元素的最少直线数”,也就是说矩阵中有多少个独立0元素,就需要多少条直线将所有0元素覆盖,而从匈牙利法解题步骤看矩阵中独立0元素的数量m 及位置,在划线前是已知,所以覆盖0元素的最少直线数m 也是已知的.由于任意两个独立0元素“(0)”都不同行且不同列,而盖0线也只能按矩阵的行或列来划,因此,一条盖0线只能覆盖一个“(0)”,要覆盖m 个“(0)”就需要m 个直线.基于“盖0线”与独立0元素“(0)”之间数量的一对一关系,只要我们始终围绕着独立0元素“(0)”来画线,首先就能用最少的直线覆盖所有的独立0元素.另外,由于矩阵中的非独立0元素总是和某个独立0元素在同一行或同一列,因此画盖“(0)”线时,只要我们能使每条盖0线都尽可能多的附带非独立0元素,那我们就能实现用最少的直线覆盖所有0元线.具体画法:（1）标记——对“(0)”所在行和列上的0元素数量在行列旁予以标注,对没有“(0)”的行与列的打×号予以标记.（2）画线——从有“(0)”的行与列中找出0元素最多的行（或列）画一横（或纵）线覆盖这些0元素.（3）修正——从“(0)”所在行与列上的0元素数量减去已被覆盖的0元素数.（4）重复上述过程,直至覆盖所有0元素.上述方法的关键是紧紧抓住独立0元素其所在行与列上的0元素的多少决定盖0线的画法（即画线的先后和方向,横向还是纵向）,使每条线都能覆盖尽可能多的0元素.另外,因某些非独立0元素处在可被两条盖0线同时覆盖的交叉点上,为减少重复性覆盖,每画一条线后都要对各行各列0元素数予以修正（从中减去已被覆盖的0元素数）.示例: 试用最少的直线覆盖下列矩阵中的所有0元素5(0)202230(0)0(0)1057298(0)0406365B ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦→ 5(0)2022230(0)03(0)10572198(0)04206365B ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⨯⎣⎦2 1 23 ×5(0)2022230(0)00(0)10572198(0)04206365B ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⨯⎣⎦→ 5(0)2020230(0)00(0)10572198(0)04206365B ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⨯⎣⎦→ 2 1 1 × × 2 × 1 × ×5(0)2020230(0)00(0)10572198(0)04006365B ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⨯⎣⎦ 2 × × × ×注意:当矩阵中的行和列旁标的0元素的数量相等时,我们从中任意选择一个画线,但是当此行（或列）中的0元素所对列（或行）中无“(0)”时,只能先划去此行（或列）.比如上面的矩阵B 中,第二行和第四列中0元素相等,都是最多（3个）,若先划去第四列,则第二行中第五列中的0元素用这种方法无法划去,若要划去这个0元素,则直线增多.3.2 不足和改进（二）用于解决指派问题的匈牙利解法,在运算过程中存在着两个问题:第一、算法不完善.从未标零元素最少的行取定0元素,不能保证0元素所在的列未标零元素最少.因此,系数矩阵已存在最大匹配,但无法取得最大匹配,而算法中途停止.第二、计算步骤烦琐.当0元素不够又没有未标零元素时,作直线覆盖,移动零元素,然后再取定0元素,反复进行.一 改进算法1 完善匈牙利算法选取零元素时,若被划行未标零元素多于一个,则要保证所标的零元素所在的列未标零元素最少．利用此方法可以解决问题一．2 改进算法步骤（1）利用匈牙利算法,由系数矩阵()ij c 得到各行各列都有零元素的等效矩阵()ij b .（2）若有未划零元素,则选有未划零元素最多的行或列作直线覆盖,直到没有未划零元素为止．（3）若直线数目小于n ,则在未划元素中选取最小元素,未划的各元素减去最小元素,直线交叉处的元素均加最小元素,转2.否则转4.（4）选取有未标零元素最少的行(或列)取未标零元素,记(0),同行同列的未标零元素记 φ;若该行(或列)未标零元素多于一个,则选列(或行)中未标零元素最少的本行未标零元素为(0),直到(0)元素个数等于n 为止．（5）结束算法,得到最大匹配.令对应于(0)的1ij x =,其余的0ij x =,并计算目标函数值．二 定义及定理定义1 作直线覆盖时,被直线覆盖的元素,称为已划元素.未被直线覆盖的元素,称为未划元素．定义2 求最大匹配时,已作记号(0)和φ的零元素称为已标元素,未作记号的零元素称为未标零元素．定理 矩阵()ij b 中已存在最大匹配的充要条件是直线覆盖其中全部零元素的最少数目为n ．证明 必要性 若()ij b 中有最大匹配,则()ij b 中存在n 个不同行不同列的零元素,故至少n 条直线才能覆盖全部元素．充分性 若覆盖全部零元素的最少直线数目为n ,则()ij b 中有n 个不同行不同列的零元素.否则可以用少于n 条的直线能覆盖全部元素.此算法的优点是,先求具有最大匹配的等效矩阵,再求最大匹配.求解过程中可以减少迭代次数,降低计算量,并且对某些用匈牙利算法无法得到最大匹配的矩阵利用此改进的算法可以得到最大匹配,例如效益矩阵010()002003ij b ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦. 3.3 不足和改进（三）3.3.1 匈牙利法存在的问题我们用“匈牙利法”处理了许多与分配问题相关的运输、调度问题,大多数情况下算法是收敛的,得到了最优解,而处理一些特殊数据时算法不收敛,无法找出最优解,矩阵阶数越大的分配问题,不收敛的情况越多.试验中,发现了一个较小阶不收敛的系数矩阵,下面用“匈牙利法”对该矩阵进行分析2 2 4 1 4 4 4 4 12 2 1 1 23 3 3 12 3 1 4 4 2 4 3 42 1 1 4 13 1 1 23 1 1 1 2 2 1 3 11 3 1 42 23 1 33 4 2 1 1 1 3 3 13 24 1 3 1 4 1 21 4 12 1 43 1 4经过算法第一步,得到修正的系数矩阵1 1 3 0 3 3 3 3 01 1 0 0 12 2 2 01 2 0 3 3 1 3 2 31 0 0 3 02 0 0 12 0 0 0 1 1 0 2 00 2 0 3 1 1 2 0 22 3 1 0 0 0 2 2 02 13 0 2 0 3 0 10 3 0 1 0 3 2 0 3进行算法第二步,做分配方案,最终第2行无(0)标记,使得第2行第2列没有分配1 1 3 (0) 3 3 3 3 ×1 1 ×× 12 2 2 ×1 2 (0) 3 3 1 3 2 31 ×× 3 (0)2 ×× 12 ××× 1 1 (0) 2 ×(0) 2 × 3 1 1 2 × 22 3 1 ××× 2 2 (0)2 13 × 2 × 3 × 1× 3 × 1 × 3 2 (0) 3进行算法第三步,最终所有的行和所有的列都有∨标记,所有的行末画一条横线,所有的列都画上了竖线,各行列作标记的顺序如下∨∨∨∨∨∨∨∨∨⒄⑿⑵⑶⑻⑼⒀⒁⑷1 1 3 (0) 3 3 3 3 ×⑹∨1 1 ×× 12 2 2 ×⑴∨1 2 (0) 3 3 1 3 2 3 ⑸∨1 ×× 3 (0)2 ×× 1 ⑽∨2 ××× 1 1 (0) 2 ×⒂∨(0) 2 × 3 1 1 2 × 2 ⒅∨2 3 1 ××× 2 2 (0) ⑺∨2 13 × 2 (0) 3 × 1 ⑾∨× 3 × 1 × 3 2 (0) 3 ⒃∨进行算法第四步,没有找到未被直线覆盖的元素,所以也就无法找到最小的元素,也就不能产生新的效能矩阵,算法进入死循环.这就否定了“匈牙利法”主要过程的算法基础.若算法第二步未完成一个完全分配时,则一定能生成一个新的效能矩阵,出现新的零元素,再重新进行完全分配,最终一定能得到一个完全的最优解.3.3.2 匈牙利算法的改进为了使“匈牙利法”对任意数据都能有效的找到最优解,我们在原算法的基础上增加第六步,以及在第三步后面增加判断功能:若生成n条直线,无法生成新的效能矩阵,则退出“匈牙利法”,进行第六步.第六步:产生新的小系数矩阵,使原矩阵分解.（1）从第二步算法中,记下有(0)标记的行号和列号,作为部分解进行保存.（2）从系数矩阵中抽取行列都没有(0)标记的数据,组成一个新的小系数矩 阵:[]ij E ,1,2,,,1,2,,,i m j m m n ==<.（3）将小系数矩阵再代入“匈牙利法”, 继续计算, 得到小系数矩阵的分配解, 把它添加到部分解的结果中去,组合得到一个新的解,如果新的解仍然不是完全解,则转（1）继续处理.（4）对已分配的元素,两两一对组成任意一个矩形的斜对角顶点, 相加后生成一个基础量, 再将矩形的另一对斜对角顶点的元素相加,生成一个改变量,有n 个已分配的元素将产生12321n n ++++-+-对基础量和改变量.（5）对于每对基础量和改变量,如果存在基础量大于改变量的情况,则找出基础量与改变量差值最大的一对,由改变量取代基础量,转（4）继续处理.（6）得到整个分配的最优解,输出分配结果.在上例中,新的小系数矩阵仅为第2行和第2列,m 为1.另外,也没有找到改变量小于基础量的两对值,所以无须进行优化,直接将该元素添加到部分解中去,通常新的小系数矩阵的阶数都很小.文献[]5中给出了一个2222*的系数矩阵,存在上述问题,利用改进的匈牙利算法最终得到最优解.3.4 匈牙利算法的推广匈牙利算法的关键是在变换后的系数矩阵中找出n 个分布在不同行不同列的独立0元素,而匈牙利算法计算过程比较麻烦,文献[]8,文献[]9在匈牙利算法的基础上提出了两种比较简单的寻找独立0元素的方法:最小零元素消耗法及对角线法.3.4.1 最小零元素消耗法基本思想:对于一个给定的矩阵,其中0元素的数目是一定的,这一定的0元素最多能分配出多少个0元素来？当分配出一个0元素时,该0元素所在行和列上的其它0元素就无法再分配,失去了作用,也就是说,分配出该0元素要用去0元素的个数为:该0元素本身+该0元素所在行上的其它0元素+该0元素所在列上的其它0元素,称此数为该0元素的0消耗数.对于给定矩阵中的所有0元素,可以很容易地找出其0消耗数,根据动态规划的最优化原理,如果第1次分配出0消耗数最少的0元素,将消耗的0元素去掉,在余下的0元素中再分配0消耗最少的0元素,重复这样的过程,最终结果必将得到最多次数的分配即最大分配,这就是最小0元素消耗法.基本方法:利用匈牙利算法变换系数矩阵,使每行每列出现0元素,计算出各个0元素的消耗数,分配处0消耗数最少的那个0元素,以(0)标记.此0元素所在行所在列以不起作用,再计算余下的个各个0元素的消耗数,重复上述步骤,直至每行每列的0元素都标记完,最终得到最大匹配,若标记(0)的个数等于矩阵阶数,得到最优解.在应用此方法的时候,当遇到0消耗相同的0元素不止一个,此时应先分配哪个0元素呢？有以下三种情况:（1）0消耗数相同,但0元素在同一行或同一列上,如下所示:120(,)0(,)i j ij120(,)0(,)i j ij现就0元素在同一行的情况说,如果分配其任何一个,另一个则被消耗掉,他们的0消耗数实际上是相同的,只能表示一个分配,要么分配10(,)i j ,要么分配20(,)i j ,但第i 行则可以确定下来,等其它0元素分配完以后,如12,j j 列中有一列确定,则第i 行可以具体确定出0元素,若12,j j 列仍未确定,则说明最大分配小于n ,或者有多种最优分配方案.对于同一列的情况,可以确定第j 列,具体分配哪一个,视其它0元素的分配而定.（2）0消耗数相同且互相影响,但0元素不同行不同列,此时0元素的消耗数必共同消耗一个或两个0元素,如下所示:11220(,)00(,)i j ij 11220(,)000(,)i j ij110(,)i j 、220(,)i j 的0消耗相同,设为q ,他们的0消耗因共有0元素而相互影响,若先分配110(,)i j ,则在余下的0元素中220(,)i j 的0消耗数为1q -或2q -,必为最小,应予与分配.反之也是,因此这种情况两者应同时分配.（3）0消耗数相同但互不影响,此时必为下图所示:11220(,)0(,)i j ij此时若先分配110(,)i j ,则在余下的0元素中,220(,)i j 的0消耗必为最少,应予与分配,反之也是.这种情况可将它们同时分配.综合上述三种情况,当遇到0消耗数相同的0元素时,如果它们不在同一行同一列,可以将其同时分配;如果在同一行同一列上,可将该行或该列分配,分配数加1,具体分配视其它0元素分配结果而定.3.4.2 对角线法匈牙利算法的实质就是寻找n 个分布在不同行不同列的零元素,而匈牙利算法本身计算过程较复杂,下面给出一种使系数矩阵对角线为零的算法——对角线法.基本步骤:第一步:变换系数矩阵使每行每列都出现零元素,同匈牙利算法第一步.第二步:进行行排序,即（1）在变换后的系数矩阵()ij b 的第j 列元素中(1,2,,)j n =,从第,1,,j j n +行中选取最小元素,记为0b i j .（2）将0i 行元素与j 行进行交换.通过步骤二可使每列中的零元素或最小元素尽量出现在对角线上.若这样选取的最小元素有两个以上时,则取这些最小元素所在行中第n 个元素大者所对应的元素为最小元素;若第n 个元素也相同,则取第1n -个元素中大者对应的元素为最小元素,以此类推;若这些最小元素后各行对应元素都相同,则取这些最小元素所在行中第1j -个元素小者对应元素为最小元素;若第1j -个元素相同,则取再前一个元素中小者对应元素为最小元素,以此类推.若这些最小元素所在行的对应元素均相同,则可任选一最小元素所在行与第j 行元素交换.第三步:检验——若0ii b =(1,2,,)i n =,则以得最优解,过程结束.否则进行第四步.第四步:进行行排序,排序过程类似于第二步,只须将第二步中的“列”改为“行”.而“行”改为“列”,“后”改为“下”,“前”改为“上”即可.第五步:若0ii b =(1,2,,)i n =,则已得到最优解,迭代过程停止,否则进行第六步.第六步:,1,2,,ij ij ii b b b j n =-=. 第七步:若0,1,2,,ij b j n ≥=,则返回第五步.否则,若0ik b <,则令,1,2,,jk jk ik b b b j n =-=,返回第一步.从上述过程来看,整个过程包括两个基本部分,第一部分是通过一系列矩阵的行列变换,把零元素排列在对角线上;第二部分是最解的检验,即所有0ii b =时,已得到最优解.对于此算法的收敛性分析,文献[]9中给出了几个定理,并进行了证明,可以看出此改进算法的收敛性极好,可以有效地解决指派问题.4 对最大化指派问题的匈牙利解法的一点改进对最大化的指派问题的解法,一般方法是找出系数矩阵()ij c 中的最大元素,即1nij i M max c ==∑),,2,1(n j =,做矩阵B ,其元素为),,2,1;,,2,1(n j n i b ij ==且ij ij c M b -=,然后利用匈牙利解法最小化求B 的最优解.下面我们在此基础上对其提出一点改进,直接在原系数矩阵上进行修改.修改的原则是:在最小化问题中,系数矩阵不能出现负数,在最大化问题中,修改后的不能出现正元素,可出现零.基本步骤:第一步:修改系数矩阵.。

python的scipy（匈牙利算法）解决教学任务指派问题python的scipy（匈牙利算法）解决教学任务指派问题参考资料：匈牙利算法求解教学任务指派问题指派问题组合优化理论里的第六章_指派问题的课件问题简介在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。

由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。

于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。

这类问题称为指派问题或分派问题。

教学任务指派问题为指派问题中的一种，考虑教师对课程的擅长程度，教学任务饱满序列和学生对教师的满意度，通过匈牙利算法求得最优课程指派。

算法指派问题一般模型：匈牙利算法：教师与课程一样多把求最大值变为求最小值问题：矩阵C=20-擅长矩阵。

再进行匈牙利算法操作：如果得不到解，则：程序实现：import numpy as npfrom scipy.optimize import linear_sum_assignmentdefprintf(row_ind,col_ind):print("最优教师课程指派：")for i inrange(len(row_ind)):print("教师",row_ind[i],"->课程",col_ind[i],end='; ')print() goodAt=np.array([[18,5,7,16],[10,16,6,5],[11,6,4,7],[13,12,9 ,11]])weakAt=20-goodAtrow_ind,col_ind=linear_sum_assignment(weakAt)print(row _ind)print(col_ind)print(goodAt[row_ind,col_ind])print (goodAt[row_ind,col_ind].sum())printf(row_ind,col_ind)输出结果：教师少与课程多把求最大值变为求最小值问题：矩阵C=10-擅长矩阵。

变权多目标指派问题及其求解
李仁传;张合勇
【期刊名称】《军事运筹与系统工程》
【年(卷),期】2012(000)004
【摘要】针对同一目标在各项任务中的重要程度未必一致的实际,提出目标权重可变的多目标指派问题,并通过理想点法与匈牙利法的结合使用,给出该类问题的求解方法。

【总页数】4页(P58-61)
【作者】李仁传;张合勇
【作者单位】后勤学院,北京100858;后勤学院,北京100858
【正文语种】中文
【中图分类】N945
【相关文献】
1.多目标广义指派问题的模糊匈牙利算法求解
2.多目标C-A指派问题的模糊差值法求解
3.多目标C-A指派问题的模糊差值法求解
4.考虑目标差异的多目标指派问题研究
5.具有模糊信息的多目标指派问题求解
因版权原因，仅展示原文概要，查看原文内容请购买。