线性规划

在數學中，線性規劃（Linear Programming，簡稱LP）特指目標函數和約束條件皆為線性的最佳化問題。

线性规划

線性規劃是最優化問題中的一個重要領域。在作業研究中所面臨的許多實際問題都可以用線性規劃來處理，特別是某些特殊情況，例如：網路流、多商品流量等問題，都被認為非常重要。目前已有大量針對線性規劃演算法的研究。很多最佳化問題算法都可以分解為線性規劃子問題，然後逐一求解。在線性規劃的歷史發展過程中所衍伸出的諸多概念，建立了最優化理論的核心思維，例如「對偶」、「分解」、「凸集」的重要性及其一般化等。在微观经济学和商业管理领域中，线性规划亦被大量应用于例如降低生产过程的成本等手段，最終提升產值與營收。對線性規劃有早期貢獻的列昂尼德·维塔利耶维奇·康托罗维奇和特亚林·科普曼斯於1975年共同獲得諾貝爾經濟學獎。

标准型

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

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

${\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}}$ ，則小麥與大麥的種植面積問題可以表示為以下的線性規劃問題：

${\displaystyle \max Z=S_{1}x_{1}+S_{2}x_{2}}$		(最大化利潤 - 目標函數)
${\displaystyle s.t.}$	${\displaystyle x_{1}+x_{2}\leq A}$	(種植面積的限制)
	${\displaystyle F_{1}x_{1}+F_{2}x_{2}\leq F}$	(肥料數量的限制)
	${\displaystyle P_{1}x_{1}+P_{2}x_{2}\leq P}$	(農藥數量的限制)
	${\displaystyle x_{1}\geq 0,\,x_{2}\geq 0}$	（不可以栽種負數的面積）

增广矩阵（松弛型）

在用单纯型法求解线性规划问题之前，必须先把线性规划问题转换成增广矩阵形式。增广矩阵形式引入非负松弛变量（英语：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}$ 需要极大化的变量。

例子

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

maximize ${\displaystyle S_{1}x_{1}+S_{2}x_{2}}$ ，		(目标函数)
subject to	${\displaystyle x_{1}+x_{2}+x_{3}=A}$ ，	(限制式)
	${\displaystyle F_{1}x_{1}+F_{2}x_{2}+x_{4}=F}$ ，	(限制式)
	${\displaystyle P_{1}x_{1}+P_{2}x_{2}+x_{5}=P}$ ，	(限制式)
	${\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0}$

这里${\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 \min E=Fy_{1}+Py_{2}}$
${\displaystyle s.t.}$
${\displaystyle F_{1}y_{1}+P_{1}y_{2}\geq S_{1}}$	(控制肥料與農藥的價格，使得农夫觉得比起拿那些肥料和農藥去種植小麥，賣給園主更有利可图)
${\displaystyle F_{2}y_{1}+P_{2}y_{2}\geq S_{2}}$	(與上相似，但改為大麥)
${\displaystyle y_{1}\geq 0,\,y_{2}\geq 0}$	（不可用负数单位金額购买）

理論

幾何上，線性約束條件的集合相當於一個凸包或凸集，叫做可行域。因為目標函數亦是線性的，所以其極值點會自動成為最值點。線性目標函數亦暗示其最優解只會出現在其可行域的邊界點中。

在兩種情況下線性規劃問題沒有最優解。其中一種是在約束條件相互矛盾的情況下（例如${\displaystyle x\geq 2}$ 和${\displaystyle x\leq 1}$ ），其可行域將會變成空集，問題沒有解，因此亦沒有最優解。在這種情況下，該線性規劃問題會被稱之為「不可行」。

另一種情況是，約束條件的多面體可以在目標函數的方向無界（例如：${\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. 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 （页面存档备份，存于互联网档案馆）
• 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
• —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)
• QSopt （页面存档备份，存于互联网档案馆） Optimization software for LP (free for research purposes).
• based on linear programming
• Linear programming and linear goal programming^{[永久失效連結]} A freeware program for MS-DOS
• A quick-loading web page