
_START_ARTICLE_
线性规划
_START_PARAGRAPH_
在数学中，线性规划（Linear Programming，简称LP）特指目标函数和约束条件皆为线性的最优化问题。_NEWLINE_线性规划是最优化问题中的一个重要领域。在作业研究中所面临的许多实际问题都可以用线性规划来处理，特别是某些特殊情况，例如：网络流、多商品流量等问题，都被认为非常重要。目前已有大量针对线性规划算法的研究。很多最优化问题算法都可以分解为线性规划子问题，然后逐一求解。在线性规划的历史发展过程中所衍伸出的诸多概念，建立了最优化理论的核心思维，例如“对偶”、“分解”、“凸集”的重要性及其一般化等。在微观经济学和商业管理领域中，线性规划亦被大量应用于例如降低生产过程的成本等手段，最终提升产值与营收。乔治·丹齐格被认为是线性规划之父。
_START_SECTION_
理论
_START_PARAGRAPH_
几何上，线性约束条件的集合相当于一个凸包或凸集，叫做可行域。因为目标函数亦是线性的，所以其极值点会自动成为最值点。线性目标函数亦暗示其最优解只会出现在其可行域的边界点中。_NEWLINE_在两种情况下线性规划问题没有最优解。其中一种是在约束条件相互矛盾的情况下（例如和），其可行域将会变成空集，问题没有解，因此亦没有最优解。在这种情况下，该线性规划问题会被称之为“不可行”。_NEWLINE_另一种情况是，约束条件的多面体可以在目标函数的方向无界（例如：），目标函数可以取得任意大的数值，所以没有最优解。_NEWLINE_除了以上两种病态的情况以外（问题通常都会受到资源的限制，如上面的例子），最优解永远都能够在多面体的顶点中取得。但最优解未必是唯一的：有可能出现一组最优解，覆盖多面体的一条边、一个面、甚至是整个多面体（最后一种情况会在目标函数只能等于0的情况下出现）。
_START_SECTION_
整数规划
_START_PARAGRAPH_
要求所有的未知量都为整数的线性规划问题叫做整数规划（integer programming, IP）或整数线性规划（integer linear programming, ILP）问题。相对于即使在最坏情况下也能有效率地解出的线性规划问题，整数规划问题的最坏情况是不确定的，在某些实际情况中（有约束变量的那些）为NP困难问题。_NEWLINE_0-1整数规划是整数规划的特殊情况，所有的变量都要是0或1（而非任意整数）。这类问题亦被分类为NP困难问题。_NEWLINE_只要求当中某几个未知数为整数的线性规划问题叫做混合整数规划（mixed integer programming, MIP）问题。这类问题通常亦被分类为NP困难问题。_NEWLINE_存在着几类IP和MIP的子问题，它们可以被有效率地解出，最值得注意的一类是具有完全单位模约束矩阵，和约束条件的右边全为整数的一类。_NEWLINE_一个解决大型整数线性规划问题的先进算法为delayed column generation。