Linear Programming & Simplex algorithm 線性規劃與單純形法（最佳化簡介）

在一個線性規劃問題中，我們想要最小化一個 cost function f(x)，其中有 n 個變數與 k 個約束條件 Ax = b，並且 n 個變數都大於或等於零，寫成數學式子為： \[ Minimize\ f(x) = c^Tx \\ subject\ to\ Ax = b\ and\ x \geq 0 \] 與之後會提到的非線性優化不同的是 f(x) 與所有的約束條件 Ax=b 皆是線性函數。用一個例子來解釋，如果 A 是一個 1x3 的矩陣 [1, 1, 2]，那 Ax = b 就是一個在三維空間中的平面（像是 \(x_1 + x_2 + 2x_3 = 4\)）。這個平面加上所有的 \(x \geq 0\) 約束後會是一個三維空間中的三角形，其頂點為 (4, 0, 0)、(0, 4, 0)、以及 (0, 0, 2)。cost function 是線性的，所以其最小值一定會落在其中一個頂點上，但是當 n 跟 k 很大時要找到這個頂點計算量會很大，而單純形法 simplex method 就是可以找出線性規劃解的一種演算法，我們在下一段簡單介紹 simplex method。

Simplex method 單純形法

先簡介一下 simplex method 的精神：從任意一個上述的頂點開始，每次都找 steepest edge 至下一個頂點來降低目前的 cost。

以下拿一個例子來介紹： \[ minimize\ f(x) = -x_1 - x_2 \\ s.t.\ 2x_1+x_2\leq12, \\ x_1+2x_2\leq9, \\ x_i\geq 0 \] 第一步是要轉換以上的式子成為本文最上面提到的形式，也就是所有的約束必須要是等式。我們可以加入 slack variables \(x_3, x_4\) 讓以上約束成為等式： \[ 2x_1+x_2+x_3= 12, \\ x_1+2x_2+x_4=9 \] 因此此問題被轉換成： \[ minimize\ f(x) = -x_1 - x_2 \\ 2x_1+x_2+x_3= 12, \\ x_1+2x_2+x_4=9 \\ x_i\geq 0 \] 一開始我們從原點開始，這時的 cost function 值為 0 ，並且假設 cost function 的值為 z： \[ z = -x_1 - x_2 = 0 \] 這個問題的 cost function 包含了 \(x_1\) 跟 \(x_2\)，我們剛剛提到每次都要找一個頂點降低 cost。這兩個變數的係數都是 -1 所以挑哪一個變數都沒差，接下來取 \(x_1\) 來計算。從兩個約束的式子可以看出 \(x_1\) 最大只能變成 6 ，因為如果超過 6 的話 \(x_2, x_3\) 至少會有一個為負數。我們下一步把 \(x_1\) 移項帶入到第二式子： \[ x_1 + \frac{x_2}{2} + \frac{x_3}{2} = 6,\ (x_1 = 6 - \frac{x_2}{2} - \frac{x_3}{2}) \\ (6 - \frac{x_2}{2} - \frac{x_3}{2}) + 2x_2+x_4=9,\ (\frac{3}{2}x_2 - \frac{1}{2}x_3 + x_4 = 3) \] 也把 \(x_1\) 代入 cost function： \[ z = -(6 - \frac{x_2}{2} - \frac{x_3}{2}) - x_2 = -6 - \frac{x_2}{2} + \frac{x_3}{2} \] 下一步取 \(x_2\) 來計算，從兩個約束的式子可以看出 \(x_2\) 最大只能變成 2，否則 \(x_3, x_4\) 至少會有一個為負數。我們做一樣的事情將 \(x_2\) 移項得到： \[ x_2 - \frac{x_3}{3} + \frac{2}{3}x_4 = 2 \] 代入另外兩個式子： \[ z = -6 - \frac{2 + \frac{x_3}{3} - \frac{2}{3}x_4}{2} + \frac{x_3}{2} \\ x_1 + \frac{2 + \frac{x_3}{3} - \frac{2}{3}x_4}{2} + \frac{x_3}{2} = 6 \] 整理後得到： \[ z=-7 + \frac{x_3}{3} + \frac{x_4}{3} \\ x_1 + \frac{2}{3}x_3 - \frac{1}{3}x_4 = 5 \] 計算到這，由於 cost function 式子中 \(x_3, x_4\) 的係數都是正數，並且我們知道所有的 x 都是非負數，所以代表 cost function 的值最小就是 -7，並且此時 \(x_3= x_4=0\)，也就可以得到以下解： \[ x_1^* = 5, \\ x_2^* = 2 \] 以上只是個簡單的例子，但是實際上在解這個問題的時候必須考慮更多狀況，有興趣的讀者可以讀演算法聖經 Introduction to Algorithms 的內容。