什么是整数规划?

[拼音]：zhengshu guihua

[外文]：integer programming

要求变量取整数值的数学规划。若所有变量均要求取整数值，则称为纯整数规划。若只是部分变量要求取整数值，则称为混合整数规划。整数规划一词常指纯整数规划。要求变量取整数值的线性规划称为线性整数规划。1963年R.E.戈莫里提出解线性整数规划的割平面法。1965年R.J.达金和兰德-多伊格提出分枝限界法。此后对于一般线性整数规划先后建立了若干算法理论，对于特殊结构的线性整数规划建立了各种有效算法。60年代后期，整数规划的研究范围开始扩展到非线性整数规划。

解整数规划问题的典型方法是逐次生成一个个相关问题,即衍生问题，再对每个衍生问题放宽约束条件,构成松弛问题。衍生问题称为松弛问题的源问题。通过解松弛问题来确定舍弃此衍生问题，还是再生成一个或几个新的衍生问题，如此继续下去，直到不再有未解决的衍生问题。若松弛问题的解对于源问题是可行的，则源问题得解。否则在不排除原可行解的条件下修正可行域。解此修正问题，直到修正问题的最优解在原可行域内为止。解整数规划问题时松弛约束的方法通常是略去整数性约束和附加线性不等式约束来实现可行域的修正。略去整数性就可按线性规划求解，再分别附加两个互相排斥的线性不等式之一,就是把这一个变量修正到整数,如此继续下去，直到要求整数约束的变量都成为整数为止。此即分枝限界法。若只附加一个线性不等式，就是割平面法。

满足线性整数规划约束条件的点集 S是一离散点阵，这对求解整数规划带来本质上的困难。取消变量的整数性要求就可变成一个线性规划问题，称为原整数规划的松弛问题。解线性整数规划的割平面法就是从松弛问题的一个非整数的最优解出发，序贯地每次添加一个新的线性不等式（其对应的线性方程所代表的超平面即称为割平面），求解新的松弛问题。每次增添的新的不等式须满足两个条件：

（1）前一个松弛问题的最优解不满足这个不等式，即松弛问题的可行解集合被割去了一“块”；

（2）s中的“点”都满足这个不等式,即保证整数可行解不被割去。这一算法的主要问题是如何构造出有效的割平面，以便尽快地得到一个有整数最优解的松弛问题。

一种解离散问题的最优化方法，可用以解线性整数规划。分枝限界法的基本思想是部分枚举法。对于给定的求极大值的线性整数规划P,可按下述步骤求解：

（1）算法开始时，去掉整数约束，解对应的松弛问题P′；如果P′的最优解是整数解，也就得到了P的最优解；

（2）如果不是，则把 P的可行解集合划分成两部分，得到两个线性整数规划子问题P1,P2。然后对每个子问题，求解对应的松弛问题P姈,P娦。如果P姈的最优解是整数解x壒，则x1是P的可行解,并且目标函数值f(x壒)是P的一个下界Z0,这时对问题P1已经考虑完毕。如果P娦的最优解x壗的目标函数值f(x壗)＜Z0，则P2也没有再考虑的必要,原问题P 的最优解就是x壒。如果f(x壗)≥Z0,再分两种情况考虑:若x壗是整数解,则x壗是原问题P的最优解；若x壗不是整数解，则返回②,对P2进行类似P的考虑。经有限次循环之后，即求得原线性整数规划的最优解。

要求变量取值0或1的数学规则。从理论上说,任何有界变量的线性整数规划都可化为0-1规划。对于n个变量的0-1规划，如果采用完全枚举法，枚举次数可达2n,因此如何采用适当的判别原则和技巧,以便在分枝限界法求解过程中用较少的枚举就能得到最优解，这是隐枚举法的主要课题。

参考书目

Robert S.Garfinkel，Geoger L.Nemhause，Integer Programming, John Wiley and Sons, New York,1972.