运筹学 割平面法.pptx
2 2、从、从(LP)的最优解中，任选一个不为整数的分量的最优解中，任选一个不为整数的分量x xr,r,将最优单纯形表中该行的系数将最优单纯形表中该行的系数 和和 分解为分解为整数整数部分和小数部分之和部分和小数部分之和，并以该行为源行，按下式作割，并以该行为源行，按下式作割平面方程：平面方程：3 3、将所得的割平面方程作为一个新的约束条件置于、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对最优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回偶单纯形法求出新的最优解，返回1 1。的小数部分的小数部分的小数部分的小数部分第1页/共36页例一：用割平面法求解整数规划问题例一：用割平面法求解整数规划问题解：增加松弛变量解：增加松弛变量x3和和x4，得到，得到(LP)的初始单纯形表和最优单纯形表：的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201j00100Cj0 100CBXBbx1x2x3x40 x111 0 1/6-1/61x23/2 0 1 1/4 1/4j-3/20 0-1/4-1/4第2页/共36页 此题的最优解为：此题的最优解为：X(1,3/2)Z=3/2 但不是整数最优解，但不是整数最优解，引入割平面。以引入割平面。以x2 为源行生成割平面，由于为源行生成割平面，由于 1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为成割平面的条件为:Cj0 100CBXBbx1x2x3x40 x111 0 1/6-1/61x23/2 0 1 1/4 1/4j-3/20 0-1/4-1/4现将生成的割平面条件加入松弛变量，然后加到表中：现将生成的割平面条件加入松弛变量，然后加到表中：第3页/共36页Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41j-3/200-1/4-1/40CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4j-10000-1第4页/共36页 此时，此时，X1(2/3,1),Z=1,仍不是整数解。继续以仍不是整数解。继续以x1为源行生成割为源行生成割平面，其条件为：平面，其条件为：CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4j-10000-1将生成的割平面条件加入松弛变量，然后加到表中：将生成的割平面条件加入松弛变量，然后加到表中：第5页/共36页CBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/3000-2/3-2/31j-10000-10CBXBbx1x2x3x4s1s20 x10100-1011x20010-103/20 x3600150-60s1100011-3/2j000010-3/2第6页/共36页CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2j-10000-10 至此得到最优表，其最优解为至此得到最优表，其最优解为 X=(1,1),Z=1,这这也是原问题的最优解。也是原问题的最优解。有以上解题过程可见，表中含有分数元素且算法过有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。数对偶割平面算法。第7页/共36页例一：用割平面法求解整数规划问题例一：用割平面法求解整数规划问题解：增加松弛变量解：增加松弛变量x3和和x4，得到，得到(LP)的初始单纯形表和的初始单纯形表和最优单纯形表：最优单纯形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201j00100Cj0 100CBXBbx1x2x3x40 x111 0 1/6-1/61x23/2 0 1 1/4 1/4j-3/20 0-1/4-1/4第8页/共36页 此题的最优解为：此题的最优解为：X(1,3/2)Z=3/2 但不是整数最优解，引入但不是整数最优解，引入割平面。以割平面。以x2 为源行生成割平面，为源行生成割平面，由于由于 1/4=0+1/4,3/2=1+1/2,我们已我们已将所需要的数分解为整数和分数，将所需要的数分解为整数和分数，所以，生成割平面的条件为所以，生成割平面的条件为:也即：也即：Cj0 100CBXBbx1x2x3x40 x111 0 1/6-1/61x23/2 0 1 1/4 1/4j-3/20 0-1/4-1/4第9页/共36页第10页/共36页将将 x3=6-3x1-2x2,x4=3x1-2x2 ,带入带入 中中 得到等价的割平面条件：得到等价的割平面条件：x2 1 见下图。见下图。x1x233第一个割平面第一个割平面第11页/共36页 此题的最优解为：此题的最优解为：X(1,3/2)Z=3/2 但不是整数最优解，引入但不是整数最优解，引入割平面。以割平面。以x2 为源行生成割平面，为源行生成割平面，由于由于 1/4=0+1/4,3/2=1+1/2,我们已我们已将所需要的数分解为整数和分数，将所需要的数分解为整数和分数，所以，生成割平面的条件为所以，生成割平面的条件为:也即：也即：Cj0 100CBXBbx1x2x3x40 x111 0 1/6-1/61x23/2 0 1 1/4 1/4j-3/20 0-1/4-1/4第12页/共36页Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41j-3/200-1/4-1/40CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4j-10000-1第13页/共36页 此时，此时，X1(2/3,1),Z=1,仍不是整数解。继续以仍不是整数解。继续以x1为源行生成割为源行生成割平面，其条件为：平面，其条件为：用上表的约束解出用上表的约束解出x4 和和s1，将它们带入上式得到等价的割平面，将它们带入上式得到等价的割平面条件：条件：x1 x2，见图：，见图：CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4j-10000-1第14页/共36页 用上表的约束解出用上表的约束解出x4 和和s1，将它们带入上式得到等价的割平面，将它们带入上式得到等价的割平面条件：条件：x1 x2，见图：，见图：x1x233第一个割平面第一个割平面第二个割平面第二个割平面第15页/共36页 此时，此时，X1(2/3,1),Z=1,仍不是整数解。继续以仍不是整数解。继续以x1为源行生成割为源行生成割平面，其条件为：平面，其条件为：CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4j-10000-1第16页/共36页CBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2/3000-2/3-2/31j-10000-10CBXBbx1x2x3x4s1s20 x10100-1011x20010-103/20 x3600150-60s1100011-3/2j000010-3/2第17页/共36页CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2j-10000-10 至此得到最优表，其最优解为至此得到最优表，其最优解为 X=(1,1),Z=1,这这也是原问题的最优解。也是原问题的最优解。有以上解题过程可见，表中含有分数元素且算法过有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。数对偶割平面算法。第18页/共36页例二：用割平面法求解数规划问题例二：用割平面法求解数规划问题Cj1100CBXBbx1x2x3x40 x3621100 x4204501j1100初初始始表表第19页/共36页Cj1100CBXBbx1x2x3x40 x3621100 x4204501j1100CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3j-13/3001/6 1/6初初始始表表最最优优表表第20页/共36页CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3j-13/3001/6 1/6最最优优表表引入松弛变量引入松弛变量s1 后得到下式，将此约束条件加到上表后得到下式，将此约束条件加到上表中，继续求解。中，继续求解。第21页/共36页Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31j13/3001/61/60第22页/共36页Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31j13/3001/61/60Cj11000CBXBbx1x2x3x4s11 x10100101x24010120 x3200113j400001/2第23页/共36页Cj11000CBXBbx1x2x3x4s11 x10100101x24010120 x3200113j400001/2 得得到到整整数数最最优优解解，即即为为整整数数规规划划的的最最优优解解，而而且且此此整整数数规规划划有有两两个个最最优优解解：X=(0,4),Z=4,或 X=(2,2),Z=4。第24页/共36页例二：用割平面法求解数规划问题例二：用割平面法求解数规划问题Cj1100CBXBbx1x2x3x40 x3621100 x4204501j1100初初始始表表第25页/共36页Cj1100CBXBbx1x2x3x40 x3621100 x4204501j1100CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3j-13/3001/6 1/6初初始始表表最最优优表表第26页/共36页在松弛问题最优解中，在松弛问题最优解中，x1,x2 均为非整数解，由上表有：均为非整数解，由上表有：CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3j-13/3001/6 1/6第27页/共36页将系数和常数都分解成整数和非负真分数之和将系数和常数都分解成整数和非负真分数之和 第28页/共36页将系数和常数都分解成整数和非负真分数之和将系数和常数都分解成整数和非负真分数之和 以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选考虑。现选第二个式子第二个式子，并将真分数移到右边得：，并将真分数移到右边得：第29页/共36页 以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选考虑。现选第二个式子第二个式子，并将真分数移到右边得：，并将真分数移到右边得：引入松弛变量引入松弛变量s1 后得到下式，将此约束条件加到上表中，继续求解。后得到下式，将此约束条件加到上表中，继续求解。第30页/共36页Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31j13/3001/61/60第31页/共36页Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31j13/3001/61/60Cj11000CBXBbx1x2x3x4s11 x10100101x24010120 x3200113j400001/2第32页/共36页Cj11000CBXBbx1x2x3x4s11 x10100101x24010120 x3200113j400001/2 得得到到整整数数最最优优解解，即即为为整整数数规规划划的的最最优优解解，而而且且此此整整数数规规划划有有两两个个最最优优解解：X=(0,4),Z=4,或 X=(2,2),Z=4。第33页/共36页第34页/共36页CBXBbx1x2x3x4x50 x34001-1/34/34x24/30102/9-5/911x18/31001/92/9j000-19/9-2/9CBXBbx1x2x3x4x5s10 x30001-1064x230101/20-5/211x121000010 x530001/21-9/2j000-20-1（2，3）第35页/共36页感谢您的观看！第36页/共36页
