运筹学讲义 显然,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