§6.3.1割平面法（1）
给定整数规划

对应的松弛线性规划问题为
.
割平面法的基本思想：

利用单纯形法求解，设得其最优解为.若是整数解，则由§6.2 Th1推论知，即为的最优解；否则，设法给增加一个约束条件（割平面），将含在内的的一部分可行解“割”去，但不割去的任一可行解.然后，利用对偶单纯形法求解增加了割平面后的新的，设得其最优解为.对重复以上步骤，直到求得的最优解或判明无最优解为止.
割平面的选取：
W.L.O.G.设利用单纯形法求解最终得最优基，关于基的典式为
，
相应的单纯形表为

由单纯形表知，的最优解为，最优值为.
若为整数,，则的最优解为；
否则，不妨设不是整数，则单纯形表的第行对应的方程为
.
令，其中为的整数部分（不超过的最大整数），为的分数（小数）部分，，则上述方程即为

令，称之为以第行为源行（source row）的柯莫利割平面（Gomory cutting plane），简称为割平面.
引入松弛变量，则割平面即为
.
在算法的设计上，为尽可能快地“割去”的非整数解，常令，再以第行为源行作割平面.
割平面的两个性质：
Th1割平面割去的非整数最优解.
证明：显然，仅需证明的最优解不满足割平面即可.
将代入割平面，得，不满足割平面.
故将割平面添加到后，已不再满足新的约束条件
，
即割平面已将割去.▌
注：将割平面作为约束条件添加到后，原的最优解已不在新的可行域中.
Th2割平面不割去的任一可行解.
证明：显然，仅需证明的任一可行解均满足割平面即可.
，则由知，.
显然，满足典式，特别地

显然，，均为整数，也为整数,
又，，故满足割平面.▌
注：将割平面作为约束条件添加到后，原的可行解仍在新的可行域中.
增添割平面后的新单纯形表：
对松弛线性规划问题
，
增添割平面后，得新的线性规划

取基，其中，
则新单纯形表为

（新的单纯形表仅是在原的单纯形表中增加松弛变量的行、列而已！）
显然，，故可继续利用对偶单纯形法求解新.
根据以上的讨论，设计割平面法如下：
割平面法（Cutting Plane Algorithm）：1958年，R.E.Gomory
1.利用单纯形法求解的松弛线性规划问题.
2.若,则，停；
否则，设求得的的最优基为，相应的最优解，转3.
3.若为整数向量，则即为的最优解，停；
否则，令，以第行为源行作割平面，转4.
4.将割平面并入，得新.取正则基，在原的最优单纯形表中增加的行、列，即得新的单纯形表，利用对偶单纯形法继续解之.转2.