线性规划

描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分：

• 一个需要极大化的线性函数，例如

${\displaystyle c_{1}x_{1}+c_{2}x_{2}}$ 

• 以下形式的问题约束，例如：

${\displaystyle a_{11}x_{1}+a_{12}x_{2}\leq b_{1}}$ 

${\displaystyle a_{21}x_{1}+a_{22}x_{2}\leq b_{2}}$ 

${\displaystyle a_{31}x_{1}+a_{32}x_{2}\leq b_{3}}$ 

• 和非负变量，例如：

${\displaystyle x_{1}\geq 0}$ 

${\displaystyle x_{2}\geq 0}$ 

线性规划问题通常可以用矩阵形式表达成：

maximize ${\displaystyle \mathbf {c} ^{T}\mathbf {x} }$ 

subject to ${\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} ,\,\mathbf {x} \geq 0}$ 

其他类型的问题，例如极小化问题，不同形式的约束问题，和有负变量的问题，都可以改写成其等价问题的标准型。

例子

以下是一个线性规划的例子。假设一个农夫有一块${\displaystyle A}$ 平方千米的农地，打算种植小麦或大麦，或是两者依某一比例混合种植。该农夫只可以使用有限数量的肥料${\displaystyle F}$ 和农药${\displaystyle P}$ ，而单位面积的小麦和大麦都需要不同数量的肥料和农药，小麦以${\displaystyle (F_{1},P_{1})}$ 表示，大麦以${\displaystyle (F_{2},P_{2})}$ 表示。设小麦和大麦的售出价格分别为${\displaystyle S_{1}}$ 和${\displaystyle S_{2}}$ ，则小麦与大麦的种植面积问题可以表示为以下的线性规划问题：

在用单纯型法求解线性规划问题之前，必须先把线性规划问题转换成增广矩阵形式。增广矩阵形式引入非负松弛变量（英语：Slack variable）将不等式约束变成等式约束。问题就可以写成以下形式：

Maximize ${\displaystyle Z}$  in:

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}Z\\\mathbf {x} \\\mathbf {x} _{s}\end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}}$ 

${\displaystyle \mathbf {x} ,\,\mathbf {x} _{s}\geq 0}$ 

这里${\displaystyle \mathbf {x} _{s}}$ 是新引入的松弛变量, ${\displaystyle Z}$ 需要极大化的变量。

例子

以上例子的转换成增广矩阵：

这里${\displaystyle x_{3},x_{4},x_{5}}$ ，是（非负）松弛变量。

写成矩阵形式：

Maximize ${\displaystyle Z}$  in:

${\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}Z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\A\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0}$ 

每个线性规划问题，称为原问题，都可以变换为一个对偶问题。可将“原问题”表达成矩阵形式：

maximize ${\displaystyle \mathbf {c} ^{T}\mathbf {x} }$ 

subject to ${\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} ,\,\mathbf {x} \geq 0}$ 

而相应的对偶问题就可以表达成以下矩阵形式：

minimize ${\displaystyle \mathbf {y} ^{T}\mathbf {b} }$ 

subject to ${\displaystyle \mathbf {y} ^{T}\mathbf {A} \geq \mathbf {c} ^{T},\,\mathbf {y} \geq 0}$ 

这里用${\displaystyle y}$ 来作为未知向量。

例子

上述线性规划例子的对偶问题：

假如有一个种植园主缺少肥料和农药，他希望同这个农夫谈判付给农夫肥料和农药的价格。可以构造一个数学模型来研究如何既使得农夫觉得有利可图肯把肥料和农药的资源卖给他，又使得自己支付的金额最少？

问题可以表述如下

假设${\displaystyle y_{1},y_{2}}$ 分别表示每单位肥料和农药的价格，则所支付租金最小的目标函数可以表示为

几何上，线性约束条件的集合相当于一个凸包或凸集，叫做可行域。因为目标函数亦是线性的，所以其极值点会自动成为最值点。线性目标函数亦暗示其最优解只会出现在其可行域的边界点中。

在两种情况下线性规划问题没有最优解。其中一种是在约束条件相互矛盾的情况下（例如${\displaystyle x\geq 2}$ 和${\displaystyle x\leq 1}$ ），其可行域将会变成空集，问题没有解，因此亦没有最优解。在这种情况下，该线性规划问题会被称之为“不可行”。

另一种情况是，约束条件的多面体可以在目标函数的方向无界（例如：${\displaystyle maxz=x_1+3x_{2}s.t.x_1\ge 0,x_2\ge 0,x_1+x_2\ge 10}${\displaystyle \max z=x_{1}+3x_{2}\ s.t.\ x_{1}\geq 0,x_{2}\geq 0,x_{1}+x_{2}\geq 10}  ），目标函数可以取得任意大的数值，所以没有最优解。

除了以上两种病态的情况以外（问题通常都会受到资源的限制，如上面的例子），最优解永远都能够在多面体的顶点中取得。但最优解未必是唯一的：有可能出现一组最优解，覆盖多面体的一条边、一个面、甚至是整个多面体（最后一种情况会在目标函数只能等于0的情况下出现）。

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

第一个在最坏情况具有多项式时间复杂度的线性规划算法在1979年由前苏联数学家列昂尼德·哈奇扬（英语：Leonid Khachiyan）提出。这个算法建基于非线性规划中瑙姆·Z·索尔（英语：Naum Z. Shor）发明的椭球法（ellip-soid method），该法又是阿尔卡迪·内米罗夫斯基（2003年约翰·冯·诺伊曼理论奖（英语：John von Neumann Theory Prize）得主）和 D. Yudin的凸集最优化椭球法的一般化。

理论上，“椭球法”在最恶劣的情况下所需要的计算量要比“单形法”增长的缓慢，有希望用之解决超大型线性规划问题。但在实际应用上，Khachiyan的算法令人失望：一般来说，单纯形算法比它更有效率。它的重要性在于鼓励了对内点算法的研究。内点算法是针对单形法的“边界趋近”观念而改采“内部逼近”的路线，相对于只沿着可行域的边沿进行移动的单纯形算法，内点算法能够在可行域内移动。

1984年，贝尔实验室印度裔数学家纳伦德拉·卡尔玛卡尔（英语：Narendra Karmarkar）提出了投影尺度法（又名卡尔玛卡尔算法（英语：Karmarkar's algorithm））。这是第一个在理论上和实际上都表现良好的算法：它的最坏情况仅为多项式时间，且在实际问题中它比单纯形算法有显著的效率提升。自此之后，很多内点算法被提出来并进行分析。一个常见的内点算法为Mehrotra predictor-corrector method。尽管在理论上对它所知甚少，在实际应用中它却表现出色。

单形法沿着边界由一个顶点移动到“相邻”的顶点，内点算法每一步的移动考量较周详，“跨过可行解集合的内部”去逼近最佳解。当今的观点是：对于线性规划的日常应用问题而言，如果算法的实现良好，基于单纯形法和内点法的算法之间的效率没有太大差别，只有在超大型线性规划中，顶点几成天文数字，内点法有机会领先单形法。

线性规划的求解程式在各种各样的工业最优化问题里被广泛使用，例如运输网络的流量的最优化问题，其中很多都可以不太困难地被变换成线性规划问题。

线性规划理论中存在几个尚未解决的问题，这些开放问题的答案将会是数学运算中的根本突破，并且很可能是解决大规模线性规划问题的主要进展。

• LP存在强多项式时间算法吗？
• LP存在多项式时间算法以得到一个严格互补解吗?
• LP在实数（单位成本）模型下存在多项式时间算法吗?

这些问题已经由斯蒂芬·斯梅尔在二十一世纪十八个尚未解决的最伟大的问题中应用。用斯梅尔的话来说，“第三个问题是线性规划理论中最主要的尚未解决的问题”。然而，对于线性规划问题存在弱多项式时间算法，比如椭球算法和内点算法，尚未发现限制在约束条件个数和变量个数的强多项式时间算法，此算法的发展将会带来理论上重大意义，或者是解决大规模线性规划上的实际收益。

   儘管赫爾希博士猜想近來被證明是錯誤的，但是它依舊留下下面的開放問題：
   * Are there pivot rules which lead to polynomial-time Simplex variants?
   * Do all polytopal graphs have polynomially-bounded diameter?

要求所有的未知量都为整数的线性规划问题叫做整数规划（integer programming, IP）或整数线性规划（integer linear programming, ILP）问题。相对于即使在最坏情况下也能有效率地解出的线性规划问题，整数规划问题的最坏情况是不确定的，在某些实际情况中（有约束变量的那些）为NP困难问题。

0-1整数规划是整数规划的特殊情况，所有的变量都要是0或1（而非任意整数）。这类问题亦被分类为NP困难问题。

只要求当中某几个未知数为整数的线性规划问题叫做混合整数规划（mixed integer programming, MIP）问题。这类问题通常亦被分类为NP困难问题。

存在着几类IP和MIP的子问题，它们可以被有效率地解出，最值得注意的一类是具有完全单位模约束矩阵，和约束条件的右边全为整数的一类。

一个解决大型整数线性规划问题的先进算法为delayed column generation。

• 单纯形法，一种用于线性规划问题求解的常用方法
• 列昂尼德·坎托罗维奇（线性规划奠基者之一）
• 影子价格
• MPS file format
• LP example, Job Shop problem

• Alexander Schrijver: "Theory of Linear and Integer Programming". John Wiley and Sons. 1998.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. 1979.   A6: MP1: INTEGER PROGRAMMING, pg.245.