整数线性规划

第三章 整数线性规划

【教学内容】

整数线性规划问题举例、整数线性规划模型及其求解的困难性、可用线性规划求解的整

数线性规划问题、求解整数线性规划问题的Gomory割平面法、求解整数线性规划问题的分

枝定界方法、0－1规划问题举例、0－1规划问题的解法、整数线性规划问题的一些例子、

用LINGO软件包求解整数线性规划问题。

【教学要求】

要求学生熟悉整数线性规划模型，能熟练地掌握求解整数线性规划问题的Gomory割平

面法和分枝定界方法；熟悉并会求解0－1规划问题，能够建立整数线性规划模型并用软件

求解整数线性规划问题。

【教学重点】

整数线性规划模型，Gomory割平面法，分枝定界方法，0－1规划问题。

【教学难点】

Gomory割平面法，分枝定界方法，0－1规划问题的求解。

【教材内容及教学过程】

整数线性规划(Integer Linear Programming，简记为ILP)问题研究的是要求变量取整数

值时，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要

分支。其中变量只取0或1的整数线性规划问题称为0－1规划。只要求部分变量取整数值

的线性规划称为混合整数线性规划。

整数线性规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是以相应

的线性规划的最优解为出发点的。但是变量取整数值的要求本质上是一种非线性约束，因此

解整数线性规划的“困难度”大大超过线性规划，一些著名的“困难”问题都是整数线性规

划问题。

本章主要介绍整数线性规划一些基本概念、基本理论、实际背景及常用算法。

第一节 整数线性规划模型

§1．1 整数线性规划问题举例

例3.1.1[2] 工地上需要长度为mlll,,,

21的钢材数分别为mbbb,,,

21根，取长为l的

原材料进行截取。已知有n种截取方案：



12iiimiAaaa，1,2,,in

其中，jia表示一根原料用第i种方案可截得长为jl的钢材的根数（1,2,,in，1,2,,jm），因此

1122iimmilalalal，1,2,,in

下料问题就是在满足要求：截取长度为mlll,,,

21的钢材数分别为mbbb,,,

21根时，

用的原料材根数最少的方案。假定ix表示按方案iA截取用的原钢材数目，于是问题表示为：

12

11112211

21122222

1122min

..

0,1,,n

nn

nn

mmmnnm

izxxx

axaxaxb

axaxaxb

st

axaxaxb

xin



















整数， (3.1.1)

在许多实际问题中，我们所研究的量具有不可分割的性质，如人数、机器数、项目数等；

而开与关、取与舍、真与假等逻辑现象都需要用取值仅为0或1的变量来进行数量化的描述。

涉及这些量的线性规划问题，非整数的解答显然不合乎要求。

§1．2 整数线性规划模型及其求解的困难性

考虑如下形式的整数线性规划问题ILP

min

..0Tcx

Axb

stx

x





为整数向量 (3.1.2)

其中

ijmnAa

，

12,,,T

ncccc，

12,,,T

mbbbb以及

12,,,T

nxxxx，A，

b，c中的元素皆为整数。在(3.1.2)中除去x为整数向量这一约束后，就得到对应的标准线

性规划问题

min

..

0Tcx

Axb

st

x



 (3.1.3)

称(3.1.3)是(3.1.2)的松弛问题。如果(3.1.2)对应的标准线性规划问题(3.1.3)的最优解是整数，

则它也是(3.1.2)的最优解。对于标准线性规划问题，已有有效的算法。那么能不能通过求解

对应的线性规划问题，然后将其解舍入到最靠近的整数解呢？

考察图3.1.1所示的情况，可以看出舍入方法是不可取的。

既然ILP的可行域是一些离散的整数点（图3.1.1），如果其可行域有界，那么所包含的

整数点的数目就是有限的，可否用枚举法来解ILP问题呢？对一般ILP问题，枚举法是无能

为力的。如50个城市的旅行售货员问题（见例3.4.4），所有可能的旅行路线个数为

2)!49(

，

这是一个天文数字。

由上可见，求解整数线性规划问题ILP比求解对应的线性规划问题LP要困难得多。事

实上，整数线性规划模型并不是线性模型。仅以0－1规划而言，决策变量取值为0或1这

个约束是可以用一个等价的非线性约束

njxx

jj,,1,0)1( (3.1.4)

来代替的。因而变量限制为整数本质上是一个非线性约束。

第二节 求解整数线性规划问题的常用方法

从1959年R.E.Gomory提出解整数线性规划的割平面算法至今，经过几十年的努力，

已经发展起来了一些常用算法，如各种类型的割平面算法、分枝定界算法、解0－1规划的

隐枚举法、分解方法、群论方法、动态规划方法等等，本节主要介绍求解整数线性规划问题

的几个常用算法。

§2．1 可用线性规划求解的整数线性规划问题

可用线性规划问题求解的整数线性规划问题，实际上是这样的一类问题，它的解就是

线性规划解，即可以通过单纯形法来求整数规划的解。

定义3.2.1矩阵Anmija

)(，若它的任一子行列式的值均为0，1或者1，则称这样

的矩阵为幺模矩阵。

幺模矩阵的所有元素都是0，1或者1。

定理3.2.1 若Anmija

)(是幺模矩阵，B是由A中的m个列向量组成的矩阵，若B可

x的最优解LP的最优解ILP的可行区域LP

费用下降方向

01x2x

图 3.1.1                                                 逆，则1B的所有元素都是0，1或者1。

定理3.2.2 若Anmija

)(是幺模矩阵，B是由A中的m个列向量组成的可逆矩阵，

bBx

B1，若b是整数，则Bx是整数。

因此，对于规划问题(3.1.2)，若系数矩阵Anmija

)(为幺模矩阵，且右端项b是整数，

则可以用单纯形方法直接求解对应的标准线性规划问题(3.1.3)，就可以得到它本身的最优整

数解。

§2．2 求解整数线性规划问题的Gomory割平面法

1、 整数线性规划问题与其对应的松弛问题的关系

解整数线性规划问题的割平面法有多种类型，但它们的基本思想是相同的。以下我们

介绍Gomory割平面法。它在理论上是重要的，被认为是整数线性规划的核心部分。

设(3.1.2)的可行域为D，对应的松弛问题(3.1.3)的可行域为0D（多面凸集），当D

时它是由有限个或可数的整数点构成的集合。问题(3.1.2)和问题(3.1.3)之间具有如下明显的

关系：

⑴．0DD；

⑵．若问题(3.1.3)无可行解，则问题(3.1.2)无可行解；

⑶．问题(3.1.3)的最优值是问题(3.1.2)的最优值的一个下界；

⑷．若问题(3.1.3)的最优解0x是整数向量，则0x是问题(3.1.2)的最优解。

2、 割平面法的基本思想

用单纯形法先解松弛问题(3.1.3)，若问题(3.1.3)的最优解0x是整数向量，则0x是ILP

问题(3.1.2)的最优解；若问题(3.1.3)的最优解0x的分量不全是整数，设法构造一个线性约束

条件（称它为割平面条件），新增加的这个割平面条件将问题(3.1.3)的可行区域0D割掉一块，

且这个非整数解0x恰好在被割掉的区域内，而原ILP问题(3.1.2)的任何一个可行解（整数点）

都没有被割去。给问题(3.1.3)增加这个约束条件，用得到的问题替换问题(3.1.3)，继续以上

过程。

3、 Gomory割平面法的割平面条件

用单纯形方法求解问题(3.1.2)的松弛问题(3.1.3)，得到最优基本可行解0x，设它对应的

基为),,(

1mBBAAB，

mBBxx,,

1为基变量，基变量的下标集合为S，非基变量的下标集合为S。最优解所对应的问题(3.1.3)是

0min

jj

jSzxz



..,1,,

iBijji

jSstxaxbim

 (3.2.1)

为使符号简便计，令zx

B

0，jja

0，00zb。如果,0,1,,

ibim，全是整数，已经得到了问题(3.1.2)的最优解0x；否则至少有一个lb不是整数)0(ml，设lb所对应的

约束方程是





SjljljBbxax

l (3.2.2)

我们用][a表示不超过a的最大整数，则有

[],

[]ljljlj

lllaafjS

bbf

 (3.2.3)

其中ljf（01,

ljfjS）是lja的分数部分；lf（10

lf）是lb的分数部分。由于

方程(3.2.2)中的变量是非负的，因此有





Sjjlj

Sjjljxaxa][ (3.2.4)

从而方程(3.2.2)变为





SjljljBbxax

l][ (3.2.5)

因为x为整数向量，故(3.2.5)式左端为整数，所以右端用lb的整数部分去代替后，(3.2.5)式

的不等式关系仍成立，即有





SjljljBbxax

l][][ (3.2.6)

(3.2.2)减去(3.2.6)，得

][])[(

ll

Sjjljljbbxaa

 (3.2.7)

注意到(3.2.3)关系式，我们得到线性约束

l

sjjljfxf

 (3.2.8)

称它为对应于生成行l的Gomory割平面条件。

将(3.2.8)改写为（引进松弛变量s）超平面方程(3.2.9)

l

sjjljfsxf

 (3.2.9)

称它为割平面。将割平面(3.2.9)加到问题(3.2.1)，就得到了一个新的线性规划问题，且已经

具有满足最优性条件的基本不可行解。

定理3.2.3 如果把割平面(3.2.9)加到问题(3.2.1)中，那么没有割掉问题(3.1.2)的任何整数可行点，当lb不是整数时，新问题是一个满足最优性条件的不可行基本解。

4、 Gomory割平面法计算步骤

第1步 求解问题(3.1.3)。若问题(3.1.3)没有最优解（包括无可行解和无有限最优解），

则问题(3.1.2)也没有最优解；若问题(3.1.3)有最优解0x，且0x是整数向量，则0x是问题(3.1.2)