LP 的幾何：可行域是多面體、最佳解在頂點
LP 的可行域是凸多面體，而且最佳解一定落在某個頂點上——這件事撐起了整個單體法。
線性規劃（LP）之所以好解，關鍵在於它的幾何非常規矩：可行域是一塊「有稜有角」的凸多面體，而最佳解——不管目標函數的方向怎麼變——永遠可以在某個角（頂點）上找到。這篇把這件事的幾何直觀和證明都講清楚。
01 標準式與可行域
一個 LP 標準式長這樣：
可行域 是有限多個半空間 的交集。上一篇證過凸集的交集仍是凸集，半空間本身又是凸集，所以 必然是凸集——而且因為它是有限多個「平的」邊界圍出來的，形狀是有稜有角的凸多面體（polyhedron），不會有弧形邊界。
02 頂點（extreme point）
中的一點 稱為頂點（或極點，extreme point），若它不能寫成 中其他兩個相異點的凸組合——直白地說，頂點是多面體「角」上的點，無法被內部或邊上其他點夾出來。
想像一塊切割過的鑽石（多面體）。頂點就是那些尖尖的角；面上或邊上其他任何一點，都可以寫成兩個角的加權平均，只有角本身做不到。
03 目標函數的等值線與最佳解
下面這個互動把可行域畫成一個凸五邊形，拖曳滑桿轉動目標函數方向 ，看看等值線（，垂直於 的一族平行線）往外推到最遠時，會停在哪個頂點上。
磚紅色箭頭是目標方向 ；一族平行線是等值線，最外面（ 最大）那條磚紅色的線碰到的頂點就是最佳解 x*。轉動滑桿改變 的方向，你會發現最佳解永遠落在某個頂點上，而且隨著方向改變，最佳解只會在相鄰的頂點之間跳動——這正是下一篇單體法沿著邊移動的幾何基礎。
04 最佳解落在頂點上（證明）
▸展開完整證明Proof · 假設有界可行域
設 為有界（bounded）的凸多面體， 為 在 上的一個最佳解。若 本身是頂點，證明完畢。
否則 不是頂點，代表存在 中相異兩點 與 ，使得 。
因為 是最佳解， 且 。但
這是 與 的加權平均，所以必須 ——也就是說 和 也都是最佳解。
因此，只要 不是頂點，就一定能找到另一個「更接近頂點」的最佳解（ 或 ，往多面體的邊界方向推）。多面體的頂點數有限，這個過程有限步內一定會走到某個頂點——那個頂點也是最佳解。
∎
「最佳解落在頂點上」不代表唯一最佳解一定是頂點——如果目標函數的等值線剛好和多面體某條邊平行，那整條邊上的點都是最佳解（無窮多個），只是其中至少有一個頂點也是最佳解，這正是上面證明真正保證的事。
05 為什麼這件事重要
既然最佳解一定在某個頂點上，演算法就不需要搜尋整個（可能無窮大的）可行域，只需要在有限個頂點之間移動——這正是下一篇單體法（simplex method）的出發點：從一個頂點出發，沿著多面體的邊走到目標函數更好的相鄰頂點，直到走不動為止。