第五章 整数规划讲解.ppt

一、整数规划的模型 用分枝定界法求解整数规划问题 例 用分枝定界法求解整数规划问题（单纯形法） 练习：用分枝定界法求解整数规划问题 （单纯形法） 单纯形法最终表 设xi不为整数， 将 分离成一个整数与一个非负真分数之和： 则有 上式两边都为整数并且有 加入松弛变量si得 此式称为以xi行为源行(来源行)的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。 将Gomory约束方程加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。 则 例如， x1行： 移项： 令 加入松弛变量s1得 同理，对于x2行有： 例 用割平面法求解下列IP问题 解 放宽变量约束，对应的松弛问题是 加入松弛变量x3及x4后，用单纯形法求解，得到最优表 最优解X(0)＝(5/2，15/4),不是IP的最优解。选择表的第一行(也可以选第二行)为源行 Cj 4 3 0 0 b CB XB x1 x2 x3 x4 4 3 x1 x2 1 0 0 1 1/4 －1/8 －1/2 3/4 5/2 15/4 λj 0 0 －5/8 －1/4 分离系数后改写成 加入松弛变量x5得到高莫雷约束方程 将上式作为约束条件添加到上表中，用对偶单纯形法计算，如表所示: Cj 4 3 0 0 0 b CB XB x1 x2 x3 x4 x5 4 3 0 x1 x2 x5 1 0 0 0 1 0 1/4 －1/8 －1 －1/2 3/4 [－2] 0 0 1 5/2 15/4 －2→ λj 0 0 －5/8 －1/4↑ 0 4 3 0 x1 x2 x4 1 0 0 0 1 0 1/2 －1/2 1/2 0 0 1 －1/4 3/8 －1/2 3 3 1 λj 0 0 －1/2 0 －1/8 最优解X(1)＝(3，3)，最优值Z＝21。所有变量为整数，X(1)就是IP的最优解。如果不是整数解，需要继续切割，重复上述计算过程。 如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。 正则解 1 求解0－1整数规划的隐枚举法（适合于变量个 数较少的0-1规划） 隐枚举法的步骤： 1.找出任意一可行解，目标函数值为Z0 ； 2.? 原问题求最大值时，则增加一个约束 当求最小值时，上式改为小于等于约束； 3. 列出所有可能解，对每个可能解先检验式(*)，若满足再检验其它约束，若不满足式(*)，则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值 ； 4. 目标函数值最大(最小)的解就是最优解。 0－1规划的求解 例 用隐枚举法求解下列BIP问题 解 (1) 不难看出，当所有变量等于0或1的任意组合时，第一个约束满足，说明第一个约束没有约束力，是多余的，从约束条件中去掉。 还能通过观察得到X0＝(1，0，0，1)是一个可行解，目标值Z0＝11是BIP问题的下界，构造一个约束： 原BIP问题变为 (2) 列出变量取值0和1的组合，共24＝16个，分别代入约束条件判断是否可行。 首先判断式(a)是否满足，如果满足，接下来判断其它约束，否则认为不可行，计算过程见下表所示。 3. 列出所有可能解，对每个可能解先检验式(*)，若满足再检验其它约束，若不满足式(*)，则认为不可行，若所有约束都满足，则认为此解是可行解，求出目标值 ； j Xj a b c d Zj j Xj a b c d Zj 1 (0,0,0,0) × 　 　 　 　 9 (1,0,0,0) × 　 　 　 　 2 (0,0,0,1) × 　 　 　 　 10 (1,0,0,1) √ √ √ √ 11 3 (0,0,1,0) × 　 　 　 　 11 (1,0,1,0) × 　 　 　 　 4 (0,0,1,1) × 　 　 　 　 12 (1,0,1,1) √ √ √ √ 14 5 (0,1,0,0) × 　 　 　 　 13 (1,1,0,0) × 　 　 　 　 6 (0,1,0,1) × 　 　 　 　 14 (1,1,0,1) √ √ √ √ 13 7 (0,1,1,0) × 　 　 　 　 15 (1,1,1,0) √ × 　 　 　 8 (0,1,1,1) × 　 　 　 　 16 (1,1,1,1) √ √ √ × 　 (3) 由上表知，BIP问题的最优解：X＝(1，0，1，1)，最优值Z＝14。 注： (1) 选择不同的初