割平面算法简介电子教案.doc

割平面算法简介精品资料割平面法在纯整数规划中的应用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 the solution doesnt 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、 整数规划的简要介绍整数规划是指在一类问题中要求其解的全部或者一部分变量为整数的数学规划。在一般的线性规划问题中，所求的最优解可能是整数也可能是分数或小数，但是对于某些特殊的具体问题而言，常常要求最优解必须是整数。例如，所求解是工人的人数，货车的车数，机器的台数，送货的次数等等。为了满足所求解是整数的要求，初看起来好像只要把所求的非整数解用凑整数法、四舍五入法或去尾法化为整数就可以了，但是实际上化为整数后的解不一定是可行解和最优解，因此这类问题需要有特殊的方法来求得整数最优解。从广泛的意义上来说，整数规划与组合优化二者的领域是一致的，它们都是在有限个可供选择的方案中，寻求满足一系列条件的最好方案。组合优化是一系列离散问题的总和，它包含了各式各样的问题，它的许多典型问题也都反映出了整数规划的广泛背景，最常见的有背包问题、探险队问题、装箱问题、送货问题等等很多。因此，整数规划的应用范围极其广泛，不仅在工业、程序设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析方面等也有很多新的应用。整数规划的发展史可以追溯到20世纪50年代，Dantzig，运筹学的创始人和线性规划单纯形算法的发明者，首先发现可以用0-1变量来刻画最优化模型中的固定费用、变量上界、非凸分片线性函数等。他和Fulkersn以及Johnson对旅行售货员问题的研究成为后来的分枝割方法以及现代的混合整数规划法的开端。在1958年，R.E.Gomory发现了第一个一般性的线性整数规划的收敛算法割平面方法。经过50多年的发展，也发展出了很多种方法解决此类问题，目前受大家广泛认可的包括分枝界定法、割平面方法、匈牙利法以及枚举法等。他们的最典型做法是逐步生成一个相关问题，称为源问题的衍生问题，对每一个衍生问题伴随一个与它相比更加容易求解的松弛问题。通过对松弛问题求的解来确定这个源问题是应该被舍弃还是应该再生成一个或者多个它本身的衍生问题来代替原来的衍生问题。随后，再选择一个还没有被舍弃的或者还没有被替代的原问题的衍生问题，重复以上步骤直到不再有未被解决的衍生问题为止。分枝界定法和割平面方法都是在以上框架下形成的。整数线性规划一般分为纯整数线性规划、混合整数线性规划和0-1型整数线性规划。纯整数线性规划要求所有的变量全部都为整数；混合整数线性规划仅要求变量的一部分为整数；0-1型整数线性规划是一种特殊情况，要求其变量仅为0或1。它在整数规划中占有重要位置，一方面许多的实际问题例如指派问题、选址问题、送货问题等都可以归结为这一类的规划，另一方面任何的有界变量整数规划问题都可以与0-1型整数线性规划等价。2、 割平面法介绍1958年，美国著名学者R.E.Gomory提出了求解整数线性规划时的一种比较简单的方法割平面法。它的基本思想和分枝界定法基本上一致，首先不考虑变量的整数约束，利用单纯形法求解出线性规划的最优解，如果得到的解是整数那么这个最优解就是原来问题的最优解，如果最优解不是整数解，则就用一张平面将原来的含有最优解的非整数点但不包含整数可行解的点的那一部分可行域切割掉，也就是在原来的整数线性规划的基础上增加适当的线性约束不等式，这个约束不等式就叫切割不等式当其取等号时就是割平面了。此后，继续解这个新得到的整数线性规划，如果得到的新最优解是整数，运算就停止，如果不是整数则继续增加适当的线性约束不等式，直到求出的解满足最优整数要求为止。总的来说就是通过构造一系列平面切割掉不含有任何整数可行解的区域，最后得到一个包含有整数可行解的整数坐标顶点的可行域，此顶点正好是原整数线性规划的最优解，而这种方法的关键是，如何构造出切割不等式使得增加新的线性约束条件后能够达到真正的切割掉非整数点而又不会切割掉任何可行的整数点。3、 割平面法求解的一般步骤设某整数规划问题的标准型为： 对上述模型的求解过程如下：（1） 首先用单纯形法的表格方法求解不考虑整数约束条件时的松弛问题。（2） 若求得的松弛问题无可行解或者所得解就是整数最优解，则运算停止；无可行解时表示原问题也没有可行解，得到整数最优解则即为所求的整数约束条件下的最优整数解。如果存在一个或者多个变量的取值不满足整数约束条件，那么选择其中一个非整数变量建立割平面，然后进入下一步。（3） 在原来的最优单纯形表中增加割平面的新的约束条件，利用对偶单纯形法重新求解，然后返回第二步。下面介绍具体的构造割平面的过程：设表1是不考虑整数约束条件时对应的松弛问题的最优解构成的单纯形表 表1 其中（）表示基变量，（）表示非基变量，若设表示基变量中一个非整数值的变量即为非整数值，则根据表1可得 将上式中的变量系数以及变量值（）分解为整数N和非负分数f两部分相加的形式，即 其中为的取整部分，为的非负真分数部分，为的取整部分，为的非负真分数部分;并且满足以下不等式： 则（1）式可以改写为 移项得： 为了满足所有的变量均是整数的条件，（2）式的右边必然是整数，则（2）式作为等式左边也必然为整数，又因为和都是非负真分数且都是小于1的，则应有 （3） 式继续添加松弛变量变为： 将（4）式作为新的约束条件加入到表1中，利用对偶单纯形法继续求解，重复以上过程，一直到所求的最优解全部都为整数为止。5、割平面法代数求解实例例1 求解下列纯整数规划问题 其松弛问题为： 引入松弛变量并且改写为标准型： 构造原始单纯形表如下： 表2 按照一般线性规划得最优单纯形表为： 表3 由表3可得： 都不是整数解，则需要引入新的约束条件，不妨选择所对应的非整数解的约束方程来作为切割方程，那么可以得到: 将上式所有变量的系数和等式右端常数改写为一个整数与一个非负真分数相加的形式为：移项得：则有：即：在（5）式中添加新的松弛变量，化为： 把（6）式作为新的线性约束条件加入到表3得到表4 利用对偶单纯形法对表4进行求解，可得表5 则其解为：仍然不是整数，继续构造新的切割方程，选取对应的约束方程作为新的约束条件： 同理，将上式所有变量的系数和等式右端常数改写为一个整数与一个非负真分数相加的形式： 移项后调整得进一步可得约束方程为:增加新的松弛变量得约束等式：将上述约束等式增加到表5得到表6 再对上表利用对偶单纯形法解，得到这就是上述问题的整数最优解。6、割平面法的前景展望从以上的整数线性规划的割平面法中，我们可以看到割平面的过程非常慢，每次只能割去一点点，接近整数凸包的割平面每次只能割去距离凸包边缘很远的一些非整数点。另外割平面法对实际问题的结构以及解的结果都要有较高的要求，因为它要区分纯整数线性规划和混合整数线性规划，对于这两种不同类型需要有不同的切割方法。而且割平面法在增加割平面以后要改变原来的方法即变为对偶单纯形法求解。在具体实际问题中，割平面不仅表现出极低的收敛率而且在割平面运行的过程中往往会产生许多的割平面，内存占用非常大，因此在实际问题中单纯的割平面法往往不会产生期望的效果，所以常常会选择分枝界定法和割平面法混合使用的方法。现在有许多人也都致力于这两方面结合使用的研究方法，有些也取得了很不错的效果，所以这方面有待进一步的研究。仅供学习与交流，如有侵权请联系网站删除 谢谢12