《运筹学》课程教学讲义（Operations Research）第六章（6.3.2）割平面法（2/2）

运筹学讲义 §6.3.2割平面法(2) 例1利用割平面法求解整数规划 s t x1+x,≤1 x1,x2≥0,整数 解:(lP)的松弛线性规划问题为 st x1+x,≤1 (LP) x1+x2 4 x1,x2 0 其标准形为 max ==x, +x2 x tx2+x 3x1+x +x= 4 x≥0,j=1,234 取初始可行基B=(P3,P)=l2,利用单纯形法解之 x xx。x ①10|1 x2-11101 43452 (LP)的最优基为B=(P,P2) 3、3 fo=max{,}==J0,作割平面fo-(f3x3+f4x4)≤0,即-(7x3+x4)≤0 引入松弛变量x5,得 将割平面并入(LP),取正则基B=(B,P2B3),利用对偶单纯形法继续求解

运 筹 学 讲 义 1 §6.3.2 割平面法（2） 例 1 利用割平面法求解整数规划         +  − +  = + , 0,整数 3 4 . . 1 max ( ) : 1 2 1 2 1 2 1 2 x x x x st x x z x x IP . 解： (IP) 的松弛线性规划问题为         +  − +  = + , 0 3 4 . . 1 max ( ) : 1 2 1 2 1 2 1 2 x x x x st x x z x x LP ， 其标准形为         = + + = − + + = = + 0, 1,2,3,4 3 4 . . 1 max 1 2 4 1 2 3 1 2 x j x x x st x x x z x x j 取初始可行基 3 4 2 B = (P ,P ) = I ，利用单纯形法解之：  (LP) 的最优基为 ( , ) B = P1 P2 . 0 10 4 3 } 4 3 , 4 3 f max{ f k = = = ，作割平面 f 10 − ( f 13 x3 + f 14 x4 )  0 ，即 ) 0 4 1 4 3 ( 4 3 − x3 + x4  . 引入松弛变量 5 x ，得 4 3 4 1 4 3 − x3 − x4 + x5 = − . 将割平面并入 (LP) ，取正则基 ( , , ) B = P1 P2 P5 ，利用对偶单纯形法继续求解：

运筹学讲义 0 010 X1 1000 0 001 x01531315 0 (LP)的最优解为(1100,最优值为2.故(P)的最优解为(11),最优值为2 注:图解法 割平面 3x3+x4≥3 分3(1+x1-x2)+(4-3x1-x2)≥3 显然,割平面x2≤1割去(LP)的最优解 割平面14·4,但未割去(P)的任一可行解 X1 Ex.利用割平面法求解整数规划 max ==x, + x2 st 3x,+2x≤10 ≤5 x1,x2≥0,整数 解: x ③21010 x23 x110 02015

运 筹 学 讲 义 2  (LP) 的最优解为 T (1,1,1,0,0) ，最优值为 2 .故 (IP) 的最优解为 T (1,1) ，最优值为 2 .▌ 注：图解法 割平面： 1 3(1 ) (4 3 ) 3 3 3 4 3 4 1 4 3 2 1 2 1 2 3 4 3 4    + − + − −  − −  −  +  x x x x x x x x x 显然，割平面 x2 1 割 去 (LP) 的最优解 T ) 4 7 , 4 3 ( ，但未割去 (IP) 的任一可行解. Ex.利用割平面法求解整数规划          +  = + , 0，整数 2 5 . . 3 2 10 max ( ) : 1 2 2 1 2 1 2 x x x st x x z x x IP . 解：

运筹学讲义 最优基为B=(P,P2) f2o=maxi3 23 fo,作割平面x-Gx3+x4)≤0 引入松弛变量x,得-x+4+x3=3 x x4 FBx x2 3 4 sb 01-10 x10 x201 1-;0 3 (P)的最优解为(2,2),最优值为4 不难现象,随着割平面的不断增加,单纯形表的规模会变得越来越大,基变量的个数也会变得越 来越多.为避免因割平面的增加而导致的单纯形表的规模无限增大,可采取如下措施 在算法的步4中,若某次转轴后,先前附加于某割平面的松弛变量x再次变为基变量,则可从单 纯形表中删去x,所在的行、列;相应地,从(LP)中删去以x,为松弛变量的割平面 这样处理的理由:《数学规划》,郑汉鼎,刁在筠,山东教育出版社,P41引理1.2.3 在算法的步4中,当某一已变为非基变量的松弛变量x,在某次转轴后再次变为基变量时,单纯形 表中x.所在的行即对应以x为松弛变量的原割平面 例2利用割平面法求解整数规划 max ==4x,+3 x2 4x1+x,≤10 2x1+3x,≤8 x1,x2≥0,整数 解:(P)的松弛线性规划问题为

运 筹 学 讲 义 3 最优基为 ( , ) B = P1 P2 . 0 10 3 2 } 2 1 , 3 2 f max{ f k = = = ，作割平面 ) 0 3 2 3 1 ( 3 2 − x3 + x4  . 引入松弛变量 5 x ，得 3 2 3 2 3 1 − x3 − x4 + x5 = − .  (IP) 的最优解为 T (2,2) ，最优值为 4 .▌ 不难现象，随着割平面的不断增加，单纯形表的规模会变得越来越大，基变量的个数也会变得越 来越多.为避免因割平面的增加而导致的单纯形表的规模无限增大，可采取如下措施： 在算法的步 4 中，若某次转轴后，先前附加于某割平面的松弛变量 s x 再次变为基变量，则可从单 纯形表中删去 s x 所在的行、列；相应地，从 (LP) 中删去以 s x 为松弛变量的割平面. 这样处理的理由：《数学规划》，郑汉鼎，刁在筠，山东教育出版社，P41 引理 1.2.3 在算法的步 4 中，当某一已变为非基变量的松弛变量 s x 在某次转轴后再次变为基变量时，单纯形 表中 s x 所在的行即对应以 s x 为松弛变量的原割平面. 例 2 利用割平面法求解整数规划         +  +  = + , 0，整数 2 3 8 . . 4 10 max 4 3 ( ) : 1 2 1 2 1 2 1 2 x x x x st x x z x x IP . 解： (IP) 的松弛线性规划问题为

运筹学讲义 max ==4x,+3 x2 4x1+x2≤10 (LP) 2x1+3x,≤8 其标准形为 max - 4x, +3 st 4x1+x2+x3 x x≥0.j=12,34 取初始可行基B=(3,P)=l2,利用单纯形法解之: x1 x2 x3 x4 b 1010 23018 43000 02101 00 (LP)的最优基为B=(B2P2) f6o=max{,}==J2o,作割平面-(x3+x4)≤0 2 引入松弛变量x得-5x-5x4+x=5 将割平面并入(LP),取正则基B=(P1,P2,P3),利用对偶单纯形法继续求解: XI 1010 x1100 X2 010 x00-3 (LP)的最优基为B=(B,P2,B3)

运 筹 学 讲 义 4         +  +  = + , 0 2 3 8 . . 4 10 max 4 3 ( ) : 1 2 1 2 1 2 1 2 x x x x st x x z x x LP ， 其标准形为         = + + = + + = = + 0, 1,2,3,4 2 3 8 . . 4 10 max 4 3 1 2 4 1 2 3 1 2 x j x x x st x x x z x x j 取初始可行基 3 4 2 B = (P ,P ) = I ，利用单纯形法解之：  (LP) 的最优基为 ( , ) B = P1 P2 . 0 20 5 1 } 5 1 , 5 1 f max{ f k = = = ，作割平面 ) 0 5 2 5 4 ( 5 1 − x3 + x4  . 引入松弛变量 5 x 得 5 1 5 2 5 4 − x3 − x4 + x5 = − . 将割平面并入 (LP) ，取正则基 ( , , ) B = P1 P2 P5 ，利用对偶单纯形法继续求解：  (LP) 的最优基为 ( , , ) B = P1 P2 P3

运筹学讲义 ko=max:I }==f20,作割平面-(x4+7x5)≤0 引入松弛变量x得 x 将割平面并入(LP),取正则基B=(P,P2,P,P6),利用对偶单纯形法继续求解: x日xx2xx4xx6b x2 x100- x1-2 x 0 00009 xs再次出现,∴删去x3所在的行、列得 xBI x x2 x3 x4 26b x1100 00 2_3430 000 1|12 (LP)的最优基为B=(P,P2,B3) ko =max 02 2 3=J0,作割平面3-sx+3x)50 引入松弛变量x1,得-x3 将割平面并入(LP),取正则基B=(P,P2,P3,P),利用对偶单纯形法继续求解:

运 筹 学 讲 义 5 0 20 4 1 } 4 1 , 4 1 , 8 1 f max{ f k = = = ，作割平面 ) 0 4 3 2 1 ( 4 1 − x4 + x5  . 引入松弛变量 6 x 得 4 1 4 3 2 1 − x4 − x5 + x6 = − . 将割平面并入 (LP) ，取正则基 ( , , , ) B = P1 P2 P3 P6 ，利用对偶单纯形法继续求解：  5 x 再次出现，  删去 5 x 所在的行、列得  (LP) 的最优基为 ( , , ) B = P1 P2 P3 . 0 30 3 2 } 3 2 , 3 1 f max{0, f k = = = ，作割平面 ) 0 3 1 3 1 ( 3 2 − x4 + x6  . 引入松弛变量 7 x ，得 3 2 3 1 3 1 − x4 − x6 + x7 = − . 将割平面并入 (LP) ，取正则基 ( , , , ) B = P1 P2 P3 P7 ，利用对偶单纯形法继续求解：

运筹学讲义 xB x x2 x3 x4 x6 x,b x1100 02 x7000 1-21353131 xBI y x2 x xa xs x,b 10001 x110 0010③ x-90--30…4-…3 x40001 0 000010 x6再次出现,∴删去x6所在的行、列得 2 x110 2 3 2_34-3 (LP)的最优基为B=(B,P2,P4) J0=m33335J,作割平面一(x+x)≤0 2 引入松弛变量x8,得 33-21+2 将割平面并入(LP),取正则基B=(P,P,P,B),利用对偶单纯形法继续求解:

运 筹 学 讲 义 6  6 x 再次出现，  删去 6 x 所在的行、列得  (LP) 的最优基为 ( , , ) B = P1 P2 P4 . 0 20 3 2 } 3 1 , 3 2 , 3 1 f max{ f k = = = ，作割平面 ) 0 3 2 3 2 ( 3 2 − x3 + x7  . 引入松弛变量 8 x ，得 3 2 3 2 3 2 − x3 − x7 + x8 = − . 将割平面并入 (LP) ，取正则基 ( , , , ) B = P1 P2 P4 P8 ，利用对偶单纯形法继续求解：

运筹学讲义 xs b x100 30 x201001号 x400 00012 x0060 x300101 00 3 00001 (LP)的最优解为(2,1100最优值为11故(P)的最优解为(2,),最优值为1■ Ex.利用割平面法求解整数规划: maX max ==7x.+9 s t 2x1+5x2≤15 st x1+3x2≤6 (2) 2 XI ≤35 x1x2≥0,整数 x,x2≥0,整数 解:(1)(2,2),14:(2)(4,3),55.1 7

运 筹 学 讲 义 7  (LP) 的最优解为 T (2,1,1,1,0,0) ,最优值为 11.故 (IP) 的最优解为 T (2,1) ，最优值为 11.▌ Ex.利用割平面法求解整数规划： （1）         −  +  = + , 0，整数 2 2 5 . . 2 5 15 max 3 4 1 2 1 2 1 2 1 2 x x x x st x x z x x （2）         +  − +  = + , 0，整数 7 35 . . 3 6 max 7 9 1 2 1 2 1 2 1 2 x x x x st x x z x x 解：（1） (2,2) ,14 T ；（2） (4,3) ,55 T .▌