一、决策问题与 0-1变量件事是否做第决策变量 ix i
ix
1
0
做第 i件事不做第 i件事
ni,,2,1
n件事中必须 做 k件并只做 k件事 kxxx
n21
n件事中 最多做 k件事 kxxx
n21
n件事中 至少做 k件事
nxxx21 k?
做第 i件事的充要条件是做第 j件事
ji xx
做第 i件事的充要条件是不做第 j件事
ji xx 1
只在做了第 i件事前提下才考虑是否做第 j件事
ij xx
该公司只有 600万资金可用于投资，由于技术上的原因，投资受到以下约束：
1、在项目 1,2和 3中必须有一项被选中
2、项目 3和 4只能选中一项
3、项目 5被选中的前提是项目 1被选中 ;如何在 满足上述条件下选择一个最好的投资方 案，使投资收益最大例 1（投资问题）华美公司有 5个项目被列入投资计划，每个项目的投资额和期望的投资收益见下表：
项目 投资额
（万元）
投资收益
（万元）
1 210 150
2 300 210
3 100 60
4 130 80
5 260 180
)5,,2,1ix i为决策变量（解：设
ix
1
0
投资第 i个项目不投资第 i个项目
Z表示投资效益投资项目模型：
54321 1808060210150m a x xxxxxZ
ts.
600260130100300210 54321 xxxxx
1321 xxx
143 xx
15 xx?
5,,2,11,0 ix i
例 2（布点问题）某城市共有 6个区，每个区都可以建消防站。
市政府希望设置的消防站最少，
但必须满足在城市任何地区发生火火警时，消防车要在 15分钟内赶到现场。据实地测定，
各区之间消防车行驶的时间见右表。
地区
1 2 3 4 5 6
1 0 10 16 28 27 20
2 10 0 24 32 17 10
3 16 24 0 12 27 21
4 28 32 12 0 15 25
5 27 17 27 15 0 14
6 20 10 21 25 14 0
请为该市制定一个最节省的计划解：
0
1
ix
在第 i个地区建站
Z表示全区消防站总数不在第 i个地区建站
i=1,2,…,6
布点问题模型：
654321m i n xxxxxxZ
6,,2,11,0 ix i
ts.
121 xx
1621 xxx
143 xx
1543 xxx
1652 xxx
最优解
x2=1,x4=1
最优值
Z=2
二,过滤隐枚举法 （适合于变量个数较少的 0-1规划）
10,,
64
3
424
22
.
253m a x
321
32
21
321
321
321
或例：求
xxx
xx
xx
xxx
xxx
ts
xxxZ
（ x1 x2 x3) Z值 约束条件
（ 1）（ 2）（ 3）（ 4）
过滤条件
（ 0 0 0）
（ 0 0 1）
（ 0 1 0）
（ 1 0 0）
（ 1 0 1）
（ 1 1 0）
（ 0 1 1）
（ 1 1 1）
√ √ √ √0 Z≥0
枚举法：
检验可行解：
32次运算
-2
5 √ √ √ √ Z≥5
3
1
8 ×
3
6
6
111 321
Z
xxx
最优值
，，最优解：
运算次数：
21
计算目标函数值,8次
√ √ √ √
三、指派问题与匈牙利法设有 n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。 cij表示第 i个人做第 j件事的费用,求总费用最低的指派方案。
1 2 … j … n
1
2
…
i
…
n
指派问题模型：
j i ijij xcZm i n
1
.
21 inijii xxxx
ts
i=1,2,…,n
121 njijjj xxxxj=1,2,…,n
njnix ij,,2,1;,,2,11,0
解：
第 i个人做第 j 人件事
Z表示总费用
i=1,2,…,n; j=1,2,…,n
第 i个人不做第 j 人件事?
0
1
ijx
nnnjnn
inijii
nj
nj
cccc
cccc
cccc
cccc
21
21
222221
1112111、指派问题的 数学模型
j i
ijij xcZm i n
nnnnnnnn
nn
nn
xcxcxc
xcxcxc
xcxcxc
2211
2222222121
1112121111
1
.
21 inijii xxxx
ts
121 njijjj xxxx
i=1,2,…,n
j=1,2,…,n
当 n=4时,有 16变量,8个约束方程
1
1
1
.
21
222221
111211
nnnjnn
nj
nj
xxxx
xxxx
xxxx
ts
1
1
1
21
222212
112111
nninnn
ni
ni
xxxx
xxxx
xxxx
例：现有 4份工作,4个人应聘，由于各人技术专长不同，他们承担各项工作所需费用如下表所示，
且规定每人只能做一项工作，每一项工作只能由一人承担，试求使总费用最小的分派方案。
工作人 1 2 3 41
2
3
4
3 5 4 5
6 7 6 8
8 9 8 10
10 10 9 11
解：
ijx
1
0
第 i人做第 j 件事
Z表示总费用
i=1,2,3,4; j=1,2,3,4
第 i人不做第 j 件事
14131211 5453m ax xxxxZ
24232221 8676 xxxx
34333231 10898 xxxx
44434241 1191010 xxxx
1
.
14131211
xxxx
ts
124232221 xxxx
134333231 xxxx
144434241 xxxx
141312111 xxxx
142322212 xxxx
143332313 xxxx
144342414 xxxx
nj
ni
x ij
,,2,1
,,2,1
1,0
2、费用矩阵设有 n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。 cij表示第 i个人做第 j件事的费用,求总费用最低的指派方案。
1 2 … j … n
1
2
…
i
…
n nnnjnn
inijii
nj
nj
cccc
cccc
cccc
cccc
21
21
222221
111211
nnnn
n
n
ccc
ccc
ccc
C
21
22221
11211
取
cij表示第 i个人做第 j件事的费用费用矩阵例：现有 4份工作,4个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，
试求使总费用最小的分派方案。
工作人 1 2 3 41
2
3
4
3 5 4 5
6 7 6 8
8 9 8 10
10 10 9 11
费用矩阵
1191010
10898
8676
5453
C
07531
93506
65001
65320
54321
C设对应一个 5个人 5个工作的指派问题第 2个人做第 4个工作的费用 5
第 4个人做第 2个工作的费用 0
定理：在费用矩阵 C=（ cij）的任一行（列）中减去一个常数或加上一个常数不改变本问题的最优解。
n个人 n个工作的指派问题 1
nnnn
inii
n
n
ccc
ccc
ccc
ccc
C
21
21
22221
11211
-b
nnnn
inii
n
n
ccc
bcbcbc
ccc
ccc
C
21
21
22221
11211
inii cccb,,,m i n 21
3,匈牙利法
n个人 n个工作的指派问题 2
Zmin
nnnnnnnn
ininiiii
nn
nn
xcxcxc
xcxcxc
xcxcxc
xcxcxc
2211
2211
2222222121
1112121111
1
.
21 inijii xxxx
ts
121 njijjj xxxx
njnix ij,,2,1;,,2,11,0
i=1,2,…,n
j=1,2,…,n
Zmin
nnnnnnnn
ininiiii
nn
nn
xcxcc
xbcxbcxbc
xcxcxc
xcxcxc
2211
2211
2222222121
1112121111
)()()(
nnnn
inii
n
n
ccc
ccc
ccc
ccc
C
21
21
22221
11211
nnnn
inii
n
n
ccc
bcbcbc
ccc
ccc
C
21
21
22221
11211
1
.
21 inijii xxxx
ts
121 njijjj xxxx
njnix ij,,2,1;,,2,11,0
i=1,2,…,n
j=1,2,…,n
-b
Zmin
nnnnnnnn
ininiiii
nn
nn
xcxcxc
xbcxbcxbc
xcxcxc
xcxcxc
2211
2211
2222222121
1112121111
)()()(
)(
212211
2211
2222222121
1112121111
iniinnnnnnnn
ininiiii
nn
nn
xxxbxcxcxc
xcxcxc
xcxcxc
xcxcxc
bxcxcxc
xcxcxc
xcxcxc
xcxcxc
nnnnnnnn
ininiiii
nn
nn
2211
2211
2222222121
1112121111
Zmin Zmin
nnnnnnnn
ininiiii
nn
nn
xcxcxc
xcxcxc
xcxcxc
xcxcxc
2211
2211
2222222121
1112121111
bxcxcxc
xcxcxc
xcxcxc
xcxcxc
nnnnnnnn
ininiiii
nn
nn
2211
2211
2222222121
1112121111
nnnn
inii
n
n
ccc
ccc
ccc
ccc
C
21
21
22221
11211
nnnn
inii
n
n
ccc
bcbcbc
ccc
ccc
C
21
21
22221
11211
-b
1
.
21 inijii xxxx
ts
121 njijjj xxxx
njnix ij,,2,1;,,2,11,0
i=1,2,…,n
j=1,2,…,n
1
.
21 inijii xxxx
ts
121 njijjj xxxx
njnix ij,,2,1;,,2,11,0
i=1,2,…,n
j=1,2,…,n
bZ bZ
Zmin
Zmin
的最优解是若 ZX mi n0 的最优解也是，则 ZX m i n0
的最优值是若 ZZ m i n0 的最优值是，则若 ZbZ m i n0?
任务,对 C的行和列减去某个常数，
将 C化的尽可能简单，
简单到可一眼看出该问题的最优解
nnnn
inii
n
n
ccc
ccc
ccc
ccc
C
21
21
22221
11211
nnnn
inii
n
n
ccc
bcbcbc
ccc
ccc
C
21
21
22221
11211
-b
bZbZ
三、指派问题与匈牙利法
1 2 … j … n
1
2
…
i
…
n
指派问题模型：
j i ijij xcZm i n
1
.
21 inijii xxxx
ts
i=1,2,…,n
121 njijjj xxxxj=1,2,…,n
njnix ij,,2,1;,,2,11,0
解：
第 i个人做第 j 人件事
Z表示总费用
i=1,2,…,n; j=1,2,…,n
第 i个人不做第 j 人件事?
0
1
ijx
nnnjnn
inijii
nj
nj
cccc
cccc
cccc
cccc
21
21
222221
1112111、指派问题的 数学模型设有 n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。 cij表示第 i个人做第 j件事的费用,求总费用最低的指派方案。
2、费用矩阵设有 n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。 cij表示第 i个人做第 j件事的费用,求总费用最低的指派方案。
1 2 … j … n
1
2
…
i
…
n nnnjnn
inijii
nj
nj
cccc
cccc
cccc
cccc
21
21
222221
111211
nnnn
n
n
ccc
ccc
ccc
C
21
22221
11211
取
cij表示第 i个人做第 j件事的费用费用矩阵
0?
定理：在费用矩阵 C=（ cij）的任一行（列）中减去一个常数或加上一个常数不改变本问题的最优解。
nnnn
inii
n
n
ccc
ccc
ccc
ccc
C
21
21
22221
11211
-b
nnnn
inii
n
n
ccc
bcbcbc
ccc
ccc
C
21
21
22221
11211
inii cccb,,,m i n 21
3,匈牙利法
Zmin
Zmin
的最优解是若 ZX mi n0 的最优解也是，则 ZX m i n0
bZbZ
指派问题的最优解：
若 C中有 n 个位于不同行不同列的零元素，
则令这些零元素对应的变量取 1，其余变量取零，既得指派问题的最优解
0010
2350
9606
07130
C例如：
ijij
ij
xcZ
4
1
4
1
m in
1
.
4321 iiii xxxx
ts
i=1,2,3,4
14321 jjjj xxxx j=1,2,3,4
4,3,2,1;4,3,2,11,0 jix ij
0?
，取 114?x,122?x,131?x 143?x 0,?ijx其余可行解
Z总费用 1414 xc 2222 xc? 3131 xc? 4343 xc? 0?
最优解匈牙利法的基本思路：
对费用矩阵 C的行和列减去某个常数，将 C化成有 n 个位于不同行不同列的零元素，令这些零元素对应的变量取 1，其余变量取零，既得指派问题的最优解例：有一份说明书要分别译成英、
日、德、俄四种文字，现交给甲、
乙丙、丁四个人去完成，每人完成一种。由于个人的专长不同，
翻译成不同文字所需的时间（小时数）如右表，问应派哪个人去完成哪个任务，可使总花费时间最少？
工作人 英 日 德 俄甲乙丙丁
2 15 13 4
10 4 14 15
9 14 16 13
7 8 11 9
91187
1316149
1514410
413152
C
-2
-4
-9
-7
2410
4750
111006
211130
0010
2350
9606
07130
最优方案,甲翻译俄文,乙翻译日文丙翻译英文,丁翻译德文
，最优解 114?x,122?x,131?x 143?x 0,?ijx其余总费用,28小时
-4 -2
91187
1316149
1514410
413152
C
-2
-4
-9
-7
2410
4750
111006
211130
0010
2350
9606
07130
-4 -2
最优解的取法：
从含 0元素最少的行或列开始，圈出一个 0元素，用 ○表示，然后划去该○所在的行和列中的其余 0元素，用 × 表示，依次类推，若能得到 n个○，则得最优解 X0
，最优解 114?x,122?x,131?x 143?x 0,?ijx其余
4
1
4
1j i
ijij xcZ最优值：
14c? 22c? 31c? 43c? 28?
例：求费用矩阵为右表的指派问题的最优解工作人 A B C D E甲乙丙丁戊
12 7 9 7 9
8 9 6 6 6
7 17 12 14 12
15 14 6 6 10
4 10 7 10 6
6107104
10661415
121412177
66698
979712
C
-7
-6
-7
-6
-4?
26360
40089
575100
00032
20205
得 4个○，且不存在没打 × 的 0 修改方法！
对 n阶费用矩阵 C，若 C有 n 个位于不同行不同列的零元素，即可得最优解 X0。 否则，对 C进行调整。
-2
+2
04140
400811
575102
00034
20207
-2
04140
400811
35380
00034
20207
最优指派方案：甲做 B工作,乙做 C工作丙做 A工作,丁做 D工作戊做 E工作
？？
，最优解 112?x,123?x,131?x 143?x 0,?ijx其余1,55?x
26360
40089
575100
00032
20205?
当 C没有 n 个位于不同行不同列的零元素时，
对 C进行调整。
第一步：做能复盖所有 0元素的 最小直线集合,
1）对没有○的行打 √号
2）对打 √号的行上所有 0元素的列打 √号
3）再对打 √号的列上所有○的行打 √号
4）重复以上步骤直到得不出新的打 √号为止
5）对没有打 √号的行画横线，所有打 √号的列画纵线，所得到的直线既是复盖所有 0元素的最小直线集合具体步骤：
26360
40089
575100
00032
20205?
√
√
√
第二步：在没有被直线复盖的元素中找出最小元素，让打 √号的列加上这个元素，打 √号的行减去这个元素第三步：对所得到的矩阵画○，若能得到 n个○，
则得最优解，否则重复以上步骤，直至得到 n个○。
26360
40089
575100
00032
20205?
√
√
√
+2
26362
400811
575102
00034
20207
-2?
04140
400811
35380
00034
20207
-2?
例：求费用矩阵为下表的指派问题的最优解工作人 A B C D E甲乙丙丁戊
12 7 9 7 9
8 9 6 6 6
7 17 12 14 12
15 14 6 6 10
4 10 7 10 6
6107104
10661415
121412177
66698
979712
C
-7
-6
-7
-6
-4?
26360
40089
575100
00032
20205
√
√
√
+2
-2
-2
04140
400811
35380
00034
20207
，最优解 112?x,123?x,131?x 144?x 0,?ijx其余1,55?x
最优指派方案,甲做 B工作乙做 C工作,丙做 A工作丁做 D工作,戊做 E工作
Z最优值 =32 32，即总费用为匈牙利法的具体步骤：
第一步,变换指派问题的费用矩阵，使其在各行各列都出现 0元素：
方法：首先每行元素减去该行的最小元素，
然后每列减去该列的最小元素第二步,进行试指派（画○）
方法：从含 0元素最少的行或列开始，圈出一个 0
元素，用 ○表示，然后划去该○所在的行和列中的其余 0元素，用 × 表示，依次类推。
若矩阵中的○的个数等于 n，则得最优解若矩阵中的○的个数 <n，则进行第三步第三步,做能复盖所有 0元素的最小直线集合：
1）对没有○的行打 √号
2）对打 √号的行上所有 0元素的列打 √号
3）再对打 √号的列上所有○的行打 √号
4）重复以上步骤直到得不出新的打 √号为止
5）对没有打 √号的行画横线，所有打 √号的列画纵线，所得到的直线既是复盖所有 0元素的最小直线集合第四步,在没有被直线复盖的元素中找出最小元素，
让打 √号的列加上这个元素，打 √号的行减去这个元素。 转第一步例：现有 4份工作,4个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，
且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总费用最小的分派方案。
工作人 1 2 3 41
2
3
4
15 18 21 24
19 23 22 18
26 17 16 19
19 21 23 17?
17232119
19161726
18222319
24211815
C
，最优解 111?x,124?x,133?x 142?x 0,?ijx其余最优方案,第一个人做第一件事 ；
第二个人做第四件事 ； 第三个人做第三件事 ；
第四个人做第二件事 ； 总费用,70
17232119
19161726
18222319
24211815
C
0642
30110
0451
9630
0632
30010
0441
9620
0521
40010
0330
10620
√
√
√
1632
40010
1441
10620
√
√
√
√
√
2523
60012
2332
12622
0301
60012
0110
10400
，最优解 111?x,124?x,133?x
142?x 0,?
ijx其余
4、一般的指派问题
(1)求 maxZ的指派问题
(2)人数与工作数不等的指派问题
(3)一个人可做几件事的指派问题
(4)某事一定由（不能由）某人做的指派问题
1 2 … j … n
1
2
…
i
…
n
指派问题模型：
j i ijij xcZm a x
1
.
21 inijii xxxx
ts
i=1,2,…,n
121 njijjj xxxxj=1,2,…,n
njnix ij,,2,1;,,2,11,0
解：
第 i个人做第 j 人件事
Z表示总收益
i=1,2,…,n; j=1,2,…,n
第 i个人不做第 j 人件事?
0
1
ijx
nnnjnn
inijii
nj
nj
cccc
cccc
cccc
cccc
21
21
222221
111211
设有 n个工作，要由 n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。 cij表示第 i个人做第 j件事的收益,求总收益最大的指派方案。
(1)求 maxZ的指派问题工作人 1 2 … j … n
nnnjnn
inijii
nj
nj
cccc
cccc
cccc
cccc
21
21
222221
111211
1
2
…
i
…
n
指派问题最大化的数学模型：
j i
ijij xcZm a x
1
.
21 inijii xxxx
ts
i=1,2,…,n
121 njijjj xxxx j=1,2,…,n
njnix ij,,2,1;,,2,11,0
ijcM m a x?令
nnnn
n
n
cMcMcM
cMcMcM
cMcMcM
C
21
22221
11211
做 0?
指派问题最小化的数学模型：
j i ijij
xcMZm i n
1
.
21 inijii xxxx
ts
i=1,2,…,n
121 njijjj xxxx
j=1,2,…,n
njnix ij,,2,1;,,2,11,0
j i ijijij
xcMx
j i ijijj i ij xcMx
ZM
用匈牙利法
1
.
21 inijii xxxx
ts
i=1,2,…,n
121 njijjj xxxx j=1,2,…,n
njnix ij,,2,1;,,2,11,0
j i
ijij xcZm a x
j i ijij
xcMZm i n
ZM
1
.
21 inijii xxxx
ts
i=1,2,…,n
121 njijjj xxxx j=1,2,…,n
njnix ij,,2,1;,,2,11,0
21
21 m i n ZZZXX且对应的目标函数值 的可行解，是，设的可行解，也是，则 ZXX m a x21
21 ZZ由
21 ZMZM
21 ZZ
的最优解是因此，若 ZX?m i n0
的可行解是即 ZX?m i n0
0m i n ZZ取到最小值且使的可行解也是则 ZX m a x0
0m a x ZZ 取到最大值且使
00 ZMZ
21,ZZ对应的目标函数值
ijcM m ax?
对 maxZ的指派问题 工作人 1 2 … j … n
nnnjnn
inijii
nj
nj
cccc
cccc
cccc
cccc
21
21
222221
111211
1
2
…
i
…
n
ijcM m a x?令
nnnn
n
n
cMcMcM
cMcMcM
cMcMcM
C
21
22221
11211
做用匈牙利法求 C，
00 ZX 及最优值得最优解问题的最优解，就是则 ZX m a x0 0,ZM?最优值为例：现有 4份工作,4个人应聘，由于个人的技术专长不同，他们承担各项工作的效益如下表所示，
且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总效益最大的分派方案。
工作人 1 2 3 4
12 7 9 7
7 17 12 14
15 14 6 6
4 10 7 10
1
2
3
4
17?M解：
710713
111132
35010
108105
C
0306
9910
35010
5350
0006
9610
32010
5050
分派方案,第 1个人第 3项工作,第 2个人第 2项工作第 3个人第 1项工作,第 4个人第 4项工作总效益 = 9+17+15+10=51
（ 2） 人数与工作数不等 的指派问题设有 n个工作,要由 m个人来承担,每个工作只能由一个人承担，且每个人只能承担一个工作。 cij表示第 i个人做第 j件事的费用,求总费用最低的指派方案。
(a)m>n
工作人 1 2 … j … n
mnmjmm
inijii
nj
nj
cccc
cccc
cccc
cccc
21
21
222221
111211
1
2
…
i
…
m
n+1 n+2 …m
000
000
000
000
用匈牙利法求解例：现有 4份工作,6个人应聘，
由于个人的技术专长不同，他们承担各项工作所需时间如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总时间最少的分派方案。
工作人 1 2 3 41
2
3
4
5
6
5 6
0
0
0
0
0
0
0
0
0
0
0
0
12 7 9 7
7 17 12 14
15 14 6 6
4 10 7 10
6 5 5 8
4 5 7 6
006754
008556
00107104
00661415
001412177
0079712
C
002200
004002
004250
0001911
0087123
001428
分派方案：
第 3个人第 4项工作第 4个人第 1项工作第 5个人第 3项工作第 6个人第 2项工作第 1,2个人没工作总时间 = 6+4+5+5=20
工作人 1 2 … j … n
mnmjmm
inijii
nj
nj
cccc
cccc
cccc
cccc
21
21
222221
111211
1
2
…
i
…
m
m+1
m+2
…
n
0000
0000
0000
(b)m<n
用匈牙利法求解
(3)一个人可做几件事 的指派问题设 n个人中的第 k个人可同时做 t件事：
把第 k个人视为 t个人，
这 t个人做同一件事的费用系数都一样问题化为人数为 n-1+t个人的指派问题
（ 4） 某人一定不能做某事 的指派问题如在 minZ问题中，第 k个人一定不能做第 t件事：
充分大取费用系数 ijc
如在 maxZ问题中，第 k个人一定不能做第 t件事，
0?ijc取效率系数例：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由 3家建筑公司分别承建。已知第 Ai(i=1,2,3)个建筑公司对第
Bj(j=1,2,3,4,5)家新商店的建造费用的报价如下表，为保证工程进度，
每家建筑公司最多只能承建两个商店，且由于某种原因，第 B3家商店不能由第 A1个建筑公司承办，求使总费用最少的指派方案商店建筑公司 B1 B2 B3 B4 B5
A1
A2
A3
4 8 7 15 12
7 9 17 14 10
6 9 12 8 7
781296
781296
10141797
10141797
1215784
1215784B
1 B2 B3 B4 B5 A
11
A12
A21
A22
A31
A32
每家公司最多可承建两家商店：
人数 ≠工作数：
B1 B2 B3 B4 B5 B6
A11
A12
A21
A22
A31
A32
0781296
0781296
010141797
010141797
01215784
01215784
B3不能由 A1承办：
50
50
0781296
0781296
010141797
010141797
012155084
012155084
C
000012
000012
036513
036513
0573800
0573800
√
√
√
100012
100012
025402
025402
1573800
1573800
√
√√
√
√
√
√
300034
300034
225424
225424
3573822
3573822
300034
300034
003202
003202
1353600
1353600
B1 B2 B3 B4 B5 B6
A11
A12
A21
A22
A31
A32
由 A1承建 B1,B2指派方案：,由 A2承建 B5
由 A3承建 B3,B4
总费用 =42
作业：
6个人应聘 4份工作，由于个人的技术专长不同，他们承担各项工作所获得的收益如下表，且规定每人只能做一项工作，每一项工作只能由一个人承担，
试求使 总收益最大 的指派方案。
工作人 1 2 3 41
2
3
4
5
6
3 5 4 5
6 7 6 8
8 9 8 10
10 10 9 11
12 11 10 12
13 12 11 13
分派方案：
第 3个人第 2项工作第 4个人第 3项工作第 5个人第 1项工作第 6个人第 4项工作第 1,2个人没工作第一步,变换费用矩阵，使其在各行各列都出现 0元素：
方法：每行减去该行的最小元素，然后每列减去该列的最小元素第二步,进行试指派（画○）
方法：从含 0元素最少的行或列开始，圈出一个 0元素，用 ○表示，然后划去该○所在的行和列中的其余 0元素，用 × 表示，依次类推。 若矩阵中的○的个数等于 n，则得最优解若矩阵中的○的个数 <n，则进行第三步第三步,做能复盖所有 0元素的最小直线集合：
1）对没有○的行打 √号
2）对打 √号的行上所有 0元素的列打 √号
3）再对打 √号的列上所有○的行打 √号
4）重复以上步骤直到得不出新的打 √号为止
5）对没有打 √号的行画横线，所有打 √号的列画纵线，
所得到的直线既是复盖所有 0元素的最小直线集合第四步,在没有被直线复盖的元素中找出最小元素，让打 √号的列加上这个元素，打 √号的行减去这个元素。 转第一步
