研究所考試

在上一篇專欄《線性規劃(2)》中，我們將線性規劃從具體的應用問題抽象成一般的數學形式，並詳細介紹了目標函數、限制條件、可行解與最佳解等基本概念。然而建立數學模型只是解決問題的第一步，真正的挑戰在於如何有效率地找到最佳解。

本篇將介紹單體演算法（simplex algorithm），從最直觀的幾何觀點出發，先觀察雙變數線性規劃中的可行區域與目標函數，再說明為什麼最佳解通常會出現在可行區域的頂點。最後，我們會將這個幾何直覺推廣到更高維度，並理解單體演算法如何利用頂點之間的移動來尋找最佳解。那我們就廢話不多說，直接透過一個雙變數線性規劃的例子來搞清楚單體演算法是怎麼求得最佳解的吧！

為了方便從幾何角度觀察線性規劃，我們先考慮一個只有兩個變數的例子：

這個問題與上一篇介紹的線性規劃標準形式一致：我們希望讓目標函數最大，同時滿足所有限制條件。由於只有兩個變數與，我們可以將它們放在笛卡兒座標系中，直接畫出每一個限制條件，如下方圖(a)所示。

以第一個限制條件為例：，我們先將其改寫為：，可以方便觀察出這是一條斜率為4、截距為 -8 的直線。我們在座標系中任意找出該直線的兩點，最簡單的方式就是找和的兩個點，分別為(0,-8)和(2,0)，將這兩點相連即可畫出這條方程式在等式條件下所代表的直線，也就是圖(a)當中標示的直線。最後我們會需要判斷此不等式的可行區域（feasible region）在它本身的左側還是右側，我們只需要將原點(0,0)帶入不等式，並判斷是否成立，若成立則與原點同側區域為可行區域，不成立則與原點不同側區域為可行區域。其他限制條件也可以用相同方式表示，當所有限制條件同時畫在座標平面上時，每個限制條件都會排除一部分不符合要求的區域，而所有限制條件共同允許的部分，就是這個線性規劃的可行區域，也就是圖(a)當中的藍色區域。

線性規劃的可行區域具有一個重要性質：它是凸集（convex）。直觀來說，如果在可行區域中任意取兩個點，將這兩個點連成一條線段，那麼線段上的所有點也都會位於可行區域內。因此，線性規劃的可行區域不會出現不規則的凹陷，而是具有規則的幾何結構。

知道可行區域後，下一個問題是：在這些可行解之中，哪一個點能讓最大？由於可行區域通常包含無窮多個點，逐一計算每個點的目標函數值並不可行。因此，我們可以改為觀察具有相同目標值的點。假設目標函數值為 z，則：代表所有目標函數值等於 z 的點。在二維平面上，這是一條斜率為 -1 的直線。當 z 改變時，這些直線會彼此平行地移動。例如：是一條通過原點的直線，而： 與：則是向右上方平移後得到的平行線，如圖(b)所示。

我們可以從開始，逐漸增加 z，將等值線沿著目標值增加的方向平移。只要等值線仍然與可行區域相交，就代表還存在更好的可行解；當等值線即將離開可行區域時，最後仍然相交的位置就對應到最大的可能目標值。在這個例子中，最大的目標值為：，達到此目標值的點為：，因此我們可得此雙變數線性規劃的最佳解爲，最佳目標值為8。

最佳解位於可行區域的頂點並不是巧合，而是線性規劃的重要結構性質。當目標函數等值線持續往更好的方向移動時，只要它仍然穿過可行區域，就代表還存在更好的可行解。因此，當達到最大目標值時，等值線一定已經位於可行區域的邊界上。在二維情況下，最後可能出現兩種情形。第一種是等值線只與可行區域接觸一個點，這個點就是可行區域的頂點。例如本例的最佳解就是唯一的最佳頂點。第二種是等值線剛好與可行區域的一整條邊重合。此時，這條線段上的每一個點都具有相同的最佳目標值，因此它們全部都是最佳解。不過，線段兩端的頂點也同樣是最佳解。因此，即使最佳解不是唯一的，只要最佳值有限，就至少能找到一個位於頂點上的最佳解。

我們剛才解完的是一個雙變數線性規劃的問題，將數學問題轉換為幾何思維，透過平移目標函數等值線以求得最佳解。由於變數只有兩個，因此可行區域為平面，目標函數等值線爲直線。我們可以將這種幾何觀察推廣到更高維度，當線性規劃有三個變數時，每個線性限制條件會形成一個半空間（half-space），所有限制條件的交集則形成三維空間中的可行區域。目標函數的等值集合：就不會只是一條直線了，而會是一個平面。我們一樣可以將這個平面沿著目標值增加的方向移動，直到它最後接觸可行區域的邊界。

同理，當問題具有 n 個變數時，同樣的概念會推廣到 n 維空間。所有線性限制條件的交集形成一個凸多面體（convex polyhedron），而目標函數的等值集合則是更高維度的超平面（hyperplane）。雖然我們無法直接畫出四維或更高維度的圖形，但幾何直覺仍然成立：將目標函數的超平面往更好的方向移動，直到碰到可行區域的邊界，而最佳解會出現在可行區域的頂點上。

今天的專欄我們介紹了單體演算法，透過雙變數線性規劃，將抽象的最佳化問題轉換成直觀的幾何圖形。我們可以利用目標函數的等值線，觀察它如何移動到可行區域的邊界，進而找到最佳解。更重要的是，這個例子演示了一個可以推廣到高維度的重要性質：只要線性規劃存在有限的最佳值，就一定存在一個位於頂點的最佳解。因此，我們不需要搜尋所有可行解，而可以將問題轉化為頂點之間的搜尋，即可在它們當中找到最佳解。