【运筹学】匈牙利法 ( 匈牙利法步骤 | 第一步 : 使行列出现 0 元素示例 )

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

文章目录

  • 一、指派问题求解步骤
  • 二、第一步 : 使行列出现
0

元素示例

一、指派问题求解步骤

指派问题求解步骤 :

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

, 这样就得到最优解 ;

二、第一步 : 使行列出现

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

元素的矩阵 ;

博客 基础

0 人点赞