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

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

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

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

这类问题研究的是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.。