(6.3.1)--06_3割平面法.pdf

《(6.3.1)--06_3割平面法.pdf》由会员分享，可在线阅读，更多相关《(6.3.1)--06_3割平面法.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、割平面解法算法思想 由松弛问题的可行域向整数规划的可行域逼近 方法利用超平面切除 要求1.整数解保留2.松弛问题最优值减小Gomory定理在松弛问题的最优单纯形表中，假如有一常数项不是整数，且对应的方程为：分解和成整数与非负真分数之和：则为割平面方程（一）、割平面解法计算步骤：1、用单纯形法求解(IP)对应的松弛问题(LP)：.若(LP)没有可行解，则(IP)也没有可行解，停止计算。.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。2、从(LP)的最优解中，任选一个不为整数的分量xr,

2、将最优单纯形表中该行的系数和分解为整数部分和非负的真分数部分之和并且移项.把整数及带有整数系数的变量移方程左边,分数及带有分数系数的变量移方程右边.，按下式作割平面方程：的分数部分的分数部分3、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回1。把不等式划为等式 将非整数系数全部化为整数,出于割平面的需要.例如:目的:使松弛变量x3也是整数整数规划问题模型的标准化:加入松弛变量变为：例：用割平面法求解整数规划问题解：增加松弛变量x3和x4，得到(LP)的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40 x

3、3632100 x40-3201Z00100Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4Z-3/2 00-1/4-1/4此题的最优解为：X(1,3/2)Z=3/2 但不是整数最优解，引入割平面。以x2 为源行生成割平面，由于 1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:将 x3=6-3x1-2x2,x4=3x1-2x2 ,带入得到等价的割平面条件：x2 1见下图。x1x233第一个割平面Cj01000CBXBbx1x2x3x4s10 x11101/6-1/601x23/2011/41/4

4、00s1-200-1-11Z-3/200-1/4-1/40现将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s10 x12/3100-1/32/31x21010010 x320011-4Z-10000-1此时，X1(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：用上表的约束解出x4 和s1，将它们带入上式得到等价的割平面条件：x1 x2，见图：x1x233第一个割平面第二个割平面CBXBbx1x2x3x4s1s20 x12/3100-1/32/301x210100100 x320011-400s2-2000-2-21Z-10000-10将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s1s20 x10100-1011x20010-103/20 x3600150-60s1100011-3/2Z000010-3/2CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2Z-10000-10至此得到最优表，其最优解为X=(1,1),Z=1,这也是原问题的最优解。有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。