11 10 7 4
2 0 13
11
4 2


6

0 0
0 5 1
70

-4 -2
最优解的取法：
从含0元素最少的行或列开始，圈出一个0元 素，用 ○表示，然后划去该○所在的行和列 中的其余0元素，用×表示，依次类推，若能 得到n个○，则得最优解X0
13 7 06 53 10
90 02
可行解
j1 i1
xi1 xi2 xi3 xi4 1 i=1,2, 3,4 s.tx1jx2jx3jx4j 1j=1,2, 3,4

xij 0 ,1i 1 ,2 ,3 ,4 ;j 1 ,2 ,3 ,4
最 优
取x14 1，x22 1, x31 1, x43 1 ,其余 xij 0
英日德 俄
乙丙、丁四个人去完成，每人完 甲 2 15 13 4
成一种。由于个人的专长不同，
乙 丙
10 4 14 15 9 14 16 13
翻译成不同文字所需的时间（小 丁 7 8 11 9
时数）如右表，问应派哪个人去
完成哪个任务，可使总花费时间
最少？
C最总优17920费方1184用45案111：16431：211丙94甲853 小翻翻----2497时译译 英俄 0060 文文11503 ，，11-74014乙丁-12翻2421翻 译译日德0060 文文11503
c12
c22
cn2

ccc12nnnn 0
cij表示第i个人做第j件事的费用
费用矩阵
3、匈牙利法
定理：在费用矩阵C=（cij）的任一行（列）中 减去一个常数或加上一个常数不改变本 问题的最优解。
C


c11 c 21
c i1
c12 c 22
ci2


c1n c2n

c in

-b

c n1
cn2

c nn
b m c i1 i ,c i n 2 , ,c i n
C


c11 c21
ci1
b
c12 c22
ci2 b


c1n c2n

cin b

cn1
3.4 0-1整数规划 三、指派问题与匈牙利法
矩阵的概念
矩阵的引入 某班级同学早餐情况
姓名 馒头 包子 鸡蛋 稀饭
周星 4
2
驰
2
1
张曼 0
0
玉
0
0
陈水 4
9
扁
8
6
为了方便，常用下面右边的数表表示
4 2 2 1

0 4
0 9
0 8
0 6

这个数表反应了学生的早餐情况
1、指派问题的数学模型
设有n个工作，要由 n个人来承 担，每个工作只能由一个人承 担，且每个人只能承担一个工 作。cij表示第i个人做第j件事 的费用,求总费用最低的指派 方案。
解：
x ij

1
0
第i个人做第j 人件事 第i个人不做第j 人件事
i=1,2, …,n; j=1,2, …,n
Z表示总费用
12…j …n
7 6 3 0
0
9
2 0

?
最优x解 141， x22 1, x31 1, x43 1 ,其余 xij 0
2
C

10

9 7
15 4 14 8
13 14 16 11
4 -2 15 -4
13 9

-9 -7
0

6

0 0
13 0 5 1
xi1 xi2 j ixij xin 1
s.tx1jx2j xjii==j 11 ,,22,, ……x,n ,nn j1
xij0 ,1i 1 ,2 , ,n ;j 1 ,2 , ,n
2、费用矩阵
设有n个工作，要由 n个人来承 担，每个工作只能由一个人承 担，且每个人只能承担一个工 作。cij表示第i个人做第j件事 的费用,求总费用最低的指派 方案。
1 c11 c12 c1 j c1n 2 c 21 c 22 c 2 j c 2 n … i c i1 c i 2 c ij c in …
n c n1 c n 2 c nj c nn
指派问题模型：
miZ n
cijxij
解
总费用 Z c14 x14 c22x22c31x31c43x43 0
匈牙利法的基本思路：
对费用矩阵C的行和列减去某个常数，将C化成 有n 个位于不同行不同列的零元素，令这些零元 素对应的变量取1，其余变量取零，既得指派问 题的最优解
例：有一份说明书要分别译成英、 工作
日、德、俄四种文字，现交给甲、人
cn2 cnn
minZ Z b
minZ Zb
若X0是minZ的最优， 解则 X0也是 minZ的最优解
指派问题的最优解：
若C中有n 个位于不同行不同列的零元素，
则令这些零元素对应的变量取1，其余变量
取零，既得指派问题的最优解
44
minZ
cijxij
0
例如： C0060
12…j …n
1 c11 c12 c1 j c1n 2 c 21 c 22 c 2 j c 2 n … i c i1 c i 2 c ij c in … n c n1 c n 2 c nj c nn
取C ccc12n111
最优x解 141， x22 1, x31 1, x43 1 ,其余 xij 0
44
最优值 Z： cijxij c14 c22 c31 c43 28 j1 i1
例：求费用矩阵为右表的 指派问题的最优解
工作
人 甲 乙 丙 丁 戊
ABCDE
12 7 9 7 9 89 6 6 6 7 17 12 14 12 15 14 6 6 10 4 10 7 10 6
12
8
C


7
7 9 17
9 6 12
7 6 14
9 -7
6 -6
12

-7

5 2
0
0 3 10
2 0 5
0 0 7
2 0