7.4 切割平面法

3 割平面法割平面法是通过生成一系列的平面割掉非整数部分来得到最优整数解的方法。

目前，割平面法有分数割平面法，原始割平面法，对偶整数割平面法，混合割平面法等。

我们介绍Gomory割平面法（纯整数规划割平面法）用例子说明割平面法基本思想。

例5-8求下列问题：Max Z=2x 1+ 3x 2s.t.2x 1+4x 2 ≤25x 1≤82x 2 ≤10x 1,x 2 ≥0,且取整数值化成标准问题Max Z=2x 1+ 3x 2s.t.2x 1+4x 2 + x 3 =25x 1+ x 4=82x 2 + x 5 =10x j 0,且取整数值松驰问题(P)Max Z=2x 1+ 3x 2s.t.2x 1+4x 2 + x 3 =25x 1+ x 4=82x 2 + x 5 =10x j 0松驰问题(P)用单纯形法求解得到最优解：B（8，9/4）Z=22（3/4）但不是原问题（IP）的解，（IP）可行域是OABDE内的全部方格点组成。

BD E O 1 2 3 4 5 6 7 A 8 9 10 11 1210987654321X 1X 2引进割平面法l 1: x 1+ x 2=10割去非整数部分FBG l 2: x 1+2x 2=12 割去非整数部分HDGFGB F D E l 1O 1 2 3 4 5 6 7 A 8 9 10 11 1210987654321X 12l 2G B F H D E O 1 2 3 4 5 6 7 A 8 9 10 11 1210987654321X 12GH E O 1 2 3 4 5 6 7 A 8 9 10 11 1210987654321X 12形成新的凸可行域OAGHE （整点凸包），它的极点G （方格点）是原规划（IP ）的最优解（8，2）Z=22。

约束条件：l 1: x 1+ x 2≤10l 2: x 1+2x 2≤12称为割平面。

问题是如何寻找割平面？松驰问题(P)Max Z=2x 1+ 3x 2s.t.2x 1+4x 2 + x 3 =25x 1+ x 4=82x 2 + x 5 =10x j 0初始单纯形表C 2 3 0 0 0bΘC B X B X1X2X3X4X50 X3 2 4 1 0 0 250 X4 1 00 1 0 80 X50 20 0 1 10σC2 3 0C B X B X 1 X 2 X 3 X 4 X 5 bΘ2 X 1 1 0 0 1 0 8 0 X 5 0 0 -1/2 1 1 11/2 3X 2 0 1 1/4 -1/20 9/4 σ0 -3/4 -1/20 91/4最终单纯形表:最优解（8,9/4,0,0,11/2）Z =91/4C2 3 0C B X B X 1 X 2 X 3 X 4 X 5 bΘ2 X 1 1 0 0 1 0 8 0 X 5 0 0 -1/2 1 1 11/2 3X 2 0 1 1/4 -1/20 9/4 σ0 -3/4 -1/20 91/4X 2相应的方程：x 2+(1/4)x 3 –(1/2) x 4 =9/4x 2+(1/4)x 3 –(1/2) x 4 =9/4把所有系数分解成整数和非负真分数之和。

割平面法的原理嘿，朋友们！今天咱来唠唠割平面法的原理。

你说这割平面法啊，就像是一个神奇的魔法棒！它能把那些看似复杂得让人头疼的问题一点点给捋顺咯。

咱可以把要解决的问题想象成一团乱麻，而割平面法呢，就是那把能把乱麻割断、整理清楚的剪刀。

它通过巧妙地构造一些额外的约束条件，就好像是给乱麻划上一道道清晰的界限，让我们能更清楚地看到问题的本质。

比如说吧，我们在面对一个整数规划问题的时候，那些整数的要求就像是一道道坎儿，让我们不容易跨过去。

但割平面法可不怕，它勇敢地冲上去，把这些坎儿都给标记出来，然后一点点地把问题给拆解开来。

你想想看，这多厉害呀！就好像我们在走迷宫，突然有了一盏明灯照亮了正确的道路。

割平面法就是这盏明灯，指引着我们找到最优解。

它不是那种生硬的方法，而是充满了智慧和灵活性。

它能根据不同的问题，巧妙地构造出合适的割平面，就像是一个经验丰富的老工匠，总能找到最合适的工具来解决问题。

而且哦，割平面法还特别有耐心。

它不会一下子就把问题解决了，而是一步一步地，慢慢地，就像绣花一样，精细地处理每一个细节。

有时候我们可能会觉得进展好慢呀，但别着急，等它最后把答案呈现在我们面前的时候，你就会惊叹，哇，原来这么神奇！咱再打个比方，割平面法就像是一个厨艺高超的大厨。

面对一堆杂乱无章的食材，它能巧妙地搭配、切割、烹饪，最后做出一道美味可口的佳肴。

这过程可能有点复杂，有点漫长，但最后出来的成果绝对让你惊艳。

总之呢，割平面法就是这么一个神奇又实用的东西。

它能帮我们解决那些看似不可能解决的问题，让我们在数学的海洋里畅游无阻。

所以啊，大家可别小瞧了它哟！以后遇到难题的时候，不妨想想割平面法，说不定它就能帮你打开思路，找到那把解开难题的钥匙呢！原创不易，请尊重原创，谢谢!。

分支定界法和割平面法分支定界法和割平面法在上学期课程中学习的线性规划问题中，有些最优解可能是分数或消失，但现实中某些具体的问题，常要求最优解必须是整数，这样就有了对于整数规划的研究。

整数规划有以下几种分类：（1）如果整数规划中所有的变量都限制为（非负）整数，就称为纯整数规划或全整数规划；（2）如果仅一部分变量限制为整数，则称为混合整数规划；（3）整数规划还有一种特殊情形是0-1规划，他的变量取值仅限于0或1。

本文就适用于纯整数线性规划和混合整数线性规划求解的分支定界法和割平面法，做相应的介绍。

一、分支定界法在求解整数规划是，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解。

对于小型问题，变量数量很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。

而对于大型的问题，可行的整数组合数很大时，这种方法就不可取了。

所以我们的方法一般是仅检查可行的整数组合的一部分，就能定出最有的整数解。

分支定界法就是其中一个。

分枝定界法可用于解纯整数或混合的整数规划问题。

在二十世纪六十年代初由Land Doig和Dakin等人提出。

由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。

目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。

设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作z；而A的任意可行解的目标函数值将是z*的一个下界z。

分枝定界法就是将B的可行域分成子区域再求其最大值的方法。

逐步减小z和增大z，最终求到z*。

现用下例来说明：例1 求解下述整数规划 Maxz?40x1?90x2?9x1?7x2?56? ?7x1?20x2?70?x,x?0且为整数?12解（1）先不考虑整数限制，即解相应的线性规划B，得最优解为：x1?4.81,x2?1.82,z?356可见它不符合整数条件。

§3割平面法割平面法也是求解整数规划问题常用方法之一。

3.1基本思路用割平面法求解整数规划的基本思路是：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止。

如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解。

这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)。

而把所有的整数解都保留下来，故称新增加的约束条件为割平面。

当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解。

即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。

下面以全整数规划问题的割平面法为例，介绍割平面的求解过程。

3.2求解步骤与举例割平面法的具体求解步骤如下：1.对于所求的整数规划问题(4.2)，先不考虑整数约束条件，求解相应的松弛问题（4.6）2.如果该问题无可行解或已取得整数最优解，则运算停止；前者表示原问题也无可行解，后者表示已求得整数最优解。

如果有一个或更多个变量取值不满足整数条件，则选择某个变量建立割平面。

3.增加为割平面的新约束条件，用前面介绍的灵敏分析的方法继续求解，返回1。

下面介绍割平面的建立方法及其求解过程。

例1 求解下列整数规划问题（4.7）解引入松弛变量，写成标准形式：(4.8)对上述模型不考虑整数条件，用单纯形法求解相应松弛问题的最终单纯形表为（表4-2）表4-215/38/3-13/3显然，为非整数解。

为求得整数解，我们想办法在原约束条件的基础下引入一个新的约束条件，以保证一个或几个变量取值为整数。

为此，在表4-2中任选一个取值非整数的变量，如，写出用基变量表示基变量的表达式：(4.9)将上式的所有变量的系数及右端常数均改写成一个整数与一个非负真分数之和的形式。

据此，(4.9)式可以改写成若将带有整数系数的变量整数项留在方程的左边，其余移到方程的右边，则有， (4.10) 由于要求变量取值为正整数，方程(4.10)的左边必为整数。

割平面法解题思路一、引言割平面法是数学中一种常用的解题方法，特别适用于解决几何问题。

它通过将平面割分为多个部分，并分析每个部分的性质来解决问题。

本文将对割平面法的解题思路进行详细探讨。

二、割平面法的基本概念2.1 平面的割分割平面法的核心思想是将平面划分为不同的区域，通常通过绘制直线或曲线来实现。

这样做的目的是将问题转化为对单一区域进行研究，从而简化问题的复杂性。

2.2 区域的性质分析每个区域都具有一些特定的性质，例如形状、面积、角度等。

通过对区域性质的分析，可以找到与问题相关的关键信息，从而解决问题。

三、割平面法的解题步骤3.1 理解问题在应用割平面法解题之前，首先要对问题进行充分理解。

了解问题的背景、条件和要求，明确需要求解的对象。

3.2 选择适当的割平面根据问题的性质和要求，选择适合的割平面。

这需要考虑到平面的位置、方向和形状，以及是否与已知条件相符。

3.3 剖析区域性质对每个区域进行详细的性质分析。

可以借助几何性质、角度关系、对称性等知识，找到有助于解题的性质。

3.4 推导解答利用区域性质进行推导，得出问题的解答。

这一步需要运用几何、代数等知识，进行具体的计算和推理。

3.5 检验解答将得到的解答与问题的条件和要求进行比较，确保解答的正确性。

可以使用数值计算、几何作图等方法进行检验。

四、实例分析：割平面法在几何问题中的应用4.1 问题描述一道常见的几何问题：如何确定一个不规则多边形的面积？4.2 解题思路4.2.1 割平面选择选择一条割线将多边形切割为两个较简单的几何图形，通常可以选择水平线或垂直线作为割线。

4.2.2 区域性质分析分析切割后得到的两个图形的性质。

对于一个矩形，可以直接应用矩形面积公式计算面积；对于一个三角形，可以利用底边和高进行计算。

4.2.3 推导解答根据切割后得到的图形，分别计算其面积。

然后将两个图形的面积相加，得到整个多边形的面积。

4.2.4 检验解答将计算得到的面积与问题中给出的条件进行比较，确保解答的正确性。

割平面法的基本思想割平面法主要用于求解整数规划问题的方法。

1958年由美国格莫理提出。

基本思路是：先不考虑整数性约束，求解相应的线性规划问题。

若线性规划问题的最优解恰好是整数解，则此解即为整数规划问题的最优解。

否则，就增加一个新的约束条件,称为割平面。

割平面必须具有两条性质：（1)从线性规划问题的可行域中至少割掉目前的非整数最优解；（2)不割掉任何整数可行域，然后在缩小的可行域上继续解线性规划问题。

重复以上做法，经有限次切割后，必可在缩小的可行域的一个整数极点上达到整数规划问题的最优解。

混合整数线性规划（MILP）的割平面法通过将整数问题线性松弛为非整数线性问题，并对其进行求解，来求解MILP 问题。

线性规划理论说明，在温和的假定下（如果线性规划存在最优解，并且可行域不包含一条线），总存在一个极值点或顶点是最优的。

检验所获的最优解是否为整数解。

如否，则必然存在一线性不等式将最优点和真可行集的凸包分离。

找到这样的不等式是分离问题，而这样的不等式就是切割。

切割可以被加入到被松弛的线性规划中，使得当前的非整数解对松弛不再可行。

该过程不断重复，直到找到最优整数解。

用于普遍的凸连续优化和变体的割平面法有不同的名称：Kelley 法，Kelley-Cheney-Goldstein 法和捆绑法。

它们常用于不可微的凸最小化问题。

对于这类问题，通常的可微优化的梯度法无法使用，而使用这些方法可以高效地得到凸目标函数及其次梯度。

这种情况最常出现在双拉格朗日函数的凹优化中。

另一种常见情形是Dantzig-Wolfe分解应用于结构优化问题中，这类问题通常有含有指数级变量的表达式。

通过延迟列生成法按需生成这些变量等同于在对应的对偶问题上切割平面。

图1.割平面法例，如上图1，单位立方体与切割平面。

在三节点的旅行推销员问题中，该（弱）不等式表明每次旅行必须连接至少两个点。

2Gomory 切割切割平面法由Ralph Gomory 在19 世纪50 年代提出，用于解决整数规划和混合整数规划问题。