【运筹学】匈牙利法 ( 克尼格定理 | 匈牙利法引入 )

2023-03-28 20:51:09 浏览数 (1)

文章目录

  • 一、克尼格定理
  • 二、匈牙利法引入

一、克尼格定理

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

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

克尼格定理 :

分配问题 效率矩阵

[a_{ij}]

中 ,

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

u_i

,

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

v_j

,

得到新的效率矩阵

[b_{ij}]

,

两个效率矩阵

[a_{ij}]

与

[b_{ij}]

分配问题的 最优解相同 ;

克尼格定理示例 : 指派问题 , 给

4

个人指派

4

个岗位 , 每个人在不同的岗位产生的利润不同 , 如何安排使得利润最高 ;

​

A A A

B B B

C C C

D D D

甲

85 85 85

92 92 92

73 73 73

90 90 90

乙

95 95 95

87 87 87

78 78 78

95 95 95

丙

82 82 82

83 83 83

79 79 79

90 90 90

丁

86 86 86

90 90 90

80 80 80

88 88 88

A
B
C
D

甲

85
92
73
90

乙

95
87
78
95

丙

82
83
79
90

丁

86
90
80
88

给 甲 对应的行加上所有表格都加上

5

, 变为如下表格 ,

​

A A A

B B B

C C C

D D D

甲

90 90 90

97 97 97

78 78 78

95 95 95

乙

95 95 95

87 87 87

78 78 78

95 95 95

丙

82 82 82

83 83 83

79 79 79

90 90 90

丁

86 86 86

90 90 90

80 80 80

88 88 88

A
B
C
D

甲

90
97
78
95

乙

95
87
78
95

丙

82
83
79
90

丁

86
90
80
88

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

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

二、匈牙利法引入

给 甲乙丙丁 四人分配

ABCD

四项工作 , 每人做每项工作的耗时如下 , 如何指派问题使得耗时最小 ;

​

A A A

B B B

C C C

D D D

甲

6 6 6

7 7 7

11 11 11

2 2 2

乙

4 4 4

5 5 5

9 9 9

8 8 8

丙

3 3 3

1 1 1

10 10 10

4 4 4

丁

5 5 5

9 9 9

8 8 8

2 2 2

A
B
C
D

甲

6
7
11
2

乙

4
5
9
8

丙

3
1
10
4

丁

5
9
8
2

分派任务时 , 给每个人分配其所用时间最小的工作 ,

  • 给 甲 分配
D

任务 , 其只用 2 时间即可完成该任务 , 耗时最小 ;

  • 给 乙 分配
A

任务 , 其只用 4 时间即可完成该任务 , 耗时最小 ;

  • 给 丙 分配
B

任务 , 其只用 1 时间即可完成该任务 , 耗时最小 ;

  • 给 丁 分配
C

任务 ,

ABD

任务已经分配给了其它人 , 只能给 丁 分配

C

任务 ;

如果 为每个人选择了耗时最小的任务 , 正好位于不同行 , 不同列 , 那么当前的指派 , 就是该问题的 最优解 ;

但是上述示例中 , 给 丁 分配任务时 , 合适的任务都分配给了甲乙丙 , 只能分配

C

任务 ;

这时就需要讨论给 丁 指派

C

任务是否是最优的 ;

这里就需要 引入 匈牙利法 解决上述问题 ;

表格 博客 工作 效率

0 人点赞