《运筹学 割平面法[稻谷书店].ppt》由会员分享，可在线阅读，更多相关《运筹学 割平面法[稻谷书店].ppt（36页珍藏版）》请在三一文库上搜索。
1、（一）、计算步骤： 1、用单纯形法求解( IP )对应的松弛问题( LP )： .若( LP )没有可行解，则( IP )也没有可行解，停止计算。 .若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 .若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。,第二节 割平面法,1,相关知识,2、从(LP)的最优解中，任选一个不为整数的分量xr,将最优单纯形表中该行的系数 和 分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程：,3、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位
2、列向量），用对偶单纯形法求出新的最优解，返回1。,的小数部分,的小数部分,2,相关知识,例一：用割平面法求解整数规划问题,解：增加松弛变量x3和x4 ，得到(LP)的初始单纯形表和最优单纯形表：,3,相关知识,此题的最优解为：X (1 , 3/2) Z = 3/2 但不是整数最优解，引入割平面。以x2 为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:,现将生成的割平面条件加入松弛变量，然后加到表中：,4,相关知识,5,相关知识,此时，X1 (2/3, 1), Z=1,仍不是整数解。继续以x1为源行生成割平面，其条
3、件为：,将生成的割平面条件加入松弛变量，然后加到表中：,6,相关知识,7,相关知识,至此得到最优表，其最优解为 X= (1 , 1) , Z = 1, 这也是原问题的最优解。,有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。,8,相关知识,例一：用割平面法求解整数规划问题,解：增加松弛变量x3和x4 ，得到(LP)的初始单纯形表和最优单纯形表：,9,相关知识,此题的最优解为：X (1 , 3/2) Z = 3/2 但不是整数最优解，引入割平面。以x2 为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我们已将所需要的
4、数分解为整数和分数，所以，生成割平面的条件为:,也即：,10,相关知识,11,相关知识,将 x3=6-3x1-2x2 , x4=3x1-2x2 ,带入 中 得到等价的割平面条件： x2 1 见下图。,12,相关知识,此题的最优解为：X (1 , 3/2) Z = 3/2 但不是整数最优解，引入割平面。以x2 为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:,也即：,13,相关知识,14,相关知识,此时，X1 (2/3, 1), Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：,用上表的约束解出x4 和
5、s1 ，将它们带入上式得到等价的割平面条件：x1 x2 ，见图：,15,相关知识,用上表的约束解出x4 和s1 ，将它们带入上式得到等价的割平面条件：x1 x2 ，见图：,16,相关知识,此时，X1 (2/3, 1), Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：,17,相关知识,18,相关知识,至此得到最优表，其最优解为 X= (1 , 1) , Z = 1, 这也是原问题的最优解。,有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。,19,相关知识,例二：用割平面法求解数规划问题,初 始 表,20,相关知识,初 始
6、表,最优表,21,相关知识,最优表,引入松弛变量s1 后得到下式，将此约束条件加到上表中，继续求解。,22,相关知识,23,相关知识,24,相关知识,得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解： X= (0, 4), Z = 4, 或 X= (2, 2), Z = 4。,25,相关知识,例二：用割平面法求解数规划问题,初 始 表,26,相关知识,初 始 表,最优表,27,相关知识,在松弛问题最优解中，x1, x2 均为非整数解，由上表有：,28,相关知识,将系数和常数都分解成整数和非负真分数之和,29,相关知识,将系数和常数都分解成整数和非负真分数之和,以上式子只须考虑一
7、个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：,30,相关知识,以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：,引入松弛变量s1 后得到下式，将此约束条件加到上表中，继续求解。,31,相关知识,32,相关知识,33,相关知识,得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解： X= (0, 4), Z = 4, 或 X= (2, 2), Z = 4。,34,相关知识,35,相关知识,（2 ，3）,36,相关知识,