解取整之后的解(2,3)，该点的目标函数值是25。
4.2 分支定界法
整数规划问题的分支定界法可以求解全整数规划和混合整数规 划问题，其基本思想可描述为：
1) 首先求解相应的松弛问题； 2) 如果最优解不是整数解，将问题的可行域分为两部分，就
是进行分支； 3) 分别求解这两个分支可行域中的整数规划问题，对两个分
主要内容
4.1整数规划模型及穷举法 4.2 分支定界法 4.3 割平面法 4.4 0-1规划及隐穷举法
4.1 整数规划模型及穷举法
整数规划问题就是决策变量取整数值的线性或非线性规 划，由于非线性整数规划目前还没有一般解法，因此本章仅 讨论整数线性规划。在第一章例4中的截料问题即是一个整数 线性规划问题。整数线性规划问题又可分为：
首先引入符号[s]表示对s 向下取整，<s>=s - [s]表示 s的小数部分。
考虑如下整数规划问题
分
min z cx
支
s.t. Ax b
定
x 0 ，xZ
界
设此问题的松弛问题的解为x*且 xt*，则按0 如下
法 方式进行分支
min z cx s.t. Ax b
x [xt* ] x 0, x Z
整 例4.1 某厂生产甲、乙两种大型设备，生产中所需物质A
数
、B限制如下表所示，其他所需物质和零件充足，问各生 产甲、乙设备多少台，利润最大？
规
甲 乙 资源数量
划
A
11
6
模
B
59
45
每台利润 5 6
型 解：设x1，x2分别为生产甲、乙设备的台数，z为总利润 及 ，则
穷
max z 5x1 6x2
举
穷
松弛问题的可行域，并 标出可行域内所有整数
举 格点;
法
2) 找出松弛问题的解x=(9/4，15/4)，过最优点做目标函
整 数的等值线，令该等值线向可行域内保持平行移动，首先 数 遇到的格点就是最优整数解!
规
划
模
型
及
穷
举
法
此问题的最优解是x*=(3，3)，z*=33。显然不是松弛问题 的解4舍5入后的解(2,4)，该点不可行，也不是松弛问题的
❖纯整数(全整数)
所有决策变量均要求取整数；
❖混合整数
部分决策变量要求取整数；
❖纯0-1规划
求取0或1。
整数规划问题的松弛问题是指在整数规划中去掉整数性约束 后的线性规划问题，求解整数规划常常借助于松弛问题。
在本章中我们用Z表示整数集合；
一. 整数规划模型
法
(P1) max z 5x1 6x2
(P2 ) max z 5x1 6x2
s.t. x1 x2 6
s.t.x1 x2 6
5x1 9x2 45
5x1 9x2 45
x1 2 x 0，x Z
x1 3 x 0，x Z
考虑两问题的可行
域，P1的最优点是
x(1)=(2,35/9)T， P2的最
及 则该问题的数学模型为
穷
n
max z c j x j
举
j 1
n
法
s.t. a j x j b
j 1
x j 0或1 ( j 1,2,..., n)
例4.4(选址问题) 某种商品有n个销售地，各销售地每月的
整 需求量分别为bj吨(j=1,2,…,n)。现拟在m个地点选择建厂， 数 用来生产这种产品以满足供应，且规定一个地址最多只能
1 第i址建厂 yi 0 第i址不建厂
则该问题的数学模型为：
整
mn
n
数
min z
cij xij di yi
规
i1 j1
i 1
n
划
s.t.
xij ai yi
j 1
模 型
m
xij bi ( j 1,2,..., n)
i 1
及
xij 0, yi 0或1
穷 例4.1是一个全整数规划问题，例4.2是一个0—1规划
min z cx s.t. Ax b
x [xt* ]1 x 0, x Z
例4.1的整数规划问题的求解过程。
(P0 ) max z 5x1 6x2
分
s.t. x1 x2 6 5x1 9x2 45
支
x 0，x Z
定 此问题的松弛问题的解为x*=(9/4,15/4)T，x*不是整数解。 界 分支：对x1进行分支，有如下两个问题：
s.t. x1 x2 6
法
5x1 9x2 45 x1 0，x2 0
x1，x2 Z
整 例4.2 (投资决策模型)设有n个投资项目，其中第j个项目
数
需要aj万元，将来获利润cj万元。若现在有资金总
规
额为b万元，则应选那些投资项目获利最大？ 解：设决策变量为
划
模
1 投资j项目
型
x j 0 不投资j项目
(P3 ) max z 5x1 6x2
(P4 ) max z 5x1 6x2
s.t. x1 x2 6
s.t. x1 x2 6
举 问题，例4.4是一个混合整数规划问题。
法
二.穷举法
整 类似于线性规划的图解法，对于二维线性整数规划问题 数 ，也可以用图解法—穷举法。用穷举法求解例4.1
规
max z 5x1 6x2
划 模
s.t. x1 x2 6 5x1 9x2 45 x1 0，x2 0
型
x1，x2 Z
及 解：1)先作出该模型的
分 优点是x(2)=(3,3)T。显然
支
x(1)不是整数解，而x(2)是 整数解，得出例4.1的一
定 个整数解。
界 定界：当得到一个整数
法 解后可对原问题进行定
界。
z(2)=cx(2)=33，原问题的界为33，此界在最大值问题中是下
界，在最小值问题中是上界。对P1继续分支定界， P1当前 目标函数值为10+35=45，继续分支，得出以下两个问题：
支重复这一分支过程，…，当某个分支的解是整数解时， 将此解的目标函数值作为一个界，就是进行定界； 4) 在求解每个分支问题时，如果松弛问题无可行点或目标函 数值小于所定的界(极小问题)，这一分支终止，否则继续 求解并继续分支。 5) 此求解过程可用一个二叉树描述，原问题的松弛问题是树 根，两分支是左右子树，终止分支的子问题是树叶。
规 建一个工厂，若选择第i个地址建厂将来生产能力为ai吨， 划 每月的生产成本为di元(i=1,2,…,m)。已知从第i个工厂至第j 模 个销售地的运价为cij元/吨。应如何选择厂址和安排调运， 型 可使总的费用最小?
及 穷
解：设每月从第i厂至第j个销地的运量为xij吨，z为每月的 总费用， 设
举
法