您好,欢迎访问三七文档
(一)、计算步骤:1、用单纯形法求解(IP)对应的松弛问题(LP):⑴.若(LP)没有可行解,则(IP)也没有可行解,停止计算。⑵.若(LP)有最优解,并符合(IP)的整数条件,则(LP)的最优解即为(IP)的最优解,停止计算。⑶.若(LP)有最优解,但不符合(IP)的整数条件,转入下一步。第二节割平面法2、从(LP)的最优解中,任选一个不为整数的分量xr,,将最优单纯形表中该行的系数和分解为整数部分和小数部分之和,并以该行为源行,按下式作割平面方程:rjarb1nrjjrjmfxf3、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中(同时增加一个单位列向量),用对偶单纯形法求出新的最优解,返回1。的小数部分的小数部分rjarb例一:用割平面法求解整数规划问题且为整数0,023623max2121212xxxxxxxZ解:增加松弛变量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,我们已将所需要的数分解为整数和分数,所以,生成割平面的条件为:34111442xxCj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/4现将生成的割平面条件加入松弛变量,然后加到表中:214141143sxxCj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41σj-3/200-1/4-1/40214141143sxxCBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4σj-10000-1此时,X1=(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面,其条件为:41222333xsCBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4σj-10000-1将生成的割平面条件加入松弛变量,然后加到表中:323232214ssx323232214ssxCBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31σj-10000-10CBXBbx1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2σj000010-3/2CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2σj-10000-10至此得到最优表,其最优解为X*=(1,1),Z=1,这也是原问题的最优解。有以上解题过程可见,表中含有分数元素且算法过程中始终保持对偶可行性,因此,这个算法也称为分数对偶割平面算法。例一:用割平面法求解整数规划问题且为整数0,023623max2121212xxxxxxxZ解:增加松弛变量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,我们已将所需要的数分解为整数和分数,所以,生成割平面的条件为:34111442xx也即:23423423411344211114421111()244xxxxxxxxxCj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/40)4141(2143xx且为整数0,023623max2121212xxxxxxxZ212312412max326320,0Zxxxxxxxxx且为整数212312412max326320,0Zxxxxxxxxx且为整数312632xxx41232xxx将x3=6-3x1-2x2,x4=3x1-2x2,带入中得到等价的割平面条件:x2≤1见下图。x1x2⑴⑵33第一个割平面且为整数0,023623max2121212xxxxxxxZ34111442xx此题的最优解为:X*(1,3/2)Z=3/2但不是整数最优解,引入割平面。以x2为源行生成割平面,由于1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数,所以,生成割平面的条件为:也即:23423423411344211114421111()244xxxxxxxxxCj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/40)4141(2143xx34111442xxCj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41σj-3/200-1/4-1/40214141143sxxCBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4σj-10000-1此时,X1=(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面,其条件为:用上表的约束解出x4和s1,将它们带入上式得到等价的割平面条件:x1≥x2,见图:CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4σj-10000-141222333xs用上表的约束解出x4和s1,将它们带入上式得到等价的割平面条件:x1≥x2,见图:x1x2⑴⑵33第一个割平面第二个割平面此时,X1=(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面,其条件为:CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4σj-10000-1323232214ssx41222333xs323232214ssxCBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31σj-10000-10CBXBbx1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2σj000010-3/2CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2σj-10000-10至此得到最优表,其最优解为X*=(1,1),Z=1,这也是原问题的最优解。有以上解题过程可见,表中含有分数元素且算法过程中始终保持对偶可行性,因此,这个算法也称为分数对偶割平面算法。例二:用割平面法求解数规划问题且为整数0,205462max21212121xxxxxxxxZCj1100CBXBbx1x2x3x40x3621100x4204501σj1100初始表Cj1100CBXBbx1x2x3x40x3621100x4204501σj1100CBXBbx1x2x3x41x15/3105/6-1/61x28/301-2/31/3σj-13/300-1/6-1/6初始表最优表CBXBbx1x2x3x41x15/3105/6-1/61x28/301-2/31/3σj-13/300-1/6-1/6最优表34112333xx引入松弛变量s1后得到下式,将此约束条件加到上表中,继续求解。323131143sxxCj11000CBXBbx1x2x3x4s11x15/3105/6-1/601x28/301-2/31/300s1-2/300-1/3-1/31σj-13/300-1/6-1/60323131143sxxCj11000CBXBbx1x2x3x4s11x15/3105/6-1/601x28/301-2/31/300s1-2/300-1/3-1/31σj-13/300-1/6-1/60Cj11000CBXBbx1x2x3x4s11x10100-101x240101-20x320011-3σj-40000-1/2﹡Cj11000CBXBbx1x2x3x4s11x10100-101x240101-20x320011-3σj-40000-1/2﹡得到整数最优解,即为整数规划的最优解,而且此整数规划有两个最优解:X*=(0,4),Z=4,或X*=(2,2),Z=4。例二:用割平面法求解数规划问题且为整数0,205462max21212121xxxxxxxxZCj1100CBXBbx1x2x3x40x3621100x4204501σj1100初始表Cj1100CBXBbx1x2x3x40x3621100x4204501σj1100CBXBbx1x2x3x41x15/3105/6-1/61x28/301-2/31/3σj-13/300-1/6-1/6初始表最优表在松弛问题最优解中,x1,x2均为非整数解,由上表有:383132356165432431xxxxxxCBXBbx1x2x3x41x15/3105/6-1/61x28/301-2/31/3σj-13/300-1/6-1/6383132356165432431xxxxxx将系数和常数都分解成整数和非负真分数之和32231)311(321)651(65432431xxxxxx将系数和常数都分解成整数和非负真分数之和32231)311(321)651(65432431xxxxxx以上式子只须考虑一个即可,解题经验表明,考虑式子右端最大真分数的式子,往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等,可任选一个考虑。现选第二个式子,并将真分数移到右边得:以上式子只须考虑一个即可,解题经验表明,考虑式子右端最大真分数的式子,往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等,可任选一个考虑。现选第二个式子,并将真分数移到右边得:)(313224332xxxx引入松弛变量s1后得到下式,将此约束条件加到上表中,继续求解。323131143sxx34112333xxCj11000CBXBbx1x2x3x4s11x15/3105/6-1/601x28/301-2/31/300s1-2/300-1/3-1/31σj-13/300-1/6-1/60323131143sxxCj11000CBXBbx1x2x3x4s11x15/3105/6-1/601x28/301-2/31/300s1-2/300-1/3-1/31σj-13/300-1/6-1/60Cj11000CBXBbx1x2x3x4s11x10100-101x240101-20x320011-3σj-40000-1/
本文标题:运筹学--割平面法
链接地址:https://www.777doc.com/doc-4914266 .html