研究所考試

在專欄《 線性規劃(1) 》當中，我們化身為政治競選團隊，面對一場需要精密規劃的選舉：如何制定競選策略，才能確保選區內的每個區域，都能取得至少一半登記選民的支持？為了回答這個問題，我們將現實中的競選策略轉化為一個線性規劃問題，從決策變數的定義開始，逐步建立限制條件與目標函數，讓原本看似複雜的競選決策有了清晰的數學結構。最後，再透過演算法求解這個模型，找出在各項限制下最合適的策略，以順利贏得選舉。

透過上面描述的問題，我們知道當面對一個實際問題時，可以透過決策變數、限制條件與目標函數，把它整理成一個線性規劃問題。但如果今天遇到另一個不同的問題，我們又該如何判斷它是不是線性規劃呢？不同的問題雖然看起來差異很大，背後是否其實有著相同的數學結構？要回答這些問題，我們就必須先跳脫具體的應用情境，從更一般的角度來認識線性規劃。就讓我們就從線性規劃最基本的數學形式開始，重新認識這個看似簡單、卻能描述大量現實問題的最佳化工具吧！

線性規劃的核心概念其實相當直接：在一組線性限制條件下，讓某個線性函數的值最大或最小。例如有 n 個變數，以及對應的係數，我們就可以定義出以下線性函數：

若 b 為實數且 f 為線性函數，則方程式：稱為線性等式（linear equality）；而不等式：與則稱為線性不等式（linear inequalities）。這些等式與不等式統稱為線性限制條件（linear constraints）。這裡要特別注意的是，線性規劃只允許這類非嚴格的「不等式」，也就是 ≥ 與 ≤ ，而不包含 < 或 > 這兩種數學符號。

因此，線性規劃的基本任務可以濃縮成一句話：「在滿足所有線性限制條件的前提下，最大化或最小化一個線性函數。」而這個被我們希望最大化或最小化的函數，就是所謂的目標函數（objective function）。

為了方便討論，我們可以把一個線性規劃寫成統一的形式。假設有 n 個變數，以及 m 個限制條件。我們希望最大化：

其中，第一個式子就是目標函數；第二組式子則是問題中的主要限制條件；最後的則稱為非負限制（nonnegativity constraints）。

如果變數很多，逐項寫出這些式子會變得相當冗長，因此我們通常會使用矩陣來表示。令 A 為一個的矩陣，b 為 m 維向量，c 與 x 則分別為 n 維向量。原本的線性規劃就可以簡潔地寫成：

這就是線性規劃常見的標準形式（standard form）。其中，可以理解成向量 c 與 x 的內積，而 Ax 則是矩陣 A 與變數向量 x 相乘後得到的向量。這種寫法最大的好處，是讓我們可以忽略實際問題的細節，直接從數學結構討論線性規劃。例如上一篇的政治競選問題，原本可能包含候選人、選區、資源、選票等各種現實因素；但經過建模之後，最後都可以被濃縮成 A、z、c 與 x。當然，現實中的問題不一定一開始就符合這個標準形式，有些問題可能包含等式限制，也可能允許某些變數取負值。不過，這些差異通常可以透過轉換，將問題改寫成標準形式。因此，標準形式更像是一個方便我們研究與設計演算法的共同語言。

有了數學模型之後，下一個問題就是：我們找到的一組 x 到底算不算一個解？假設我們將所有變數設定成某一組特定數值，記作。如果這組數值滿足線性規劃中的所有限制條件，那麼就稱為一個可行解（feasible solution）。反過來，如果至少有一個限制條件沒有被滿足，那麼它就是不可行解（infeasible solution）。

例如，在競選問題中，如果某個策略使得資源總量超過我們原本擁有的資源，那麼即使這個策略看起來非常理想，也不能算是一個可行解。因為它根本無法在現實中執行。所有可行解集合起來形成的區域，就稱為可行區域（feasible region）。

接下來，我們還需要一個方法比較不同的可行解。這時候，目標函數就派上用場了。對於一組可行解，將它代入目標函數後所得到的值：稱為它的目標值（objective value）。如果我們的目標是最大化，那麼在所有可行解中，能讓達到最大值的解，就稱為最佳解（optimal solution）；而這個最大值則稱為最佳目標值（optimal objective value）。

換句話說，線性規劃其實是在做一件非常明確的事情：「先找出所有符合限制的解，再從中挑出目標函數表現最好的一個。」這個觀念看似簡單，卻是理解後續最佳化演算法的關鍵。

在討論最佳解之前，還有兩種特殊情況需要注意。第一種情況是不可行（infeasible）。如果一個線性規劃根本不存在任何可行解，就代表我們所設定的限制條件彼此衝突。例如，我們要求某個變數同時滿足與，那麼不論怎麼選擇 x 都不可能同時滿足兩個條件。這時候，這個線性規劃就是不可行的。

另一種情況則是無界（unbounded）。這表示雖然存在可行解，但目標函數可以不斷變好，卻不存在一個有限的最佳值。例如，如果我們希望最大化 x，但只有限制，那麼只要持續增加 x，目標值就會持續增加。這種情況下，我們就沒有辦法找到一個有限的最佳解。

因此，一個線性規劃在求解時，並不一定都會得到「某一組最佳數值」。它可能沒有任何可行解（不可行），也可能存在可行解卻沒有有限的最佳值（無界）。

到目前為止，我們已經知道如何描述一個線性規劃，也知道什麼是可行解與最佳解。但這些定義本身並不會告訴我們，究竟要怎麼找到最佳解。想像一下，我們已經知道一個問題的答案必須滿足所有限制條件，而且還必須讓目標函數達到最佳值；但如果沒有一套系統化的方法，我們仍然只能不斷嘗試不同的變數設定，看看哪一個比較好。因此，我們需要線性規劃演算法（linear-programming algorithms），讓尋找最佳解不再只是反覆嘗試，而能依循一定的方法進行。

目前已經發展出許多求解線性規劃的方法。其中，有兩大類演算法可以在多項式時間內求解線性規劃，包括橢球演算法（ellipsoid algorithms）與內點法（interior-point methods）。同時在實務上，另一個經典的方法也非常重要，那就是單體演算法（simplex algorithm）。雖然單體演算法在最壞情況下並不是多項式時間演算法，換句話說，從理論上來看，它可能遇到某些特殊的輸入，使得執行時間變得非常長。但有趣的是，理論上的最壞情況並不代表實際使用時的表現。單體演算法在許多實際問題中都有非常好的效率，因此至今仍然是廣泛使用的線性規劃求解方法之一。

這也讓我們觀察到一件重要的事情：理論上的最壞情況，與實務上的實際表現，不一定完全相同。一個演算法即使無法在理論上保證多項式時間，也可能因為實際問題具有某些特殊結構，而在真實世界中展現出非常好的效率。

今天的專欄我們從數學的角度切入線性規劃的核心，是在滿足所有限制條件的情況下，讓線性目標函數達到最大或最小。透過統一的數學表示法，我們可以將各種現實問題中的資源分配、排程、選擇與規劃問題，轉換成具有共同結構的最佳化問題。在專欄的最後，我們也看到建立模型只是第一步。當問題規模變大之後，真正困難的部分變成「如何有效率地找到最佳解？」橢球演算法與內點法提供了多項式時間的理論保證，而單體演算法雖然在最壞情況下不具備多項式時間保證，卻因為實務上的優異表現而被廣泛使用。從這裡開始，我們可以看到線性規劃真正有趣的地方：數學模型告訴我們「答案應該符合什麼條件」，而演算法則告訴我們「如何有效率地找到答案」。下一回的專欄，我們將從最直觀的幾何觀點出發，看看單體演算法究竟是如何利用線性規劃的結構，一步一步帶領我們找到最佳解。