将
B
21
,B
22
剪枝。
于是可以断定原问题的最优解为：
*
x
1
4,x
2
2,z340

从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：
开始，将要求解的 整数规划问题称为问题
A
，将与它相应的线性规划问题称为问题
B
。
（i）解问题
B
可能得到以下情况之一：
（a）
B
没有可行解，这时
A
也没有可行解，则停止．
（ b）
B
有最优解，并符合问题
A
的整数条件，
B
的最优解即 为
A
的最优解，则停止。
（c）
B
有最优解，但不符合问 题
A
的整数条件，记它的目标函数值为
z
。
（ii）用观察法找问 题
A
的一个整数可行解，一般可取
x
j
0,j1,,n
，求得其目标
函数值，并记作
z
。以
z
*
表示问题
A
的最优目标函数值；这时有
zzz

*
进行迭代。 第一步：分枝，在
B
的最优解中任选一个不符合整数条件的变量
x
j，其值为
b
j
，以
[b
j
]
表示小于
b
j
的最大整数。构造两个约束条件
x
j
[b
j
]
和
x
j
[b
j
]1

将这两个约束条件，分别加 入问题
B
，求两个后继规划问题
B
1
和
B
2
。不考虑整数条件求解
这两个后继问题。
定界，以每个后继问题为一分枝标明求解 的结果，与其它问题的解的结果中，找出最优
目标函数值最大者作为新的上界
z
。从已 符合整数条件的各分支中，找出目标函数值为最大
者作为新的下界
z
，若无作用
z0
。
第二步：比较与剪枝，各分枝的最优目标函数中若有小于
z
者， 则剪掉这枝，即以后
不再考虑了。若大于
z
，且不符合整数条件，则重复第一步骤。一 直到最后得到
zz
为
止。得最优整数解
x
j
,j

1,

,n
。
2.2 整数规划的计算机解法
3
*
*

例2 求解下列整数规划问题：
minzx
1
x
2
4x
3

x
1
x
2
2x
3
9


x
1
x
2
x
3
2
s.t.

(2.2)
xxx4
123


x,x,x0为整数

123
在LINGO 模型窗口中输入下列模型：
MIN=X1+X2-4*X3;
X1+X2+2*X3<=9;
X1+X2-X3<=2;
-X1+X2+X3<=4;
@GIN(X1); @GIN(X2); @GIN(X3);
选菜单Lingo|Solve（或按Ctrl-S），或用鼠标点击“solv e”按钮，可得结果如下：
Global optimal solution found.
Objective value: -16.00000
Extended solver steps: 0
Total solver iterations: 0
Variable Value Reduced Cost
X1 0.000000 1.000000
X2 0.000000 1.000000
X3 4.000000 -4.000000
Row Slack or Surplus Dual Price
1 -16.00000 -1.000000
2 1.000000 0.000000
3 6.000000 0.000000
4 0.000000 0.000000
三、0-1型整数规划
3.1 0-1整数规划实际问题举例：
01
型 整数规划是整数规划中的特殊情形，它的变量
x
j
仅取值0或1。我们先介绍几
4

个0-1整数规划实际问题，再研究其解法。
3.1.1 投资场所的选定
某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）
A
i
(i1,2,,7)
可
供选择。规定
在东区：由
A
1
,A
2
,A
3
三个点中至多选两个；
在西区：由
A
4
,A
5
两个点中至少选一个；
在南区：由
A
6
,A
7
两个点中至少选一个。
如选用
A
i
点，设备投资估计为
b
i
元，每年可获利润估计 为
c
i
元，但投资总额不能超过
B
元。问应选择哪几个点可使年利润 为最大？
解题时先引入
01
变量
x
i
(i1,2, ,7)

令

1,
当A
i
点被选中
，

i1,2,,7
.
x
i



0，
当A
i
点没被选中.
于是问题可列写成：
7

Maxz

cx
i
i1
i


7


b
i
x
i
i1

< br> s.t.

x
1
x
2
< br>xx
5

4


x
6
x
7
B
x
3
2
1
1,x
i
0
或
1
(2.3)
3.1.2 背包问题 某人打算外出旅游并登山，需要带
n
件物品，重量分别为
a
i
， 受到个人体力所限，行
李的总重量不能超过
b
，若超过，则需要裁减。该旅行者为了决 策带哪些物品，对这些物品
的重要性进行了量化，用
c
i
表示，试建立该问题 的数学模型。这个问题称为背包问题。
解题时先引入
01
变量
x
i

i
1
,
2
,

,n

，
x
i
1
表示物品i放入背包中，否则不放，
5

于是背包问题可列写成：
n

Maxz

c
i1
i
x
i


n


a
i
x
i
b
s.t.

i1

x
0
或
1
,i
1
,
2
,n

i
(2.4)
3.1.3 指派问题
拟分配
n
人去干
n
项 工作，每人干且仅干一项工作，若分配第
i
人去干第
j
项工作，需
花 费
c
ij
单位时间，问应如何分配工作才能使工人花费的总时间最少？
容易 看出，要给出一个指派问题的实例，只需给出矩阵
C(c
ij
)
，
C
被称为指派问题
的系数矩阵。
解题时先引入变量
x
ij
，若分配
i
干
j
工作，则取
x
ij
1
， 否则取
x
ij
0
。上述指派问
题的数学模型为
nn
ij

min

c
i1j1
x
ij

< br>n


x
ij
1,i1,2,

,n< br>
j1
n


s.t.


x< br>ij
1,j1,2,

,n

i1

x0 或 1 ,i,j1,2,

,n
ij



(2.5)
(2.5)的变量只能取0或1，从而是一个0-1规划问题。由于其约束方程组的系数矩 阵十分特
殊（被称为全单位模矩阵，其各阶非零子式均为
1
），其非负可行解的分量 只能取0或1，
故约束
x
ij
0
或
1
可改写为< br>x
ij
0
而不改变其解。此时，指派问题被转化为一个特殊的运输
问 题，其中
mn
，
a
i
b
j
1
。由于 指派问题的特殊性，匈牙利数学家Kuhn于1955年提
出了一种更为简便的算法—匈牙利算法。



6

四、0-1型整数规划解法之一（过滤隐枚举法）
4.1过滤隐枚举法介绍
解
01
型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即
检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取
值的
2
n
个组合。对于变量个数
n
较大（例如
n10
），这几乎是不可能的。因此常设计一些
方法，只检查变量取值的组合的一部分，就能求到问题的最优解 。这样的方法称为隐枚举法
（Implicit Enumeration），分枝定界法也是一种隐枚 举法。当然，对有些问题隐枚举法并不
适用，所以有时穷举法还是必要的。
下面举例说明一种解
01
型整数规划的隐枚举法。
例3
Maxz3x
1
2x
2
5x
3


x
1
2x
2
x
3
2

x 4x
2
x
3
4

1

s.t.

x
1
x
2
3
(2.6)

4xx6
3

2


x
1
,x
2
,x
3
0或1
求解思路及改进措施：
（i） 先试探性求一个可行解，易看出
(x
1
,x
2
,x
3
)(1,0,0)
满足约束条件，故为一个可
行解，且相应的目标函数值 为
z3
。
（ii） 因为是求极大值问题，故求最优解时，凡是目标值
z 3
的解不必检验是否满足
约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件 （目标值下界）：
3x
1
2x
2
5x
3
3
，称该条件为过滤条件。从而原问题等价于：
Maxz3x
1
2x
2
5x
3


3x
1
2x
2
5x
3
3

x2x
2
x
3
2

1


x
1
4x
2
x
3
4
s.t.


xx3
2

1
4xx6
23



x
1
,x
2
,x
3
0或1
(a)
(b)
(c)
(d)
(e)
(f)
(2.7)

7

若用全部枚举法，3个变量共有8种可能的组合，我们将这8种组合依次检验它 是否满
足条件(a)—(e)，对某个组合，若它不满足(a)，即不满足过滤条件，则(b)—(e) 即可行性条件
不必再检验；若它满足(a)—(e)且相应的目标值严格大于3，则进行（iii）。
（iii） 改进过滤条件。
（iv） 由于对每个组合首先计算目标值以验证过滤条件，故 应优先计算目标值较大的
组合，这样可提前抬高过滤门槛，以减少计算量。
按上述思路与方法，例6的求解过程可由下表来表示：
(x
1
，x
2
,x
3
)

目标值 约束条件
a b c d e
过滤条件
(0,0,0)

(1,0,0)

(0,1,0)

(0,0,1)

(1,1,0)

(1,0,1)

(1,1,1)

(0,1,1)

0
3
-2
5
1
8
6
3



√ √ √ √ √
3x2x53

123



√ √ √ √ √
3x2x55

123



√ √ √ √ √
3x2x58

123






***
*
从而得最优解
(x1
,x
2
,x
3
)(1,0,1)
，最优值
z8
。
4.2 求解0-1规划的MATLAB函数
对于0-1规划问题，MATLAB提供命令bintprog求解。 MATLAB中0-1规划的标准形
式为：
min f'*X
s.t. A*X <= b,
Aeq*X = beq,
其中X的每个分量为0或者1。
（1）X = BINTPROG(f) 求解问题 min f'*X
8

（2）X = BINTPROG(f,A,b) 求解min f'*X s.t. A*X <= b
（3）X = BINTPROG(f,A,b,Aeq,beq) 求解 min f'*X s.t. Aeq*X = beq, A*X <= b
例4 某公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：

项目
1
2
3
4
5

该公司只有600百万资金可用于投资，由于技术上的原因投资受到以下约束:
1. 在项目1，2和3中必须有一项被选中；
2. 项目3和4只能选中一项；
3. 项目5被选中的前提是项目1必须被选中；
问：如何在上述条件下选择一个最好的投资方案，使投资收益最大？
解：设0-1变量

1

x
i



0
选中项目i
不选项目i
投资额(百万)
210
300
100
130
260
投资收益(百万)
150
210
60
80
180

为使投资收益最大，故有目标函数：
maxS150x
1
210x2
60x
3
80x
4
180x
5

投资不超过公司的600百万资金，故有条件：
210x
1
300x2
100x
3
130x
4
260x
5
 600

在项目1，2和3中必须有一项被选中，故有条件：
x
1
x
2
x
3
1

项目3和4只能选中一项，故有条件：
x
3
x
4
1

项目5被选中的前提是项目1必须被选中，故有条件：
9

x
5
x
1

这样，我们就可得到这问题的数学模型如下：

maxS150x
1210x
2
60x
3
80x
4
180x
5

s.t.210x
1
300x
2
100x
3
130x
4
260x
5
600
x
1x
2
x
3
1
x
3
x
4
1
x
5
x
1
x
i
0或1，i1，2， 5
(2.8)
用MATLAB求解可得：
c=-[150,210,60,80,180]; %转换求max为求min
a=[210,300,100,130,260;0,0,1,1,0;-1,0,0,0,1];
b=[600;1;0];
Aeq=[1,1,1,0,0];
beq=1;
[x,fval]=bintprog(c,a,b,Aeq,beq)
x =
1
0
0
1
1
fval =
-410

例5 一架货机，有效载重量为24（吨） ，可运输物品的重量及运费收入下表所示：其中各物
品只有一件可供选择，问如何选运物品运费总收入最 多？
物品 1 2
13
5

3
6
2
4
9
4
5
5
2
6
7
3
重量（吨） 8
收入（万元） 3

1
解 记 < br>x
i



0
当选运第i种物品
其他
则可建立下述0-1规划模型：
maxf3x
1
5x
2
2 x
3
4x
4
2x
5
3x
6

10


8x
1
13x
2
6 x
3
9x
4
5x
5
7x
6
24< br>s.t.

2

6

x
i
为
0
或
1
，i
1
，
(2.9)
用MATLAB求解可得：
c=-[3,5,2,4,2,3]; %转换求max为求min
a=[8,13,6,9,5,7];
b=24;
[x,fval]=bintprog(c,a,b)
x =

1
0
0
1
0
1
fval =
-10

















11

习题二
1．某公司的营业时间是上午8 点到21 点，服务人员中途需要1个小时的吃饭和休息时间，
每人工作时间为8小时，上午8点到下午17 点工 作的人员工资为800元，中午12点到21点工作
的人员月工资为900元，为保证营业时间内都有人 值班，公司安排了四个班次，其班次与休
息时间安排如表1，各时段的需求人数如表2，问应如何安排服 务人员使公司所付工资总数最
少，建立此问题的数学模型。
表一：
班次
1
2
3
4
工作时间
8：00－17：00
8：00－17：00
12：00－21：00
12：00－21：00

表二：
时段 8:00－
10:00
需求人数





20
10:00－
12:00
25
12:00－
14:00
10
14:00－
16:00
30
16:00－
18:00
20
18:00－
21:00
10
休息时间
12：00－13：00
13：00－14：00
16：00－17：00
17：00－18：00
月工资
800
800
900
900
12