在線性約束下最佳化線性目標函數
線性規劃研究在線性約束下最大化或最小化線性目標函數的問題。廣泛應用於資源調配、生產計劃、投資組合優化、網路流等領域。1947 年 George Dantzig 發明的單形法（Simplex Method）是第一個實用演算法。
最大化 cᵀx，滿足 Ax ≤ b, x ≥ 0。其中 c 為目標係數向量，A 為約束矩陣，b 為約束常數向量，x 為決策變數向量。
單形法從一個可行解開始，沿約束邊界移動，每次迭代改善目標函數值，直到達到最優解。雖然最壞情況為指數時間，但實際表現非常優異。
每個線性規劃問題都有對應的對偶問題。原問題與對偶問題的最優目標值相等（強對偶定理）。對偶性提供了問題的另一种視角，並可用於敏感度分析。