线性规划问题的求解.doc

线性规划问题的求解在数学中，线性规划 (Linear Programming，简称LP) 问题是目标函数和约束条件都是线性的最优化问题。线性规划是最优化问题中的重要领域之一。很多运筹学中的实际问题都可以用线性规划来表述。线性规划的某些特殊情况，例如网络流、多商品流量等问题，都被认为非常重要，并有大量对其算法的专门研究。很多其他种类的最优化问题算法都可以分拆成线性规划子问题，然后求得解。在历史上，由线性规划引申出的很多概念，启发了最优化理论的核心概念，诸如“对偶”、“分解”、“凸性”的重要性及其一般化等。我们在以前的学习过程中曾经接触过最简单的线性规划平面规划，但由于其是在平面上求解，形式较为简单，通过作图和平移目标函数即可得到最优解。但是通过对平面规划的类比，我们可以得出求解线性规划问题的一般方法单纯形法。几何上，线性约束条件的集合相当于一个凸包或凸集，叫做可行域。因为目标函数亦是线性的，所以其极值点会自动成为最值点。线性目标函数亦暗示其最优解只会出现在其可行域的边界点中。在两种情况下线性规划问题没有最优解。其中一种是在约束条件相互矛盾的情况下（例如 x 2 和 x 1），其可行域将会变成空集，问题没有解，因此亦没有最优解。在这种情况下，该线性规划问题会被称之为“不可行”。另一种情况是，约束条件的多面体可以在目标函数的方向无界（例如： max z=x1 + 3 x2 s.t. x1 0, x2 0, x1 + x2 10），目标函数可以取得任意大的数值，所以没有最优解。除了以上两种病态的情况以外（问题通常都会受到资源的限制，如上面的例子），最优解永远都能够在多面体的顶点中取得。但最优解未必是唯一的：有可能出现一组最优解，覆盖多面体的一条边、一个面、甚至是整个多面体（最后一种情况会在目标函数只能等于0的情况下出现）。 在使用单纯形法求解线性规划问题之前，我们首先需要了解什么是标准型，这是线性规划问题中最常用也最直观的形式。 标准型包括以下三个部分： 一个需要极大化的线性函数，例如: 以下形式的问题约束，例如: 和非负变量， 例如:在求解线性规划问题时，我们首先根据题中给出的条件列出目标函数以及约束条件，若不是标准形式则要将其化为标准形式，具体方法便是再次引入非负变量，例如若上式中的约束条件变为小于，则需加上非负变量x3,使其转变为标准型，才可继续解线性规划问题。将目标函数及约束条件均化为标准型后，我们就可以利用单纯形法求解线性规划问题了。单纯形法利用多面体的顶点构造一个可能的解，然后沿着多面体的边走到目标函数值更高的另一个顶点，直至到达最优解为止。虽然这个算法在实际上很有效率，在小心处理可能出现的“循环”的情况下，可以保证找到最优解。在用单纯形法求解线性规划问题之前，必须先把线性规划问题转换成增广矩阵形式。增广矩阵形式引入非负松弛变量将不等式约束变成等式约束。问题就可以写成以下形式： Maximize Z in:这里 xs 是新引入的松弛变量, Z 需要极大化的变量。但在使用单纯形法求解线性规划问题时一定要注意求解的顺序，往往要有一定的观察能力和分析能力才能得到最优的解题过程，往往能事半功倍，且不易出错。如果按照凸多边形的各个顶点来求最优解，变量、约束条件越多，凸多边形的顶点也越多，那么求解线性规划问题所需的时间也就越多，可能还会频频出错，所以在使用单纯形法时要注意使用正确的方法，如果约束条件太多还可以使用单纯形表，这样看上去更为简洁，也避免了出错。在工程中应用的最多是线性规划中的整数规划，因为在线性规划求解出的最优解往往是小数，但是工程中的问题大多是整数问题，小数便没有意义了。但这并不意味着线性规划问题便没有了用武之地，在线性规划基础上使用割平面法便可以求解整数规划问题。根据对所有变量的要求不同，整数线性规划又分为下列几种类型：（1） 纯整数线性规划（Pure Integer Linear Programming）：指全部决策变量都必须取整数值的整数线性规划。有时也称为全整数规划。（2） 混合整数规划（Mixed Integer Linear Programming）：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。（3） 0-1型整数规划（Zero-one Integer Linear Programming）：指决策变量只能取值0或1的整数线性规划。整数规划的割平面法是Gomory在1958年提出来的，所以又称为Gomory割平面法。该法的基本思想是在非整数解的松弛问题中逐次增加一个新约束（即割平面），它能割去原松弛问题可行域中一块不含有整数解的区域。逐次切割下去，直到切割最终所得松弛可行域的一个最优顶点（即整数解）为止。割平面法较为复杂，其在个割平面过程中并没有减少整数解的数目，但