北邮运筹学ch割平面法.pptVIP

运筹学 北京邮电大学 * §5.3 割平面法 Cutting-plane Method Ch5 Integer Programming?? Page * of 11 设纯整数规划 松弛问题 的最优解 设xi不为整数， 将 分离成一个整数与一个非负真分数之和： 则有 等式两边都为整数并且有 加入松弛变量si得 此式称为以xi行为源行（来源行）的割平面，或分数切割式，或R.E.Gomory(高莫雷)约束方程。 将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。 则 例如， x1行： 移项： 令 加入松弛变量s1得 同理，对于x2行有： 如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。 【例】已知整数规划 【解】不考虑整数约束，松弛问题的最优表如下 －5/4 －1/4 0 0 λj 13/4 3/4 －1/4 0 1 x1 3 5/2 －1/2 1/2 1 0 x2 2 b x4 x3 x2 x1 XB CB 0 0 2 3 cj 最优表 最优解X=(－1/2，3/4，0，0)T， x1 、x2不满足整数要求，选择x2行进行分割： 得到Gomory约束 添加到最优表中，得 0 1 0 0 x5 0 －1/2 －1/2 －1/2 0 0 x5 0 －5/4 －1/4 0 0 λj 13/4 3/4 －1/4 0 1 x1 3 5/2 －1/2 1/2 1 0 x2 2 b x4 x3 x2 x1 XB CB 0 0 2 3 cj －1/2 －2 －1/2 ? 1 1 1 0 0 x3 0 －1 0 0 0 λj 7/2 1 0 0 1 x1 3 －1 0 1 0 x2 2 2 x1行： Gomory约束 添加到最优表中，得 0 1 0 0 0 x6 0 －1/2 －1/2 0 0 0 0 x6 0 －1/2 －1 －1/4 ? x5 0 1 1 1 0 0 x3 0 －1 0 0 0 λj 7/3 1 0 0 1 x1 3 2 －1 0 1 0 x2 2 b x4 x3 x2 x1 XB CB 0 0 2 3 cj －1 －2 －4 －1 2 1 1 0 0 0 0 x6 0 0 0 0 0 3 1 1 0 0 x3 0 －1 0 0 0 λj 4 1 0 0 1 x1 3 －1 0 1 0 x2 2 1 * §5.3 割平面法 Cutting-plane Method Ch5 Integer Programming?? Page * of 11