线性规划概述

1、线性规划1.简介在数学中，线性规划(Linear Programming,简称LP)问题是目标函数和约 束条件都是线性的最优化问题。线性规划是最优化问题中的重要领域之一。很多运筹学中的实际问题都可以 用线性规划来表述。线性规划的某些特殊情况，例如网络流、多商品流量等问题， 都被认为非常重要，并有大量对其算法的专门研究。很多其他种类的最优化问题 算法都可以分拆成线性规划子问题，然后求得解。在历史上，由线性规划引申出 的很多概念，启发了最优化理论的核心概念，诸如“对偶”、“分解”、“凸性” 的重要性及其一般化等。同样的，在微观经济学和商业管理领域，线性规划被大 量应用于解决收入极大化或生产过程的成

2、本极小化之类的问题。乔治丹齐格被 认为是线性规划之父。10 30 50 70 W JIO L30 IS。2.标准型描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分: 一个需要极大化的线性函数，例如!国1 + C皿以下形式的问题约束，例如：血m +曲匝和非负变量，例如:1 00线性规划问题通常可以用矩阵形式表达成:maximize C Xsubject to Ax 上 I). * * 其他类型的问题，例如极小化问题，不同形式的约束问题，和有负变量的问题，都可以改写成其等价问题的标准型。3.例子以下是一个线性规划的例子。假设一个农夫有一块A平方千米的农地，打算种植小麦或大麦或是两

3、者依某一比例混合种植。该农夫只可以使用有限数量的肥料F和农药P，而单位面积的小麦和大麦都需要不同数量的肥料和农药，小麦以（七P表示，贝U小麦与大麦的种植面积问题可以表示为以下的线性规划问题:大麦以 电，P2）表示。设小麦和大麦的售出价格分别为S1和max（最大化利润-目标函数）（Ti+T2 APiii + 0这里xs是新引入的松弛变量，Z需要极大化的变量.5.例子以上例子的转换成增广矩阵:maximize subject to .厂| - .七 -: 一 iF1S += FPlTi +产魂+购=P这里.i七 是（非负）松弛变量.写成矩阵形式：z-1 -S1 & 0 0 0-Hl01110 0A

4、0 F10 1 0旬F0 Pl 耳 0 0 1X-4P_5_Maximize Z in:6.对偶每个线性规划问题，称为原问题，都可以变换为一个对偶问题。我们可将“原 问题”表达成矩阵形式：maximize C Xsubject to Ax 上 I）. * * 而相应的对偶问题就可以表达成以下矩阵形式：minimize V subject to这里用“y”来作为未知向量。7.理论几何上，线性约束条件的集合相当于一个凸包或凸集，叫做可行域。因为目 标函数亦是线性的，所以其极值点会自动成为最值点。线性目标函数亦暗示其最 优解只会出现在其可行域的边界点中。在两种情况下线性规划问题没有最优解。其中一种是

5、在约束条件相互矛盾的 情况下（例如x2和x W 1），其可行域将会变成空集，问题没有解，因 此亦没有最优解。在这种情况下，该线性规划问题会被称之为“不可行”。另一种情况是，约束条件的多面体可以在目标函数的方向无界（例如：max z=x + 3 x s.t. x0, x0, x + x10），目标函数可以取得任意121212大的数值，所以没有最优解。除了以上两种病态的情况以外（问题通常都会受到资源的限制，如上面的例 子），最优解永远都能够在多面体的顶点中取得。但最优解未必是唯一的：有可 能出现一组最优解，覆盖多面体的一条边、一个面、甚至是整个多面体（最后一 种情况会在目标函数只能等于0的情况下出

6、现）。两个变量的线性规划问题中，一组线性约束条件划定了对两个变量的解的可 行域。可解的问题会有一个简单多边形的可行域。单纯形算法利用多面体的顶点构造一个可能的解，然后沿着多面体的边走到 目标函数值更高的另一个顶点，直至到达最优解为止。虽然这个算法在实际上很 有效率，在小心处理可能出现的“循环”的情况下，可以保证找到最优解，但它 的最坏情况可以很坏：可以构筑一个线性规划问题，单纯形算法需要问题大小的 指数倍的运行时间才能将之解出。事实上，有一段时期内人们曾不能确定线性规 划问题是NP完全问题还是可以在多项式时间里解出的问题。第一个在最坏情况具有多项式时间复杂度的线性规划算法在1979年由前苏 联

7、数学家Leonid Khachiyan提出。这个算法建基于非线性规划中Naum Shor发 明的椭球法(ellip-soid method)，该法又是 Arkadi Nemirovski (2003 年冯 诺伊曼运筹学理论奖 得主)和D. Yudin的凸集最优化椭球法的一般化。理论上，“椭球法”在最恶劣的情况下所需要的计算量要比“单形法”增长 的缓慢，有希望用之解决超大型线性规划问题。但在实际应用上，Khachiyan的 算法令人失望：一般来说，单纯形算法比它更有效率。它的重要性在于鼓励了对 内点算法的研究。内点算法是针对单形法的“边界趋近”观念而改采“内部逼近” 的路线，相对于只沿着可行域的

8、边沿进行移动的单纯形算法，内点算法能够在可 行域内移动。1984年，贝尔实验室印度裔数学家卡马卡(Narendra Karmarkar)提出了投 影尺度法(又名Karmarkars algorithm)o这是第一个在理论上和实际上都表 现良好的算法：它的最坏情况仅为多项式时间，且在实际问题中它比单纯形算法 有显著的效率提升。自此之后，很多内点算法被提出来并进行分析。一个常见的内点算法为Mehrotra predictor-corrector method。尽管在理论上对它所知甚 少，在实际应用中它却表现出色。单形法沿着边界由一个顶点移动到“相邻”的顶点，内点算法每一步的移动 考量较周详，“跨过

9、可行解集合的内部”去逼近最佳解。当今的观点是：对于线 性规划的日常应用问题而言，如果算法的实现良好，基于单纯形法和内点法的算 法之间的效率没有太大差别，只有在超大型线性规划中，顶点几成天文数字，内 点法有机会领先单形法。线性规划的求解程式在各种各样的工业最优化问题里被广泛使用，例如运输 网络的流量的最优化问题，其中很多都可以不太困难地被转换成线性规划问题。有待解决的问题LP 一种强多项式时间(polynomial-time)算法吗？Does LP admit a strongly polynomial algorithm to find a strictly complementary sol

10、ution?Does LP admit a polynomial algorithm in the real number (unit cost) model of computation?解第一提。polynomial-time，多项式成长，指的是数学问题会呈现多项式 成长，随变量越多，限制越多，成长越快。当然越大的问题越难求解。另外还 有指数成长(exponential-time)，简单说明，数学问题的成长速度，会是多项式 成长的倍数。此类问题，更难求解。整数规划要求所有的未知量都为整数的线性规划问题叫做整数规划(integer programming, IP)或整数线性规划(integer linear programming, ILP)问题。 相对于即使在最坏情况下也能有效率地解出的线性规划问题，整数规划问题的最 坏情况是不确定的，在某些实际情况中(有约束变量的那些)为NP困难问题。0-1整数规划是整数规划的特殊情况，所有的变量都要是0或1(而非任意整数)。这类问题亦被分类为NP困难问题。只要求当中某几个未知数为整数的线性规划问题叫做混合整数