線性規劃

線性規劃，有時也稱為線性最佳化，是在由線性和非負約束指定的凸多面體上最大化或最小化線性函式的問題。 簡單來說，線性規劃是基於一組約束，使用線性數學模型來最佳化結果。

線性規劃在 Wolfram 語言 中實現為LinearProgramming[c, m, b]，它找到一個向量 ，該向量在約束條件 和 (對於 ) 下最小化數量 。

線性規劃理論屬於 凸最佳化理論 範疇，也被認為是 運籌學 的重要組成部分。 線性規劃廣泛應用於商業和經濟學，但也可以用於解決某些工程問題。

經濟學方面的例子包括里昂惕夫的投入產出模型、影子價格的確定等；商業應用的一個例子是在一家工廠中最大化利潤，該工廠使用相同的原材料和資源製造多種不同的產品；工程應用示例包括切比雪夫逼近和結構設計（例如，平面桁架的極限分析）。

線性規劃可以使用 單純形法（Wood 和 Dantzig 1949，Dantzig 1949）求解，該方法沿視覺化實體的 多面體稜邊 執行以找到最佳答案。 Khachian (1979) 找到了一個 多項式時間 演算法。 Karmarkar (1984) 找到了一個效率更高的 多項式時間 演算法。 這種方法穿過實體的中間（使其成為所謂的 內點法），然後進行變換和扭曲。 可以說，早在 1960 年代，以內點法形式存在的屏障函式方法就已為人所知，但伴隨 Karmarkar 宣佈而來的媒體炒作使這些方法受到了極大的關注。

變數只能取整數值的線性規劃被稱為 整數規劃。

在電視劇《數字追兇》(NUMB3RS) 第 4 季的開篇劇集“信任度量”（2007 年）中，數學天才 Charlie Eppes 使用了短語“你不需要 Karmarkar 演算法”來表示“你不需要成為火箭科學家就能知道……”。