第二节 Gomory割平面法

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切割法的步骤如下：
1. 对于原问题中的每个不等式约束，将其转化为一个或多个等式约束，并将这些约束作为新引入的决策变量。

2. 对于每个新引入的决策变量，计算其取值对原问题目标函数的影响，并将这些影响转化为约束条件。

3. 对于每个新引入的决策变量，计算其取值对原问题约束条件的影响，并将这些影响转化为新的约束条件。

4. 重复步骤1-3，直到所有不等式约束都被转化为等式约束，或者无法再继续引入新的决策变量为止。

5. 将所有新引入的决策变量和对应的约束条件组合成一个纯等式约束的优化问题，并求解该问题得到最优解。

需要注意的是，Gomory切割法是一种基于树形结构的方法，因此在实际应用中需要对树形结构进行处理，如剪枝、合并等，以提高求解效率。

此外，Gomory切割法适用于求解线性规划问题，对于非线性规划问题，需要采用其他的优化方法。

gomory割平面法一、概述Gomory割平面法是一种用于解决整数规划问题的算法。

它的基本思想是将线性规划问题转化为整数规划问题，通过不断添加割平面来逐步逼近整数解。

二、线性规划与整数规划1. 线性规划线性规划（Linear Programming，LP）是指目标函数和约束条件均为线性函数的最优化问题。

它可以表示为：$$ \begin{aligned} &\max_{x} c^T x \\ &s.t. \quad Ax \leq b, x \geq 0 \end{aligned} $$其中，$c$、$x$、$b$均为向量，$A$为矩阵。

2. 整数规划整数规划（Integer Programming，IP）是指在线性规划的基础上，要求$x$取值必须为整数的最优化问题。

它可以表示为：$$ \begin{aligned} &\max_{x} c^T x \\ &s.t. \quad Ax \leq b, x\in Z^n_+ \end{aligned} $$其中，$Z^n_+$表示$n$维非负整数集合。

三、Gomory割平面法的基本思想1. 割平面法概述割平面法是一种用于求解整数规划问题的算法。

它的基本思想是通过添加割平面来逐步逼近整数解。

割平面法的核心是确定割平面的方法。

2. Gomory割平面法Gomory割平面法是一种经典的割平面法，由Ralph Gomory于1958年提出。

其基本思想是通过将松弛线性规划问题转化为整数规划问题，并不断添加新的约束条件（即割平面），来逼近整数解。

Gomory割平面法的具体步骤如下：（1）将线性规划问题转化为松弛线性规划问题，即将$x$取值限制为非负整数变量改为非负实数变量，得到如下形式：$$ \begin{aligned} &\max_{x} c^T x \\ &s.t. \quad Ax \leq b, x \geq 0 \end{aligned} $$（2）求解松弛线性规划问题，得到最优解$x^*$。

gomory割平面法gomory割平面法是一种在线性规划中常用的方法，旨在通过添加割平面约束来逐步逼近最优解。

它是由美国数学家Ralph E. Gomory于1958年提出的，被广泛应用于解决线性规划问题。

1. 背景介绍线性规划是一种在数学和运筹学中广泛应用的优化问题，旨在寻找最大化或最小化一组线性约束条件下的目标函数值。

它具有广泛的应用领域，如生产规划、资源分配、运输问题等。

2. 基本原理gomory割平面法的基本原理是通过添加新的割平面约束来逼近整数约束条件下的最优解。

该方法基于单纯形法，通过检测当前解中的分数解，确定需要添加的割平面约束，并将其添加到线性规划模型中。

3. 算法步骤gomory割平面法的具体步骤如下：步骤1: 初始化线性规划问题，求解得到初始解。

步骤2: 检测解中是否存在分数解，即解中某些变量取非整数值。

步骤3: 如果解中存在分数解，根据当前解计算一个新的割平面约束，并将其添加到线性规划模型中。

步骤4: 使用单纯形法求解新的线性规划问题，得到新的解。

步骤5: 重复步骤2至步骤4，直到最优解满足整数约束条件。

4. 优点和局限性gomory割平面法在解决整数线性规划问题方面具有以下优点：- 通过添加割平面约束逐步逼近整数线性规划问题的最优解。

- 可以有效减少搜索空间，提高计算效率。

- 可以用于处理具有大规模约束条件和变量的问题。

然而，gomory割平面法也有其局限性：- 该方法在处理具有较大维度的问题时计算复杂度较高。

- 在某些情况下，该方法可能需要添加大量的割平面约束才能达到最优解。

- 对于某些特殊问题，该方法可能无法找到最优解。

5. 总结与回顾gomory割平面法是一种常用的用于解决整数线性规划问题的方法。

它通过添加割平面约束逐步逼近最优解，并具有一定的计算效率和准确性。

然而，在实际应用中需要根据具体问题评估其适用性，并结合其他方法进行求解。

在本文中，我们对gomory割平面法的基本原理进行了介绍，并给出了其算法步骤。