当前位置:首页 >> 经济学 >>

第五讲 分配问题(指派问题)与匈牙利法


分配问题(指派问题) 第5讲 分配问题(指派问题)与匈牙利法

分配问题的提出

分配问题的提出
若干项工作或任务需要若干个人去完成 由于每人的知识、 若干项工作或任务需要若干个人去完成。由于每人的知识、 工作或任务需要若干个人去完成。 能力、经验的不同, 能力、经验的不同,故各人完成不同任务所需要的时间不同 (或其他资源)。 或其他资源) 问: 应指派哪个人完成何项工作,可使完成所有工作所消 应指派哪个人完成何项工作, 可使完成所有工作所消 耗的总资源最少? 耗的总资源最少?

分配问题的提出
设某公司准备派 n 个工人 x1,x2, …, xn 时间为cij (i,j=1,2,…,n)。 现问: 如何确定一个分派工人去工作的方案, 现问 : 如何确定一个分派工人去工作的方案 , 使 得工人们完成工作的总时间为最少。 得工人们完成工作的总时间为最少。 总时间为最少
还比如: 还比如:
, 去作

n

件工作 y1,y2,…,yn。已知工人xi完成工作 yj 所需

n台机床加工n 项任务; n 条航线有n 艘船去航行等。

整体解题思路总结
例题: 例题: 单位: 单位:小时

工作1 工作 工作2 工作 工作3 工作 工作4 工作 工作5 工作

工作者 工作者 工作者 工作者 工作者 1 2 3 4 5 4 8 7 15 12 7 9 17 14 10 6 9 12 8 7 6 7 14 6 10 6 9 12 10 6

标准形式的分配问题

标准形式的分配问题
设某公司准备派 n 个工人 x1 , x2 , … , xn (i,j=1,2,…,n)。 现问:如何确定一个分派工人去工作的方案, 使得工人们 现问 : 如何确定一个分派工人去工作的方案, 完成工作的总时间为最少。 完成工作的总时间为最少。 总时间为最少
, 去作

n 件工作

y1 , y2 , … , yn 。 已 知 工 人 xi 完 成 工 作 yj 所 需 时 间 为 cij

分派方案满足下述两个条件: 分派方案满足下述两个条件:
1.任一个工人都不能去做两件或两件以上的工作 1.任一个工人都不能去做两件或两件以上的工作 2.任一件工作都不能同时接受两个及以上的工人去做 2.任一件工作都不能同时接受两个及以上的工人去做

标准形式的分配问题
n个人 个人 n件事 件事

每件事 每件事必有且只有一个人去做 每个人 每个人必做且只做一件事

数学模型
n个人 个人 n件事 件事
cij:第i人做第 事的费用 人做第j事的费用 人做第 1 若指派第 人做第 事 若指派第i人做第 人做第j事 xij=

时间、原料、 时间、原料、 金钱等资源

i,j=1,...,n ,=

0 若指派第 人不做第 事 若指派第i人不做第 人不做第j事

总费用: 总费用:

∑∑ cij xij
i =1 j =1

n

n

每件事 每件事必有且只有一个人去做 每个人 每个人必做且只做一件事

∑x

n

∑x
j =1

i =1 n

ij

= 1 j=1,...,n =
= = 1 i=1,...,n

ij

数学模型
min z = ∑∑ cij xij
i =1 j =1 n n

∑x
i =1
n

n

ij

=1
=1

j=1,...,n = i=1,...,n =

s.t.

∑x
j =1

ij

xij = 0或1 i,j = 1,2 ,...,n

线性规划问题

0-1型整数规划问题 型整数规划问题 运输问题

匈牙利法 匈牙利法
1955年由美国数学家 W kuhn(库恩 提出, 库恩) 1955 年由美国数学家W.W.kuhn( 库恩 ) 提出 , 利用了 年由美国数学家 匈牙利数学家D Konig(康尼格 证明的2个定理。 康尼格) 匈牙利数学家D.Konig(康尼格)证明的2个定理。

? c11 c12 ?c ? 21 c22 C= ? ... ... ? ?cn1 cn1

... c1n ? ? ... c2 n ? ... ... ? ? ... cnn ?

? x11 ?x X = ? 21 ? ... ? ? xn1

x12 x22 ... xn1

... x1n ? ... x2 n ? ? ... ... ? ? ... xnn ?

系数矩阵
(效率矩阵 效率矩阵) 效率矩阵

解矩阵

n个人 个人 n件事 件事

(决策变量矩 决策变量矩 阵)

在系数矩阵C中 处在不同行不同列的一 定义:在系数矩阵 中,处在不同行不同列的一 组零元素, 称为独立零元素组 独立零元素组, 组零元素 , 称为 独立零元素组 , 其中每个元素 称为独立零元素 独立零元素。 称为独立零元素。
?5 ?2 C=? ?0 ? ?4 ?0 ?0 X =? ?1 ? ?0 0 2 0? 3 0 0? ? 5 6 7? ? 8 0 0? 1 0 0? ? 0 0 1? 0 0 0? ? 0 1 0?

{c12 , c24 , c31 , c43 } {c12 , c23 , c31 , c44 } {c14 , c23 , c31 , c44 }
最优解
min z = ∑∑ cij xij
i =1 j =1 n n

相关定理

使每行每列 都出现零元素

定理: 将分配问题系数矩阵的每一行 每一列分别 每一行及 定理:若将分配问题系数矩阵的每一行及每一列分别 减去各行及各列的最小元素, 各行及各列的最小元素 减去各行及各列的最小元素,则新分配问题与原分配 问题有相同的最优解,只有最优值差一常数。 问题有相同的最优解,只有最优值差一常数。 相同的最优解
时 工作 间 人员 时 工作 间 C 人员

A 7 9 8

B 8 12 5

A 0 5 4

B 0 1 7 8 0 1

C 2 0 0

甲 乙 丙

9 甲 4 乙 4 丙

步骤1:变换系数矩阵,使其每行每列都出现0元素 步骤 :变换系数矩阵,使其每行每列都出现 元素
把各行元素分别减去本行元素的最小值,然后在此基础上 把各行 元素分别减去本行元素的最小值, 然后在此基础上 再把每列元素减去本列中的最小值。 再把每列元素减去本列中的最小值。

min

?4 ? ?7 ?6 ? ?6 ?6 ?

8 7 15 12 ? 4 ? 0 4 3 11 8 ? ? 0 3 0 11 8 ? ? ? ? ? ? 9 17 14 10 ? 7 ? 0 2 10 7 3 ? ?0 1 7 7 3 ? 9 12 8 7 ? 6 ? ? 0 3 6 2 1 ? ? ? 0 2 3 2 1 ? ? ? ? ? ? 7 14 6 10 ? 6 ?0 1 8 0 4 ? ? 0 0 5 0 4? ? ?0 3 6 4 0 ? ? 0 2 3 4 0? 9 12 10 6 ? 6 ? ? ? ? min 0 1 3 0 0
此时每行及每列中肯定都有0元素 此时每行及每列中肯定都有 元素

步骤2:进行试分配,判断是否存在n个独立零元素 步骤 :进行试分配,判断是否存在 个独立零元素
尝试对所有零元素做标记,确定独立零元素。 尝试对所有零元素做标记,确定独立零元素。 标记 独立零元素

(1)逐行检验 )
只有一个未标记的零元素的行 未标记的零元素的 记号O将该零元素圈起 将该零元素圈起, 对只有一个未标记的零元素的行,用记号 将该零元素圈起,然后 被圈起的零元素所在列的其他未标记的零元素用记号/划去 的其他未标记的零元素 划去。 将被圈起的零元素所在列的其他未标记的零元素用记号 划去。 重复行检验,直到每一行都没有未被标记的零元素或 每一行都没有未被标记的零元素 重复行检验,直到每一行都没有未被标记的零元素或至少有两个未 被标记的零元素为止 的零元素为止。 被标记的零元素为止。

表示此事已不能由 其他人来做 此人已不能做其他事) (此人已不能做其他事)

? 0 13 7 0 ? ?6 0 6 9 ? ? ? ?0 5 3 2? ? ? ?0 1 0 0 ?

表示此人只能做该事 此事只能由该人做) (此事只能由该人做)

步骤2:进行试分配,判断是否存在n个独立零元素 步骤 :进行试分配,判断是否存在 个独立零元素
尝试对所有零元素做标记,确定独立零元素。 尝试对所有零元素做标记,确定独立零元素。 标记 独立零元素

(2)逐行检验 )

?0 ? ?0 ?0 ? ?0 ?0 ?

3 0 11 8 ? ? 1 7 7 3? ? 2 3 2 1 ? 0 5 0 4? ? 2 3 4 0?
圈0即独立零元素 即独立零元素

步骤2:进行试分配,判断是否存在n个独立零元素 步骤 :进行试分配,判断是否存在 个独立零元素
尝试对所有零元素做标记,确定独立零元素。 尝试对所有零元素做标记,确定独立零元素。 标记 独立零元素

(2)逐列检验 )
与行检验类似:对只有一个未标记的零元素的列 用记号O将该 与行检验类似:对只有一个未标记的零元素的列,用记号 将该 零元素圈起,然后将被圈起的零元素所在行 零元素圈起,然后将被圈起的零元素所在行的其他未标记的零元 素用记号/划去 划去。 素用记号 划去。 重复列检验,直到没有未被标记的零元素或至少有两个未被标记 没有未被标记的零元素 重复列检验,直到没有未被标记的零元素或 的零元素为止。 的零元素为止。

? 0 13 7 0 ? ?6 0 6 9 ? ? ? ?0 5 3 2? ? ? ?0 1 0 0 ?

步骤2:进行试分配,判断是否存在n个独立零元素 步骤 :进行试分配,判断是否存在 个独立零元素
尝试对所有零元素做标记,确定独立零元素。 尝试对所有零元素做标记,确定独立零元素。 标记 独立零元素

(2)逐列检验 )

?0 ? ?0 ?0 ? ?0 ?0 ?

3 0 11 8 ? ? 1 7 7 3? ? 2 3 2 1 ? 0 5 0 4? ? 2 3 4 0?
圈0即独立零元素 即独立零元素

独立零元素的个数 (3)判断独立零元素的个数 )判断独立零元素

可能出现三种情况

1.每一行均有圈 出现,圈0的个数恰好等于 每一行均有圈0出现 的个数恰好等于n 每一行均有圈 出现, 的个数恰好等于 2.存在未标记过的零元素, 但它们所在的行和列中 , 未被标 存在未标记过的零元素, 存在未标记过的零元素 但它们所在的行和列中, 记过的零元素的个数均至少有两个。 记过的零元素的个数均至少有两个。 3.不存在未被标记过的零元素,但圈 的个数 不存在未被标记过的零元素, 的个数<n 不存在未被标记过的零元素 但圈0的个数 可进行分配:令圈0位置的决策变量取值为1,其他为 位置的决策变量取值为 ,其他为0 可进行分配: 位置的决策变量取值

? 0 13 7 0 ? ?6 0 6 9 ? ? ? ?0 5 3 2? ? ? ?0 1 0 0 ?

?0 ?0 ? ?1 ? ?0

0 0 1? ? 1 0 0? 0 0 0? ? 0 1 0?

独立零元素的个数 (3)判断独立零元素的个数 )判断独立零元素

可能出现三种情况

2.存在未标记过的零元素, 但它们所在的行和列中 , 未被标 存在未标记过的零元素,但它们所在的行和列中, 存在未标记过的零元素 记过的零元素的个数均至少有两个。 记过的零元素的个数均至少有两个。 3.不存在未被标记过的零元素,但圈 的个数 不存在未被标记过的零元素, 的个数<n 不存在未被标记过的零元素 但圈0的个数 从某行 两个未被标记过的零元素中任选一个加上 未被标记过的零元素中任选一个加上圈 从某行(列)的两个未被标记过的零元素中任选一个加上圈, 然后给同 的其他未被标记的零元素都加/, 然后给同列、同行的其他未被标记的零元素都加 ,然后再 进行行、列检验,可能出现情况1或3。 进行行、列检验,可能出现情况 或 。
圈0个数等于n=5 个数等于 个数等于

?5 0 2 0 ?2 3 0 0 ? ? 0 10 5 7 ? ?9 8 0 0 ?0 6 3 6 ?

9? 8? ? 5? ? 4? 0? ?

?0 ?0 ? ?1 ? ?0 ?0 ?

1 0 0 0? 0 1 0 0? ? 0 0 0 0? ? 0 0 1 0? 多重最优解 0 0 0 1? ?

?5 0 2 0 ?2 3 0 0 ? ? 0 10 5 7 ? ?9 8 0 0 ?0 6 3 6 ?

9? 8? ? 5? ? 4? 0? ?

?5 0 2 0 ?2 3 0 0 ? ? 0 10 5 7 ? ?9 8 0 0 ?0 6 3 6 ? ?5 0 2 0 ?2 3 0 0 ? ? 0 10 5 7 ? ?9 8 0 0 ?0 6 3 6 ?

9? 8? ? 5? ? 4? 0? ? 9? 8? ? 5? ? 4? 0? ?

独立零元素的个数 (3)判断独立零元素的个数 )判断独立零元素

可能出现三种情况

3.不存在未被标记过的零元素,但圈0的个数 不存在未被标记过的零元素,但圈 的个数 的个数<n 不存在未被标记过的零元素

作 最少直线覆盖当前所有零元素, 便 最少直线覆盖当前所有零元素 , 于下步增加独立零元素的个数。 于下步增加独立零元素的个数。
个数4 圈0个数 < n=5 个数

?0 ? ?0 ?0 ? ?0 ?0 ?

3 0 11 8 ? ? 1 7 7 3? 2 3 2 1? ? 0 5 0 4? 2 3 4 0? ?

定理:系数矩阵C中独立零元素的最多个数等于 等于能覆 定理:系数矩阵 中独立零元素的最多个数等于能覆
盖所有零元素的最少线数。 最少线数 盖所有零元素的最少线数。
由匈牙利数学家D.Konig(康尼格 所证明 康尼格)所证明 由匈牙利数学家 康尼格

例:分别求下列矩阵中的独立零元素的最多个数。 分别求下列矩阵中的独立零元素的最多个数。

?5 ?2 ? ?0 ? ?4
独立零元素 的个数最多: 的个数最多:

0 2 0? ? 3 0 0? 5 6 7? ? 8 0 0?

?5 0 2 0 ?2 3 0 0 ? ? 0 10 5 7 ? ?9 8 0 0 ?0 6 3 6 ?

2? ? 0? 2? ? 4? 5? ?

4

4

①对不含圈0的行打 ; 不含圈 的行打 的行中,对所有零元素所在列 ②在打 的行中,对所有零元素所在列打 ; 的列中,对圈0所在 所在行 ③在所有打 的列中,对圈 所在行打 ; 重复2,3步 直到不能打 为止。 ④重复 步,直到不能打 为止。 的每一行画一横线 画一横线, 的每一列画 ⑤对未打 的每一行画一横线,对已打 的每一列画 一纵线,即得到覆盖当前0元素的最少直线集 元素的最少直线 一纵线,即得到覆盖当前 元素的最少直线集。
?0 ? ?0 ?0 ? ?0 ?0 ? 3 0 11 8 ? ? 1 7 7 3? 2 3 2 1? ? 0 5 0 4? ? 2 3 4 0?

⑥找未被直线覆盖的最小数字k; 找未被直线覆盖的最小数字k 对矩阵的每行:当该行有直线覆盖时 有直线覆盖时, ⑦对矩阵的每行:当该行有直线覆盖时,令ui=0; 当该行无直线覆盖 无直线覆盖时 =k。 当该行 无直线覆盖 时 , 令 ui=k 。 对矩阵的每列:当该列有直线覆盖时 有直线覆盖时, ⑧对矩阵的每列:当该列有直线覆盖时,令vj=-k; 当该列 无直线覆盖时 当该 列 无直线覆盖 时 , 令 vj=0 。
ui ? 0 3 0 11 8 ? 0 ? ? ?0 1 7 7 3? 1 ?0 2 3 2 1? 1

vj

? ?0 0 5 ?0 2 3 ?
-1 0

0 4
0

? 4? 0 ? 0 0?
0

0

⑨从原矩阵的每个元素aij 中分别减去 i和vj,得到新元 从原矩阵的每个元素 中分别减去u 素
ui ? 0 3 0 11 8 ? 0 ? ? ?0 1 7 7 3? 1

?0 2 3 ? ?0 0 5 ?0 2 3 ?
vj -1 0

2 0 4
0

1? 1 ? 4? 0 0? 0 ?
0

?0 ? ?0 ?0 ? ?0 ? ?0

3 0 11 8 ? ? 0 6 6 2? 1 2 1 0? ? 0 5 0 4? ? 2 3 4 0?

0

原题: 原题:

⑩再次寻找独立零元素

逐列检验
?0 ? ?0 ?0 ? ?0 ? ?0 3 0 11 8 ? ? 0 6 6 2? 1 2 1 0? ? 0 5 0 4? ? 2 3 4 0?

?4 ? ?7 ?6 ? ?6 ?6 ?
?0 ? ?0 ?1 ? ?0 ? ?0

8 7 15 12 ? ? 9 17 14 10 ? 9 12 8 7 ? ? 7 14 6 10 ? 9 12 10 6 ? ?
0 1 0 0? ? 1 0 0 0? 0 0 0 0? ? 0 0 1 0? ? 0 0 0 1?

分配方案A=7+9+6+6+6=34 分配方案

⑩再次寻找独立零元素

逐列检验
?0 ? ?0 ?0 ? ?0 ? ?0 3 0 11 8 ? ? 0 6 6 2? 1 2 1 0? ? 0 5 0 4? ? 2 3 4 0?

?4 ? ?7 ?6 ? ?6 ?6 ?
?0 ? ?0 ?0 ? ?0 ? ?1

8 7 15 12 ? ? 9 17 14 10 ? 9 12 8 7 ? ? 7 14 6 10 ? 9 12 10 6 ? ?
0 1 0 0? ? 1 0 0 0? 0 0 0 1? ? 0 0 1 0? ? 0 0 0 0?

分配方案B=7+9+7+6+6=35 分配方案

①对不含圈0的行打 ; 不含圈 的行打 的行中,对所有零元素所在列 ②在打 的行中,对所有零元素所在列打 ; 的列中,对圈0所在 所在行 ③在所有打 的列中,对圈 所在行打 ; 重复2,3步 直到不能打 为止。 ④重复 步,直到不能打 为止。 的每一行画一横线 画一横线, 的每一列画 ⑤对未打 的每一行画一横线,对已打 的每一列画 一纵线,即得到覆盖当前0元素的最少直线集 元素的最少直线 一纵线,即得到覆盖当前 元素的最少直线集。
?5 0 2 0 ?2 3 0 0 ? ? 0 10 5 7 ? ?9 8 0 0 ?0 6 3 6 ? 2? 0? ? 2? ? 4? 5? ?

个数4 圈0个数 < n=5 个数

?5 0 2 0 ?2 3 0 0 ? ? 0 10 5 7 ? ?9 8 0 0 ?0 6 3 6 ?

2? 0? ? 2? ? 4? 5? ?

⑥找未被直线覆盖的最小数字k; 找未被直线覆盖的最小数字k 对矩阵的每行:当该行有直线覆盖时 有直线覆盖时, ⑦对矩阵的每行:当该行有直线覆盖时,令ui=0; 当该行无直线覆盖 无直线覆盖时 =k。 当该行 无直线覆盖 时 , 令 ui=k 。 对矩阵的每列:当该列有直线覆盖时 有直线覆盖时, ⑧对矩阵的每列:当该列有直线覆盖时,令vj=-k; 当该列 无直线覆盖时 当该 列 无直线覆盖 时 , 令 vj=0 。

?5 0 2 0 ?2 3 0 0 ? ? 0 10 5 7 ? ?9 8 0 0 ?0 6 3 6 ?
vj -2 0 0 0

2? 0? ? 2? ? 4? 5? ?
0

ui 0 0 2 0 2

⑨从原矩阵的每个元素aij 中分别减去 i和vj,得到新元 从原矩阵的每个元素 中分别减去u 素

?5 0 2 0 ?2 3 0 0 ? ? 0 10 5 7 ? ?9 8 0 0 ?0 6 3 6 ?
vj -2 0 0 0

2? ? 0? 2? ? 4? 5? ?
0

ui 0 0 2 0 2

?5 ? ?2 ?0 ? ?9 ? ?0

0 2 0 2? ? 3 0 0 0? 8 3 5 0? ? 8 0 0 4? ? 4 1 4 3?

⑩再次寻找独立零元素
分配方案B 分配方案

?5 ? ?2 ?0 ? ?9 ? ?0

0 2 0 2? ? 3 0 0 0? 8 3 5 0? ? 8 0 0 4? ? 4 1 4 3?

?0 ? ?0 ?0 ? ?0 ? ?1

1 0 0 0? ? 0 0 1 0? 0 0 0 1? ? 0 1 0 0? ? 0 0 0 0?

⑩再次寻找独立零元素
分配方案B 分配方案

?5 ? ?2 ?0 ? ?9 ? ?0

0 2 0 2? ? 3 0 0 0? 8 3 5 0? ? 8 0 0 4? ? 4 1 4 3?

?0 ? ?0 ?0 ? ?0 ? ?1

1 0 0 0? ? 0 1 0 0? 0 0 0 1? ? 0 0 1 0? ? 0 0 0 0?

整体解题思路总结

整体解题思路总结
例题: 例题: 单位: 单位:小时

工作1 工作 工作2 工作 工作3 工作 工作4 工作 工作5 工作

人1 4 7 6 6 6

人2 8 9 9 7 9

人3 7 17 12 14 12

人4 15 14 8 6 10

人5 12 10 7 10 6

整体解题思路总结
例题: 例题:

?4 ? ?7 ?6 ? ?6 ?6 ?

8 7 15 12 ? ? 9 17 14 10 ? 9 12 8 7 ? ? 7 14 6 10 ? 9 12 10 6 ? ?

步骤1:变换系数矩阵,使其每行每列都出现0元素 步骤 :变换系数矩阵,使其每行每列都出现 元素
把各行元素分别减去本行元素的最小值,然后在此基础上 把各行 元素分别减去本行元素的最小值, 然后在此基础上 再把每列元素减去本列中的最小值。 再把每列元素减去本列中的最小值。

min

?4 ? ?7 ?6 ? ?6 ?6 ?

8 7 15 12 ? 4 ? 0 4 3 11 8 ? ? 0 3 0 11 8 ? ? ? ? ? ? 9 17 14 10 ? 7 ? 0 2 10 7 3 ? ?0 1 7 7 3 ? 9 12 8 7 ? 6 ? ? 0 3 6 2 1 ? ? ? 0 2 3 2 1 ? ? ? ? ? ? 7 14 6 10 ? 6 ?0 1 8 0 4 ? ? 0 0 5 0 4? ? ?0 3 6 4 0 ? ? 0 2 3 4 0? 9 12 10 6 ? 6 ? ? ? ? min 0 1 3 0 0
此时每行及每列中肯定都有0元素 此时每行及每列中肯定都有 元素

步骤2:进行试分配,判断是否存在n个独立零元素 步骤 :进行试分配,判断是否存在 个独立零元素
尝试对所有零元素做标记,确定独立零元素。 尝试对所有零元素做标记,确定独立零元素。 标记 独立零元素

(2)逐行检验 )

?0 ? ?0 ?0 ? ?0 ?0 ?

3 0 11 8 ? ? 1 7 7 3? ? 2 3 2 1 ? 0 5 0 4? ? 2 3 4 0?
圈0即独立零元素 即独立零元素

独立零元素的个数 (3)判断独立零元素的个数 )判断独立零元素

可能出现三种情况

3.不存在未被标记过的零元素,但圈0的个数 不存在未被标记过的零元素,但圈 的个数 的个数<n 不存在未被标记过的零元素

作 最少直线覆盖当前所有零元素, 便 最少直线覆盖当前所有零元素 , 于下步增加独立零元素的个数。 于下步增加独立零元素的个数。
个数4 圈0个数 < n=5 个数

?0 ? ?0 ?0 ? ?0 ?0 ?

3 0 11 8 ? ? 1 7 7 3? 2 3 2 1? ? 0 5 0 4? 2 3 4 0? ?

①对不含圈0的行打 ; 不含圈 的行打 的行中,对所有零元素所在列 ②在打 的行中,对所有零元素所在列打 ; 的列中,对圈0所在 所在行 ③在所有打 的列中,对圈 所在行打 ; 重复2,3步 直到不能打 为止。 ④重复 步,直到不能打 为止。 的每一行画一横线 画一横线, 的每一列画 ⑤对未打 的每一行画一横线,对已打 的每一列画 一纵线,即得到覆盖当前0元素的最少直线集 元素的最少直线 一纵线,即得到覆盖当前 元素的最少直线集。
?0 ? ?0 ?0 ? ?0 ?0 ? 3 0 11 8 ? ? 1 7 7 3? 2 3 2 1? ? 0 5 0 4? ? 2 3 4 0?

⑥找未被直线覆盖的最小数字k; 找未被直线覆盖的最小数字k 对矩阵的每行:当该行有直线覆盖时 有直线覆盖时, ⑦对矩阵的每行:当该行有直线覆盖时,令ui=0; 当该行无直线覆盖 无直线覆盖时 =k。 当该行 无直线覆盖 时 , 令 ui=k 。 对矩阵的每列:当该列有直线覆盖时 有直线覆盖时, ⑧对矩阵的每列:当该列有直线覆盖时,令vj=-k; 当该列 无直线覆盖时 当该 列 无直线覆盖 时 , 令 vj=0 。
ui ? 0 3 0 11 8 ? 0 ? ? ?0 1 7 7 3? 1 ?0 2 3 2 1? 1

vj

? ?0 0 5 ?0 2 3 ?
-1 0

0 4
0

? 4? 0 ? 0 0?
0

0

⑨从原矩阵的每个元素aij 中分别减去 i和vj,得到新元 从原矩阵的每个元素 中分别减去u 素
ui ? 0 3 0 11 8 ? 0 ? ? ?0 1 7 7 3? 1

?0 2 3 ? ?0 0 5 ?0 2 3 ?
vj -1 0

2 0 4
0

1? 1 ? 4? 0 0? 0 ?
0

?0 ? ?0 ?0 ? ?0 ? ?0

3 0 11 8 ? ? 0 6 6 2? 1 2 1 0? ? 0 5 0 4? ? 2 3 4 0?

0

原题: 原题:

⑩再次寻找独立零元素

逐列检验
?0 ? ?0 ?0 ? ?0 ? ?0 3 0 11 8 ? ? 0 6 6 2? 1 2 1 0? ? 0 5 0 4? ? 2 3 4 0?

?4 ? ?7 ?6 ? ?6 ?6 ?
?0 ? ?0 ?1 ? ?0 ? ?0

8 7 15 12 ? ? 9 17 14 10 ? 9 12 8 7 ? ? 7 14 6 10 ? 9 12 10 6 ? ?
0 1 0 0? ? 1 0 0 0? 0 0 0 0? ? 0 0 1 0? ? 0 0 0 1?

分配方案A=7+9+6+6+6=34 分配方案

⑩再次寻找独立零元素

逐列检验
?0 ? ?0 ?0 ? ?0 ? ?0 3 0 11 8 ? ? 0 6 6 2? 1 2 1 0? ? 0 5 0 4? ? 2 3 4 0?

?4 ? ?7 ?6 ? ?6 ?6 ?
?0 ? ?0 ?0 ? ?0 ? ?1

8 7 15 12 ? ? 9 17 14 10 ? 9 12 8 7 ? ? 7 14 6 10 ? 9 12 10 6 ? ?
0 1 0 0? ? 1 0 0 0? 0 0 0 1? ? 0 0 1 0? ? 0 0 0 0?

分配方案B=7+9+7+6+6=35 分配方案


相关文章:
运筹学指派问题的匈牙利法实验报告
五、 算例结果。 六、 结论与总结。 一、 题目:匈牙利法求解指派问题。 ...针对这个问题我尝试了好几次,也没有解决。查了一些资 料,好像可以通过动态分配...
指派问题的匈牙利解法
指派问题匈牙利解法 1、 把各行元素分别减去本行元素的最小值;然后在此基础上 再把每列元素减去本列中的最小值。 ?4 ? ?7 ?6 ? ?6 ?6 ? 2、 8 ...
运筹学指派问题的匈牙利法
运筹学指派问题匈牙利法_数学_自然科学_专业资料。指派问题匈牙利法运筹...不同列中至少有一个零元素,从 而得到与这些零元素相对应的一个完全分配方案。...
求解指派问题的匈牙利算法.doc
3.2 求解指派问题匈牙利算法 由于指派问题的特殊性,又存在着由匈牙利数学家 ...第五讲 分配问题(指派问... 44页 1下载券 喜欢此文档的还喜欢 指派...
匈牙利算法在企业员工指派问题的应用(最终版)
匈牙利算法在企业员工指派问题的应用(最终版)_人力资源管理_经管营销_专业资料。...第五讲 分配问题(指派问... 44页 1下载券 运筹学指派问题的匈牙利... ...
指派问题的匈牙利解法
第五讲_分配问题(指派问题... 44页 免费 分配问题与匈牙利法-毕德春... 25页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击...
更多相关标签: