3.1 整数规划数学模型

在一个线性规划问题中，如果它的所有决策变量都要求取整数时，就称为纯整数规划；如果仅部分决策变量要求取整数则称为混合整数规划，二者统称为整数规划。整数规划的一个特殊情形是0－1规划，它的决策变量取值仅限于0或1两个逻辑值。

例3.1 某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如表3.1所示。两种货物各装运多少箱，可使获得利润最大？

解：设甲、乙两种货物装运箱数分别为 x ₁ 和 x ₂ ，显然， x ₁ 和 x ₂ 都需取整数，于是可建立整数规划模型如下：

若暂且不考虑 x ₁ 和 x ₂ 取整数这一条件，则规划就变为下列线性规划：

去掉整数限定后的规划问题称为原整数规划的伴随规划或松弛规划。求解例3.1的伴随规划： x ₁ ＝4.8， x ₂ ＝0， z′ ＝96。

但此解不满足整数要求，因此它不是原规划的最优解，一个直观的想法是对伴随规划的解进行四舍五入处理，得到 x ₁ ＝5， x ₂ ＝0，但它不是原规划的可行解。

若伴随规划的可行域是有界的，则原整数规划的可行域应是伴随规划可行域中有限个格点（整数点）的集合。因此，另一个直接的思路是能否用“穷举法”来求解整数规划。将伴随规划中所有整数点的目标函数值都计算出来，然后逐一比较找出最优解。这种方法对变量所能取的整数值个数较少时，勉强可以应用，如本例 x ₁ 可取0，1，2，3，4共5个数值，而 x ₂ 只能取0，1，2共三个数值，因此其组合最多为15个（其中还包含不可行的点）。但对大型问题，这种组合数的个数可能大得惊人，如在指派问题中，有 n 项任务指派 n 个人去完成，不同的指派方案共有 n ！种。当 n ＝20时，这个数超过2 ¹⁰¹³ 。显然穷举法并不是求解整数规划的有效方法。自20世纪60年代以来，已发展了一些常用的解整数规划的算法，如各种类型的割平面法、分支定界法、解0－1规划的隐枚举法、分解方法、群论方法、动态规划方法等。近十年来有人发展了一些近似算法及用计算机模拟法，也取得了较好的效果。

割平面法是从松弛问题的一个非整数的最优解出发，序贯地每次添加一个新的线性不等式（其对应线性方程所代表的超平面即称为割平面），求解新的松弛问题。每次增添的新的不等式要满足两个条件：①前一个不等式的最优解不满足这个不等式，即松弛问题的可行解集合被割去了一块。② S 中的“点”都满足这个不等式，即保证整数可行解不被割去。 56KWJWurIyNn/0+KGKhTPHuf4hwSKbxymV9dig58CP2ExA4W0TKertt6NR6jIBaN