Gomory割平面法课件

第二节Gomory割平面法Gomory

割平面法基本思想Gomory

割平面法计算步骤第二节Gomory割平面法1.Gomory割平面法基本思想整数规划松弛的线性规划问题()()两个问题具有如下明显关系：(1)()的可行域是()的可行域的子集;(2)若()无可行解，则()无可行解；(3)()的最优值优于()的最优值的；(4)若()的最优解是整数向量，则它也是()的最优解.1.Gomory割平面法基本思想整数规划松弛的线性规划问由松弛问题的可行域向整数规划的可行域逼近方法—利用超平面切除要求整数解保留松弛问题最优值增加由松弛问题的可行域向整数规划的可行域逼近。。。。（松弛问题最优解）费用减少方向(整数规划最优解)。。（松弛问题最优解）费用减少方向(整数规划第二节Gomory割平面法课件割平面法生成方法割

平

面

生

成

方

法条件--保留整数解删除非整数最优解!!下面是求P的松弛问题最后一张单纯形表：割平面法生成方法割

平

面

生

成

方

法条件--保留整数解第二节Gomory割平面法课件–加入松弛变量s—

割平面–加入松弛变量s—割平面即即第二节Gomory割平面法课件第二节Gomory割平面法课件不是整数P0最终表不是整数P0最终表第二节Gomory割平面法课件第二节Gomory割平面法课件用对偶单纯形法求解用对偶单纯形法求解定理3.2.1如果把割平面加到松弛问题的最优单纯形表里，那么没有割掉原ILP的任何整数可行点；当bi不是整数时，新表是一个原始基本不可行解和对偶可行解。定理3.2.1如果把割平面2.

Gomory

割平面法计算步骤求松弛问题的最优基可行解判断是否为整数解是得到最优解否在单纯性表中加入一行利用对偶单纯形算法求最优解2.Gomory割平面法计算步骤求松弛问题的判断是否是得例3.2.1求解ILP问题(1,1.5)松弛问题的最优解是（1，1.5),不是整数解,从图中看出(1，1)是ILP问题的最优解，例3.2.1(1,1.5)松弛问题的最优解是（1，1.5),下面用割平面法求解整数规划1、先求其松弛问题的最优解下面用割平面法求解整数规划第二节Gomory割平面法课件松弛问题的最优解是（1，3/2),最优值为Z*=3/2，不是整数解。松弛问题的最优解是（1，3/2),最优值为Z*=3/2，不以第二行生成割平面割平面方程为将其加到表中得以第二行生成割平面割平面方程为利用对偶单纯形法求解得利用对偶单纯形法求解得它的最优解为(2/3,1),仍不是整数解。以第一行生成的割平面方程为它的最优解为(2/3,1),仍不是整数解。用对偶单纯形法求解得将用对偶单纯形法求解得将最优解为（1，1）.最优解为（1，1）.(1,1.5)第一个割平面条件第二个割平面条件(1,1.5)第一个割平面条件书P99习题3且为整数解：（1）(16/3,4/3)456784最优解为x*=（5,1），最优值z*=0,书P99习题3且为整数解：（1）(16/3,4/3)4（2）引入松弛变量x3、剩余变量x4和人工变量x5,

原问题的松弛问题转化为用两阶段法，先求解下模型，列单纯形表注意本题不能用对偶单纯形法（2）引入松弛变量x3、剩余变量x4和人工变量x5,用两阶段x1x2x3x4x5RHSz-150000g0000-10x3121008x51-10-114z-150000g1-10-104x3121008x51-10-114z040-114g0000-10x30311-14x11-10-114x1x2x3x4x5RHSz-150000g0000-10xx1x2x3x4RHSz040-14x303114x11-10-14z00-4/3-7/3-4/3x2011/31/34/3x1101/3-2/316/30-15在上表中加入割平面方程-1/3x3-1/3x4+s1=-1/3,继续迭代，x1x2x3x4RHSz040-14x303114x11-1x1x2x3x4s1RHSz00-4/3-7/30-4/3x2011/31/304/3x1101/3-2/3016/3s100-1/3-1/31-1/3z000-1-40