《Gomory割平面法》PPT课件

《《Gomory割平面法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、整数最优解!!下面是求P的松弛问题最后一张单纯形表：–加入松弛变量s—割平面即不是整数P0最终表用对偶单纯形法求解定理3.2.1如果把割平面加到松弛问题的最优单纯形表里，那么没有割掉原ILP的任何整数可行点；当bi不是整数时，新表是一个原始基本不可行解和对偶可行解。2.Gomory割平面法计算步骤求松弛问题的最优基可行解判断是否为整数解是得到最优解否在单纯性表中加入一行利用对偶单纯形算法求最优解例3.2.1求解ILP问题(1,1.5)松弛问题的最优解是（1，1.5),不是整数解,从图中看出(1，1)是ILP问题的最优解，下面用割平面法求解整数规划1、先

3、求其松弛问题的最优解松弛问题的最优解是（1，3/2),最优值为Z*=3/2，不是整数解。以第二行生成割平面割平面方程为将其加到表中得利用对偶单纯形法求解得它的最优解为(2/3,1),仍不是整数解。以第一行生成的割平面方程为用对偶单纯形法求解得将最优解为（1，1）.(1,1.5)第一个割平面条件第二个割平面条件书P99习题3且为整数解：（1）(16/3,4/3)456784最优解为x*=（5,1），最优值z*=0,（2）引入松弛变量x3、剩余变量x4和人工变量x5,原问题的松弛问题转化为用两阶段法，先求解下模型，列单纯形表注意本题不能用对偶单纯形法x1x

4、2x3x4x5RHSz-150000g0000-10x3121008x51-10-114z-150000g1-10-104x3121008x51-10-114z040-114g0000-10x30311-14x11-10-114x1x2x3x4RHSz040-14x303114x11-10-14z00-4/3-7/3-4/3x2011/31/34/3x1101/3-2/316/30-15在上表中加入割平面方程-1/3x3-1/3x4+s1=-1/3,继续迭代，x1x2x3x4s1RHSz00-4/3-7/30-4/3x2011/31/304/3x110

5、1/3-2/3016/3s100-1/3-1/31-1/3z000-1-40x2010011x1100-115x30011-31用对偶单纯形法求解最优解为x*=（5，1），最优值z*=0,