规划中的变量 （部分或全部） 限制为整数时， 称为整数规划。 若在线性规划模型中，变量限制为整数，则称为整数线性规划。

1、原线性规划有最优解， 当自变量限制为整数后， 其整数规划解出现下述情况：

2、整数规划最优解不能按照实数最优解简单取整而获得

对有约束条件的最优化问题 （其可行解为有限数） 的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。把全部可行解空间反复地分割为越来越小的子集，称为分枝。对每个子集内的解集计算一个目标下界（对于最小值问题） ，这称为定界。

在每次分枝后， 凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。

例 1

求

解：

1、先不考虑整数限制，直接按照线性规划求解，将此线性规划问题视为 B，得

再取 x1 = x2 = 0，得到 z 为 0，那么，以上便可求出可行解 z 的上下界

2、任选 x1 和 x2 进行分枝，取 x1 = 5

可得

对 z 再定界，有

3、对 x2 进行分枝，取 x2 = 3，有

再定界，有

4、若再对 x2 以 1 进行分支定界，无可行解，那么，可推断，最优解为

0-1 整数规划指的是变量 xj 仅能取 0 或 1，即

题目描述：某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置 Aj（j = 1, 2, 3...7）可供选择，规定

Aj 点的投资为 bj 元，每年利润为 cj 元，投资总额不能超过 B 元，问如何选择可使年利润最大？

解：

引入变量 xj，令

那么问题可写为

1、

可写为

M 为充分大的数

2、

可写为

例 2

某工厂为了生产某种产品，有三种方式可供选择：

要求最小化生产成本。

解：

第 j 种生产方式的总成本为

引入 0 - 1 变量 yj，为

于是目标函数为

对于（3）式的规定，可改写为

前者和后者分别为充分小和充分大的数

穷举法是最容易想到的一种方法，但是计算量太大，因此设计一种仅检查变量取值的组合的一部分，称为过滤隐枚举法。分枝定界法也为过滤隐枚举法的一种。

例 3

解题思路：

前面讲的是线性整数规划，接下来说明非线性整数规划的问题，当数据量很大时，采用穷举法得到最优解不符合现实，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。

例 4

解：

若采用穷举法，共 1010 个点，可随机分析 106 便可达到最优。

mente.m 如下：目标函数 f ，约束向量函数 g

mainint.m 如下：

上面代码中 sum(g =1;

x3+x5>=1;

x1+x2