运筹学教学 | 十分钟教你求解分配问题(assignment problem)

biu~ biu~ biu~

我们的运筹学教学推文又出新文拉

还是熟悉的配方,熟悉的味道

今天向大家推出的是

运筹学教学--第六弹

分配问题(Assignment Problem)与匈牙利算法(Hungarian Method)

内容提要

什么是分配问题

什么是匈牙利算法

匈牙利算法的实例教学

1

问题描述

什么是分配问题:

分配问题也称指派问题,是一种特殊的整数规划问题,分配问题的要求一般是这样的:

n个人分配n项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。

简单的说:就是n*n矩阵中,选取n个元素,每行每列各有一个元素,使得和最小。

2

匈牙利算法

解决分配问题的算法有多种,但是最常用的是匈牙利算法。

什么是匈牙利算法?

1、理论基础:

若从指派问题的系数矩阵的某行(列)各元素中分别减去或者加上常数k,其最优任务分解问题不变。

2.匈牙利算法的流程图

3.计算步骤

这个流程图...

看起来很复杂的样子?

下面小编用一个简单的例子来说明

例如:有A、B、C、D四项任务,需要分配给甲乙丙丁四个人来完成。他们完成任务所需要支付的酬劳如下表所示,问,如何分配任务,可使总费用最少?

得到的支付矩阵是:

Step 1: 行归约

找出每行的最小元素,分别从每行中减去这个最小元素;

矩阵变换如下:

Step 2 : 列归约

找出每列的最小元素,分别从每列中减去这个最小元素

经过以上两步变换,矩阵的每行每列都至少有了一个零元素。接下来就进行第三步,试着指派任务。

Step 3 : 指派任务

① 确定独立零元素。

i 从第一行(列)开始,若该行(列)中只有一个零元素,对该零元素标1,表示这个任务就指派给某人做。

每标一个1,同时将该零元素同列的其他零元素标为2,表示此任务已不能由其他人来做。(此处标1、2的操作与课本画圈、划去操作同理)

如此反复进行,直到系数矩阵中所有的零元素都已经被标为1或者2为止。

我们得到的矩阵如下:

② 指派

我们观察到,系数矩阵中标记为1的零元素正好等于4,这表示已经确定了最优的指派方案。

此时,只需将0(1)所在位置记为1,其余位置记为0,则获得了该问题的最优解。

最优解为:

即:A任务交给丙负责,B任务交给丁负责,C任务交给甲负责,D任务交给乙负责。

此时总报酬为:1+5+2+3 = 11;

至此,指派问题就解决拉?

这么..简单吗?

好吧,上例仅为一种理想情况

正常情况下,我们在对支付矩阵进行变换时

会出现两种情况

① 出现零元素的闭合回路

②标记成1的元素个数小于n

为了让支付矩阵中出现个独立零元素,需要对支付矩阵进行变换。

下面我们针对这两种情况举例说明:

01

i.出现零元素的闭合回路(有多于两行或两列存在两个以上的零元素。)

对于矩阵:

我们所有变化后,得到矩阵:

图的第一行的一二列零元素和第四行的一二列零元素构成回路

这里我们的处理方法是:

先对cost方阵做一个备份(因为会出现多解),然后我们可以顺着回路的走向,对间隔的零元素标记成1,然后对标记成1的零元素所有的行列划一条直线,把这两条直线的其他零元素标记成2,得到一种结果后,再求出多解。

这里我们采用间隔标记法,得到矩阵:

最优解为:

最小酬劳为:1+2+2+2=7

02

ii. 矩阵中所有标记成1的零元素小于n。

例如矩阵:

经过所有变换后得到矩阵:

被标为1的0总共有3个,小于4。

因此,我们需要对其进行【画盖0线】的操作。(即画出可以覆盖最多0元素的直线)

(1)画盖0线:利用最少的水平线和垂直线覆盖所有的零。

具体操作如下:

① 对没有标记为1的零元素所在的行打√;

②在已打“√”的行中,对标记为2的零元素所在列打√

③ 在已打“√”的列中,对标记为1的零元素所在行打“√”

④重复②和③,直到再不能找到可以打√的行或列为止。

⑤对没有打“√”的行画一横线,对打“√”的列画一垂线,这样就得到了覆盖所有零元素的最少直线数目的直线集合。

对矩阵进行操作:

① 打勾

② 划线

(2)继续变换系数矩阵

①在未被覆盖的元素中找出一个最小元素。

②对未被覆盖的元素所在行中各元素都减去这一最小元素。这时已被覆盖的元素中会出现负元素。

③对负元素所在的列中各元素加上这一最小元素。

对上述矩阵:20为未被覆盖元素中最小的元素。变换矩阵,并寻找得:

Step4

我们发现,在经过一次变换后,独立零元素的个数仍然少于4.此时返回第三步,反复进行,直到矩阵中每一行都有一个被标记为1的元素为止。

例如在上述矩阵中:

矩阵中独立零元素仍然小于n。对矩阵执行打勾、划线等操作,得出未被覆盖区最小元素为5,进行系数变换之后得到矩阵:

我们发现得到的矩阵每行列有多个零元素(零元素的闭合回路),再运用上述方法可以得到矩阵:

最优解为:

最小酬劳为:15+65+25+50=155

以上,我们的指派问题和匈牙利算法原理就

搞! 定! 拉!

3

代码实例说明

如约而至的,仍旧是我们的代码(C++版)

若想获得代码.txt文件,可以直接滑到本文最后

点击“阅读原文”下载哦~

下载只需复制黏贴即可,so easy!

运筹学·教学笔记 第六弹 —— 分配问题篇

画上句点!

本文的参考书是一本《运筹学教程》(胡运权),为了鼓励大家支持正版书籍,还是请大家自行到书店购买书籍。

本文的源代码,算例以及编译好的程序的下载地址之后将会在留言之中给出,请大家关注留言区

如果大家对 分配问题 及 文中所叙内容 还有疑问或想要交流心得建议,欢迎移步留言区!

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2017-10-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏freesan44

python 算法开发笔记

1752
来自专栏数据结构与算法

BZOJ4517: [Sdoi2016]排列计数(组合数+错位排列)

Description 求有多少种长度为 n 的序列 A,满足以下条件: 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 的值为 i,则称 ...

2907
来自专栏蜉蝣禅修之道

网络流算法Dinic的Python实现

1504
来自专栏小樱的经验随笔

hihoCoder #1142 : 三分求极值

#1142 : 三分·三分求极值 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 这一次我们就简单一点了,题目在此: ? 在直...

3499
来自专栏蜉蝣禅修之道

优化后的Levensthein distance算法实现

3695
来自专栏软件开发 -- 分享 互助 成长

经典算法学习之回溯法

回溯法的应用范围:只要能把待求解的问题分成不太多的步骤,每个步骤又只有不太多的选择就可以考虑使用回溯法。  若用回溯法求问题的所有解时,要回溯到根,且根结点的所...

2358
来自专栏开发与安全

算法:图解最小生成树之普里姆(Prim)算法

我们在图的定义中说过,带有权值的图就是网结构。一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。所谓的最小成本,就...

3799
来自专栏数据结构与算法

Day4晚笔记

数据结构 并查集:捆绑两个点的信息,判断对错 倍增:LCA, 字符串 hash,模拟, 最小表示法 给定一个环状字符串,切开,使得字符串的字典序最小 图和树 割...

2614
来自专栏大数据挖掘DT机器学习

python数据分析师面试题选

python数据分析部分 1. 如何利用SciKit包训练一个简单的线性回归模型 利用linear_model.LinearRegression()函数 #...

5606
来自专栏潇涧技术专栏

Python Algorithms - C7 Greedy

Python算法设计篇(7) Chapter 7: Greed is good? Prove it!

1112

扫码关注云+社区

领取腾讯云代金券