2024年4月15日发(作者：数学试卷里面图形)
第五章 整数规划
§1 整数规划的数学模型及特点
要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。
其模型为：
Max(或min)z=
cx
j
j1
n
j
n
a
ij
x
ij
(,)b
i
i1,2,
m
j1
x
j
0j1,2,
n
s.t
x,x,
x
中部分或全部取整数
12n
若要求决策变量只能取值0或1的整数规划称为0-1型整数线性规划。
§5 指 派 问 题
一． 指派问题的标准形式及数学模型
在现实生活中，有各种性质的指派问题。例如，有若干项工作需要分配给若干人（或部
门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在各教室上
课等等。诸如此类的问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的
总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。
指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j
件事的费用为
c
ij
(i,j
1,2,
n)
，要求确定人和事之间的一一对应的指派方案，是完成这n
件事的总费用最少。
为了建立标准指派问题的数学模型，引入
n
个0-1变量：
2
0
若不指派第i人作第j事
x
ij
1
若指派第i人作第j件事
这样，问题的数学模型可写成
minz
nn
i，j=1,2,…n
c
i1j1
ij
x
ij
（5.1）
n
（5.2）
x
ij
1j1,2,
n
1
i
n
s.t
x
ij
1i1,2,
n
（5.3）
j1
x
ij
0,1i,j1,2,
n
（5.4）
其中，（5.1）表示每件事必优且只有一个人去做，（5.2）表示每个人必做且只做一件事。
1
指派问题是产量（
a
）注：○
i
、销量（
b
j
）相等，且
a
i
=
b
j
=1，i，j=1,2,…n的运输
1
问题。
2
有时也称
c
为第i个人完成第j件工作所需的资源数，○称之为效率系数（或价值系
ij
数）。并称矩阵
c
11
c
21
C=
(c
ij
)
nn
=
c
n1
c
12
c
22
c
n2
c
1n
c
2n
（5.5）
c
nn
为效率矩阵（或价值系数矩阵）。
并称决策变量
x
ij
排成的n×n矩阵
x
11
x
21
X=
(x
ij
)
nn
=
x
n1
x
12
x
22
x
n2
x
1n
x
2n
（5.6）
x
nn
为决策变量矩阵。
(5.6)的特征是它有n个1，其它都是0。这n个1位于不同行、不同列。每一种情况为指派
问题的一个可行解。共n!个解。
其总的费用 z =C⊙X
这里的⊙表示两矩阵对应元素的积，然后相加。
问题是：把这n个1放到X的
n
2
个位置的什么地方可使耗费的总资源最少？（解最优）
例1 已知效率矩阵
5
2
C=
0
4
则
0
3
5
8
2
0
6
0
1
0
0
0
0
0
7
0
0
0
0
1
0
0
1
0
，
X
（2）
=
10
00
1
0
0
0
0
1
0
0
0
0
0
1
0
0
X
（
1
）
=
1
0
都是指派问题的最优解
例12/P-149：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由
5家建筑公司分别承建。已知建筑公司A
i
（i=1，2，…5）对新商店B
j
（1，2，…5）的建造
费用的报价（万元）为
c
ij
（i，j=1,2,…5）,见表5-9。商业公司应当对5家建筑公司怎样
分派建筑任务，才能使总的建筑费用最少？
表5-9
2
c
B
1
B
2
B
3
B
4
B
5
ij
A
1
4 8 7 15 12
A
2
7 9 17 14 10
A
3
6 9 12 8 7
A
4
6 7 14 6 10
A
5
6 9 12 10 6
解：这是一标准的指派问题。若设0-1变量
x
1
当A
i
承建B
j
时
ij
=
0
当A
i
不承建B
…5
j
时
i,j=1,2,
则问题的数学模型为
Min z=4
x
11
+8
x
12
+…+10
x
54
+6
x
55
5
x
ij
1j1,2,
5
i1
s.t
5
x
ij
1i1,2,
5
j1
x
ij
0,1i,j1,2,
5
若看成运输问题，且
x
ij
如上所述，则表5-9为
商B
1
B
2
B
3
B
4
B
5
任务
店
公司
A
1
（4） （8） （7） （15） （12） 1
x
11
x
12
x
13
x
14
x
15
A
2
（7） (9) (17) (14) (10) 1
x
21
x
22
x
23
x
24
x
25
A
3
(6) (9) (12) (8) (7) 1
x
31
x
32
x
33
x
34
x
35
A
4
(6) (7) (14) (6) (10) 1
x
41
x
42
x
43
x
44
x
45
A
5
(6) (9) (12) (10) (6) 1
x
51
x
52
x
53
x
54
x
55
3
所选的公司数 1 1 1 1 1 5
当然，第一行的1应放在（1，1）位置，此位置同时是第一列的费用最小。但一般情况下没
有这么好。需找一适合一般的方法。
二． 匈牙利解法原理：
虽然指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问
题，因此，它可以用多种相应的解法来求解。但是，这些解法都没有充分利用指派问题的特
殊性质，有效地减少计算量。1955年，库恩（）提出了匈牙利法。
定理1：设指派问题的效率矩阵为C=
(c
ij
)
nn
，若将该矩阵的某一行（或某一列）的各
)
nn
，则以
C
为效率个元素都减去统一常数t（t可正可负），得到新的效率矩阵
C
(c
ij
矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优解之减少t.
证明：设式（5.1）～（5.4）为原指派问题。现在C矩阵的第k行个元素东减去同一常
数t,记新的指派问题的目标函数为
Z
.则有
Z
=
i1
n
c
x
=
c
x
+
c
x
=
c
ijij
n
n
nn
n
n
ijijijijij
j1
i1
ik
n
j1j1
i1
ik
n
j1
x
ij
+
(c
kj
t)x
kj
j1
n
=
c
i1
ik
j1
n
n
ij
x
ij
+
c
kj
x
kj
-t
x
kj
=
j1
j1
n
n
i1
c
j1
ij
x
ij
-t·1=Z-t
因此有
Min
Z
=min(Z-t)=minZ-t
而新问题的约束方程同原指派问题。因此其最优解比相同，而最优解差一个常数。
推论：若将指派问题的效率矩阵每一行即每一列分别减去各行及各列的最小元素，则得
到新指派问题与原指派问题有相同的最优解。
证明：结论是显然的。只要反复运用定理1便可得证。
当将效率矩阵的每一行都减去各行的最小元素，将所得的矩阵的每一列在减去当前列中
=0，从第i行来看，它最小元素，则最后得到新效率矩阵
C
中必然出现一些零元素。设
c
ij
表示第i个人去干第j项工作效率（相对）最好。而从第j列来看，这个0表示第j项工作
以第i人来干效率(相对)最高。
定义：在效率矩阵C中，有一组在不同行不同列的零元素，称为独立零元素组，此时
每个元素称为独立零元素。
例2: 已知
5
2
C=
0
4
0
3
5
8
2
0
6
0
0
0
7
0
则｛
c
12
=0，
c
24
=0，
c
31
=0，
c
43
=0｝是一个独立零元素组，
c
12
=0，
c
24
=0，
c
31
=0，
｛
c
12
=0，
c
23
=0，
c
31
=0，
c
44
=0｝也是一个独立零元素组，而
c
43
=0分别称为独立零元素。
4
｛
c
14
=0，
c
23
=0，
c
31
=0，
c
44
=0｝就不是一个独立零元素组，因为
c
14
=0与
c
44
=0这两个
零元素位于同一列中。
根据以上对效率矩阵中零元素的分析，对效率矩阵C中出现的的独立零元素组中零元
素所处的位置，在决策变量矩阵中令相应的
x
ij
=1，其余的
x
ij
=0。就可找到指派问题的一个
最优解。
就上例中
0
0
X
（
1
）
=
1
0
就是一个最优解。同理
1
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
0
1
，
0
0
0
0
0
1
0
0
X
（2）
=
1
0
也是一个最优解。
但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个，这样就无法求出最
优指派方案，需作进一步的分析。首先给出下述定理。
定理2 效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。
我们不证它，说一下意思：
例3：已知矩阵
5
2
C
1
=
0
4
0
3
5
8
2
0
6
0
5
0
2
0
0
，C=
2
7
4
0
0
0202
3000
5572
，C
3
=
8004
6365
7
4
0
6
0
0202
3000
335
8004
4143
分别用最少直线去覆盖各自矩阵中的零元素：
5
2
C
1
=
0
4
0
3
5
8
2
0
6
0
5
0
2
0
0
， C=
2
7
4
0
0
0202
3000
5572
， C
3
=
8004
6365
7
4
0
6
0
0202
3000
335
8004
4143
可见，C
1
最少需要4条线，C
2
最少需要4条线，C
3
最少需要5条线，方能划掉矩阵中
所有的零。即它们独立零元素组中零元素最多分别为4，4，5。
三． 匈牙利法求解步骤：
5
我们以例题来说明指派问题如何求解：
例4 给定效率矩阵
215134
1041415
C=
9141613
78119
求解该指派问题。
解：ⅰ）变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。
min
215134
2
1041415
4
行变换
C=
9141613
9
78119
7
01311
6010
057
014
2
01370
列变换
11
6069
=
C
40532
2
0100
Min
0 0 4 2
这样得到的新矩阵
C
中，每行每列都必然出现零元素。
ⅱ）用圈0法求出新矩阵
C
中独立零元素。
（1）进行行检验
对
C
进行逐行检验，对每行只有一个未标记的零元素时，用○记号将该零元素圈起。
然后将被圈起的零元素所在的列的其它未标记的零元素用记号×划去。如
C
中第2行、第
3行都只有一个未标记的零元素，用○分别将它们圈起。然后用×划去第1列其它未被标记
的零元素（第2列没有），见
C
01370
6069
C
=
C
0532
0100
在第i行只有一个零元素
c
ij
=0时，表示第i人干第j件工作效率最好。因此优先指派
第i人干第j项工作，而划去第j列其它未标记的零元素，表示第j项工作不再指派其它人
去干（即使其它人干该项工作也相对有最好的效率）。
重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为
止。
本题
C
中第1行此时也只有1个未被标记的零元素。因此圈起
C
中第1行第4列的
零元素
c
14
，然后用×划去第4列中未被标记的零元素。这是第4行也只有一个未被标记的
零元素
c
43
，再用○圈起，见
C
6
01370
6069
C
=
C
0532
0100
（2）进行列检验
与进行行检验相似，对进行了行检验的矩阵逐列进行检验，对每列只有一个未被标记
的零元素，用记号○将该元素圈起，然后技改元素所在行的其他未被标记的零元素打×。重
复上述列检验，直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。
这时可能出现以下三种情况：
1
每一行均有圈0出现，圈0的个数m恰好等于n,即m=n. ○
2
存在未标记的零元素，但他们所在的行和列中，为标记过的零元素均至少有两个。 ○
3
不存在未被标记过的零元素，当圈0的个数m< n. ○
ⅲ) 进行试指派
1
出现，则可进行试指派：令圈0为止的决策变量取值为1，其他决策变量取值若情况○
均为零，得到一个最优指派方案，停止计算。
1
，可令
x
=1，
x
=1，
x
=1，
x
=1，其余
x
=0。上例中得到
C
后，出现了情况○
31
1422
43
ij
即为最优指派。
2
出现，则在对每行、每列的其它未被标记的零元素任选一个，加上标记○，若情况○
即圈上该零元素。然后给同行、同列的其它未被标记的零元素加标记×。然后再进行行、列
1
或○
3
，出现情况○
1
则由上述得到一最优指派，停止计算。 检验，可能出现情况○
3
出现，则要转入下一步。 若情况○
ⅳ）：做最少直线覆盖当前所有零元素。
我们还以例12来说明过程：
已知例12指派问题的系数矩阵为：
4
7
C
6
6
6
0
行变换
0
C
0
0
0
43
87
917
912
714
912
1512
1410
87
810
106
30118
1773
2321
=
C
0504
2340
先对各行元素分别减去本行的最小元素，然后对各列也如此，即
118
0
21073
0
列变换
3621
0
1804
0
03640
此时，
C
中各行各列都已出现零元素。
为了确定
C
中的独立零元素，对
C
加圈，即
7
0
0
C
=
0
0
0
30118
1773
2321
0504
2340
由于只有4个独立零元素，少于系数矩阵阶数n=5,不能进行指派，为了增加独立零元
素的个数，需要对矩阵作进一步的变换，变换步骤如下：
（1）对
C
中所有不含圈0元素的行打√，如第3行。
（2）对打√的行中，所有零元素所在的列打√，如第1列。
（3）对所有打√列中圈0元素所在行打√，如第2行。
（4）重复上述（2），（3）步，直到不能进一步打√为止。
（5）对未打√的每一行划一直线，如第1，3，5行。对已打√的每一列划一纵线，如
第1列，既得到覆盖当前0元素的最少直线数。见
C
。
0
0
C
=
0
0
0
30118
0
1773
0
2321
0
0504
0
02340
30118
1773
2321
=
C
0504
2340
Ⅴ）：对矩阵
C
作进一步变换，以增加0元素。
在未被直线覆盖过的元素中找最小元素，将打√行的各元素减去这个最小元素，将打
√裂的各元素加上这个最小元素（以避免打√行中出现负元素），这样就增加了零元素的个
数。
如
C
中未被直线覆盖过的元素中，最小元素为
c
21
=
c
35
=1，对打√的第2，3行各元素
都减去2，对打√的第1列各元素都加上1，得到矩阵
C
。
0
1
C
1
0
0
1
0
C
=
0
1
1
30118
1
0662
0
1210
0
0504
1
12340
30118
0662
1210
=
C
0504
2340
Ⅵ）：回到步骤Ⅱ），对已增加了零元素的矩阵，再用圈0法找出独立零元素组。
30118
0662
1210
0504
2340
C
中已有5个独立零元素，故可确定指派问题的最优方案。本例的最优解为
8
0
0
*
X=
1
0
0
0100
1000
0000
0010
0001
也就是说，最优指派方案是：让A
1
承建
B
3
A
2
B
2
A
3
B
1
A
4
B
4
A
5
B
5
这样按排能使总的建造费最少，为 z=7＋9＋6＋6＋6=34（万元）
四． 一般的指派问题
在实际应用中，常会遇到非标准形式，解决的思路是：先化成标准形式，然后再用匈
牙利法求解。
1． 最大化的指派问题
其一般形式为
maxz
c
i1j1
nn
ij
x
ij
n
x
ij
1j1,2,
n
1
i
n
s.t
x
ij
1i1,2,
n
j1
x
ij
0,1i,j1,2,
n
处理办法：设最大化的指派问题的系数矩阵为C=
(c
ij
)
nn
，m=max｛
c
11
,c
12
,c
nn
｝,令
B=
(B
ij
)
nn
=
(mc
ij
)
nn
，则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大
化指派问题有相同的最优解。
例5：某工厂有4名工人A
1
，A
2
，A
3
，A
4
，分别操作4台车床B
1
，B
2
，B
3
，B
4
。每小时单
产量如下表，求产值最大的分配方案。
车床 B
1
B
2
B
3
B
4
工人
A
1
A
2
A
3
A
4
10 9 8 7
3 4 5 6
2 1 1 2
4 3 5 6
9
10
3
解：C=
(c
ij
)
nn
=
2
4
9
4
1
3
8
5
1
5
7
6
，m=max｛10,9,8,7,…5,6｝=10,
2
6
0
7
B=
(B
ij
)
nn
=
(10c
ij
)
nn
=
8
6
=
B
B
中的◎数=n=4, 所以
1
6
9
7
2
5
9
5
3
0
4
3
0
8
2
4
1
2
1
3
2
1
1
1
3
0
0
3
00
20
0
1
0
2
1
0
0
0
3
0
=
0
0
1
0
X=
0
0
0
0
1
0
0
0
0
1
0
1
（5。7）
0
0
即为最优解。
从而产值最大的分配方案也为（5.7），最大产值为
Z=10＋6＋1＋5=22
2． 人数和事数不等的指派问题。
1
若人数< 事数，○添一些虚拟的“人”，此时这些虚拟的“人”做各件事的费用系数取为0，
理解为这些费用实际上不会发生。
2
若人数> 事数，添一些虚拟的“事”○，此时这些虚拟的“事”被各个人做的费用系数同
样也取为0。
例6：现有4个人，5件工作。每人做每件工作所耗时间如下表：
工
作 B
1
B
2
B
3
B
4
B
5
工人
A
1
10 11 4 2 8
A
2
7 11 10 14 12
A
3
5 6 9 12 14
A
4
13 15 11 10 7
问指派那个人去完成哪项工作，可是总消耗最小？
解：添加虚拟人A
5
，构造标准耗时阵：
10
1011428
711101412
行变换
691214
C=
5
131511107
00000
8
0
C
=
0
6
0
8
0
0
6
0
9206
4375
1479
=
C
8430
0000
所圈0数=4< 5=n,下找最少覆盖0的直线。
9206
4375
1479
8430
0000
从未划去的元素中找最小者：｛4，3，7，5，1，4，7，9｝=1。未划去的行减去此最小者1，
划去的列加上次最小者1，得
C
。
9
0
C
=
0
7
1
0
1
X
=
0
0
0
9206
3264
0368
8430
0000
0010
0000
1000
0001
0100
◎个数=n,从而的一最优指派：
从而最少耗时为 z=2＋7＋6＋7=22
3.一个人可做几件事的指派问题。
若某人可作几件事，则可将该人化作相同的几个“人”来接受指派。这几个“人”做同
一件事的费用系数当然一样。
例6：对例12的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司A
4
和A
5
，让技
术力量较强的建筑公司A
1
、A
2
、A
3
来承建。根据实际情况，可以允许每家建筑公司承建一
家或两家商店。求使总费用最少的指派方案。
解：反映投标费用的系数矩阵为：
B
1
B
2
B
3
B
4
B
5
4871512
A
1
79171410
A
2
691287
A
3
由于每家建筑公司最多可承建两家新商店，因此，把每家建筑公司化作相同的两家建筑公司
（
A
i
和
A
i
，i=1，2，3）。这样，系数矩阵变为：
B
1
B
2
B
3
B
4
B
5
11
4
4
7
7
6
6
8
8
7
7
917
917
912
912
1512
1512
1410
1410
127
127
上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚拟事，使之成
为标准的指派问题，其系数矩阵为：
B
1
B
2
B
3
B
4
B
5
B
6
48715120
48715120
C=
791714100
791714100
6912870
6912870
000750
000750
C
列变换
3110630
=
C
3110630
215000
215000
C
的◎数=5< 6=n,下找0元素的最少直线覆盖。
000750
000751
000750
000751
C
=
3110630
√
209520
3110630
-1
√ -1
9520
=
C
0
215000
2
215001
215000
215001
从而得一最优指派：
001000
承建
100000
公司
商店
X
=
010000
A
1
B
1
000001
B
3
000010
00100
A
2
B
2
0
B
6
=ψ
ψ
A
B
4
3
B
5
12
总费用为z=7＋4＋9＋7＋8=35(万元)
4．某事不能由某人去做的指派问题
某事不能由某人去做，可将此人做此时的费用取作足够大的M。
例7：分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的
时间如下表。由于任务重，人数少，考虑：
a). 任务E必须完成，其它4项任务可选3项完成。但甲不能做A项工作。
b) 其中有一人完成两项，其他人每人完成一项。
试分别确定最优分配方案，使完成任务的总时间最少。
任务 A B C D E
人
甲
乙
丙
丁
25 29 31 42 37
39 38 26 20 33
34 27 28 40 32
24 42 36 23 45
解：这是一人数与工作不等的指派问题，若用匈牙利法求解，需作一下处理。
a) 由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作E必须完成，故设
戊完成E的时间为M（M为非常大的数），即戊不能做工作E，其余的假想时间为0，建立
的效率矩阵表如下：
任
务
人
甲
乙
丙
丁
戊
A B C D E
M 29 31 42 37
39 38 26 20 33
34 27 28 40 32
24 42 36 23 45
0 0 0 0 M
用匈牙利法求解过程如下：
M
39
C=
34
24
0
29314237
38262033
行变换
27284032
42362345
000M
M02138
19186013
列变换
701135
11913022
0000M
M02133
1918608
701130
11913017
0000M
由于◎数=4< 5=阶数，下找最少覆盖0的直线
13
M02133
1918608
√ -1
C
=
701130
11913017
√ -1
0000M
m=｛19,18.6.13,1,19,13,22｝=1,第2、4行减去1，第4列加上1得
C
：
M02133
1817507
C
=
701140
从而得最优指派：
01812016
0001M
甲
乙
丙
B
D
E
丁 A
最少的耗时数z=29＋20＋32＋24=105.
甲
，乙，丙，丁。 b) 思路：方案1：甲，○
乙
，丙，丁。 方案2：甲，乙，○
丙
，丁。 方案3：甲，乙，丙，○
丁
。 方案4：甲，乙，丙，丁，○
甲
，乙，○
乙
，丙，○
丙
，丁，○
丁
。此为人；而工作：A，B，C，D，E， 方案5：甲，○
虚拟工作：F，G，H。
这些思路都比较烦，请看下面的思路：
设有虚拟人戊，它集五人优势为一身。即戊的费用是每人的最低。戊所做的工作即为此项工
作的费用最低者的工作。
任
务
人
甲
乙
丙
丁
戊
A B C D E
25 29 31 42 37
39 38 26 20 33
34 27 28 40 32
24 42 36 23 45
24 27 26 20 32
以下用匈牙利法求解：
25
39
C=
34
24
24
29314237
38262033
行变换
27284032
42362345
27262032
0461712
19186013
701135
1913022
476012
0461712
19186013
701135
=
C
1913022
476012
14
对
C
加圈确定独立0元素，◎个数=3<5=n,作0元素的最少直线覆盖：
0461712
19186013
C
=
701135
1913022
476012
√
√
√
在未划去的数中选最小者1，未划取得行都减去1，划去的列都加上1得：
045187
1817407
C
=
700140
再圈0且试指派：◎个数=3< 5，再作0元素的最
0811016
36406
少直线覆盖。从未划取的元素中找最小者4，未划取得行都减去这个4，划去的列都加上这
个4，得
C
：
00
1813
C
=
110
04
32
1183
103
0180
再圈0试指派，结果为：
7012
002
甲
乙
丙
丁
B
D
E
A
戊 C
其中戊是虚拟人，不能真作，它作C工作是借乙
（此列最小时数26是C所创业绩）优势，应由C来作。即C做两件工作：D，C。
15
更多推荐
指派,元素,问题,矩阵,效率,公司,系数,建筑
发布评论