第四章 整数规划
§1 整数规划问题
在前面的线性规划问题中，它的解都假
设为可以取连续数值。但是在许多实际问题
中，决策变量仅仅取整数值时才有意义，比
如变量表示的是工人的人数、机器的台数、
货物的箱数、装货的车皮数等等。为了满足
整数解的要求，比较自然的简便方法似乎就
是把用线性规划求得的非整数解进行“四舍
五入”取整或“舍尾取整”处理。当然，这样做
有时确实也是有效的，可以取得与整数最优
解相近的可行整数解，因此它是实际工作中
经常采用的方法。但是实际问题中并不都是
如此，有时这样处理得到的解可能不是原问
题的可行解，有的虽是原问题的可行解，但
却不是整数最优解。（详见后面例 1）。因而
有必要专门研究只取整数解的线性规划的
解法问题。
在一个线性规划问题中，如果它的所有
决策变量都要求取整数时，就称为纯整数规
划；如果仅部分决策变量要求取整数则称为
混合整数规划，二者统称为整数规划。整数
规划的一个特殊情形是0-1规划，它的决策
变量取值仅限于0或1两个逻辑值。整数规
划是近几年发展起来的规划论的一个分支。
下面举例说明对于整数规划问题，用“四舍
五入”取整或“舍尾取整”方法，是行不通的。
例 1.现有甲、乙两种货物拟用集装箱托运，
每件货物的体积、重量、可获利润，以及集
装箱的托运限制如下表：
货物 体积 （立方米/件） 重量 （万元/件） 利润 （万元/件）
甲
乙
5
4
2
5
20
10
托运限制 24 13
试确定集装箱中托运甲、乙货物的件数，使
托运利润最大。
设 12,xx分别表示甲、乙货物托运的件数
（整数），则该问题数学模型为：
12
12
12
12
max2010 (1)
5424 (2)
2513 (3)
,0, (4)
Zxx
xx
xx
xx
=+
+￡
+￡
? 整数
这里货物的件数只能是整数，所以这是一个
纯整数规划。
若先不考虑整数限制，可求得问题的最
优解为： 124.8,0,maxZ96xx===
由于1 4.8x = 不符合整数要求，所以该解
不是整数规划的最优解。是否可以将非整数
解用“四舍五入”方法处理呢？
事实上，如果将 124.8,0xx==近似为
125,0xx==，则该解不符合体积限制条件
（2）： 125424 xx+￡，因而它不是最优解。
那么用“舍尾取整”方法处理又如何呢？
将 124.8,0xx==舍尾取整，显然满足各约束
条件，因而它是整数规划问题的可行解，但
它不是整数最优解。因为它对应的目标函数
值 80Z = ，而 124,1xx==这个解也是可行解，
但它对应的目标函数值 90Z = 。
由此例看出，简单的处理方法常常得不
到整数规划的最优解，甚至得不到可行解。
如何求得这类问题的整数最优解呢？
到目前为止，整数规划还没有一种很满
意的和有效的解法。现在用以求解整数规划
的方法基本都是将整数规划变为一系列线
性规划来求解的。我们将介绍两种方法-----
分枝定界法和割平面法。
§2 分枝定界法
分枝定界法是求解整数规划的常用算
法，既可用来解全部变量取值都要求为整数
的纯整数规划，又可用以求解混合整数规划。
该算法的基本思路是：先不考虑整数限
制，求出相应的线性规划的最优解，若此解
不符合整数要求，则去掉不包含整数解的部
分可行域，将可行域D分为 12DD、 两部分
（分枝），然后分别求解这两部分可行域对
应的线性规划，如果它们的解仍不是整数解，
则继续去掉不包含整数解的部分可行域，将
可行域 12DD或 分成 3D与 4D两部分，再求解 3D
与 4D对应的线性规划，L ，在计算中若已得
到一个整数可行解 0X ，则以该解的目标函数
值 0Z 作为分枝的界限，如果某一线性规划的
目标值 0ZZ￡ ,就没有必要继续分枝，因为分
枝（增加约束）的结果所得的最优解只能比
0Z 更差。反之若 0ZZ> ,则该线性规划分枝后，
有可能产生比 0Z 更好的整数解，一旦真的产
生了一个更好的整数解，则以这个更好的整
数解目标值作为新的界限，继续进行分枝，
直至产生不出更好的整数解为止。
例2 求解下面整数规划
12
12
12
12
12
maxZ4090 (1)
9756 (2)
72070 (3)
,0 (4)
,
xx
xx
xx
xx
xx
=+
+￡
+￡
?
整数 (5)
解：先不考虑条件（5），求解相应的线性规
划问题L,得最优解
1204.81,1.82,356xxZ===
该解不是整数解。选择其中一个非整数变量，
如 1 4.81x = ，对问题L 分别增加约束条件：
114,5xx￡?，将问题L 分解为两个子问题
12,LL(分枝)，也就是去掉L 不含整数解的一
部分可行域，将原可行域D变为 12DD、 两部
分。
求解线性规划 12,LL得最优解为：
问题 1L : 1+4Lx￡ 问题 2L： 1+5Lx?
124.00,2.10xx==
1 349Z =
125.00,1.57xx==
2 341Z =
因为没有得到整数解，所以继续对 1L进行分
解，增加约束： 222,3xx￡?，将 1L分解成问
题 3L与 4L ,并求得最优解如下：
问题 3122LLx+￡： 问题 412:3LLx+?
124.00,2.00xx==
3 340Z =
121.42,3.00xx==
4 327Z =
问题 3L 的解已是整数解，它的目标值
3 340Z = ，大于问题 4L的目标值，所以问题 4L
已无必要再分枝。但由于问题 2L的目标值 2Z
大于 3Z ，分解 2L还有可能产生更好的整数解，
因此继续对 2L分枝。增加约束 221,2xx￡?，
将 2L分解成问题 56LL， ,并求解，结果如下：
问题 5221LLx+￡： 问题 622:2LLx+?
125.441.00xx==，
5 308Z =
无可行解
问题 5L 的 53305340ZZ=<= ,所以不必分解
了。问题 6L无可行解，于是可以断定问题 3L
的解： 124.00,2.00xx==即为最优整数解。
用分枝定界法求解整数规划的步骤可
总结如下：
步骤 1：求解与整数规划相对应的线性
规划L,若L无可行解，则整数规划也没有可
行解，计算停；若L,的最优解是整数解，则
该解即为整数规划的最优解，计算停；若L
的最优解不是整数解，则转步骤2
步骤2（分枝）：在 L的最优解中任选一
个不符合整数条件的变量 BiX ，其值为 1(Bb)i- ，
1Bb
i
-??o?为小于 1(Bb)
i
- 的最大整数，构造两个
约束条件 1BbBi iX -??￡ o?和 1Bb+1Bi iX -??? o? ，将
这两个约束条件分别加在问题L的约束条件
上，形成两个子问题 12LL， .
步骤3（定界）：取整数解中最大目标值
为界限值Z (下界)，如果计算中尚无整数解，
则取 .Z =-￥ 检查分枝 iL，若它的最优解不
是整数解，且 iZZ> ，则重复步骤2，若 iZZ￡ ，
则 iL不再分枝。
重复步骤2，步骤3，直至所有分枝都不
能再分解为止，这时界限值Z对应的整数解
即为原问题的最优解。
用分枝定界法可解纯整数规划问题和
混合整数规划问题。它比穷举法优越，因为
它仅在一部分可行的整数解中寻求最优解，
计算量比穷举法小。若变量数目很大，其计
算量也是相当可观的。
练习：用分枝定界法求解整数规划
12
12
12
12
12
maxZ23
5735
4936
,0
,
xx
xx
xx
xx
xx
=+
+￡
+￡
?
整数
答案： 124,2,14xxz===
§3 割平面法
割平面法是 1958 年美国学者
R.E.Gomory 提出的求解纯整数规划的一种
比较简便的方法，其基本思想是：先不考虑
变量的整数限制求解线性规划，如果得到的
解不是整数解，则不断增加适当的约束，割
掉原可行域不含整数解的一部分，最终得到
一个具有若干整数顶点的可行域，而这些顶
点中恰有一个顶点是原问题的整数解。
割平面法的基本步骤：
步骤 1、不考虑变量的整数限制，求解
相应的线性规划问题，如果该问题无解，或
最优解已是整数解，则停止计算，否则转下
一步。
步骤 2、对上述线性规划的可行域进行
切割，去掉不含整数解的一部分可行域，即
增加适当的线性约束，然后转步骤1
割平面法的关键在于如何确定切割方
程，使之能对可行域进行真正的切割，而且
切去部分不含有整数解点。
下面讨论切割方程的求法。
设与整数规划相对应的线性规划最优
解中基变量 1(b)BiiXB-= 不是整数，将最优
单纯形表中该基变量对应的行还原成约束
方程，即 1(Bb)BiijjiXax -+= （1）
将 1(Bb)iija- ， 都分解成整数与非负真分
数之和的形式，即
1()01(2)
01(3)
iiii
ijijijij
BbNff
aNff
- =+<<
=+<<
其中
其中
这里 ,iijNN是整数，将（2）（ 3 ） 代 入 （ 1 ），
得 ()BiijijjiiXNfxNf++=+
即 BiijjiiijjXNxNffx+ －＝－（４）
当 iX 都是整数时，（4）式左端是整数，所以
右端也应是整数，但右端是两个数之差，且
01,if<
0 iijjffx￡ - （5）
取（5）式为切割方程。因为任何整数可
行解都满足这个方程，所以把它加到原问题
的约束中，它能够对原可行域进行切割，而
不会切割掉整数解。
例3、用割平面法求解
12
12
12
12
max=
1
34
,0,
Zxx
xx
xx
xx
+
-+￡
+￡
? 整数
解：利用单纯形法求解，解得
12
3710,,2.5
444xxz
====
1
3,
4x = 不是整数，将表中第一行还原成方程，
即 134113444xxx-+=
因为 3313110,1,0444444=+-=-+=+
所以有 1334331444xxxx-=--
因而有切割方程： 34313444xx+?
即 3433xx+?
得到新的方程：
34533xxx--+=- （切割方程）
将新的约束方程加到原最优表下面（切割），
利用对偶单纯形法，求得新的最优解为：
121,1,2xxz
===
割平面法只能用于纯整数规划。在求解
实际问题中，割平面法经常会遇到收敛很慢
的情况，但若和其它方法，如分枝定界法，
联合使用，一般能收到比较好的效果。
练习：用割平面法求解纯整数线性规划
12
12
12
12
max=
26
4520
,0,
Zxx
xx
xx
xx
+
+￡
+￡
? 整数
答案： 120,4,4xxz===
§4 0-1 型整数规划
0-1 型整数规划是整数规划的特殊情形，
它的决策变量仅取0或1这两个值，这时的
决策变量也称为0-1变量。在实际问题中，
有些问题只需回答“是”或“否”，问题就解决
了，描述这类问题的变量只需取两个值就可
以了。例如是否采纳某个方案；某项任务是
否可以交某人承担；集装箱内是否装入某种
货物等等。
对于这类问题我们可以用逻辑变量来
描述： 10x =
是
否
4.1 引入0-1变量的实例
1.确定投资方案-----相互排斥的计划
例4、某市工商银行拟抽调a万元资金对小五
金、小百货和洗涤剂三个行业给予低息贷款。
由于资金有限，只能在四个小五金企业
1234AAAA、 、 、 中至多选两个；在五个小百货
企业 56789AAAAA、 、 、 、 中至多选三个；在三
个洗涤企业 101 12AAA、 、 中至多选两个给予
低息贷款。已知企业 iA得到贷款 ia万元后，可
获利 ib万元。问工商银行如何发放贷款，可
使总利润最大？
解：因为本问题只要求解决是否给企业贷款，
因此可用0-1变量描述所求方案。
设 1 1,2,...,120 ii
i
xi ==
给A 贷款，
不给A贷款
于是，根据题意，本问题可描述为：
12
1
124
11
912
510
maxZ
,2
3,2
011,2,...12
ii
i
iii
ii
ii
i
bx
axax
xx
xi
=
==
==
￡￡
￡￡
或，
这是一个0-1整数规划问题。与其相类似的
问题很多，比如：投资项目的选择；投资场
所的选定；工厂的选址；新产品开发方案的
确定等等。总之，凡是一些相互排斥的计划，
方案的确定问题都可以归结为与例4类似的
0-1整数规划问题。
2、相互排斥的约束条件
回顾本章例 1，例 1.现有甲、乙两种货物拟
用集装箱托运，每件货物的体积、重量、可
获利润，以及集装箱的托运限制如下表：
货物 体积 （立方米/件） 重量 （万元/件） 利润 （万元/件）
甲
乙
5
4
2
5
20
10
托运限制 24 13
试确定集装箱中托运甲、乙货物的件数，使
托运利润最大。
设 12,xx 分别表示甲、乙货物托运的件
数（整数），则该问题数学模型为：
12
12
12
12
max2010 (1)
5424 (2)
2513 (3)
,0, (4)
Zxx
xx
xx
xx
=+
+￡
+￡
? 整数
今设集装箱有车运和船运两种方式，（3）式
是车运时的重量限制条件。如用船运时关于
重量的限制条件为 122520xx+￡。试确定集
装箱托运甲、乙货物的数量及运输方式，使
总利润最大。为了建立问题的模型，除了设
甲、乙货物托运的件数分别为 12,xx外，还要
把运输方式表示出来。由于只有两种运输方
式，所以可设 10y =
车运
船运 ，在约束条件中，
两种不同运输方式对应的重量约束条件是
相互排斥的，所以不能简单地将它们都写在
约束中。
利用y这个 0-1 变量可以将上述两个重
量约束改写成：
12
12
2513+(1-y)M
2520+yM (6)
xx
xx
+￡
+￡
(5)
其中M是相当大正数，显然当 1y = 时，（5）
式就是车运的重量限制条件，而（6）式自然
成立，因而是多余的；当 0y = 时，（6）式就
是船运的重量限制条件，而（5）式成为多余
的。经过这样处理后，问题的数学模型就可
以写成如下形式：
12
12
12
12
12
max2010
5424
2513+(1-y)M
2520
,0,
y=0
Zxx
xx
xx
xxyM
xx
=+
+￡
+￡
+￡+
?
整数
或1
类似地，如果有m个相互排斥的约束条件：
1122 ... (i1,2,...)iiinniaxaxaxbm+++￡=
为了保证这m个条件只有一个起作用，可以
引入m个 0-1 变量 (i1,2...m)iy = 和充分大正
数M，将这个约束条件改写成：
1122 ... yM(i1,2,...)iiinniiaxaxaxbm+++￡+=
12....1myyym+++=-
显然，这些 iy中只能有一个取0值，因而这
m个约束中只能有一个起作用，而其余都是
多余的。
4.2 0-1型整数规划的解法
对于0-1型整数规划的求解问题，由于
每个变量只取0、1两个值，人们自然会想到
用穷举法来求解，即排出变量取值为0或1
的每一种组合（共2n 个点），验证它们是否
满足约束条件，再算出每个可行解的目标函
数值，比较各函数值以求得最优解。显然当
n较大时，计算量是相当大的。（ 1021024= ）
因此，常设计一些方法，只检查变量取值组
合的一部分，就能求得问题的最优解。这一
类方法称为隐枚举法。
为了便于应用隐枚举法，当目标函数要
求极大值时，可先将0-1型整数规划中变量
ix的顺序重新排列，使 ix在目标函数中的系
数呈递增（不减）的，并且按二进制数码从
小到大的顺序排列每一组解，即按
(00...00)(00...01)(00...10)...(11...11)、 、 的顺序
排列。这样，可使最优解容易比较早地发现，
使得计算简化。
下面举例说明如何运用隐枚举法求解
0-1型整数规划。
例5、求解下列整数规划
123
123
123
12
23
123
max32+5
22
44
3
46
,,01
Zxxx
xxx
xxx
xx
xx
xxx
=-
+-￡
++￡
+￡
+￡
= 或
解：调整 12,xx的顺序，使目标函数中变量的
系数呈递增（不减）的顺序，则问题变为：
213
213
213
21
23
123
max2+3+5
2+2 (1)
44(2)
3(3)
46(4)
,,01
Zxxx
xxx
xxx
xx
xx
xxx
=-
-￡
++￡
+￡
+￡
= 或
按二进制数码从小到大的顺序排列并检查
各个解，先计算解的目标值，若目标值小于
目前可行解最好的目标值，则不必检查是否
满足约束条件，当所有解被检查完毕，就可
判断出最优解。计算结果可列表表示，如下
表
解（ 213,,xxx） 目标值 约束条件 （1）（ 2 ）（ 3 ）（ 4 ）
（0 0 0 ） 0 √ √ √ √
（0 0 1 ） 5 √ √ √ √
（0 1 0 ） - - - - -
（0 1 1 ） 8 √ √ √ √
（1 0 0 ） - - - - -
（1 0 1 ） - - - - -
（1 1 0 ） - - - - -
（1 1 1 ） 6 - - - -
最终得到最优解： 1231,0,1,8xxxz====
练习：用隐枚举法解下列0-1型整数规划
123
123
123
13
123
max432
2534
433
1
01
Zxxx
xxx
xxx
xx
xxx
=++
-+￡
++?
+?
= ， ， 或
§5 指派问题
在实际问题中，常常会碰到这样的问题，
要指派n个人去完成n项不同任务，每个人
必须完成其中一项而且仅仅一项。但由于个
人的专长不同，任务的难易程度不一样，所
以完成不同任务的效率就不同，那么应该指
派哪个人去完成哪项任务，能使总的效率最
好呢？这就是典型的指派问题。
例 6 今欲指派张王李赵四人加工
A,B,C,D 四种不同的零件，每人加工四种零
件所需要的时间如下表所示，问应该指派谁
加工何种零件可使总的花费时间最少？
零件
人 A B C D
张
王
李
赵
4 6 5 8
6 10 7 8
7 8 11 9
9 3 8 4
在类似问题中都必须给出一个像上表一样
的矩阵C,称为效率矩阵。
1 121
21222
12
...
...
..... .. ...
...
n
n
nnnn
CCC
CCCC
CCC
??
??
=
??o?
矩阵中的元素 ijC 表示指派第i 个人去
完成第j项任务时的效率
求解这类问题时，通常引入0-1变量：
1 ,1,2,...,
0ij
ijxijn ==
指派第个人去完成第项任务 ，
不指派第个人去完成第项任务
于是，对于极小化问题，指派问题数学模型
为：
11
1
1
min
1,1,2,...,n
1,1,2,...,
10
nn
ijij
ij
n
ij
i
n
ij
j
ij
Zcx
xj
xin
x
==
=
=
=
==
==
=
或
从模型看，指派问题是特殊的0-1规划，
也是特殊的运输问题，可以用这两种问题的
求解方法求解，但这就如同用单纯形法求解
运输问题一样是不合算的。
根据指派问题的特殊结构，我们有更为
简便的方法。这就是下面将介绍的匈牙利法，
这个方法是由匈牙利数学家康尼格给出的。
匈牙利算法是以指派问题最优解的性
质为根据的。
指派问题最优解性质：如果将指派问题
的效率矩阵的每一行（列）的各个元素都减
去该行（列）的最小元素，得到一新的矩阵
C￠,则以C￠为效率矩阵的指派问题的最优解
与原问题的最优解相同。
证明：设C的第i行元素都减去该行最小
元素 ia，第j列元素都减去该列最小元素 jb，
则新矩阵C￠第i行第j列都减去该列最小元
素为 ijijijCCab￠ =--，以新矩阵C￠为效率矩
阵的指派问题的目标函数为
()iji ijijij
iji ij
ij
ZCxCabx
Cxab
Zab
￠￠==--
=--
=--
可见新问题的最优解与原问题的最优解相
同，只是目标值相差一个常数。证毕.
利用这个性质，可以使原效率矩阵变换
为含有多个0元素的新效率矩阵，而最优解
不变。在新的效率矩阵中如果能找到n个不
同行且不同列的0元素，则可以令它们对应
的 ijx 等于 1，其它 ijx 等于 0.显然，该解一定
是最优解。这就是匈牙利算法的基本思想。
具体步骤如下：
第一步 变换效率矩阵，使各行各列都
出现0元素
1 效率矩阵每行元素都减去该行最小
元素
2 效率矩阵每列都减去该列最小元素
第二步 圈出不同行且不同列的0元素，
进行试指派
1 （行搜索）给只有一个0元素的行中
的0画圈，记作“◎”，并划去与其同列的其
余0元素；
2 （列搜索）给只有一个0元素的列中
的0画圈，记作“◎”，并划去与其同行的其
余0元素
3 反复进行1、2，直至所有0元素都有
标记为止
4 若行（列）的0元素均多于一个，则
在0元素最少的行（列）中选定一个0元素，
标“◎”，并划去与其同行同列的其余0元素
5 若不同行且不同列的“◎”已达 n 个，
则令它们对应的 1ijx = ，其余 0ijx = ，已得到
最优解，计算停，否则转到第三步
第三步 用最少直线覆盖效率矩阵中的
0元素
1 对没有“◎”的行打“√”
2 对打“√”行中的0元素所在列打“√”
3 对打“√”列中“◎”所在行打“√”
4 反复进行2,、3，直至打不出新“√”为
止
5 对没打“√”的行画横线，对打“√”列画
竖线，则效率矩阵中所有0元素被这些直线
所覆盖
第四步 调整效率矩阵，使出现新的0元
素
1 找出未被划去元素中的最小元素，以
其作为调整量q
2 矩阵中打“√”行各元素都减去q，打“√”
列各元素都加q（以保证原来的0元素不变），
然后去掉所有标记，转第二步
下面用上述方法求解例6
零件
人 A B C D
张
王
李
赵
4 6 5 8
6 10 7 8
7 8 11 9
9 3 8 4
解：先变换效率矩阵，然后圈出不同行不同
列的0元素，结果如下：
465802140203
6107804120401
7811901420131
938460516040
??????
??????
? ?
?????
?? ?o?o?o?
由于不同行不同列的 0 元素仅有 3 个，
所以要继续第三步和第四步
最后调整 =1q ，调整效率矩阵使之出现
更多的0元素。而后，再重新圈出不同行且
不同列的0元素，进行再指派。由于◎的个
数已达4个，所以令◎所对应的 1ijx = ，其余
0ijx = ，已得到最优解。即最优指派方案为：
张-C,王-A,李-D,赵-B.
所需最少时间为：5+6+9+3=23。
注意：本例的最优方案不唯一。张-A王
-C,李-B,赵-D也是最优方案。
以上讨论仅限于极小化问题，对于极大
化问题，不能按maxZ(C)ijijx￠ =- 求解，
因为匈牙利法要求效率矩阵的元素 0ijC ? ，
这时可取 { }max ijMC= ，令 ,ijijbMC=-以
=(b)ijnnB · 为效率矩阵求解。
(M)iji ijijCxnMCx-=- Q
(M)ijijCx\- 当 取最小时， ijijCx 便
为最大。
另外，如果任务数与人数不相等，可以
向不平衡运输问题一样，虚设一项任务或人，
并且令相应的 1,njC + 或 ,1inC + 等于0，然后用匈
牙利法求解。
练习1：求表所示效率矩阵的指派问题的最小解
任务
人员 A B C D E
甲
乙
丙
丁
戊
12
8
7
15
4
7
9
17
14
10
9
6
12
6
7
7
6
14
6
10
9
6
9
10
9
练习2：有四个工人甲、乙、丙、丁，要指派他们
分别完成4项工作A、B、C、D，每个人做各项工作
所消耗的时间如表所示，问指派哪个人去完成哪项工
作，可使总的消耗时间为最小。
任务
人员 A B C D
甲
乙
丙
丁
15
19
26
19
18
23
17
21
21
22
16
23
24
18
19
17
|
|
