[数学建模算法] (4) 整数程序设计的基本概念和常规算法：分支与边界法

之前的三节我们讨论了关于线性规划的相关知识，在实际问题中，比如运输问题，线性规划的变量有一个隐藏的要求——整数，而Matlab中的线性规划算法算出的最优变量一般不会是整数，那么我们有什么办法求出符合整数条件的变量呢，这一节我们就来聊聊线性规划的特殊情况，整数规划。

整数规划的定义

规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

整数规划的分类

如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：
1.变量全部为整数的，为完全整数规划。
2.变量部分限制为整数的，称为混合整数规划。

整数规划的特点

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

(1)原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。

(2)整数规划无可行解。
例1

易知没有能满足限制条件的整数解。故若作为一个整数规划问题，该问题无可行解。

(3)有可行解（也就是存在最优解），但最优解值变差。
例2

其最优实数解为：

若限制整数：

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

求解方法分类

整数规划算法分类

下面将对整数规划算法进行一一介绍。

分枝定界法

对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。

分枝：把全部可行解空间反复地分割为越来越小的子集，称为分枝。
定界：并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。
剪枝：在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。
上面就是分枝定界法的一个主要流程，下面将用一个例题来详细说明。

例3 求解下列整数规划问题

1.假设整数规划问题为，对应的非整数规划问题为，从求解问题开始。
得到最优解为：

此时的是问题所能求得的目标函数值的上界，记为，而显然是一个整数可行解，这时，是问题所能求得的目标函数的下界。将问题的目标函数值设为，此时。

2.选进行分枝，把可行集分成两个子集：

由于4与5之间无整数，所以两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。对两个子集分别进行规划和求解。

设问题


最优解为：

设问题


最优解为：

再定界：

3.对问题再进行分枝得问题和，

设问题


问题


他们的最优解为。


将剪枝，因为其得到的已经不在第一轮的定界中了，综合得到新界：

4.对问题再次分枝为和。

设问题


设问题


其最优解为：

无可行解
由于所得出的解不在之前定界范围内，所以，均被剪枝。

5.综上，得到最优解：

分枝定界法的一般步骤

从上述问题中可以总结出分枝定界法的一般步骤：

一。将要求解的整数规划问题称为问题，对应的整数规划问题称为问题，先对问题进行求解，可能得到以下情况。
1.无可行解，则也定无可行解，计算终止，此题无可行解。
2.有最优解，且最优解为整数解，此时计算终止，的最优解同时也是的最优解。
3.有最优解，但最优解不是整数解，记下此时目标函数值为。
一般来说，可代入各自变量的最小值获得的最小值，得到初始定界：

二。迭代
1.分枝：在的最优解中任选一个不符合整数条件的变量，其值为以表示不大于的最大整数，构造两个约束条件：

用这两个分支分别替换问题中对应变量的限制条件，不考虑整数条件求解两个后继问题。
2.定界：以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界，从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界。若无符合整数条件的结果则下界不变。
3.比较和剪枝：若各分支的最优目标函数有小于的，则直接剪掉这枝，若大于但不符合整数条件，则重复迭代步骤中的第一步，再选一个不符合整数条件的变量重复运算，直到得到，则运算结束，得到最优整数解。

本节对整数规划问题有了一个基本的论述并介绍了其中一个经典算法——分枝定界法。