提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

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

问题 总结 出现 元素 覆盖 定理 行列 运筹学
2023-06-13 09:17:49 时间

文章目录

一、克尼格定理

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

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

克尼格定理 :

分配问题 效率矩阵

[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

任务是否是最优的 ;

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

三、指派问题求解步骤

指派问题求解步骤 :

1 . 使行列出现

0

元素 : 指派问题系数矩阵

(c_{ij})

变换为

(b_{ij})

系数矩阵 , 在

(b_{ij})

矩阵中 每行 每列 都出现

0

元素 ;

  • 每行都出现
0

元素 :

(c_{ij})

系数矩阵中 , 每行都 减去该行最小元素 ;

  • 每列都出现
0

元素 : 在上述变换的基础上 , 每列元素中 减去该列最小元素 ;

注意必须先变行 , 然后再变列 , 行列不能同时进行改变 ; 否则矩阵中会出现负数 , 该矩阵中 不能出现负数 ;

2 . 试指派 : 进行尝试指派 , 寻求最优解 ;

在

(b_{ij})

系数矩阵 中找到尽可能多的 独立

0

元素 , 如果能找到

n

个独立

0

元素 , 以这

n

个独立

0

元素对应解矩阵

(x_{ij})

中的元素为

1

, 其余元素为

0

, 这样就得到最优解 ;

四、匈牙利法示例 1

1、第一步 : 使行列出现

0

元素示例

上一篇博客 【运筹学】匈牙利法 ( 克尼格定理 | 匈牙利法引入 ) 中的指派问题 :

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

系数矩阵

(c_{ij}) =\begin{bmatrix} & 6 & 7 & 11 & 2 & \\\\ & 4 & 5 & 9 & 8 & \\\\ & 3 & 1 & 10 & 4 & \\\\ & 5 & 9 & 8 & 2 & \\ \end{bmatrix}

使每行都出现

0

元素 :

(c_{ij})

系数矩阵中 , 每行都 减去该行最小元素 ;

第

1

行减去

2

, 第

2

行减去

4

, 第

3

行减去

1

, 第

4

行减去

2

,

得到新的系数矩阵 系数矩阵

\begin{bmatrix} & 4 & 5 & 9 & 0 & \\\\ & 0 & 1 & 5 & 4 & \\\\ & 2 & 0 & 9 & 3 & \\\\ & 3 & 7 & 6 & 0 & \\ \end{bmatrix}

每列都出现

0

元素 : 在上述变换的基础上 , 每列元素中 减去该列最小元素 ; 观察矩阵后发现 , 只有第三列没有

0

元素 , 这里将第

3

列 , 都减去最小值

5

, 得到如下矩阵 :

(b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 3 & 7 & 1 & 0 & \\ \end{bmatrix}

这样就得到每行每列都有

0

元素的矩阵 ;

2、第二步 : 试指派操作示例 ( 方法一 :克尼格定理 )

在 【运筹学】匈牙利法 ( 匈牙利法步骤 | 第一步 : 使行列出现 0 元素示例 ) 博客示例基础上 , 已经得到了行列都有

0

元素的系数矩阵 :

(b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 3 & 7 & 1 & 0 & \\ \end{bmatrix}

下面进行试指派操作 , 试指派就是找独立

0

元素 , 独立

0

元素就是位于不同行不同列的

0

元素 ;

第

1

行只有

1

个

0

, 选第

4

个 ; 每行每列只能选择

1

个 , 第

4

行第

4

列的

0

元素就不能再用了 ;

第

3

行只有

1

个

0

, 选第

2

个 ;

第

2

行有

2

个

0

, 都可以选择 , 这里选择第

1

个 ;

最终试指派结果 :

上面只找到了

3

个独立的

0

元素 , 应该找出

4

个独立

0

元素 ;

调整上述系数矩阵

(b_{ij})

, 每行每列同时增加或减去一个数 , 且不能出现负数 ;

第

4

行都减去

1

, 得到如下矩阵 :

(b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 2 & 6 & 0 & -1 & \\ \end{bmatrix}

第

4

行第

4

列出现了

-1

, 这里在将第

4

列都加上

1

, 得到如下矩阵 :

(b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 1 & \\\\ & 0 & 1 & 0 & 5 & \\\\ & 2 & 0 & 4 & 4 & \\\\ & 2 & 6 & 0 & 0 & \\ \end{bmatrix}

第一行此时没有独立的

0

了 , 第一行再减去

1

, 得到如下矩阵 :

(b_{ij}) = \begin{bmatrix} & 3 & 4 & 3 & 0 & \\\\ & 0 & 1 & 0 & 5 & \\\\ & 2 & 0 & 4 & 4 & \\\\ & 2 & 6 & 0 & 0 & \\ \end{bmatrix}

再次进行试指派 , 找到了如下独立

0

元素 ;

在上述没有找到

4

个独立

0

元素后 , 由于在第

4

行没有找到

0

元素 , 开始从第

4

行进行调整 ,

调整时将非

0

的最小值转为

0

, 这样本行就多出一个

0

, 以及负数 , 负数有需要再对应列加上一个值 , 保持矩阵中所有的值都是非负的 ;

3、打 √ ( 方法二 : 直线覆盖 )

分析 【运筹学】匈牙利法 ( 匈牙利法步骤 | 第二步 : 试指派操作示例 ) 博客中试指派调整矩阵的原理 ;

下面的矩阵是完成第一步操作后 , 得到的行列都有

0

的元素的系数矩阵

(b_{ij})

:

(b_{ij}) = \begin{bmatrix} & 4 & 5 & 4 & 0 & \\\\ & 0 & 1 & 0 & 4 & \\\\ & 2 & 0 & 4 & 3 & \\\\ & 3 & 7 & 1 & 0 & \\ \end{bmatrix}

试指派后的结果如下 :

定位一个没有独立

0

元素的行 : 先对没有

0

元素的行打钩 √ : 第

4

行没有独立

0

元素 , 第

4

行打 √ ;

讨论第

4

行 : 第

4

行没有独立的

0

元素 , 但是有废弃的

0

元素 , 因为在第一步已经保证了每行每列都有

0

元素 ;

在第

4

行

0

元素所在列 , 即第

4

列 , 打 √ ;

讨论第

4

列 : 上述打钩的列中 , 查看是否有 独立的

0

元素 , 如果有对应的行就打 √ ;

第

1

行有独立的

0

元素 , 在第

1

行位置打 √ ;

讨论第

1

行 : 查看第

1

行是否有废弃的

0

元素 , 如果有就继续打 √ , 如果没有就停止 ;

第

1

行没有废弃的

0

元素 , 直接停止 ;

讨论 行 的时候讨论的是 废弃的

0

元素 ,

讨论 列 的时候讨论的是 独立的

0

元素 ;

4、直线覆盖 ( 方法二 : 直线覆盖 )

打 √ 完毕 , 开始讨论覆盖 ,

没有 打 √ 的行划线 , 打 √ 的列划线 , 三条线就将所有的

0

元素覆盖了 ,

在没有被覆盖的元素中 , 找最小的元素

1

, 将没有覆盖的行

-1

, 覆盖的列

+1

; 这里的情况是没有覆盖的行 ;

第

1,4

行

-1

, 第

4

列

+1

;

最终得到如下矩阵 :

(b_{ij}) = \begin{bmatrix} & 3 & 4 & 3 & 0 & \\\\ & 0 & 1 & 0 & 5 & \\\\ & 2 & 0 & 4 & 4 & \\\\ & 2 & 6 & 0 & 0 & \\ \end{bmatrix}

五、匈牙利法示例 2

四人分别完成四项工作所用时间 :

A A A

B B B

C C C

D D D

甲

2 2 2

15 15 15

13 13 13

4 4 4

乙

10 10 10

4 4 4

14 14 14

15 15 15

丙

9 9 9

14 14 14

16 16 16

13 13 13

丁

7 7 7

8 8 8

11 11 11

9 9 9

A
B
C
D

甲

2
15
13
4

乙

10
4
14
15

丙

9
14
16
13

丁

7
8
11
9

1、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )

先写出指派问题的系数矩阵 :

(c_{ij}) =\begin{bmatrix} & 2 & 15 & 13 & 4 & \\\\ & 10 & 4 & 14 & 15 & \\\\ & 9 & 14 & 16 & 13 & \\\\ & 7 & 8 & 11 & 9 & \\ \end{bmatrix}

使每行都出现

0

元素 :

(c_{ij})

系数矩阵中 , 每行都 减去该行最小元素 ;

  • 第
1

行减去最小值

2

;

  • 第
2

行减去最小值

4

;

  • 第
3

行减去最小值

9

;

  • 第
4

行减去最小值

7

;

(c_{ij}') =\begin{bmatrix} & 0 & 13 & 11 & 2 & \\\\ & 6 & 0 & 10 & 11 & \\\\ & 0 & 5 & 7 & 4 & \\\\ & 0 & 1 & 4 & 2 & \\ \end{bmatrix}

此时发现有两列 , 第

4

列 , 第

5

列 , 没有

0

元素 , 这两列每列都减去最小值 :

  • 第
3

列减去最小值

4

;

  • 第
4

列减去最小值

2

;

最终得到行列都有

0

元素的系数矩阵

(b_{ij})

:

(b_{ij}) =\begin{bmatrix} & 0 & 13 & 7 & 0 & \\\\ & 6 & 0 & 6 & 9 & \\\\ & 0 & 5 & 3 & 2 & \\\\ & 0 & 1 & 0 & 0 & \\ \end{bmatrix}

2、第二步 : 试指派 ( 找独立 0 元素 )

基于上一步的行列都有

0

元素的系数矩阵 ,

(b_{ij}) =\begin{bmatrix} & 0 & 13 & 7 & 0 & \\\\ & 6 & 0 & 6 & 9 & \\\\ & 0 & 5 & 3 & 2 & \\\\ & 0 & 1 & 0 & 0 & \\ \end{bmatrix}

进行试指派 ;

找出每行的独立

0

元素 ,

优先从唯一选择开始 ,

第

2

行只有

1

个

0

元素 , 该元素是独立

0

元素 ;

第

3

行只有

1

个

0

元素 , 该元素是独立

0

元素 ( 红色矩形框 ) , 位于第

1

列 ; 同时第

1

列中的其它

0

元素标记为 废弃

0

元素 ( 绿色矩形框 );

第

1

行和第

4

行都有多个

0

元素 ;

然后从列里面找独立

0

元素 , 第

1

列 和 第

2

列都已经找到了

0

元素 , 这里看 第

3

列 和 第

4

列 ;

第

3

列有 独立

0

元素 ( 红色矩形框 ) ; 位于第

4

行 , 将第

4

行的其它

0

元素标记为 废弃

0

元素 ( 绿色矩形框 ) ;

第

4

列有 独立

0

元素 ( 红色矩形框 ) ; 位于第

1

行 , 将第

1

行的其它

0

元素标记为 废弃

0

元素 ( 绿色矩形框 ) , 已经标记过了 , 不用再进行标记 ;

这里第一次指派就找到了最优解 ;

六、匈牙利法示例 3

1、使用匈牙利法求解下面的指派问题

四人分别完成四项工作所用时间 :

A A A

B B B

C C C

D D D

甲

7 7 7

15 15 15

13 13 13

4 4 4

乙

9 9 9

4 4 4

14 14 14

15 15 15

丙

8 8 8

14 14 14

16 16 16

13 13 13

丁

7 7 7

8 8 8

11 11 11

9 9 9

戊

4 4 4

8 8 8

11 11 11

9 9 9

A
B
C
D

甲

7
15
13
4

乙

9
4
14
15

丙

8
14
16
13

丁

7
8
11
9

戊

4
8
11
9

2、第一步 : 变换系数矩阵 ( 每行每列都出现 0 元素 )

先写出指派问题的系数矩阵 :

(c_{ij}) =\begin{bmatrix} & 7 & 5 & 9 & 8 & 11 & \\\\ & 9 & 12 & 7 & 11 & 9 & \\\\ & 8 & 5 & 4 & 6 & 9 & \\\\ & 7 & 3 & 6 & 9 & 6 & \\\\ & 4 & 6 & 7 & 5 & 11 & \\ \end{bmatrix}

使每行都出现

0

元素 :

(c_{ij})

系数矩阵中 , 每行都 减去该行最小元素 ;

  • 第
1

行减去最小值

5

;

  • 第
2

行减去最小值

7

;

  • 第
3

行减去最小值

4

;

  • 第
4

行减去最小值

3

;

  • 第
5

行减去最小值

4

;

(c_{ij}') =\begin{bmatrix} & 2 & 0 & 4 & 3 & 6 & \\\\ & 2 & 5 & 0 & 4 & 2 & \\\\ & 4 & 1 & 0 & 2 & 5 & \\\\ & 4 & 0 & 3 & 6 & 3 & \\\\ & 0 & 2 & 3 & 1 & 7 & \\ \end{bmatrix}

此时发现有两列 , 第

4

列 , 第

5

列 , 没有

0

元素 , 这两列每列都减去最小值 :

  • 第
4

列减去最小值

1

;

  • 第
5

列减去最小值

2

;

最终得到行列都有

0

元素的系数矩阵

(b_{ij})

:

(b_{ij}) =\begin{bmatrix} & 2 & 0 & 4 & 2 & 4 & \\\\ & 2 & 5 & 0 & 3 & 0 & \\\\ & 4 & 1 & 0 & 1 & 3 & \\\\ & 4 & 0 & 3 & 5 & 1 & \\\\ & 0 & 2 & 3 & 0 & 5 & \\ \end{bmatrix}

3、第二步 : 试指派 ( 找独立 0 元素 )

基于上一步的行列都有

0

元素的系数矩阵 ,

(b_{ij}) =\begin{bmatrix} & 2 & 0 & 4 & 2 & 4 & \\\\ & 2 & 5 & 0 & 3 & 0 & \\\\ & 4 & 1 & 0 & 1 & 3 & \\\\ & 4 & 0 & 3 & 5 & 1 & \\\\ & 0 & 2 & 3 & 0 & 5 & \\ \end{bmatrix}

进行试指派 ;

找出每行的独立

0

元素 ,

优先从唯一选择开始 ,

第

1

行只有

1

个

0

元素 , 该元素是独立

0

元素 ( 红色矩形框 ) , 位于第

2

列 ;

同时第

2

列中的其它

0

元素标记为 废弃

0

元素 ( 绿色矩形框 );

第

3

行只有

1

个

0

元素 , 该元素是独立

0

元素 ( 红色矩形框 ) , 位于第

3

列 ;

同时第

3

列中的其它

0

元素标记为 废弃

0

元素 ( 绿色矩形框 );

第

2

行中原来有两个

0

元素 , 有一个被标记为 废弃

0

元素 , 因此只剩下一个

0

元素 , 标记为独立

0

元素 ;

第

4

行没有独立

0

元素 , 第

5

行都有多个

0

元素 ;

然后从列里面找独立

0

元素 , 第

2,3,5

列都已经找到了

0

元素 , 这里看 第

1,4

列 ;

第

1

列有 独立

0

元素 ( 红色矩形框 ) ; 位于第

5

行 , 将第

5

行的其它

0

元素标记为 废弃

0

元素 ( 绿色矩形框 ) ;

这里只找到了

4

个独立

0

元素 , 红色矩形框中 ;

使用最少的直线 , 覆盖所有的

0

元素 ;

4、第二步 : 试指派 ( 打 √ )

本步骤的目的是使用最少的直线 , 将所有的

0

元素都覆盖住 , 如果能一眼看出来最好 , 如果不能 , 就需要使用打钩的方法 ;

定位一个没有独立

0

元素的行 : 先对没有

0

元素的行打钩 √ : 第

4

行没有独立

0

元素 , 第

4

行打 √ ;

讨论第

4

行 : 第

4

行没有独立的

0

元素 , 但是有废弃的

0

元素 , 因为在第一步已经保证了每行每列都有

0

元素 ;

在第

4

行 的 废弃

0

元素所在列 , 即第

2

列 , 打 √ ;

讨论第

2

列 : 上述打钩的列中 , 查看是否有 独立的

0

元素 , 如果有对应的行就打 √ ;

第

1

行有独立的

0

元素 , 在第

1

行位置打 √ ;

讨论第

1

行 : 查看第

1

行是否有废弃的

0

元素 , 如果有就继续打 √ , 如果没有就停止 ;

第

1

行没有废弃的

0

元素 , 直接停止 ;

讨论 行 的时候讨论的是 废弃的

0

元素 ,

讨论 列 的时候讨论的是 独立的

0

元素 ;

5、第二步 : 试指派 ( 直线覆盖 )

本步骤的目的是使用最少的直线 , 将所有的

0

元素都覆盖住 , 如果能一眼看出来最好 , 如果不能 , 就需要使用打钩的方法 ;

打 √ 完毕 , 开始讨论覆盖 ,

没有 打 √ 的行划线 , 打 √ 的列划线 , 四条线就将所有的

0

元素覆盖了 ,

在没有被覆盖的元素中 , 找最小的元素

1

, 将该元素所在的没有覆盖的行

-1

, 覆盖的列

+1

;

第

1, 4

行中的元素

-1

, 第

2

列中的元素

+1

;

最终得到如下矩阵 :

(b_{ij}) =\begin{bmatrix} & 1 & 0 & 3 & 1 & 3 & \\\\ & 2 & 6 & 0 & 3 & 0 & \\\\ & 4 & 2 & 0 & 1 & 3 & \\\\ & 3 & 0 & 2 & 4 & 0 & \\\\ & 0 & 3 & 3 & 0 & 5 & \\ \end{bmatrix}

本质 : 没有覆盖的元素统一减去最小值 , 被覆盖的行列交叉值增加了该最小元素值 ;

6、第二步 : 试指派 ( 第二轮 )

再次进行试指派此时发现 , 试指派还是

4

个独立

0

元素 ,

先找有独立

0

元素的行 , 找到后 标记为 独立

0

元素 ( 红色矩形框 ) , 将对应列的

0

元素标记为废弃 ( 绿色矩形框 ) ;

然后找有独立

0

元素的列 ;

再次执行 打 √ ,

没有

0

元素的行为起点 :

将该行废弃

0

元素列打钩 , 有两个 :

将废弃

0

元素列中对应的 独立

0

元素 行 打钩 :

上述两行对应的 废弃

0

元素的列打钩 :

在上述打钩的列中 , 将独立

0

元素所在行打钩 :

直线覆盖 : 没打勾的行画一条直线 , 打钩的列画一条直线 ; 目的是使用最少的直线覆盖住所有的

0

;

在没有被覆盖的元素中 , 找最小的元素

1

, 将该最小元素所在的没有覆盖的行

-1

, 覆盖的列

+1

;

第

1, 2,3,4

行中的元素

-1

, 第

2,3,4

列中的元素

+1

;

最终矩阵为 :

(b_{ij}) =\begin{bmatrix} & 0 & 0 & 3 & 0 & 3 & \\\\ & 1 & 6 & 0 & 2 & 0 & \\\\ & 3 & 2 & 0 & 0 & 3 & \\\\ & 2 & 0 & 2 & 3 & 0 & \\\\ & 0 & 4 & 4 & 0 & 6 & \\ \end{bmatrix}

本质 : 没有覆盖的元素统一减去最小值 , 被覆盖的行列交叉值增加了该最小元素值 ;

这个矩阵

0

很多 , 选出

5

个独立

0

元素 , 成立的解有好多个 ;

如下指派 , 正好能找出

5

个独立

0

元素 ;

相关文章