资源描述：
《运筹学 割平面法复习过程.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、（一）、计算步骤：1、用单纯形法求解(IP)对应的松弛问题(LP)：⑴.若(LP)没有可行解，则(IP)也没有可行解，停止计算。⑵.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。⑶.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。第二节割平面法2、从(LP)的最优解中，任选一个不为整数的分量xr,,将最优单纯形表中该行的系数和分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程：3、将所得的割平面方程作为一个新的约束条件置于最
2、优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回1。的小数部分的小数部分例一：用割平面法求解整数规划问题解：增加松弛变量x3和x4，得到(LP)的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201σj00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/4此题的最优解为：X＊(1,3/2)Z=3/2但不是整数最优解，引入割平面。以x2为源行生成割平
3、面，由于1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/4现将生成的割平面条件加入松弛变量，然后加到表中：Cj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41σj-3/200-1/4-1/40CBXBbx1x2x3x4s10x12/3100-
4、1/32/31x21010010x320011-4σj-10000-1此时，X1＝(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4σj-10000-1将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31σj-10000-10CBXBb
5、x1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2σj000010-3/2CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2σj-10000-10至此得到最优表，其最优解为X＊=(1,1),Z=1,这也是原问题的最优解。有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。例一：用割平面法求解整数
6、规划问题解：增加松弛变量x3和x4，得到(LP)的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201σj00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/4此题的最优解为：X＊(1,3/2)Z=3/2但不是整数最优解，引入割平面。以x2为源行生成割平面，由于1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:也即：Cj0
7、100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/4将x3=6-3x1-2x2,x4=3x1-2x2,带入中得到等价的割平面条件：x2≤1见下图。x1x2⑴⑵33第一个割平面此题的最优解为：X＊(1,3/2)Z=3/2但不是整数最优解，引入割平面。以x2为源行生成割平面，由于1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:也即：Cj0100CBXBbx1x2x3x40x11101/
8、6-1/61x23/2011/41/4σj-3/200-1/4-1/4Cj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41σj-3/200-1/4-1/40CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4σj-10000-1此时，X1＝(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：用上表的约束解出x4和
