下载文档原格式
割平面法Gommoy算法步骤：① 求解原整数规划对应的线性规划 min f （x ）=cx ， .⎩⎨⎧≥≤为整数xi x b A t s x .0.，设最优解为x*。
② 如果最优解的分量均为整数,则x ＊为原整数规划的最优解:否则任选一个x ＊中不是整数的分量,设其对应的基变量为x p ，, 定义包含这个基变量的切割约束方程∑=+jcom j ij b x r p x ，其中x j 为非基变量。
③ 令][b b b ],[r com com com ij ij ij r r -=-=,其中［]为高斯函数符号,表示不大于某数的最大整数. 将切割约束方程变换为∑∑-=-+jj ij j j ijp x r x r x com com b ][b ][,由于10,1r 0<≤<≤com ij b ,所以有∑-j ij com x r b 〈1,因为自变量为整数，则∑-j ij com x r b 也为整数,所以进一步有∑-j ij com x r b 〈=0.④ 将切割方程加入约束方程中,用对偶单纯算法求解线性规划⎪⎪⎩⎪⎪⎨⎧≥≤-≤=∑00b b Ax .,)(min com x x r t s cx x f j j ij ，转 。
算法MATLAB 实现代码：function ［intx ，intf ］=Gomory(A,c ，b ，base ）%约束矩阵:A ；%目标函数系数向量：c％约束右端向量:b%初始基向量base%目标函数取最小化时的自变量值:x％目标函数的最小值：minfsz=size（A）;nVia=sz(2）;n=sz（1)；xx=1:nVia；if length(base）~=ndisp(’基变量的个数要与约束矩阵的行数相等!');mx=NaN;mf=NaN;return;endM=0；sigma=—［transpose（c） zeros（1，（nVia—length（c）))]；xb=b;while 1［maxs,ind]=max(sigma）;if maxs〈=0vr=find(c~=0，1，’last')；for l=1:vrele=find（base==l,1)；if（isempty（ele))mx（l）=0;elsemx(l）=xb(ele)；endendif max(abs(round(mx）—mx））<1.0e—7intx=mx;intf=mx＊c；return；elsesz=size（A);sr=sz（1）;sc=sz（2）；［max_x,index_x］=max（ads（round（mx)—mx)）； [isB,num]=find(index_x==base）；fi=xb（num）-floor（xb（num)）；for i=1：(index_x—1）Atmp（1,i)=A(num，i)-floor（A(num，i)）；endfor i=（infex_x+1):scAtmp（1，i)=A（num，i)-floor（A(num,i）);end%构建对单纯形法的初始表格Atmp（1,index_x)=0;A=［A zeros(sr,1）;-Atmp(1，:） 1]；xb=［xb;-fi]；base=［base sc+1］；sigma=［sigma 0］;％对偶单纯形法迭代过程while 1if(xb)>=0if max（abs（round(xb）—xb）)<1。
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，继续迭代求解新的线性规划问题，直到找到最优解。
通过不断割平面的过程，割平面法可以逐步逼近最优解。
由于每次迭代都添加了一个新的约束条件，所以割平面法可以保证每次迭代的解都更接近最优解。
割平面法在实际应用中有很多优点。
首先，它可以解决一般的线性规划问题，不需要对问题进行特殊的处理。
其次，割平面法可以适用于高维问题，具有较好的扩展性。
此外，割平面法还可以用于求解整数规划问题，通过将整数规划问题转化为线性规划问题，然后使用割平面法求解。
分支定界法和割平面法在上学期课程中学习的线性规划问题中，有些最优解可能是分数或消失，但现实中某些具体的问题，常要求最优解必须是整数，这样就有了对于整数规划的研究。
整数规划有以下几种分类：（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 求解下述整数规划 219040Maxx x z +=⎪⎩⎪⎨⎧≥≥+≤+且为整数0,702075679212121x x x x x x解 （1）先不考虑整数限制，即解相应的线性规划B ，得最优解为：124.81, 1.82,356x x z ===可见它不符合整数条件。
§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)的左边必为整数。
割平面算法
割平面算法是一种计算几何的算法，主要用于求解多边形的内部或外部区域。
该算法的基本思想是通过构造一些直线（称为割平面）将多边形划分成一些简单的区域（称为小区域），然后根据小区域的情况确定多边形的内部或外部区域。
具体而言，该算法的步骤如下：首先确定一个多边形和一些割平面，然后将多边形和割平面进行求交，得到一些线段和点。
接着，根据这些线段和点将多边形划分成一些小区域，再根据每个小区域的情况判断其是否在多边形的内部或外部。
最后将所有在多边形内部的小区域合并在一起，就得到了多边形的内部区域。
割平面算法的优点是可以处理一些复杂的多边形，而且算法复杂度比较低。
不过该算法也存在一些缺点，比如对于一些具有孔洞的多边形，需要额外的处理，并且对于一些不规则的多边形，该算法的结果可能不准确。
- 1 -。
§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)的左边必为整数。
