任务一　整数规划的概念

1.1　整数规划问题

1.1.1　整数规划的概念

在实际问题中，因为决策变量不可无限细分而必须取整数时，这类规划问题称为整数规划。整数规划可以是线性的，也可以是非线性的。如果目标函数和约束条件都是线性的，那么把这种整数规划称为整数线性规划。本书只研究整数线性规划。

1.1.2　整数规划的分类

如果一个整数规划问题中所有决策变量要求取非负整数，那么把它称为纯整数规划。如果只有一部分的决策变量要求取非负整数，另一部分可以取非负实数，就把它称为混合整数规划。当所有决策变量只能取0或1两个整数时，把它称为0—1规划。

1.1.3　整数规划问题的提出

整数线性规划问题和线性规划问题的区别就是决策变量要求部分还是全部为整数，所以，整数规划模型的建立类似线性规划。在下面的叙述中，我们把整数线性规划简称为整数规划。

例3-1-1　生产计划问题　某厂在一个计划期内拟生产甲、乙两种大型设备。该厂有充分的生产能力来加工制造这两种设备的全部零件，所需原材料和能源基本上能满足供应，只有A、B两种生产原料的供应受到严格限制。可供原料总量、每台设备所需的原料的数量及利润如表3-1-1所示。问该厂安排生产甲、乙设备各多少台，才能使利润达到最大？

表3-1-1

解：设x1、x2分别为该厂计划期内生产甲、乙设备的台数，z为生产这两种设备可获得的总利润。x1、x2都是非负整数，根据题意，该生产计划问题的数学模型为

显然，若不考虑取整的条件的话，上述模型就是线性规划模型。因此我们可以把去掉整数约束条件后得到的线性规划称为原整数规划的松弛问题。

因此，整数规划的一般形式为

1.2　整数规划问题的求解

整数规划问题就是一种特殊的线性规划问题，那么可不可以用单纯形法来求解，然后用取整数的方式获得整数规划的解呢？我们通过下面的例题3-1-2来分析一下。

例3-1-2　求解整数规划问题。

先不考虑整数约束，用图解法求解上述整数规划的松弛问题，得到其可行域，如图3-1-1所示。

通过图3-1-1可以看出，该线性规划问题的最优解，，。如果用“舍入取整法”可得到4个点即（1，3）、（2，3）、（1，4）、（2，4）。通过图可以发现，它们都不是整数规划的最优解，甚至不是可行解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，因此，可以将集合内的整数点一一找出，其最大目标函数的值为最优解，这种方法叫做完全枚举法。

可以发现在所有的可行解中，在（2，2）、（3，1）处可以取得目标函数的最大值，这时z＝4。

由此可见，将松弛问题的最优解简单取整之后，一般得不到原整数规划的最优解，甚至不能保证是可行解。如果整数规划的可行域是有界的，那么原整数规划的可行解集应该是有限点集，因此，在问题规模不太大的情况下，可以考虑用上文的完全枚举法来求解整数规划。但对于复杂问题而言，这种方法并不是有效的。有时候即使用计算机，也无法在人们可接受的时间内找到最优解。整数规划问题的求解成了运筹学的一大难题。近几十年来，经过艰苦的努力，人们研究出了许多相对有效的算法来解决这个难题，比如分支定界法、割平面法等。从原理上看，这些方法大部分都是基于整数规划和它的松弛问题的关系的。