線性規劃

線性規劃（英語：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