單純形法（simplex method）

想像一個問題所有容許方案構成一塊多面的晶體——一個多面體——而你想要使利潤（一個沿某方向橫越晶體穩定增加的量）最大化的方案。有個關鍵事實讓搜尋變得可行：最佳方案總是落在晶體的某個「角」（頂點）上。單純形法利用這點，從一個角跳到相鄰的角、且總跳向利潤更高的那個，直到沒有任何鄰角更好——那個角就是最佳。

這是線性規劃的經典演算法：在線性不等式與等式約束（如 A x <= b 且 x >= 0）下，最大化（或最小化）線性目標 c^T x。可行區域是個凸多面體，而因為目標與約束都是線性的，最佳值在某頂點達到（或沿一條同樣好的頂點所成的邊）。單純形法由 George Dantzig 於 1947 年提出，從一個可行頂點出發，反覆沿一條邊移到使目標增大的相鄰頂點，用對約束方程的「樞紐（pivot）」步驟來交換哪些約束是緊的。當沒有相鄰頂點能改進目標時，最佳性獲得認證，演算法停止。實務上它出奇高效，通常在大致與約束數成正比的樞紐次數內完成。

線性規劃是計算數學的偉大成功故事之一——它驅動排程、物流、網路流、飲食與配料問題，是無數規劃系統內部的引擎——而對偶性（duality）是它深刻的夥伴：每個 LP（原始問題）都有一個配對的對偶 LP，兩者的最佳值相同（強對偶），對偶變數扮演約束的影子價格，正是受約束問題的拉格朗日乘子。誠實的提醒：儘管日常速度極佳，單純形法的「最壞情形」執行時間是指數的（Klee-Minty 例子迫使它造訪指數多個頂點），這正是可證明多項式的內點法成為里程碑的原因。兩者並存：單純形法給出精確頂點解、暖啟動便宜；內點法在某些大問題上擴展性更好。而該方法處處假設「線性」——對非線性目標或約束，你需要別的工具。