运筹学讲义 §6.3.1割平面法(1) 给定整数规划 max (IP): s.L. Ax=b x20整数,j=12…n 对应的松弛线性规划问题为 max 2=c (LP): s.L. Ax=b 0 割平面法的基本思想 利用单纯形法求解(LP),设得其最优解为x’.若x 是整数解,则由§6.2Thl推论知,x即为(P)的最优 解;否则,设法给(LP)增加一个约束条件(割平面),将 K 含x在内的(LP)的一部分可行解“割”去,但不割去(lP 的任一可行解.然后,利用对偶单纯形法求解增加了割平 A 面后的新的(LP),设得其最优解为x”.对x”重复以上 步骤,直到求得(P)的最优解或判明(P)无最优解为止 割平面的选取 W.L.O.G.设利用单纯形法求解(LP)最终得最优基B=(F,P2…P),(LP)关于基B的典式 为 x+∑bx1=b1=12…,mx1=b-∑x,1=12 S 相应的单纯形表为
运 筹 学 讲 义 1 §6.3.1 割平面法（1） 给定整数规划 = = = x j n st Ax b z c x IP j T 0, , 1,2, , . . max ( ) : 整数 对应的松弛线性规划问题为 = = 0 . . max ( ) : x st Ax b z c x LP T . 割平面法的基本思想： 利用单纯形法求解 (LP) ，设得其最优解为 x .若 x 是整数解，则由§6.2 Th1 推论知， x 即为 (IP) 的最优 解；否则，设法给 (LP) 增加一个约束条件（割平面），将 含 x 在内的 (LP) 的一部分可行解“割”去，但不割去 (IP) 的任一可行解.然后，利用对偶单纯形法求解增加了割平 面后的新的 (LP) ，设得其最优解为 x .对 x 重复以上 步骤，直到求得 (IP) 的最优解或判明 (IP) 无最优解为止. 割平面的选取： W.L.O.G.设利用单纯形法求解 (LP) 最终得最优基 ( , , , ) B = P1 P2 Pm ，(LP) 关于基 B 的典式 为 + = + = = = + = + 0 1 0 1 , 1,2, , z r x z x b x b i m n j m j j i n j m i ij j = − = − = = + = + n j m j j n j m i i ij j z z r x x b b x i m 1 0 1 0 , 1,2,, ， 相应的单纯形表为
运筹学讲义 x110 0 bn 1 b bnb 由单纯形表知,(LP)的最优解为x=(b0。b20…,bn00…0),最优值为z0 若bo为整数,i=12…m,则(lP)的最优解为x=(b,b20,…,bm0,0.0,…0) 否则,不妨设bo(1≤k≤m)不是整数,则单纯形表的第k行对应的方程为 x+∑b2x=b0→xk=bo-∑b 令b=[b]+/,j= 1…,n,其中[b]为b的整数部分(不超过b的最大整 数),J为b的分数(小数)部分,J60>0,J∈[D,1,j=m+1,m+2,…,n,则上述方程即为 ∑bx=([bol+fo) ([b]+/)x ∑bJx1+f0-∑f 令A0-∑x≤0,称之为以第k行为源行( source row)的柯莫利割平面( Gomory cutting plane),简称为割平面 引入松弛变量xn1≥0,则割平面即为 f0-∑/x≤0分f-∑ 04-∑ 在算法的设计上,为尽可能快地“割去”(LP)的非整数解,常令f0=max{f0>0},再以第k
运 筹 学 讲 义 2 由单纯形表知， (LP) 的最优解为 T b b bm x ( , , , ,0,0, ,0) = 10 20 0 ，最优值为 0 z . 若 i0 b 为整数, i = 1,2, ,m，则 (IP) 的最优解为 T b b bm x ( , , , ,0,0, ,0) = 10 20 0 ； 否则，不妨设 (1 ) bk 0 k m 不是整数，则单纯形表的第 k 行对应的方程为 = + = + + = = − n j m k k k kj j n j m k kj j x b x b x b b x 1 0 0 1 . 令 bkj = [bkj ] + f kj , j = 0,m +1,m +1, ,n ，其中 [ ] bkj 为 kj b 的整数部分（不超过 kj b 的最大整 数）， kj f 为 kj b 的分数（小数）部分， f k 0 0; f kj [0,1), j = m +1,m + 2, ,n ，则上述方程即为 [ ] [ ] . ([ ] ) ([ ] ) 1 0 1 0 1 0 0 1 0 = + = + = + = + = − + − = − = + − + n j m k kj j n j m k kj j n j m k k kj kj j n j m k k kj j b b x f f x x b b x b f b f x 令 0 1 0 − = + n j m k kj j f f x ，称之为以第 k 行为源行（source row）的柯莫利割平面（Gomory cutting plane），简称为割平面. 引入松弛变量 xn+1 0 ，则割平面即为 1 0 1 1 1 0 1 0 0 0 n k n j m n kj j n j m k kj j n j m k kj j f − f x f − f x + x = − f x + x = − f + = + + = + = + . 在算法的设计上，为尽可能快地“割去”(LP) 的非整数解，常令 max{ 0} 0 1 0 = i i m k f f ，再以第 k
运筹学讲义 行为源行作割平面 割平面的两个性质: Th割平面Ao-∑/x,≤0割去(LP)的非整数最优解 J=m+1 证明:显然,仅需证明(LP)的最优解x=(b0,b20…,bn,00…,0)不满足割平面即可 x=0,j=m+1,“n 将x代入割平面,得f0-∑fx J6o>0,∴x不满足割平面 故将割平面添加到(LP)后,x已不再满足新(LP)的约束条件 x≥0 即割平面已将x割去 注:将割平面作为约束条件添加到(LP)后,原(LP)的最优解已不在新(LP)的可行域中 Th2割平面f-∑/x≤0不割去(P)的任一可行解 证明:显然,仅需证明(lP)的任一可行解均满足割平面即 =(x,x2,…,文n)∈K(P),则由K(P)K(LP)知,∈K(LP) 显然,x满足典式,特别地 =b0-∑b=([b61+J)-∑(b]+f) bo-∑b]+f0-∑/ 显然,,bo-∑[b均为整数,∴fA0-∑元也为整数
运 筹 学 讲 义 3 行为源行作割平面. 割平面的两个性质： Th1 割平面 0 1 0 − = + n j m k kj j f f x 割去 (LP) 的非整数最优解. 证明：显然，仅需证明 (LP) 的最优解 T b b bm x ( , , , ,0,0, ,0) = 10 20 0 不满足割平面即可. 将 x 代入割平面，得 0 0 0, 1, , 1 0 − = = = + = + k n x j m n j m k kj j f f x f j ， x 不满足割平面. 故将割平面添加到 (LP) 后， x 已不再满足新 (LP) 的约束条件 − = = + 0 0 1 0 x f f x Ax b n j m k kj j ， 即割平面已将 x 割去.▌ 注：将割平面作为约束条件添加到 (LP) 后，原 (LP) 的最优解已不在新 (LP) 的可行域中. Th2 割平面 0 1 0 − = + n j m k kj j f f x 不割去 (IP) 的任一可行解. 证明：显然，仅需证明 (IP) 的任一可行解均满足割平面即可. ˆ (ˆ , ˆ , , ˆ ) ( ) 1 2 x x x x K IP T = n ，则由 K(IP) K(LP) 知， x ˆ K(LP) . 显然， x ˆ 满足典式，特别地 [ ] [ ]ˆ ˆ . ˆ ˆ ([ ] ) ([ ] )ˆ 1 0 1 0 1 0 0 1 0 = + = + = + = + = − + − = − = + − + n j m k kj j n j m k kj j n j m k k kj kj j n j m k k kj j b b x f f x x b b x b f b f x 显然， k x ˆ ， = + − n j m k kj j b b x 1 0 [ ] [ ]ˆ 均为整数， = + − n j m k kj j f f x 1 0 ˆ 也为整数
运筹学讲义 又J0-∑/,≤J60<1,…∴f-∑≤0,故满足割平面■ 注:将割平面作为约束条件添加到(P)后,原(P)的可行解仍在新(P)的可行域中 增添割平面后的新单纯形表 对松弛线性规划问题 (LP): s.t. Ax= b x≥0 增添割平面f0-∑/x,50分f0-∑x1+xm=0分-∑/x+xm=-后, 得新的线性规划 max 2=c x s.t. Ax=b x1≥0,j=1,2,…,n,n+1 取基B:=/B0 071/其中0=(00,…0)y∈R", 则新单纯形表为 x201…02+1b xbb:b 1 b x00…0-+1一天测 z|00 o r he (新(LP)的单纯形表仅是在原(LP)的单纯形表中增加松弛变量xn的行、列而已!)
运 筹 学 讲 义 4 又 ˆ 0 1 0 ˆ 0 1 0 − = + k f x n j m k kj j f f x f kj j ， ˆ 0 1 0 − = + n j m k kj j f f x ，故 x ˆ 满足割平面.▌ 注：将割平面作为约束条件添加到 (IP) 后，原 (IP) 的可行解仍在新 (IP) 的可行域中. 增添割平面后的新单纯形表： 对松弛线性规划问题 = = 0 . . max ( ) : x st Ax b z c x LP T ， 增添割平面 1 0 1 1 1 0 1 0 0 0 n k n j m n kj j n j m k kj j n j m k kj j f − f x f − f x + x = − f x + x = − f + = + + = + = + 后， 得新的线性规划 = + − + = − = = + = + 0, 1,2, , , 1. . . max 1 0 1 x j n n f x x f st Ax b z c x j n k n j m kj j T 取基 = 0 1 0 : T B B ，其中 T m 0 = (0,0,, 0) R ， 则新单纯形表为 （新 (LP) 的单纯形表仅是在原 (LP) 的单纯形表中增加松弛变量 n+1 x 的行、列而已！）
运筹学讲义 显然,r≥0,J∈J,故可继续利用对偶单纯形法求解新(LP) 根据以上的讨论,设计割平面法如下 割平面法( Cutting Plane Al gor ithm):1958年,R.E. Gomol 1利用单纯形法求解(P)的松弛线性规划问题(LP) 2若K(LP)=中则K(P)=Φ,停 否则,设求得的(LP)的最优基为B,相应的最优解x,转3 3若x为整数向量,则x即为(P)的最优解,停 否则,令A0=mx{0>0},以第k行为源行作割平面f0-∑/x,≤0,转4 4将割平面并入(LP),得新(LP)取正则基B:=|0) 在原(LP)的最优单纯形表 中增加xn的行、列,即得新(LP)的单纯形表,利用对偶单纯形法继续解之转2
运 筹 学 讲 义 5 显然， r j J j 0, ，故可继续利用对偶单纯形法 ．．．．．．求解新 (LP) . 根据以上的讨论，设计割平面法如下： 割平面法（Cutting Plane Algorithm）：1958 年，R.E.Gomory 1.利用单纯形法求解 (IP) 的松弛线性规划问题 (LP) . 2.若 K(LP) = ,则 K(IP) = ，停； 否则，设求得的 (LP) 的最优基为 B ，相应的最优解 x ，转 3. 3.若 x 为整数向量，则 x 即为 (IP) 的最优解，停； 否则，令 max{ 0} 0 1 0 = i i m k f f ，以第 k 行为源行作割平面 0 1 0 − = + n j m k kj j f f x ，转 4. 4.将割平面并入 (LP) ，得新 (LP) .取正则基 = 0 1 0 : T B B ，在原 (LP) 的最优单纯形表 中增加 n+1 x 的行、列，即得新 (LP) 的单纯形表，利用对偶单纯形法继续解之.转 2