線性規劃問題

線性規劃是最優化問題中的一個重要領域。在作業研究中所面臨的許多實際問題都可以用線性規劃來處理，特別是某些特殊情況，例如：網絡流、多商品流量等問題，都被認為非常重要。現階段已有大量針對線性規劃算法的研究。很多最優化問題算法都可以分解為線性規劃子問題，然後逐一求解。在線性規劃的歷史發展過程中所衍伸出的諸多概念，建立了最優化理論的核心思維，例如“對偶”、“分解”、“凸集”的重要性及其一般化等。在微觀經濟學和商業管理領域中，線性規劃亦被大量應用於例如降低生產過程的成本等手段，最終提升產值與營收。喬治·丹齊格被認為是線性規劃之父。

描述線性規劃問題的常用和最直觀形式是標準型。標準型包括以下三個部分：

一個需要極大化的線性函數，例如：

以下形式的問題約束，例如：

和非負變量，例如：

線性規劃問題通常可以用矩陣形式表達成：

maximize

subject to

其他類型的問題，例如極小化問題，不同形式的約束問題，和有負變量的問題，都可以改寫成其等價問題的標準型。

以下是一個線性規劃的例子。假設一個農夫有一塊 A平方千米的農地，打算種植小麥或大麥，或是兩者依某一比例混合種植。該農夫只可以使用有限數量的肥料 F 和農藥 P，而單位面積的小麥和大麥都需要不同數量的肥料和農藥，小麥以

表示，大麥以

表示。設小麥和大麥的售出價格分別為

和

，則小麥與大麥的種植面積問題可以表示為以下的線性規劃問題：

max

(最大化利潤 - 目標函數)

(種植面積的限制)

(肥料數量的限制)

(農藥數量的限制)

（不可以栽種負數的面積）

在用單純型法求解線性規劃問題之前，必須先把線性規劃問題轉換成增廣矩陣形式。增廣矩陣形式引入非負鬆弛變量將不等式約束變成等式約束。問題就可以寫成以下形式：

Maximize

in:

這裏

是新引入的鬆弛變量, Z需要極大化的變量。

以上例子的轉換成增廣矩陣：

maximize

目標函數

subjuct to

這裏

，是（非負）鬆弛變量。

寫成矩陣形式：

Maximize Z in:

每個線性規劃問題，稱為原問題，都可以變換為一個對偶問題。我們可將“原問題”表達成矩陣形式：

maximize

subject to

而相應的對偶問題就可以表達成以下矩陣形式：

maximize

subject to

這裏用

來作為未知向量。

上述線性規劃例子的對偶問題：

假如有一個種植園主缺少肥料和農藥，他希望同這個農夫談判付給農夫肥料和農藥的價格。可以構造一個數學模型來研究如何既使得農夫覺得有利可圖肯把肥料和農藥的資源賣給他，又使得自己支付的金額最少？

問題可以表述如下

假設

分別表示每單位肥料和農藥的價格，則所支付租金最小的目標函數可以表示為

(控制肥料與農藥的價格，使得農夫覺得比起拿那些肥料和農藥去種植小麥，賣給園主更有利可圖)

(與上相似，但改為大麥)

（不可用負數單位金額購買）

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

在兩種情況下線性規劃問題沒有最優解。其中一種是在約束條件相互矛盾的情況下（例如

和

），其可行域將會變成空集，問題沒有解，因此亦沒有最優解。在這種情況下，該線性規劃問題會被稱之為“不可行”。

另一種情況是，約束條件的多面體可以在目標函數的方向無界（例如：

），目標函數可以取得任意大的數值，所以沒有最優解。

除了以上兩種病態的情況以外（問題通常都會受到資源的限制，如上面的例子），最優解永遠都能夠在多面體的頂點中取得。但最優解未必只有一個：有可能出現一組最優解，覆蓋多面體的一條邊、一個面、甚至是整個多面體（最後一種情況會在目標函數只能等於0的情況下出現）。

單純形算法利用多面體的頂點構造一個可能的解，然後沿着多面體的邊走到目標函數值更高的另一個頂點，直至到達最優解為止。雖然這個算法在實際上很有效率，在小心處理可能出現的“循環”的情況下，可以保證找到最優解，但它的最壞情況可以很壞：可以構築一個線性規劃問題，單純形算法需要問題大小的指數倍的運行時間才能將之解出。事實上，有一段時期內人們曾不能確定線性規劃問題是NP完全問題還是可以在多項式時間裏解出的問題。

第一個在最壞情況具有多項式時間複雜度的線性規劃算法在1979年由前蘇聯數學家Leonid Khachiyan提出。這個算法建基於非線性規劃中Naum Shor發明的橢球法 ^[1]  (ellip-soid method)，該法又是Arkadi Nemirovski（2003年馮‧諾伊曼運籌學理論獎得主）和 D. Yudin的凸集最優化橢球法的一般化。

理論上，“橢球法”在最惡劣的情況下所需要的計算量要比“單形法”增長的緩慢，有希望用之解決超大型線性規劃問題。但在實際應用上，Khachiyan的算法令人失望：一般來説，單純形算法比它更有效率。它的重要性在於鼓勵了對內點算法的研究。內點算法是針對單形法的“邊界趨近”觀念而改採“內部逼近”的路線，相對於只沿着可行域的邊沿進行移動的單純形算法，內點算法能夠在可行域內移動。

1984年，貝爾實驗室印度裔數學家卡馬卡（Narendra Karmarkar）提出了投影尺度法（又名Karmarkar's algorithm）。這是第一個在理論上和實際上都表現良好的算法：它的最壞情況僅為多項式時間，且在實際問題中它比單純形算法有顯著的效率提升。自此之後，很多內點算法被提出來並進行分析。一個常見的內點算法為Mehrotra predictor-corrector method。儘管在理論上對它所知甚少，在實際應用中它卻表現出色。

單形法沿着邊界由一個頂點移動到“相鄰”的頂點，內點算法每一步的移動考量較周詳，“跨過可行解集合的內部”去逼近最佳解。當今的觀點是：對於線性規劃的日常應用問題而言，如果算法的實現良好，基於單純形法和內點法的算法之間的效率沒有太大差別，只有在超大型線性規劃中，頂點幾成天文數字，內點法有機會領先單形法。

線性規劃的求解程式在各種各樣的工業最優化問題裏被廣泛使用，例如運輸網絡的流量的最優化問題，其中很多都可以不太困難地被轉換成線性規劃問題。

線性規劃理論中存在幾個尚未解決的問題，這些開放問題的答案將會是數學運算中的根本突破，並且很可能是我們解決大規模線性規劃問題的主要進展。

這些問題已經由斯蒂芬·斯梅爾在二十一世紀十八個尚未解決的最偉大的問題中應用。用斯梅爾的話來説，“第三個問題是線性規劃理論中最主要的尚未解決的問題”。然而，對於線性規劃問題存在弱多項式時間算法，比如橢球算法和內點算法，尚未發現限制在約束條件個數和變量個數的強多項式時間算法，此算法的發展將會帶來理論上重大意義，或者是解決大規模線性規劃上的實際收益。

要求所有的未知量都為整數的線性規劃問題叫做整數規劃（integer programming, IP）或整數線性規劃（integer linear programming, ILP）問題。相對於即使在最壞情況下也能有效率地解出的線性規劃問題，整數規劃問題的最壞情況是不確定的，在某些實際情況中（有約束變量的那些）為NP困難問題。

0-1整數規劃是整數規劃的特殊情況，所有的變量都要是0或1（而非任意整數）。這類問題亦被分類為NP困難問題 ^[2]  。

只要求當中某幾個未知數為整數的線性規劃問題叫做混合整數規劃（mixed integer programming, MIP）問題。這類問題通常亦被分類為NP困難問題。

存在着幾類IP和MIP的子問題，它們可以被有效率地解出，最值得注意的一類是具有完全單位模約束矩陣，和約束條件的右邊全為整數的一類。

一個解決大型整數線性規劃問題的先進算法為delayed column generation。