【运筹学】指派问题、匈牙利法总结 ( 指派问题 | 克尼格定理 | 匈牙利法 | 行列出现 0 元素 | 试指派 | 打 √ | 直线覆盖 ) ★★★

文章目录

• 一、克尼格定理
• 二、匈牙利法引入
• 三、指派问题求解步骤
• 四、匈牙利法示例 1
• • 1、第一步 : 使行列出现 $0$ 元素示例
  • 2、第二步 : 试指派操作示例 ( 方法一 :克尼格定理 )
  • 3、打 √ ( 方法二 : 直线覆盖 )
  • 4、直线覆盖 ( 方法二 : 直线覆盖 )
• 五、匈牙利法示例 2
• • 1、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )
  • 2、第二步 : 试指派 ( 找独立 0 元素 )
• 六、匈牙利法示例 3
• • 1、使用匈牙利法求解下面的指派问题
  • 2、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )
  • 3、第二步 : 试指派 ( 找独立 0 元素 )
  • 4、第二步 : 试指派 ( 打 √ )
  • 5、第二步 : 试指派 ( 直线覆盖 )
  • 6、第二步 : 试指派 ( 第二轮 )

一、克尼格定理

匈牙利法 主要用于解决指派问题 , 其主要依据是 克尼格定理 ;

指派问题 参考 【运筹学】整数规划 ( 整数规划求解方法 | 指派问题 ) 博客 ;

克尼格定理 :

分配问题 效率矩阵 $[a_{ij}]$ 中 ,

每一行元素 中加上或减去一个常数 $u_i$ ,

每一列元素 中加上或减去一个常数 $v_j$ ,

得到新的效率矩阵 $[b_{ij}]$ ,

两个效率矩阵 $[a_{ij}]$ 与 $[b_{ij}]$ 分配问题的 最优解相同 ;

克尼格定理示例 : 指派问题 , 给 $4$ 个人指派 $4$ 个岗位 , 每个人在不同的岗位产生的利润不同 , 如何安排使得利润最高 ;

给 甲 对应的行加上所有表格都加上 $5$ , 变为如下表格 ,

甲 今天状态好 , 不管四个工作 , 哪个分配给 甲 , 其产生的利润都会增加 ;

最终计算出来的指派问题的最优解是不变的 ;

二、匈牙利法引入

给 甲乙丙丁 四人分配 $ABCD$ 四项工作 , 每人做每项工作的耗时如下 , 如何指派问题使得耗时最小 ;