第5章-整数规划(割平面法)

割平面法割平面法 求解整数规划问题 求解整数规划问题 Max Z 3x1 2x2 2x1 3x2 14 4x1 2x2 18 x1 x2 0 且为整数 且为整数 解 首先 将原问题的数学模型标准化 解 首先 将原问题的数学模型标准化 这里标准化有两层含义 这里标准化有两层含义 1 将不等式转 将不等式转 化为等式约束 化为等式约束 2 将整数规划中所有非 将整数规划中所有非 整数系数全部转化为整数 以便于构造切整数系数全部转化为整数 以便于构造切 割平面 从而有 割平面 从而有 Max Z 3x1 2x2 2x1 3x2 x3 14 2x1 x2 x4 9 x1 x2 0 且为整数 且为整数 利用单纯形法求解 得到最优单纯形表 利用单纯形法求解 得到最优单纯形表 见表见表 1 表表 1 CBXBb3200 X1X2X3X4 2X25 2011 2 1 2 3X113 410 1 43 4 j59 4001 45 4 最优解为 最优解为 x1 13 4 x2 5 2 Z 59 4 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 0 01 12 23 34 45 56 67 78 89 9 2 2x x1 1 3 3x x2 2 1 14 4 2 2x x1 1 x x2 2 9 9 B A C 根据上表 写出非整数规划的约束方程 根据上表 写出非整数规划的约束方程 如 如 x2 1 2x3 1 2x4 5 2 1 将该方程中所有变量的系数及右端常数项将该方程中所有变量的系数及右端常数项 均改写成均改写成 整数与非负真分数之和整数与非负真分数之和 的形的形 式 即 式 即 1 0 x2 0 1 2 x3 1 1 2 x4 2 1 2 把整数及带有整数系数的变量移到方程左把整数及带有整数系数的变量移到方程左 边 分数及带有分数系数的变量称到方程边 分数及带有分数系数的变量称到方程 右边 得 右边 得 x2 x4 2 1 2 1 2x3 1 2x4 2 由于原数学模型已经由于原数学模型已经 标准化标准化 因此 在 因此 在 整数最优解中 整数最优解中 x2和和 x4也必须取整数值 也必须取整数值 所以所以 2 式左端必为整数或零 因而其右端式左端必为整数或零 因而其右端 也必须是整数 又因为也必须是整数 又因为 x3 x4 0 所以必有 所以必有 1 2 1 2x3 1 2x4 1 由于由于 2 式右端必为整数 于是有 式右端必为整数 于是有 1 2 1 2x3 1 2x4 0 3 或或 x3 x4 1 4 这就是考虑整数约束的一个割平面约束方这就是考虑整数约束的一个割平面约束方 程 它是用非基变量表示的 如果用基变程 它是用非基变量表示的 如果用基变 量来表示割平面约束方程 则有 量来表示割平面约束方程 则有 2x1 2x2 11 5 从图从图 1 中可以看出 中可以看出 5 式所表示的割平面式所表示的割平面 约束仅割去线性规划可行域中不包含整数约束仅割去线性规划可行域中不包含整数 可行解的部分区域 使点可行解的部分区域 使点 E 3 5 2 成为可成为可 行域的一个极点 行域的一个极点 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 10 0 0 01 12 23 34 45 56 67 78 89 9 2 2x x1 1 3 3x x2 2 1 14 4 2 2x x1 1 x x2 2 9 9 2 2x x1 1 2 2x x2 2 1 11 1 A D E C B 图图 1 在在 3 式中加入松弛变量式中加入松弛变量 x5 得 得 1 2x3 1 2x4 x5 1 2 6 将将 6 式增添到问题的约束条件中 得到新式增添到问题的约束条件中 得到新 的整数规划问题 的整数规划问题 Max Z 3x1 2x2 2x1 3x2 x3 14 2x1 x2 x4 9 1 2x3 1 2x4 x5 1 2 xi 0 且为整数 且为整数 i 1 2 5 该问题的求解可以在表该问题的求解可以在表 1 中加入中加入 6 式 然式 然 后运用对偶单纯形法求出最优解 具体计后运用对偶单纯形法求出最优解 具体计 算过程见表算过程见表 2 表表 2 32000CBXBb X1X2X3X4X5 2X25 2011 2 1 2 0 3X113 410 1 43 40 0X5 1 200 1 2 1 2 1 j59 4001 45 40 2X22010 11 3X17 21001 1 2 0X310011 2 j58 400011 2 由此得最优解为 由此得最优解为 x1 7 2 x2 2 z 58 4 该最优解仍不满足整数约束条件 因而需该最优解仍不满足整数约束条件 因而需 进行第二次切割 为此 从表进行第二次切割 为此 从表 2 中抄下非中抄下非 整数解整数解 x1的约束方程为 的约束方程为 x1 x4 1 2x5 7 2 按整数 分数归并原则写成 按整数 分数归并原则写成 x1 x4 x5 3 1 2 1 2x5 0 7 这就是一个新的割平面方程 用基变量来这就是一个新的割平面方程 用基变量来 表示 得 表示 得 x1 x2 5 8 在在 7 中加入松弛变量中加入松弛变量 x6 得 得 1 2x5 x6 1 2 9 将将 9 式增添到前一个问题的约束条件中去 式增添到前一个问题的约束条件中去 得到又一个新的整数规划问题 对它求解得到又一个新的整数规划问题 对它求解 可以在表可以在表 2 中加入中加入 7 式 然后运用对偶单式 然后运用对偶单 纯形法求出最优解 具体计算过程见表纯形法求出最优解 具体计算过程见表 3 表表 3 320000CBXBb X1X2X3X4X5X6 2X22010 110 3X17 21001 1 20 0X510011 20 0X6 1 20000 1 2 1 j58 400011 20 2X21010 102 3X1410010 1 0X3300110 4 0X5100001 2 j14000101 由此得最优解为 由此得最优解为 x1 4 x2 1 z 14 该最优 该最优 解符合整数条件 因此也是原整数规划问解符合整数条件 因此也是原整数规划问 题的最优解 题的最优解 从图从图 1 中可以看出 由中可以看出 由 8 式表示的割平式表示的割平 面约束 不仅割去线性规划可行域中剩下面约束 不仅割去线性规划可行域中剩下 的不含整数解域 而且使最优整数解的不含整数解域 而且使最优整数解 x1 4 x2 1 即图 即图 2 中的中的 G 点 点 成为新的线性规 成为新的线性规 划可行域的一个极点 划可行域的一个极点 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7