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

第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.任一个工人都不能去做两件或两件以上的工作 2.任一件工作都不能同时接受两个及以上的工人去做

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

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

每个人必做且只做一件事

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

时间、原料、 金钱等资源

i,j=1,...,n

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

总费用：

cij xiji 1 j 1

n

n

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

x

n

每个人必做且只做一件事

xj 1

i 1 n

ij

1 j=1,...,n

ij

1 i=1,...,n

数学模型min z cij xiji 1 j 1 n n

xi 1

n

ij

1

j=1,...,n

s.t.

xj 1

n

ij

1

i=1,...,n

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

线性规划问题

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

匈牙利法1955年由美国数学家W.W.kuhn(库恩)提出，利用了 匈牙利数学家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 3 5 8 1 0 0 0 2 0 6 0 0 0 0 1 0 0

7 0 0 1 0 0

c12 , c24 , c31 , c43 c12 , c23 , c31 , c44 c14 , c23 , c31 , c44 最优解min z cij xiji 1 j 1 n n

相关定理

使每行每列 都出现零元素

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

A

B

A

B

C

甲 乙丙

7 98

8 125

9 甲 4 乙4 丙

0 54

0 1 7 80 1

2 0 0

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

min 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

0 7 0 6 0 6 0 0 6 min 04

4 3 11 8 0 2 10 7 3 0 3 6 2 1 0 1 8 0 4 0 0 3 6 4 0

3 0 11 8 1 7 7 3 2 3 2 1 0 5 0 4 2 3 4 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.不存在未被标记过的零元素，但圈0的个数<n 可进行分配：令圈0位置的决策变量取值为1,其他为0

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

0 0 1 0

0 1 0 0

0 0 0 1

1 0 0 0

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

可能出现三种情况

2.存在未标记过的零元素，但它们所在的行和列中，未被标 记过的零元素的个数均至少有两个。 3.不存在未被标记过的零元素，但圈0的个数<n

从某行(列)的两个未被标记过的零元素中任选一个加上圈， 然后给同列、同行的其他未被标记的零元素都加/,然后再 进行行、列检验，可能出现情况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