下载文档原格式
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把所有系数分解成整数和非负真分数之和。
§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)的左边必为整数。
割平面法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.0e-7%用对偶单纯形法求得了整数解vr=find(c~=0 ,1,'last');for l=1:vrele =find (base==l,1);if(isempty(ele))mx_1(l)=0;elsemx_1(l)=xb(ele);endendintx=mx_1;intf=mx_1*c;return;elsesz=size(A);sr=sz(1);sc=sz(2);[max_x,index_x]=max(abs(round(mx_1)-mx_1)); [isB,num]=find(index_x==base);fi=xb(num)-flooor(xb (num));for i=1:(index_x-1)Atmp(1,i)=a(num,i)-floor(A(num,i));endfor i=(index_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];continue;end%对偶单纯形法的换基变量过程elseminb_1=inf;chagB_1=inf;sA=size(A);[br,idb]=min(xb);for j=1:sA(2)if A(idb,j)<0bm=sigma(j)/A(idb,j);if bm<minb_1minb_1=bm;chagB_1=j;endendendsigma=sigma-A(idb,:)*minb_1;xb(idb)=xb(idb)/A(idb,chagB_1);A(idb,:)=A(idb,:)/A(idb,chagB_1);for i=1:sA(1)if i ~=idbxb(i)=xb(i)-A(i,chagB_1)*xb(idb);A(i,:)=A(i,:)-A(i,chagB_1)*A(idb,:);endendbase=chagB_1;endendendelseminb=inf;chagB=inf;for j=1:nif A(j,ind)>0bz=xb(j)/A(j,ind);if bz <minbminb=bz;chagB=j;endendendsigma=sigma-A(chagB,:)*maxs/A(chagB,ind);xb(chagB)=xb(chagB)/A(chagB,ind);A(chagB,:)=A(chagB,:)/A(chagB,ind); for i=1:nif i~=chagBxb(i)=xb(i)-A(i,ind)*xb(chagB); A(i,:)=A(i,:)-A(i,ind)*A(chagB,:); endendbase(chagB)=ind;endM=M+1;if (M==1000000)disp('找不到最优解!');mx=NaN;minf=NaN;return ;endend算法举例⎪⎩⎪⎨⎧≥≤+≤+--=为整数且2121212121,,0,4222.,)(inf m x x x x x x x x t s x x x解:首先引入人工变量x3,x4,将约束条件化为等式形式⎪⎩⎪⎨⎧≥=++=++--=为整数且21432142132121,,0,,,422x 2.,)(inf m x x x x x x x x x x x t s x x x在MATLAB 命令行输入下列命令:>>A=[-1 2 1 0 ;2 1 0 1];C=[1;-1];B=[2;4];>>[intx,intf]=Gomory(A,c,b,[3 4])结果为:intx= 0 1Intf= -1。
gomory割平面法原理及应用标题：Gomory割平面法：原理及应用引言：在运筹学领域，Gomory割平面法是一种强大的整数规划求解方法，它通过引入一系列割平面来逐步逼近最优解。
本文将深入探讨Gomory割平面法的原理和应用，解释其工作原理以及在实际问题中的应用场景。
对于理解和应用这一方法，本文将从简到繁、由浅入深地进行解释。
一、Gomory割平面法原理1.1 整数规划问题简介在介绍Gomory割平面法之前，我们首先了解整数规划问题。
整数规划是线性规划的一种扩展形式，其中变量被限制为取整数值。
我们将探讨整数规划问题的基本概念、约束条件以及目标函数。
1.2 割平面的引入割平面是指在整数规划问题中，通过添加一系列附加约束来限制解的空间。
这些约束通常是线性的，并且通过改进松弛线性规划问题的解来逼近整数解。
1.3 Gomory割平面法的基本思想Gomory割平面法通过将松弛线性规划问题求解为一个整数规划问题，然后应用割平面的思想逐步逼近最优整数解。
本节将详细介绍Gomory割平面法的基本思想和具体步骤。
二、Gomory割平面法应用案例在本节中，我们将通过一个实际案例来展示Gomory割平面法的应用。
假设我们有一个生产计划问题，需要确定如何分配资源以最大化利润并满足资源的限制条件。
我们将逐步应用Gomory割平面法来解决这个问题，并解释每一步的具体操作。
三、Gomory割平面法的优缺点在实际应用中，我们需要综合考虑Gomory割平面法的优点和局限性。
本节将讨论Gomory割平面法的优缺点，并帮助读者在实践中做出合理的选择。
四、总结与回顾通过本文的学习，我们了解了Gomory割平面法的原理和应用。
这种方法通过引入割平面，可以逐步逼近整数规划问题的最优解。
我们探讨了Gomory割平面法的基本思想、具体步骤以及应用案例，希望读者能够对该方法有更深入、全面的理解和应用。
观点和理解：Gomory割平面法作为整数规划领域中的重要方法，具有以下观点和理解：1. Gomory割平面法通过引入割平面，可以在保证最优解的情况下进一步限制解的空间，提高整数规划问题的求解效率。
Gomory切割法是一种求解最优化问题的数学方法，常用于求解线性规划问题。
该方法通过不断引入新的决策变量来消除不等式约束，最终得到一个纯等式约束的优化问题，然后通过求解该问题得到最优解。
Gomory切割法的基本思想是将原问题转化为一个等价的纯等式约束问题，从而简化求解过程。
具体来说，Gomory切割法的步骤如下：
1. 对于原问题中的每个不等式约束，将其转化为一个或多个等式约束，并将这些约束作为新引入的决策变量。
2. 对于每个新引入的决策变量，计算其取值对原问题目标函数的影响，并将这些影响转化为约束条件。
3. 对于每个新引入的决策变量，计算其取值对原问题约束条件的影响，并将这些影响转化为新的约束条件。
4. 重复步骤1-3，直到所有不等式约束都被转化为等式约束，或者无法再继续引入新的决策变量为止。
5. 将所有新引入的决策变量和对应的约束条件组合成一个纯等式约束的优化问题，并求解该问题得到最优解。
需要注意的是，Gomory切割法是一种基于树形结构的方法，因此在实际应用中需要对树形结构进行处理，如剪枝、合并等，以提高求解效率。
此外，Gomory切割法适用于求解线性规划问题，对于非线性规划问题，需要采用其他的优化方法。
§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 ===ξ。
如果m i b i ,,1,0,Λ= 全是整数，则 0x 是（P ）的最优解。
计算结束。
否则至少有一个 l b 不是整数)0(m l ≤≤，设 l b 所对应的约束方程为,∑∈=+Sj l j lj B b x a x l （3.2.2）用 ][a 表示不超过实数 a 的最大整数，则,][,,][l l l lj lj lj f b b S j f a a +=∈+= （3.2.3）其中，lj f 是 lj a 的分数部分，有 S j f lj ∈<≤,10， l f 是 l b 的分数部分，有 .10<≤l f由于在（3.2.2）中的变量是非负的，因此有∑∑∈∈≤Sj j ljSj jljxa x a ][ （3.2.4）所以由（3.2.2）得,][∑∈≤+Sj l j lj B b x a x l （3.2.5）因为在ILP 中 x 限制为整数向量，故（3.2.5）的左端为整数，所以右端用 l b 的整数部分去代替后，（3.2.5）式的不等式关系仍成立，即],[][∑∈≤+Sj l j lj B b x a x l （3.2.6）用（3.2.2） 减（3.2.6）得]),[(])[(∑∈-≥-Sj l l j lj ljb b x a a（3.2.7）由（3.2.2），可得线性约束,∑∈≥Sj l j ljf x f（3.2.8）称它为对应于生成行 l 的 Gomory 割平面条件。
为了将（3.2.8）加到松弛问题（P 0）的最优单纯形表，应将它变为等式，所以引入一个剩余变量 s ，从而 （3.2.8）变为,∑∈=-S j l j ljf s x f在两端同乘以 （-1），得,∑∈-=+-Sj l j lj f s x f （3.2.9）（3.2.9）是一个超平面，称它为割平面。
把割平面（3.2.9）加到松弛问题（P 0）的最优单纯形表的最后一行，可得改进的松弛问题（P 1）的单纯形表∑∈=+Sj j j z x z 0ξm i b x a x Sj i jij B i ,,1,Λ==+∑∈,∑∈-=+-Sj l j lj f s x f（P 1）的变量个数为 1+n ，等式约束为 1+m ，它的基变量个数为 1+m 。
显然，s x x m B B ,,,1Λ是（P 1）的基变量。
所以，对（P 1），获得了一个基本解，并且它的检验数向量 0)0,,,(1≤=T n ξξξΛ。
所以可用对偶单纯形方法求解改进的松弛问题（P 1）。
定理 3.2.1 如果把割平面（3.2.9）加到松弛问题（P 0）的最优单纯形表里，那么没有割掉原ILP 的任何整数可行点，当 l b 不是整数时，新表里是一个原始基本不可行解和对偶可行解。
证：ILP 的任何整数可行点都一定满足（3.2.2）和（3.2.6），所以满足（3.2.8）和（3.2.9），因此不会被割平面（3.2.9）割掉。
注：松弛问题（P 0）的非整数最优解 0x 被割平面（3.2.9）割掉了。
因为S j x b x j l B l∈==,0,0所以，,00∑∈<=Sj l j lj f x f所以 0x 不满足（3.2.8），即不满足（3.2.9）。
2、G o m o r y 割平面的计算步骤第1步 用单纯形法求解（P ）的松弛问题（P 0）。
若（P 0）没有最优解，则停止计算，（P ）也没有最优解； 若（P 0）的最优解 0x 是整数向量，则 0x 是（P ）的最优解。
计算结束。
否则，转第2步。
第2步 求割平面任选 0x 的一个非整数分量 )0(m l b l ≤≤，由 l b 所在的这一行,∑∈=+Sj l j lj B b x a x l得到Gomory 割平面条件 ,∑∈≥S j l j ljf x f再得到割平面,∑∈-=+-Sj l j lj f s x f （3.2.10）第3步 将割平面（3.2.10）加到第1步所得的最优单纯形表里，用对偶单纯形方法求解这个改进的松弛问题。
若其最优解是整数向量，则它是原问题（P ）的最优解，计算结束。
否则，将这个最优解重新记为 0x ，返回第2步。
例3.2.1 求解 ILP 问题⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+=整数,0,023623..max 2121212x x x x x x t s x z （3.2.11）解：先将（3.2.11）化为标准形式⎪⎪⎩⎪⎪⎨⎧≥=++-=++-=整数,0,,,023623..min 43214213212x x x x x x x x x x t s x z （P ）它对应的松弛问题（P 0）为⎪⎪⎩⎪⎪⎨⎧≥=++-=++-=0,,,023623..min 43214213212x x x x x x x x x x t s x z （P 0）显然，T x )0,6,0,0(=是（P 0）的初始解，其基变量是 3x 和4x 。
所以（P 0）的第一张单纯形表为1x 2x 3x 4xRHS z0 1 0 0 0 3x 3 2 1 0 6 4x-3211x 2x 3x4x RHS z3/2 0 0 -1/2 0 3x 61 -1 6 2x-3/2 11/2 0（3.2.13）所以，松弛问题（P 0）的最优解为 T x )0,0,23,1(0=，因0x 不是整数向量，所以生成割平面（第0行和第2行均可生成割平面）。
由第2行生成的割平面条件为21414143≥+x x相应的割平面为214141143-=+--s x x （3.2.16）把（3.2.16）加到松弛问题（P 0）的最优单纯形表（3.2.13）中，得到改进的松弛问题（P 1）的单纯形表用对偶单纯形算法求解1x 2x 3x 4x RHS z 0 0 -1/4 -1/4 -3/2 1x 1 0 1/6 -1/6 1 2x 0 1 1/4 1/4 3/2 1x 2x 3x 4x 1s RHS z 0 0 -1/4 -1/4 0 -3/2 1x 1 0 1/6 -1/6 0 1 2x 0 1 1/4 1/4 0 3/2 1s 0 0 -1/4 -1/4 1 -1/2 1x 2x 3x 4x 1s RHS z 0 0 -1/4 -1/4 0 -3/2 1x 1 0 1/6 -1/6 0 1 2x 0 1 1/4 1/4 0 3/2 1s 0 0 -1/4 -1/4 1 -1/2（3.2.17）所以，改进的松弛问题（P 1）的最优解为 T x )2,0,0,1,32(1=，由于0x 不是整数向量，所以生成割平面。
由第1行生成的割平面条件为32323214≥+s x相应的割平面为323232214-=+--s s x （3.2.18）把（3.2.18）加到改进的松弛问题（P 1）的最优单纯形表（3.2.17）中，得到新的松弛问题（P 2）的单纯形表用对偶单纯形算法求解1x 2x 3x4x 1s RHS z0 0 0 0 -1 -1 1x 1 0 0 -1/3 2/3 2/3 2x 0 1 0 0 1 1 3x11 -42 1x 2x 3x 4x 1s 2s RHS z 0 0 0 0 -1 0 -1 1x 1 0 0 -1/3 2/3 0 2/3 2x 0 1 0 0 1 0 1 3x 0 0 1 1 -4 0 2 2s 0 0 0 -2/3 -2/3 1 -2/3所以，松弛问题（P 2）的最优解为 T x )0,0,1,1,1,1(2=。
所以，原问题的最优解为 T x )1,1(*=。
注： 原问题（P ）的松驰问题（P 0）的可行区域是如图的三角形 OAB ∆区域，（P ）的可行区域是OAB ∆中的四个格点：（0，0），（1，0），（2，0），（1，1）。
割平面条件21414143≥+x x 等价为 12≤x割平面条件32323214≥+s x 等价为 12x x ≤1x 2x 3x 4x 1s 2sRHS z0 0 0 0 -1-1 1x 1 0 0 0 1 -1/2 1 2x 0 1 0 0 11 3x0 1 0 -5 3/2 1 2s 011 -3/21。
