运筹学匈牙利法优秀课件

(1) (2) (3) (4)
√√√ √ 0 √√√ √ 5 √ √ √ √ -2 √√√ √ 3 √×√ √ √√√ √ 8 ××√ √ √×√ √
max Z 3 x1 2 x 2 5 x 3
x1 2 x 2 x3 2 (1)
x x
1 1
4 x2 x2
x3
4 3
(2) (3)
译俄文 4 15 13 9 xij =0或1 (i=1,2,3,4; j=1,2,3,4)
4、指派问题的匈牙利解法
第1步：变换指派问题的系数矩阵（cij），使各行
各列中都出现0元素
(1) 从（cij）的每行元素都减去该行的最小元素；
(2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。
2 15 13 4 2
译日文：
44
min f
ci jxi j译德文：
i1 j1
译俄文：
工作 人 甲 乙 丙 丁 甲：
乙：
译英文 2 10 9
7 丙：
译日文 15 4 译德文 13 14
14 8 丁：
16 11
x21+ x22 + x23 + x24 =1 x31+ x32 + x33 + x34 =1 x41+ x42 + x43 + x44 =1 x11+ x21 + x31 + x41 =1 x12+ x22 + x32 + x42 =1 x13+ x23 + x33 + x43 =1 x14+ x24 + x34 + x44 =1
任务
人员
A
B
C
D
甲
6
7
11
2
乙
4
5
9
8
丙
3
1
10
4
丁
5
9
8
2
0 13
6
0
0 5
0
1
7 0
6
9
3 2
0
0
0 0 0 1
x ij
0
1
1 0
0 0
0
0
0 0 1 0
2 15 13 4
10
4
14
15
9 14 16 13
7
8 11
9
例2 有甲、乙、丙、丁四个工人，要分别派他们
完成四乡不同的任务，分别记作A、B、C、D。他们完成各
项任务所需时间如下表所示，问如何分派任务，可使总时 间最少？
0 13
6
0
0 5
0
1
（1）从有唯一的零元素的行或列开
7 0 始确定独立零元素，并用 0 表示，
6
9
并划掉其所在行或列的其他零。直 到尽可能多的零元素都被圈出和划
3 2 掉为止。
0
0
（2）若独立零元素的数目m等于矩 阵的阶数n，那么这指派问题的最优
解已得到。若m < n, 则转入下一步。
设n 个人被分配去做n 件工作，每人只能完成一项任务，
每项任务只能由一人完成。已知第i 个人去做第j 件工作的的
效率为Cij(i=1.2…n;j=1.2…n)并假设Cij ≥0。问应如何分配
才能使总效率（ 时间或费用）最高？
n
n
min Z
c ij x ij
1分配i第 个人取完j成 项第 任务
xij
满足约束条件（是∨ 否×） (1) (2) (3) (4)
过滤 条件
√√√ √ 0
√√√ √ 5
-2
3
3
√√√ √ 8
1
6
max Z 3 x 1 2 x 2 5 x 3
x 1 2 x 2 x 3 2 (1)
x1 x1
4
x2 x2
x3
Hale Waihona Puke 4 3(2) (3)
4 x 2 x 3 6 (4)
n
0不分配i个 第人取完j成 项第 任务
x ij
j1
i1 j1
1 ( i 1 .2 . .n )
n
x ij 1 ( j 1 . 2 . . n )
i1
x ij 0 或 1( i , j 1 . 2 . . n )
典型问题
例1：有一份说明书，要分别译成英、日、 德、俄四种文字，交与甲、乙、丙、丁四个 人去完成，因各人专长不同，他们完成翻译 不同文字所需要的时间（小时）如表所示。 规定每项工作只能交与其中的一个人完成， 每个人只能完成其中的一项工作。
工作 人 甲 乙 丙 丁
译英文 译日文 译德文 译俄文
2 10 15 4 13 14 4 15
97 14 8 16 11 13 9
问：如何分配，能使所需的总时间最少？
设 xij=
1 若第i项工作交与第j个人完成 0 若第i项工作不交与第j个人完成
建立模型
译英文： x11+ x12 + x13 + x14 =1
10
4
14
15
4
9 14 16 13 9
7
8 11
9
7
0 13 11 2
6
0
10
11
0 5 7 4
0
1
4
2
42
第2步：进行试指派，即确定独立零元素
在变化后的效率矩阵中找尽可能多的独立0元素，若
能找出n个独立0元素，就以这n个独立0元素对应解 矩阵(xij)中的元素为1，其余为0，这就得到最优解。
x
1
,
x
4 2,
x2 x3
x3 0或
6 1
(4)
二、0－1 整数规划——隐枚举法
首先，找到一个可行解，并计算其目标函数值；然后，以其目标值作为 一个过滤条件，优于其值的再判断约束条件，直到找到最优解。
x1 . x2. x3
( 0. 0. 0 ) ( 0. 0. 1 ) ( 0. 1. 0 ) ( 1. 0. 0 ) ( 0. 1. 1 ) ( 1. 0. 1 ) ( 1. 1. 0 ) ( 1. 1. 1 )
2、指派问题的假设 ▪被指派者的数量和任务的数量是相同的 ▪每一个被指派者只完成一项任务
▪每一项任务只能由一个被指派者来完成
▪每个被指派者和每项任务的组合有一个相关成本 ▪目标是要确定怎样进行指派才能使得总成本最小
3、指派问题模型 （The Model for Assignment Problem）
x 1 , x 2 , x 3 0 或 1
思考：如果将目标 函数变为下式会改 进吗？
mZ a 2 x x 2 3 x 1 5 x 3
三、指派问题的匈牙利法
指派问题（The Assignment Problem）
1、指派问题的形式表述
给定了一系列所要完成的任务（tasks）以及一系列完成 任务的被指派者（assignees），所需要解决的问题就是 要确定出哪一个人被指派进行哪一项任务
运筹学匈牙利法优秀课件
一、0－1 整数规划——枚举法
x1 . x2. x3
( 0. 0. 0 ) ( 0. 0. 1 ) ( 0. 1. 0 ) ( 1. 0. 0 ) ( 0. 1. 1 ) ( 1. 0. 1 ) ( 1. 1. 0 ) ( 1. 1. 1 )
满足约束条件（是∨ 否×） Z 值