运筹学3.2割平面算法

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把所有系数分解成整数和非负真分数之和。

python割平面法割平面法是一种用于求解凸多面体的优化问题的方法，它通过不断割平面来逼近最优解。

本文将介绍割平面法的基本原理和应用，并通过一个简单的例子来说明其具体操作过程。

割平面法是一种求解凸多面体的线性规划问题的有效方法。

在线性规划中，我们需要找到满足一组线性约束条件的目标函数取得最优值的变量取值。

而割平面法则通过不断添加新的线性约束条件来逼近最优解。

我们需要将线性规划问题转化为标准形式。

标准形式的线性规划问题可以写成如下形式：max c^T xs.t. Ax ≤ bx ≥ 0其中，c是目标函数的系数向量，x是变量向量，A是约束条件的系数矩阵，b是约束条件的常数向量。

割平面法的基本思想是通过不断添加新的线性约束条件来逼近最优解。

具体操作过程如下：1. 初始化：将原始约束条件转化为等式形式，并添加一个非负约束条件x ≥ 0。

将初始可行解设为x^0。

2. 求解：使用线性规划求解器求解当前的线性规划问题，得到最优解x^*和对应的目标函数值z^*。

3. 检验：判断当前解x^*是否满足所有约束条件，如果满足则终止算法，输出最优解x^*和对应的目标函数值z^*；否则转到下一步。

4. 割平面：添加一个新的线性约束条件，将当前解x^*加入约束条件中，得到一个新的约束条件。

将新的约束条件添加到线性规划问题中，得到一个新的线性规划问题。

5. 更新：更新线性规划问题，将新的线性规划问题转化为标准形式。

6. 转到步骤2，继续迭代求解新的线性规划问题，直到找到最优解。

通过不断割平面的过程，割平面法可以逐步逼近最优解。

由于每次迭代都添加了一个新的约束条件，所以割平面法可以保证每次迭代的解都更接近最优解。

割平面法在实际应用中有很多优点。

首先，它可以解决一般的线性规划问题，不需要对问题进行特殊的处理。

其次，割平面法可以适用于高维问题，具有较好的扩展性。

此外，割平面法还可以用于求解整数规划问题，通过将整数规划问题转化为线性规划问题，然后使用割平面法求解。

第５章整数规划（割平面法）求解整数规划问题：Max Z=3x1+2x22x1+3x2≤144x1+2x2≤18x1,x2≥0，且为整数解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。

从而有：Max Z=3x1+2x22x1+3x2+x3=142x1+x2+x4=9x1,x2≥0，且为整数利用单纯形法求解，得到最优单纯形表，见表1：表1最优解为：x1=13/4, x2=5/2, Z=59/4根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1)将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得：x2 - x4-2 =1/2-(1/2x3+1/2x4) (2)由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。

又因为x3,x4 0，所以必有：1/2-(1/2x3+1/2x4)<1由于(2)式右端必为整数，于是有：1/2-(1/2x3+1/2x4)≤0 (3)或x3+x4≥1 (4)这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有：2x1+2x2≤11 (5)从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E(3.5，2)成为可行域的一个极点。

图1在(3)式中加入松弛变量x5，得：-1/2x3-1/2x4+x5=-1/2 (6)将(6)式增添到问题的约束条件中，得到新的整数规划问题：Max Z=3x1+2x22x1+3x2+x3=142x1+x2+x4=9-1/2x3-1/2x4+x5=-1/2x i≥0，且为整数，i=1,2,…,5该问题的求解可以在表1中加入(6)式，然后运用对偶单纯形法求出最优解。

§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)的左边必为整数。

88 实用运筹学：案例、方法及应用 由于LP 1已得到整数解，所以该分枝停止继续计算。

而2116z z >=，原问题可能有比16更大的最优解，此时*1656z z z ==≤≤，但210/3x =不是整数解，故针对2x 对问题LP 2增加约束条件23x ≤，24x ≥，进行分枝得到LP 21和LP 22。

LP 22无可行解，故该枝剪掉。

而z (21)＞z (1)，故对问题LP 21进行分枝，得到问题LP 211和LP 212。

z (212)＜z (211)=17，故对LP 212分枝已无必要，剪掉改枝。

整数解z (212)＞z (1)，故该问题最优值为z *＞z (212)=17，最优解为 *T (2,3)X = 上述求解计算过程如图4-4所示。

图4-4 分支定界法图解 用分枝定界法比穷举法优越，因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小。

但若变量数目很大，其计算量也是相当可观的。

4.3.2 割平面法 整数规划的割平面法（Cutting Plane Algorithm ）是1958年由R.E .Gomory 提出的，更方便于纯整数规划问题的求解，其基础仍然是用解LP 的方法去解整数规划问题。

割平面法的基本思想是：在松弛问题中逐次增加一个新约束（即割平面），割掉原可行域的一部分（只含非整数解），使得切割后最终得到这样的可行域（不一定一次性得到），它的一个有整数坐标的顶点恰好是问题的最优解，如图4-5所示。

95第3章 整数规划 由此可见，整数规划的可行解是离散的、可数的点集，它是相应的松弛问题的可行集的子集，整数规划对应的松弛问题的可行集是凸集，而整数规划的可行集不一定为凸集。

在目标函数求最大化（或最小化）时，整数规划的松弛问题的最优解对应的目标函数值要大于（或小于）该整数规划的最优解对应的目标函数值，即整数规划的最优解不优于相应的线性规划问题的最优解。

下面两节分别讨论求解整数规划的割平面方法和分支定界方法。

§3.2 割平面方法3.2.1 割平面法的基本思想解整数线性规划问题的割平面法有多种类型，但它们的基本思想是来自Gomory 割平面算法，它在理论上是重要的。

考虑纯整数线性规划问题：1112,,max ,1,2,,s.t.0,1,2,,,n j jj n ij j i j j n z cx a x b i mx j n x x x ==⎧⎪⎪⎪⎨⎪⎪⎪⎩=∑===∑"""≥全部为整数 （3.2.1）其中不妨假设ij a ，1,2,,1,2,,i m j n ==""；，均为整数，否则在等式约束条件中乘上相应的倍数，使其转化为整数。

若式（3.2.1）中不考虑决策变量的整数条件，则称这样的规划问题为纯整数线性规划的松弛问题（记为P 0）。

割平面法求解纯整数线性规划的基本思想是：用单纯形法求解其松弛问题（P 0），若松弛问题（P 0）的最优解均为整数解，则该最优解即为原纯整数线性规划问题（P ）的最优解，此时计算结束；若松弛问题（P 0）的最优解不全是整数解，则可以考虑对松弛问题（P 0）增加一个线性约束条件，该条件称为割平面条件。

新增加的这个割平面条件要求将松弛问题（P 0）的可行区域“切掉”一块，且这个不满足整数解要求的最优解恰在被“切掉”的区域内，而原纯整数线性规划问题（P ）的任何一个可行解都不能被“切掉”。

此时把增添了割平面条件的问题记为P 1，可将P 1视为原纯整数线性规划问题（P ）的一个改进的松弛问题，用对偶单纯形法求解LP 问题P 1。

割平面法的解题步骤补充说明1. 引言1.1 概述:本文将介绍割平面法的解题步骤。

割平面法是一种常用的解决几何、优化和约束问题的数学工具。

通过确定割平面方程、求解割线与图形交点坐标以及确定割线与图形交点个数及位置关系，可以有效地求解各种复杂问题。

1.2 文章结构:本文主要分为四个部分：引言、割平面法的解题步骤、实例分析和结论。

在引言中，将简要介绍本文主题并提供一个概览。

然后，在割平面法的解题步骤部分，我们将详细讨论该方法的具体步骤。

接着，在实例分析部分，我们将通过三个不同领域的实例来展示割平面法在实际问题中的应用。

最后，在结论中，我们将总结该方法的优势和局限性，并对未来研究进行展望。

1.3 目的:本文旨在帮助读者了解割平面法并掌握其解题步骤。

通过阅读本文，读者将了解如何使用割平面法来解决各种几何、优化和约束问题，并对该方法在未来研究中的潜力和局限性有更深入的了解。

2. 割平面法的解题步骤：2.1 理解割平面法:割平面法是一种通过不断添加割平面（即直线或超平面）来逼近解集的方法。

它常用于几何问题中，以及某些最优化问题和约束条件下的求解过程中。

该方法通过将多个割线与待求图形进行交点计算，进而获得关于交点位置和数量的信息。

2.2 准备工作:在使用割平面法之前，我们需要先明确待求图形的性质和要求。

具体而言，在开始解题之前，我们应该详细了解如下内容：- 待求图形的类型和特征：对于几何问题，需要明确图形的类型（例如圆、矩形等）以及边界条件或限制。

- 目标函数或约束函数：对于最优化问题和带有约束条件的问题，需要定义目标函数和约束函数，并了解这些函数与待求图形之间的关系。

- 约束条件：如果存在限制条件，则需要明确这些约束对应的方程式或不等式。

2.3 步骤一：确定割平面方程:通过观察待求图形及其特征，并结合已知信息，我们可以推导出一条直线或超平面的方程。

这个割线将帮助我们定位图形的交点，从而逐步逼近解集。

为了确定割平面方程，我们可以采取不同的方法。

§3.2Gomory割平⾯法§3.2 G o m o r y 割平⾯法1、G o m o r y 割平⾯法的基本思想≥=为整数向量x x bAx t s xc T 0..min （P ） ≥=0..min x b Ax t s x c T （P 0）称（P 0）为（P ）的松弛问题。

记（P ）和（P 0）的可⾏区域分别为D 和D 0 , 则（1）0D D ?；（2）若（P 0）⽆可⾏解，则（P ）⽆可⾏解；（3）（P 0）的最优值是（P ）的最优值的⼀个下界；（4）若（P 0）的最优解 0x 是整数向量，则 0x 是（P ）的最优解。

基本思想：（1）⽤单纯形法求解松弛问题（P 0），若（P 0）的最优解 0x 是整数向量，则 0x 是（P ）的最优解。

计算结束。

(2) 若（P 0）的最优解 0x 不是整数向量，则对松弛问题（P 0）增加⼀个线性约束条件（称它为割平⾯条件），新增加的约束条件将（P 0）的⾏区域D 0割掉⼀块，且这个⾮整数向量 0x 恰在被割掉的区域内，⽽原问题（P ）的任何⼀个可⾏解（格点）都没有被割去。

记增加了割平⾯的问题为（P 1），称（P 1）为（P 0）的改进的松弛问题。

（3）⽤对偶单纯形法求解（P 1），若（P 1）的最优解 1x 是整数向量，则 1x是（P ）的最优解。

计算结束。

否则转（2）割平⾯的⽣成：对给定的（P ），⽤单纯形法求解它的松弛问题（P 0），得到（P 0）的最优基本可⾏解 0x ，设它对应的基为 ),,(1m B B A A B Λ=， m B B x x ,,1Λ为 0x 的基变量，记基变量的下标集合为 S ，⾮基变量的下标集合为 S 。

则松弛问题（P 0）的最优单纯形表为∑∈=+Sj j j z x z 0ξm i b x a x Sj i j ij B i ,,1,Λ==+∑∈（3.2.1）为了使符号简便，令000,,0z b a z x j j B ===ξ。

割平面法在纯整数规划中的应用1、摘要：割平面法是整数规划问题中常用的一种重要方法。

割平面法解整数规划问题的基本思路是：首先根据单纯形法，画出单纯形表格,利用迭代法求出不考虑整数约束条件时的松弛问题的最优解，如果得到的解是整数则即为问题的整数解，运算停止。

但是在大多数情况下得到的解不完全是整数，其中会出现非整数的形式，也就是这个松弛问题的最优解中存在某个或者某几个基变量为非整数的形式，这就需要进一步的运算：从最优表格中提取出关于非整数基变量的约束等式，再从这个约束等式出发构造出一个割平面方程添加到原来的约束条件中去，再进行单纯形表格的迭代运算，求出最优解，如果得到的最优解是整数则即为所要求的问题的最优解，运算停止。

如果得到的解仍然不完全是整数，就需要继续进行运算，重复以上步骤，一直求解出满足条件的最优解则运算停止。

这就是割平面法的整数求解的一般步骤。

Cutting plane method which is used in an integer programming problem is a kind of important method. Cutting plane method solution in integer programming problem is the basic train of thought: first according to the simplex method, draw the simplex form, using iterative algorithm to find the integer constraint conditions do not consider the relaxation of the optimal solution of the problem, given the solution is for the problem that is the integer solutions, stop operations. But in most cases thesolution doesn't get completely integer, which could not be the integer form, also is the relaxation of the optimum solution of the existence of a or certain base the variable is not the integer form, this needs further operation: the optimal form from the extract about the base variables the constraint equation integer variables, and again from the constraint equation is constructed on a cutting plane equation added to the original conditions to, and then to simplex form iterative operation, to work out the optimal solution, if we get the optimal solution is required for the integer is the problem of optimal solution, stop operations. If the solution have still not quite integer, it needs to continue operations, repeat the above steps, has been worked out to meet the conditions of the optimal solution is to stop operations. This is cutting plane method of solving the integral general steps.1、整数规划的简要介绍整数规划是指在一类问题中要求其解的全部或者一部分变量为整数的数学规划。