® §十整数规划问题 在前面的线性规划问题中，它的解都假设为可以取连续数值。 但是在许多实际问题中，决策变量仅仅取整数值时才有意义，比如 变量表示的是工人的人数、机器的台数、货物的箱数、装货的车皮 数等等。为了满足整数解的要求，比较自然的简便方法似乎就是把 用线性规划方法所求得的非整数解进行“四舍五入”取整或“舍尾 取整”处理。当然，这样做有时确实也是有效的，可以取得与整数 最优解相近的可行整数解，因此它是实际工作中经常采用的方法。 但是实际问题中并不都是如此，有时这样处理得到的解可能不是原 问题的可行解，有的虽是原问题的可行解，但却不是整数最优解。 (详见后面例1)。因而有必要专门研究只取整数解的线性规划的 解法问题。 在一个线性规划问题中，如果它的所有决策变量都要求取整数 时，就称为纯整数规划；如果仅部分决策变量要求取整数则称为混 合整数规划，二者统称为整数规划。整数规划的一个特殊情形是01 规划，它的决策变量取值仅限于0或两个逻辑值。整数规划是近几 年发展起来的规划论的一个分支
§1 整数规划问题 在前面的线性规划问题中，它的解都假设为可以取连续数值。 但是在许多实际问题中，决策变量仅仅取整数值时才有意义，比如 变量表示的是工人的人数、机器的台数、货物的箱数、装货的车皮 数等等。为了满足整数解的要求，比较自然的简便方法似乎就是把 用线性规划方法所求得的非整数解进行“四舍五入”取整或“舍尾 取整”处理。当然，这样做有时确实也是有效的，可以取得与整数 最优解相近的可行整数解，因此它是实际工作中经常采用的方法。 但是实际问题中并不都是如此，有时这样处理得到的解可能不是原 问题的可行解，有的虽是原问题的可行解，但却不是整数最优解。 （详见后面例1）。因而有必要专门研究只取整数解的线性规划的 解法问题。 在一个线性规划问题中，如果它的所有决策变量都要求取整数 时，就称为纯整数规划；如果仅部分决策变量要求取整数则称为混 合整数规划，二者统称为整数规划。整数规划的一个特殊情形是0-1 规划，它的决策变量取值仅限于0或1两个逻辑值。整数规划是近几 年发展起来的规划论的一个分支
下面我们举例说明对于整数规划问题，用“四舍五入”取 整，或“舍尾取整”方法，是行不通的。 例1现有甲、乙两种货物拟用集装箱托运，每件货物的体 积、重量、可获利润，以及集装箱的托运限制如下表： 货物 体积（米3件） 重量（万斤件利润（万元/件） 甲 5 2 20 乙 4 5 10 托运限制 24 13 试确定集装箱中托运甲、乙货物的件数，使托运利润最大。 设x,x分别表示甲、乙货物托运的件数（整数），则该问题的 数学模型为： maxZ=20x+10x2 (1) 5x+4x2≤24 (2) 2x1+5x2≤13 (3) X1X2≥0，整数 (4)
下面我们举例说明对于整数规划问题，用“四舍五入”取 整，或“舍尾取整”方法，是行不通的。 例1 现有甲、乙两种货物拟用集装箱托运，每件货物的体 积、重量、可获利润，以及集装箱的托运限制如下表： 货物 体积（米3 /件） 重量（万斤/件）利润（万元/件） 甲 乙 5 4 2 5 20 10 托运限制 24 13 试确定集装箱中托运甲、乙货物的件数，使托运利润最大。 设x1 ,x2分别表示甲、乙货物托运的件数（整数），则该问题的 数学模型为： maxZ=20x1+10x2 ⑴ 5x1+4x2 ≤24 ⑵ 2x1+5x2 ≤13 ⑶ x1 ,x2 ≥0，整数 ⑷
这里货物的件数只能是整数，所以这是一个纯整数规划。荐先不考 虑整数限⑧永得问题的最优解为： x1=4.8,x2=0,maxZ=96 由于X二4：8不符合整数要求，所以该解不是整数规划的最优解。 是否可以将非整数解用“四舍五入”方法处理呢？事实上，如 果将x=4.8,x2=0近似为x=5,X2=0,则该解不符合体积限制条件(2)： 5x1+4X≤24 因而它不是最优解； 那么用“舍尾取整”方法处理又如何呢？将x=4.8,x2=0“舍 尾取整”为x=4,X,0,显然满足各约束条件，因而它是整数规划 问题的可行解，但它不是整数最优解。因为它对应的目标函数值 Z=80,而x=4,x2=1这个解亦是可行解，但它对应的目标函数值 Z=90。 个 由此例看出，简单的处理方法常常得不到整数规划的最优解， 甚至得不到可行解。 如何求得这类问题的整数最优解呢？到目前为止，整数规划还 没有一种很满意的和有效的解法。现在用以求解整数规划的方法基 本都是将整数规划变为一系列线性规划来求解的。我们将介绍两种
这里货物的件数只能是整数，所以这是一个纯整数规划。若先不考 虑整数限制，可求得问题的最优解为： x1=4.8，x2=0， maxZ=96 由于x1=4.8不符合整数要求，所以该解不是整数规划的最优解。 是否可以将非整数解用“四舍五入”方法处理呢？事实上，如 果将x1=4.8，x2=0近似为x1=5，x2=0，则该解不符合体积限制条件⑵： 5x1+4x2 ≤24 因而它不是最优解； 那么用“舍尾取整”方法处理又如何呢？将x1=4.8，x2=0 “舍 尾取整”为x1=4，x2=0，显然满足各约束条件，因而它是整数规划 问题的可行解，但它不是整数最优解。因为它对应的目标函数值 Z=80，而x1=4，x2=1这个解亦是可行解，但它对应的目标函数值 Z=90。 由此例看出，简单的处理方法常常得不到整数规划的最优解， 甚至得不到可行解。 如何求得这类问题的整数最优解呢？到目前为止，整数规划还 没有一种很满意的和有效的解法。现在用以求解整数规划的方法基 本都是将整数规划变为一系列线性规划来求解的。我们将介绍两种 方法——分枝定界法和割平面法
®§2分枝定界法 分枝定界法是求解整数规划的常用算法，既可用来解全部变量 取值都要求为整数的纯整数规划，又可用以求解混合整数规划 该算法的基本思路是：先不考虑整数限制，求出相应的线性规 划的最优解，若此解不符合整数要求，则去掉不包含整数解的部分 可行域，将可行域D分成D1、D2两部分（分枝），然后分别求解这 两部分可行域对应的线性规划，如果它们的解仍不是整数解，则继 续去掉不包含整数解的部分可行域，将可行域D1或D2分成D3与D4两 部分，再求解D,与D4对应的线性规划，.，在计算中若已得到一 个整数可行解X,则以该解的目标函数值乙作为分枝的界限，如果 某线性规划的目标值Z≤Z。，就没有必要继续分枝，因为分枝 (增加约束)的结果所得的最优解只能比乙，更差。反之若乙>Z, 则该线性规划分枝后，有可能产生比乙，更好的整数解，一旦真的产 生了一个更好的整数解，则以这个更好的整数解目标值作为新的界 限，六继续进行分枝，直至产生不出更好的整数解为止。 下面以实例来说明算法的步骤
§2 分枝定界法 分枝定界法是求解整数规划的常用算法，既可用来解全部变量 取值都要求为整数的纯整数规划，又可用以求解混合整数规划。 该算法的基本思路是：先不考虑整数限制，求出相应的线性规 划的最优解，若此解不符合整数要求，则去掉不包含整数解的部分 可行域，将可行域D分成D1、D2两部分（分枝） ，然后分别求解这 两部分可行域对应的线性规划，如果它们的解仍不是整数解，则继 续去掉不包含整数解的部分可行域，将可行域D1或D2分成D3与D4两 部分，再求解D3与D4对应的线性规划，……，在计算中若已得到一 个整数可行解X 0 ，则以该解的目标函数值Z0作为分枝的界限，如果 某一线性规划的目标值Z≤ Z0 ，就没有必要继续分枝，因为分枝 （增加约束）的结果所得的最优解只能比Z0 更差。反之若Z＞ Z0 ， 则该线性规划分枝后，有可能产生比Z0 更好的整数解，一旦真的产 生了一个更好的整数解，则以这个更好的整数解目标值作为新的界 限，继续进行分枝，直至产生不出更好的整数解为止。 下面以实例来说明算法的步骤
例2求解下面整数规划 maxZ=40x+90x2 1) 8 9x1+7X2=56 9x+7x≤56 (2) Z=40x+90x2 7x+20x2≤70 (3) X1,X2≥0 (4) X1,X2整数 7x1+20x2=70 (5) 解：先不考虑条件（⑤），求解相 10 X 应的线性规划问题L,得最优解 x=4.81,X2=1.82,Z0=356 （见图) 求解线性规划L1、L2 该解不是整数解。选择其中一个 得最优解为： 非整数变量，如x=4.81,对问题 问题L1: 问题L2: L分别增加约束条件： L+X1≤4 L+X1≥5 X1≤4，X1≥5 x1=4.00 X=5.00 将问题L分解为两个子问题L,L? (分枝)，也就是去掉问题L不含 x2=2.10 x2=1.57 整数解的一部分可行域，将原可 Z=349 Z2=341 行域D变为D1、D2两部分（如图）
例2 求解下面整数规划 maxZ=40x1+90x2 ⑴ 9x1+ 7x2 ≤56 ⑵ 7x1 +20x2 ≤70 ⑶ x1 ,x2 ≥0 ⑷ x1 ,x2 整数 ⑸ 解：先不考虑条件⑸，求解相 应的线性规划问题L，得最优解 x1=4.81，x2=1.82，Z0=356（见图） x2 8 0 6 4 10 x1 9x1+ 7x2=56 7x1+20x2=70 Z=40x1+90x2 该解不是整数解。选择其中一个 非整数变量，如x1=4.81，对问题 L分别增加约束条件： x1≤4，x1≥5 将问题L分解为两个子问题L1，L2 （分枝），也就是去掉问题L不含 整数解的一部分可行域，将原可 行域D变为D1、D2两部分（如图）。 4 D1 D2 求解线性规划L1、L2 得最优解为： 问题L1： L+ x1≤4 问题L2： L+ x1≥5 x1=4.00 x2=2.10 Z1=349 x1=5.00 x2=1.57 Z2=341