数学建模（二）：从线性规划到整数规划

&1.概论
1）定义：当一个规划问题中的变量至少有一个被限制为整数时，这个规划问题被称为⎡整数规划⎦，假如这个规划问题是一个⎡线性规划⎦，那这样的既是整数规划又是线性规划的问题我们把它称为⎡整数线性规划⎦。目前为我们流行的求解整数规划的方法，往往只适用于整数线性规划问题，尚未找到一种能够有效求解一切整数规划问题的方法。
2）分类：我们按照变量是否被全部限制为整数来对整数规划进行划分，如果变量被全限制为整数，我们把这样的规划叫做⎡纯（完全）整数规划⎦，否则称为⎡混合整数规划⎦。
3）整数规划特点：
1^。原线性规划有最优解，当决策变量被限制为整数后，会出现以下情况：
(i)原线性规划问题最优解全为整数，则整数规划问题与线性规划问题具有相同最优解，这种情况是最为简单的。
(ii)整数规划此时无可行解。

此时我们限制这个线性规划中的x₁,x₂都必须为整数，那么显然约束条件中的等号是无法成立的，此时的这个转化得到的整数规划是没有可行解的。
(iii)有最优解，但整数规划的最优解和线性规划的最优解不是同一个。

2^。整数线性规划的最优解，不能按照线性规划的实数最优解简单取整得到。
3）求解方法分类：
1^。分枝定界法——可求完全或混合整数线性规划；
2^。割平面法——可求完全或混合整数线性规划；
3^。隐枚举法——求解“0-1”整数规划：过滤隐枚举法和分枝隐枚举法。
4^。匈牙利法——解决指派问题（“0-1”规划的特殊情况）
5^。蒙特卡洛法——求解各种类型的规划。

&2.分枝界定法
对有约束条件的具有有限个可行解的最优化问题，把它所有的可行解空间进行系统的搜索。把全部可行解空间反复分割，称为分枝；把分割后的每个子集的解计算一个目标下界，称为定界。在每次分枝后，对界限超出已知当前得到的最优下界的子集不再分枝，称为剪枝。
设有最大化的整数规划问题A，与它相应的线性规划问题B，我们从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必定是最优目标函数z^*的上界，而A的任意可行解的目标函数值是z^*的下界。逐步减小上界和下界，最终可以求得最优解。

(4.17后续待更新)