指派问题 |
您所在的位置：网站首页 › 运筹学最小化指派问题 › 指派问题 |
指派问题
|
对于多人完成多个代价不同的任务的指派问题，匈牙利算法是一种有效的解决方案，本文记录相关内容。 指派问题在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务的代价不同（收益不同）。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总代价最小（收益最大）。这类问题称为指派问题或分派问题。这类问题可以依据人员和代价（收益）建立矩阵，称为效率矩阵或系数矩阵，其元素 𝑐_{𝑖𝑗}＞0(𝑖,𝑗 = 1,2,…,𝑛)表示指 派第𝑖人去完成第𝑗项任务时的效率(或时间、成本等)。代价矩阵有一个性质，若从指派问题的系数矩阵的某行（列）各元素中分别减去或者加上常数k，其最优任务分解问题不变。匈牙利算法叫做匈牙利算法 的事实上有两个算法，分别解决指派问题和二分图最大匹配求解问题，此处算法指求解指派问题的匈牙利算法。 算法流程 算法内容第一步 数矩阵经变换，在各行各列中都出现0 元素。
使指派问题的系数矩阵经变换，在各行各列中都出现0 元素。从系数矩阵的每行元素减去该行的最小元素；从所得系数矩阵的每列元素中减去该列的最小元素。若某行(列)已有0元素，那就不必再减了。每行每列最小元素非负 第二步进行试指派，以寻求最优解。为此，按以下步骤进行。 经第一步变换后，系数矩阵中每行每列都已有了0元素；但需找出𝑛个独立的0元素。若能找出，就以这些独立0元素对应解矩阵 (𝑥_{𝑖,𝑗})中的元素为1，其余为0，这就得到最优解。步骤为： 从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎ 。这表示对这行所代表的人，只有一种任务可指派。然后划去◎ 所在列(行)的其他0元素，记作Φ。这表示这列所代表的任务已指派完，不必再考虑别人了。只有一个0元素列(行)的0元素加圈，记作◎；然后划去◎ 所在行的0元素，记作Φ。反复进行(1)，(2)两步，直到所有0元素都被圈出和划掉为止。若仍有没有划圈的0元素，且同行(列)的0元素至少有两个( 表示对这个可以从两项任务中指派其一)。这可用不同的方案去试探。从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元 素的数目，选择0元素少的那列的这个0元素加圈 (表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。若◎元素的数目𝑚等于矩阵的阶数𝑛，那么这指派问题的最优解已得到。若𝑚＜𝑛，则转入下一步。第三步(𝑚 < 𝑛时的处理办法)：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以下步骤进 行： 对没有◎的行打√号；对已打√号的行中所有含◎元素的列打√号；再对打有√号的列中含◎元素的行打√号；重复(2)，(3)直到得不出新的打√号的行、列为止。对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数。 令这直线数为𝑙。若𝑙＜𝑛，说明必须再变换当前的系数矩阵，才能找到𝑛个独立的0元素，为此需要转第四步：若l=n，而m＜n， 应回到第二步(4)，另行试探。第四步对矩阵进行变换的目的是增加0元素。为此，在没有被直线覆盖的部分中找出最小元素，然后在打√行各元素中都减去这最小元素，而在打√列的各元素都加上这最小元素，以保证原来0元素不变。这样得到新系数矩阵(它的最优解和原问题相同)。若得到𝑛个独立的0元素，则已得最优解，否则回到第三步重复进行。算法示例有A、B、C、D、 E五项任务，需要分配给甲、乙、丙、丁、戊 五个人来完成。他们完成任务所需要支付的酬劳如下表所示，问，如何分配任务，可使总费用最少？  一、减法归约 行归约：每行元素减去该行最小元素。
画圈为行最小值：
 每行减去最小值：
 列归约：每行元素减去该行最小元素。
每列最小值已经为 0 无须继续归约：二、圈零划零找到含零元素最少的行，对零元素打圈，划去打圈零元素所在行和列存在的零元素，重复这个步骤，直到矩阵中所有的零元素都被处理完。 三、打勾划线打钩无 〇 行打钩 √无 〇 行有 〇 列打钩 √√ 列有 〇 行打钩 √ 划线无 √ 行划线有 √ 列划线得到覆盖所有0元素的最少直线数。  此时线数为4，少于节点数5，需要进入下一个调整值的步骤四、元素调整在没有被直线覆盖的部分选择最小值，作为调整元素 划线列，不划线行为需要调整的行列 （划 √ 的行列）
调整行减去调整元素
调整列加上调整元素
此种操作会保证行中的 0 元素不变
 五、重新圈零 重新进行第三步圈零操作
乙和丁的任务可以交换
 因此指派方案确定甲 乙 丙 丁 戊 任务安排 B C E D A 最终匈牙利算法的结果 总共花费的费用和为 32Python 实现python 解决方案中，用到的是 scipy.optimize.linear_sum_assignment(cost_matrix)以上文的算法示例为例代码语言：javascript复制from scipy.optimize import linear_sum_assignment
import numpy as np
cost =np.array(
[
[12,7,9,7,9],
[8,9,6,6,6],
[7,17,12,14,9],
[15,14,6,6,10],
[4,10,7,10,9]
])
row_ind, col_ind=linear_sum_assignment(cost)
res = np.zeros_like(cost)
res[row_ind, col_ind] = 1
print(res) # 结果矩阵
print(cost[row_ind,col_ind].sum()) # 数组求和，求得总花费输出结果代码语言：javascript复制[[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 0 1]
[0 0 0 1 0]
[1 0 0 0 0]]
32参考资料https://www.cnblogs.com/ylHe/p/9287384.htmlhttps://www.pianshen.com/article/35751358181/https://www.freesion.com/article/5336622238/https://blog.csdn.net/qq_40894102/article/details/105980364https://blog.csdn.net/siss0siss/article/details/51325656
|
【本文地址】
今日新闻 |
推荐新闻 |