[最佳化] 淺談線性規劃(4)- How to move from one Basic Feasible solution to another- An Example

延續前篇，我們現在手上有了 LP問題的基本定理：

=================================
Theorem (Fundamental Theorem of LP)：
考慮標準型式的線性規劃 (Standard LP)問題

令 $x \in \mathbb{R}^n$，
$$\begin{array}{l} \min {c^T}x\\ s.t.\\ \left\{ \begin{array}{l} Ax = b,\\ x \ge 0 \end{array} \right. \end{array}$$ 其中 $A$ 為 $m \times n$ 矩陣且 $n>m$, $rank(A) = m$，$A$ 沒有全為零的column$；b \geq 0$，
1. 若其存在一個 Feasible Solution，則必存在一個 Basic + Feasible 的解
2. 若其存在一個optimal + feasible solution，則必定存在一個optimal basic + feasible solution 。
=================================

現在我們來看看線性規劃的一些例子：

Example：
考慮如下 LP 問題：
$$\begin{array}{l} \max \left( {3{u_1} + 5{u_2}} \right)\\ s.t.\\ \left\{ \begin{array}{l} {u_1} + 5{u_2} \le 40\\ 2{u_1} + {u_2} \le 20\\ {u_1} + {u_2} \le 12 \end{array} \right.\\ {u_i} \ge 0,i = 1,2 \end{array}$$ 首先將其改寫成標準型式LP問題： (引入 slack variable $y_3, y_4, y_5 \geq 0$)
$$\begin{array}{l} \min \left( { - 3{u_1} - 5{u_2}} \right)\\ s.t.\\ \left\{ \begin{array}{l} {u_1} + 5{u_2} + {y_3} = 40\\ 2{u_1} + {u_2} + \begin{array}{*{20}{c}} {} \end{array}{y_4} = 20\\ {u_1} + {u_2} + \begin{array}{*{20}{c}} {} \end{array}\begin{array}{*{20}{c}} {} \end{array}\begin{array}{*{20}{c}} {} \end{array}{y_5} = 12 \end{array} \right.\\ {u_i} \ge 0,i = 1,2,3,4,5 \end{array}$$ 定義 $x := [x_1 \ x_2 \ x_3 \ x_4 \ x_5 ]^T = [u_1 \ u_2 \ y_1 \ y_2 \ y_3 ]^T$ 我們得到標準型LP問題如下
$$\begin{array}{l} \min \left( { - 3{x_1} - 5{x_2}} \right)\\ s.t.\\ \left\{ \begin{array}{l} {x_1} + 5{x_2} + {x_3} = 40\\ 2{x_1} + {x_2} + \begin{array}{*{20}{c}} {} \end{array}{x_4} = 20\\ {x_1} + {x_2} + \begin{array}{*{20}{c}} {} \end{array}\begin{array}{*{20}{c}} {} \end{array}\begin{array}{*{20}{c}} {} \end{array}{x_5} = 12 \end{array} \right.\\ {x_i} \ge 0,i = 1,2,3,4,5 \end{array}$$
注意到我們可以把拘束條件改寫為
$$\begin{array}{l} {x_1}\left[ {\begin{array}{*{20}{c}} 1\\ 2\\ 1 \end{array}} \right] + {x_2}\left[ {\begin{array}{*{20}{c}} 5\\ 1\\ 1 \end{array}} \right] + {x_3}\left[ {\begin{array}{*{20}{c}} 1\\ 0\\ 0 \end{array}} \right] + {x_4}\left[ {\begin{array}{*{20}{c}} 0\\ 1\\ 0 \end{array}} \right] + {x_5}\left[ {\begin{array}{*{20}{c}} 0\\ 0\\ 1 \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {40}\\ {20}\\ {12} \end{array}} \right]\\ {x_i} \ge 0,i = 1,2,3,4,5 \end{array}$$ 且 $x= [0, 0, 40, 20, 12]^T$ 為一個 feasible solution 且 為一個 Extreme point (由之前文章的定理可知Exterme Point $\Leftrightarrow$ Basic Feasible Solution)。但是如果我們選此 $x$則我們的cost ：$-3 x_1 - 5 x_2 = -3 \cdot 0 + -5 \cdot 0 =0$。亦即此cost並不是minimum，故我們需要在其他 Extreme Point 中尋找最佳解。

想法： 從一個 Extreme Point 移動到另一個 Exterme Point 使得我們的cost 可以逐步降低。

故由 $x= [0, 0, 40, 20, 12]^T$ 開始，我們有
$${0\underbrace {\left[ {\begin{array}{*{20}{c}} 1\\ 2\\ 1 \end{array}} \right]}_{{a_1}} + 0\underbrace {\left[ {\begin{array}{*{20}{c}} 5\\ 1\\ 1 \end{array}} \right]}_{{a_2}} + 40\underbrace {\left[ {\begin{array}{*{20}{c}} 1\\ 0\\ 0 \end{array}} \right]}_{{a_3}} + 20\underbrace {\left[ {\begin{array}{*{20}{c}} 0\\ 1\\ 0 \end{array}} \right]}_{{a_4}} + 12\underbrace {\left[ {\begin{array}{*{20}{c}} 0\\ 0\\ 1 \end{array}} \right]}_{{a_5}} = \left[ {\begin{array}{*{20}{c}} {40}\\ {20}\\ {12} \end{array}} \right]} \\ \Rightarrow 0 a_1 + 0 a_2 + 40 a_3 +20 a_4 + 12 a_5 = b$$ 現在為了要選取下一個鄰近的 Extreme Point，我們選 $a_1$ column 做為新的基底。然後我們需要把現有的舊的基底 $a_3, a_4, a_5$ 中剔除一個。那麼該怎麼做呢? 方法如下：

首先把 $a_1$ 用舊基底線性組合來表示：
$$a_1 = 1 a_3 + 2 a_4 + 1 a_5$$ 對上式兩邊同乘 $\varepsilon_1 >0$，我們可得
$${{\varepsilon _1}{a_1} = {\varepsilon _1}{a_3} + 2{\varepsilon _1}{a_4} + {\varepsilon _1}{a_5}}$$ 現在把上式加到 $(*)$ 並整理如下：
$$\begin{array}{l} \left( {{\varepsilon _1}{a_1} - {\varepsilon _1}{a_3} - 2{\varepsilon _1}{a_4} - 1{\varepsilon _1}{a_5}} \right) + \left( {0{a_1} + 0{a_2} + 40{a_3} + 20{a_4} + 12{a_5}} \right) = 0 + b\\  \Rightarrow \left( {{\varepsilon _1} + 0} \right){a_1} + 0{a_2} + \left( {40 - {\varepsilon _1}} \right){a_3} + \left( {20 - 2{\varepsilon _1}} \right){a_4} + \left( {12 - 1{\varepsilon _1}} \right){a_5} = b \end{array}$$ 那麼現在我們想要選 $\varepsilon_1$ 使得 上式的係數都非負，且同時舊的基底 $a_3, a_4, a_5$ 其中一個的係數變成零 (這樣我們就可以把舊的基底其中一個換成新基底 $a_1$)。觀察上式可以發現選舊的基底 $a_3, a_4, a_5$ 對應的係數中最小的， 亦即我們要選 $\varepsilon_1 = 10$ (替換 $a_4$ 基底)。故得到
$$\Rightarrow 10{a_1} + 0{a_2} + 30{a_3} + 0{a_4} + 2{a_5} = b$$ 其對應的 Basic Feasible Solution (Extreme Point) 為
$$[10, 0, 30, 0, 2]^T$$ 且此時我們的Cost: $-3 x_1 - 5 x_2 = -30$，亦即從原本的 $0$ 降低到 $-30$。

接著我們重複上述步驟在移動到下一個鄰近的Extreme Point，希望可以再降低我們的Cost 。這次我們選 $a_2$ 做為新的基底，故我們讓 $a_2$ 用現有的基底 $a_1, a_3, a_5$表示：
$$a_2 = 1/2 a_1 + 9/2 a_3 + 1/2 a_5 \ \ \ \ (**)$$ 接著對上式兩邊同乘 $\varepsilon_2 >0$，我們可得
$${{\varepsilon _2}{a_2} = \frac{1}{2}{\varepsilon _2}{a_1} + \frac{9}{2}{\varepsilon _2}{a_3} + \frac{1}{2}{\varepsilon _2}{a_5}}$$ 把上式 與 $(**)$ 相加
$$\Rightarrow \left( {10 - \frac{1}{2}{\varepsilon _2}} \right){a_1} + {\varepsilon _2}{a_2} + \left( {30 - \frac{9}{2}{\varepsilon _2}} \right){a_3} + 0{a_4} + \left( {2 - \frac{1}{2}{\varepsilon _2}} \right){a_5} = b$$ 同之前步驟，我們需要把 現有基底 $a_1, a_3, a_5$ 中踢出一個，故應選 $\varepsilon_2$ 使得 上式的係數都非負，且同時舊的基底 $a_1, a_3, a_5$ 其中一個的係數變成零；觀察上式發現應選 $\varepsilon_2 = 4$，我們得到
$$\Rightarrow 8{a_1} + 4{a_2} + 12{a_3} + 0{a_4} + 0{a_5} = b$$ 此時對應的解為
$$[8, 4, 12, 0, 0]^T$$ 且對應的 Cost： $-3 x_1 -5 x_2 = -44$亦即又比剛剛的 $-30$ 更小。現在我們再重複上述例子，這次我們選 $a_4$做為新的替換基底並將其用舊的基底表示為
\[
a_4 = a_1 - a_2 +4 a_3
\]接著對上式兩邊同乘 $\varepsilon_3 >0$，並將其與原有的基底相加可得
$$(8-\varepsilon_3) a_1 + (4 + \varepsilon_3) a_2 +(12 - 4 \varepsilon_3) a_3 + \varepsilon_3 a_4 = b$$ 觀察上式，我們應選 $\varepsilon_3 = 3$，故得到
$$5 a_1 + 7 a_2 +0 a_3 + 3 a_4 = b$$ 故對應的解為
$$[5, 7, 0, 3, 0]^T$$ 此時對應的 Cost 為 $-3 x_1 -5 x_2 = -50$且此即為對此 標準LP問題的最佳解，故我們的最佳解對原本問題即為 $x^* = [x_1, x_2]= [u_1, u_2] = [5, 7]$。 $\square$

上述的方法：從一個Extreme point 到另一個 Extreme Point的方法，亦會在之後的 Simplex Method 中再做詳細的介紹。

ref: E. K. P. Chong, S. H. Zak, An Introduction to Optimization 2nd, Chapter 15.

==============
延伸閱讀
[最佳化] 淺談線性規劃(0)- Standard form of Linear Programming

[最佳化] 淺談線性規劃(1)- Feasible solution and Basic solution

[最佳化] 淺談線性規劃(2)- Optimality Theorem

[最佳化] 淺談線性規劃(3)- Geometric View of LP

[最佳化] 淺談線性規劃(4)- How to move from one Basic Feasible solution to another- An Example