运筹学割平面法

运筹学割平面法演示文稿现在是1页\一共有35页\编辑于星期日运筹学割平面法现在是2页\一共有35页\编辑于星期日2、从(LP)的最优解中，任选一个不为整数的分量xr,,将最优单纯形表中该行的系数和分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程：3、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回1。的小数部分的小数部分现在是3页\一共有35页\编辑于星期日例一：用割平面法求解整数规划问题解：增加松弛变量x3和x4

，得到(LP)的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201σj00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/4现在是4页\一共有35页\编辑于星期日

此题的最优解为：X＊

(1,3/2)Z=3/2但不是整数最优解，引入割平面。以x2为源行生成割平面，由于1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/4现将生成的割平面条件加入松弛变量，然后加到表中：现在是5页\一共有35页\编辑于星期日Cj01000CBXBbx1x2x3x4s10x11101/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现在是6页\一共有35页\编辑于星期日

此时，X1

＝(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4σj-10000-1将生成的割平面条件加入松弛变量，然后加到表中：现在是7页\一共有35页\编辑于星期日CBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31σj-10000-10CBXBbx1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2σj000010-3/2现在是8页\一共有35页\编辑于星期日CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2σj-10000-10

至此得到最优表，其最优解为X＊=(1,1),Z=1,这也是原问题的最优解。

有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。现在是9页\一共有35页\编辑于星期日例一：用割平面法求解整数规划问题解：增加松弛变量x3和x4

，得到(LP)的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201σj00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/4现在是10页\一共有35页\编辑于星期日

此题的最优解为：X＊

(1,3/2)Z=3/2但不是整数最优解，引入割平面。以x2为源行生成割平面，由于1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:也即：Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/4现在是11页\一共有35页\编辑于星期日现在是12页\一共有35页\编辑于星期日将x3=6-3x1-2x2,x4=3x1-2x2,带入中

得到等价的割平面条件：x2≤

1见下图。x1x2⑴⑵33第一个割平面现在是13页\一共有35页\编辑于星期日

此题的最优解为：X＊

(1,3/2)Z=3/2但不是整数最优解，引入割平面。以x2为源行生成割平面，由于1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:也即：Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4σj-3/200-1/4-1/4现在是14页\一共有35页\编辑于星期日Cj01000CBXBbx1x2x3x4s10x11101/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现在是15页\一共有35页\编辑于星期日

此时，X1

＝(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：

用上表的约束解出x4和s1，将它们带入上式得到等价的割平面条件：x1≥x2，见图：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4σj-10000-1现在是16页\一共有35页\编辑于星期日

用上表的约束解出x4和s1，将它们带入上式得到等价的割平面条件：x1≥x2，见图：x1x2⑴⑵33第一个割平面第二个割平面现在是17页\一共有35页\编辑于星期日

此时，X1

＝(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4σj-10000-1现在是18页\一共有35页\编辑于星期日CBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31σj-10000-10CBXBbx1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2σj000010-3/2现在是19页\一共有35页\编辑于星期日CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2σj-10000-10

至此得到最优表，其最优解为X＊=(1,1),Z=1,这也是原问题的最优解。

有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。现在是20页\一共有35页\编辑于星期日例二：用割平面法求解数规划问题Cj1100CBXBbx1x2x3x40x3621100x4204501σj1100初始表现在是21页\一共有35页\编辑于星期日Cj1100CBXBbx1x2x3x40x3621100x4204501σj1100CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/3σj-13/300－1/6－1/6初始表最优表现在是22页\一共有35页\编辑于星期日CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/3σj-13/300－1/6－1/6最优表引入松弛变量s1后得到下式，将此约束条件加到上表中，继续求解。现在是23页\一共有35页\编辑于星期日Cj11000CBXBbx1x2x3x4s11x15/3105/6－1/601x28/301－2/31/300s1－2/300－1/3－1/31σj－13/300－1/6－1/60现在是24页\一共有35页\编辑于星期日Cj11000CBXBbx1x2x3x4s11x15/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﹡现在是25页\一共有35页\编辑于星期日Cj11000CBXBbx1x2x3x4s11x10100－101x240101－20x320011－3σj－40000－1/2﹡

得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：X＊=(0,4),Z=4,或X＊=(2,2),Z=4。

现在是26页\一共有35页\编辑于星期日例二：用割平面法求解数规划问题Cj1100CBXBbx1x2x3x40x3621100x4204501σj1100初始表现在是27页\一共有35页\编辑于星期日Cj1100CBXBbx1x2x3x40x3621100x4204501σj1100CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/3σj-13/300－1/6－1/6初始表最优表现在是28页\一共有35页\编辑于星期日在松弛问题最优解中，x1,x2

均为非整数解，由上表有：CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/3σj-13/300－1/6－1/6现在是29页\一共有35页\编辑于星期日将系数和常数都分解成整数和非负真分数之和现在是30页\一共有35页\编辑于星期日将系数和常数都分解成整数和非负真分数之和

以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：现在是31页\一共有35页\编辑于星期日

以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：引入松弛变量s1后得到下式，将此约束条件加到上表中，继续求解。现在是32页\一共有35页\编辑于星期日