线性规划

线性规划（英语：Linear Programming，简称LP）是一种数学方法，通过线性方程或不等式描述问题的约束条件和目标，以实现最佳结果（例如利润最大化或成本最小化）。作为最优化的一种特例，线性规划在许多领域都有重要应用。

一个简单的二元线性规划问题的图示表示。其中包含六个不等式约束，可行解集用黄色表示，形成了一个多边形，即二维多胞形。线性目标函数的最优解位于红线与多边形的交点处。这条红线是目标函数的等值线，箭头指示了优化的方向。

一个具有三个变量的问题的闭合可行域是一个凸多面体。目标函数的固定值所形成的表面是平面（图中未显示）。线性规划问题就是要在这个多面体上找到一个点，使其位于具有最高可能值的平面上。

更严谨地说，线性规划旨在优化一个线性目标函数，该函数需满足一定的线性等式和不等式约束。其解的可行域是一个凸多胞形，这一区域由若干线性不等式描述的有限半空间的交集定义。目标函数本质上是定义在这一凸多面体上的实值仿射函数。通过线性规划算法，可以在多胞形内找到目标函数的最大值或最小值（若解存在）。

线性规划问题通常用标准型表达为：

${\begin{aligned}&{\text{Find a vector}}&&\mathbf {x} \\&{\text{that maximizes}}&&\mathbf {c} ^{\mathsf {T}}\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}$

其中，$\mathbf {x}$是待求解的变量向量，$\mathbf {c}$和$\mathbf {b}$是已知向量，$A$是已知矩阵。需要最大化的$\mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}}\mathbf {x}$被称为目标函数，而约束条件$A\mathbf {x} \leq \mathbf {b}$和$\mathbf {x} \geq \mathbf {0}$定义了目标函数优化范围内的凸多面体。

线性规划的应用覆盖多个领域。它在数学研究中尤为常见，同时也在商业、经济学以及某些工程问题中具有重要价值。线性规划与特征方程、冯·诺依曼的总体均衡模型及结构均衡模型紧密相关（详见对偶线性规划）。 目前，运输、能源、电信和制造业等行业广泛使用线性规划模型。通过这种方法，可以高效解决规划、路由、日程安排、任务分配和设计等各类复杂问题，为实际应用提供精确的数学支持。

历史

列昂尼德·坎托罗维奇

约翰·冯诺伊曼

线性不等式组求解问题可追溯到傅里叶的时期，他于1827年发表了一种求解方法， 这一方法后来被称为傅里叶-莫茨金消元法。

20世纪30年代末期，苏联数学家康托罗维奇和美国经济学家列昂惕夫各自独立开展了线性规划的应用研究。康托罗维奇致力于解决生产调度问题，列昂惕夫则专注于经济领域的应用。然而，他们的开创性成果在相当长的时期内并未受到应有的重视。

二战期间，线性规划迎来了重大转机。这一数学工具在应对战时各种复杂挑战时展现出独特优势，特别是在运输物流、任务调度和资源分配等方面。考虑到成本和资源限制等现实约束条件，线性规划在优化这些环节时发挥了不可替代的作用。

正是战时的显著成效让线性规划逐渐受到广泛关注。二战结束后，这一方法获得了学界普遍认可，并在运筹学、经济学等诸多领域奠定了基础性地位。康托罗维奇和列昂惕夫在30年代末期提出的理论贡献，最终成为线性规划在决策优化领域广泛应用的重要基石。

康托罗维奇的研究成果起初在苏联并未得到重视。 同一时期，美籍荷兰经济学家库普曼斯开始用线性规划方法处理经典经济问题。两位学者后来共同获得了1975年诺贝尔经济学奖。 1941年，希区柯克（Frank Lauren Hitchcock）将运输问题也纳入线性规划框架，提出了一种与后来的单纯形法极为相似的解法。 可惜希区柯克于1957年去世，而诺贝尔奖是不能追授的。

1946年至1947年间，丹齐格独立开发了通用线性规划方法，用于解决美国空军的规划难题。 1947年，他发明了单纯形法，这是首个能够高效解决大多数线性规划问题的方法。 当丹齐格与冯·诺伊曼会面讨论单纯形法时，后者敏锐地发现这一理论与其正在研究的博弈论问题本质上是等价的，由此提出了对偶理论。 丹齐格在1948年1月5日完成的未发表报告《线性不等式定理》（A Theorem on Linear Inequalities）中对此作出了严格证明。 他的研究成果于1951年正式发表，此后在战后各行业的日常规划中得到广泛应用。

丹齐格最初研究的是一个70人对应70个岗位的最优分配问题。若要穷举所有可能的排列组合来寻找最佳方案，所需的计算量是天文数字，甚至超过了可观测宇宙中的粒子总数。然而，将这一问题转化为线性规划模型并使用单纯形法，却能在很短时间内求得最优解。这得益于线性规划理论大幅降低了需要检验的可行解数量。

1979年，哈奇扬（Leonid Khachiyan）首次证明了线性规划问题可在多项式时间内求解。 而该领域更具突破性的理论与实践进展出现在1984年，当时卡马卡（Narendra Karmarkar）提出了求解线性规划的新型内点法。

用途

线性规划作为一个被广泛应用的优化领域，这绝非偶然。运筹学中大量的实际问题都可以转化为线性规划问题。 在线性规划领域，网络流问题和多商品流问题等特殊案例因其重要性而催生了大量针对性的算法研究。许多其他类型的优化算法也往往通过解决线性规划的子问题来实现其目标。从发展历程来看，线性规划孕育了优化理论中的诸多核心理念，包括对偶性、分解，以及凸性及其推广的重要性等。线性规划不仅在微观经济学的创立期发挥了重要作用，如今在企业管理中仍然扮演着关键角色，广泛应用于规划、生产、运输和技术等领域。虽然现代企业面临的管理挑战日新月异，但在有限资源条件下实现利润最大化和成本最小化始终是企业追求的目标。值得一提的是，谷歌也将线性规划应用于YouTube视频的稳定性优化。

标准型

标准型是描述线性规划问题时最常用、最直观的形式。其由以下三个部分组成：

• 需要最大化的线性（或仿射）目标函数

e.g. $f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}$

• 问题约束条件，形式如下：

e.g.

${\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}$

• 非负变量

e.g.

${\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}$

问题通常以矩阵形式表达，形式如下：

$\max\{\,\mathbf {c} ^{\mathsf {T}}\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}$

其他形式，例如最小化问题、包含其他形式约束条件的问题以及涉及负变量的问题，均可以重写为等价的标准型问题。

示例

农夫例子的图形解法——在标出违反条件的区域后，无阴影区域中距离原点最远的顶点（与虚线相交）给出了最优组合（该点位于土地和农药线上，说明收入受到土地和农药的限制，而不是化肥的限制）。

假设一位农民有一片面积为 L 公顷的农田，可以种植小麦或大麦，或者两者的组合。农民拥有 F 千克的肥料和 P 千克的农药。每公顷小麦需要 F₁ 千克肥料和 P₁ 千克农药，而每公顷大麦需要 F₂ 千克肥料和 P₂ 千克农药。设 S₁ 和 S₂ 分别为每公顷小麦和大麦的售价。如果用 x₁ 和 x₂ 分别表示种植小麦和大麦的面积，则通过选择 x₁ 和 x₂ 的最佳值可以实现利润最大化。这个问题可以表示为以下标准型的线性规划问题：

max:	$S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$	（最大化收益，即小麦总销售额加大麦总销售额，收益是“目标函数”）
s.t.	$x_{1}+x_{2}\leq L$	（总面积限制）
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F$	（肥料限制）
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P$	（农药限制）
	$x_{1}\geq 0,x_{2}\geq 0$	（种植面积不能为负）

矩阵形式表示为：

max ${\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}$

s.t. ${\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.$

增广型（松弛型）

线性规划问题可以转换为增广型，以便使用单纯形法的通用形式求解。这种形式引入非负的松弛变量（slack variable），将约束中的不等式转化为等式。此时问题可以用以下分块矩阵形式表示：

max $z$：

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

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

其中，$\mathbf {s}$是新引入的松弛变量，$\mathbf {x}$是决策变量，$z$是需要最大化的变量。

示例

上述例子可转换为以下增广型：

max: $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$		（目标函数）
s.t.	$x_{1}+x_{2}+x_{3}=L$	（增广约束）
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F$	（增广约束）
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}+x_{5}=P$	（增广约束）
	$x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.$

其中$x_{3},x_{4},x_{5}$是（非负的）松弛变量，分别表示未使用的面积、未使用的肥料量和未使用的农药量。

矩阵形式表示为：

max $z$：

$${\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\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0.$$

对偶

主条目：对偶线性规划

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

max $\mathbf {c} ^{T}\mathbf {x}$

s.t. $\mathbf {A} \mathbf {x} \leq \mathbf {b} ,\,\mathbf {x} \geq 0$

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

min $\mathbf {y} ^{T}\mathbf {b}$

s.t. $\mathbf {y} ^{T}\mathbf {A} \geq \mathbf {c} ^{T},\,\mathbf {y} \geq 0$

这里用$y$来作为未知向量。

例子

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

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

问题可以表述如下

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

$\min E=Fy_{1}+Py_{2}$
$s.t.$
$F_{1}y_{1}+P_{1}y_{2}\geq S_{1}$	(控制肥料与农药的价格，使得农夫觉得比起拿那些肥料和农药去种植小麦，卖给园主更有利可图)
$F_{2}y_{1}+P_{2}y_{2}\geq S_{2}$	(与上相似，但改为大麦)
$y_{1}\geq 0,\,y_{2}\geq 0$	（不可用负数单位金额购买）

理论

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

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

另一种情况是，约束条件的多面体可以在目标函数的方向无界（例如：$\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年由前苏联数学家列昂尼德·哈奇扬提出。这个算法建基于非线性规划中瑙姆·Z·索尔发明的椭球法（ellip-soid method），该法又是阿尔卡迪·内米罗夫斯基（2003年约翰·冯·诺伊曼理论奖得主）和 D. Yudin的凸集最优化椭球法的一般化。

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

1984年，贝尔实验室印度裔数学家纳伦德拉·卡尔玛卡尔提出了投影尺度法（又名卡尔玛卡尔算法）。这是第一个在理论上和实际上都表现良好的算法：它的最坏情况仅为多项式时间，且在实际问题中它比单纯形算法有显著的效率提升。自此之后，很多内点算法被提出来并进行分析。一个常见的内点算法为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. ISBN 978-0-262-03293-3. Chapter 29: Linear Programming, pp.770–821.
• Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. 1979. ISBN 978-0-7167-1045-5.  A6: MP1: INTEGER PROGRAMMING, pg.245.

外部链接

• Guidance on Formulating LP problems （页面存档备份，存于互联网档案馆）
• 0-1 Integer Programming Benchmarks with Hidden Optimum Solutions （页面存档备份，存于互联网档案馆）
• COIN-OR- Open Source Library for linear programming （页面存档备份，存于互联网档案馆）
• Cplex - Commercial library for linear programming
• Xpress-MP - Optimization software free to students （页面存档备份，存于互联网档案馆）
• MOSEK - Optimization software for LP, QP, MIP, SOCP and more （页面存档备份，存于互联网档案馆）
• A Tutorial on Integer Programming （页面存档备份，存于互联网档案馆）
• The linear programming FAQ （页面存档备份，存于互联网档案馆）

求解软件包

• AIMMS—include linear programming in industry solutions (free trial license available);
• COIN-OR （页面存档备份，存于互联网档案馆）—COmputational INfrastructure for Operations Research, open-source library
• Cplex—Commercial library for linear programming
• HOPDM （页面存档备份，存于互联网档案馆）—Higher Order Primal Dual Method
• LINDO （页面存档备份，存于互联网档案馆）—LP, IP, Global solver/modeling language
• LiPS （页面存档备份，存于互联网档案馆）—Free easy-to-use program intended for solving linear, integer and goal programming problems.
• lp_solve （页面存档备份，存于互联网档案馆）
• MOSEK （页面存档备份，存于互联网档案馆）—Optimization software for LP, QP, MIP, SOCP and more
• Premium Solver （页面存档备份，存于互联网档案馆）—Spreadsheet add-in
• What's Best! （页面存档备份，存于互联网档案馆）—Spreadsheet add-in
• Xpress-MP （页面存档备份，存于互联网档案馆）—Optimization software free to students
• GIPALS （页面存档备份，存于互联网档案馆）—Linear programming environment and dynamic link library (DLL)
• DecisionPro Linear Programming Optimization Software
• QSopt （页面存档备份，存于互联网档案馆） Optimization software for LP (free for research purposes).
• Microarray Data Classification Server (MDCS) based on linear programming
• Linear programming and linear goal programming A freeware program for MS-DOS
• Simplex Method Tool A quick-loading web page