[線性規劃] Discrete Time Dynamic System Linear Programming

這次要介紹的是如何把一個 有拘束條件 離散時間的動態系統
透過 線性規劃問題來求解。

考慮 離散時間系統的狀態空間表示(state space representation)：
\[
x(k+1) = A x(k) + B u(k), \ \ \ \ \text{given $x(0)$}
\]其中 $x(k) \in \mathbb{R}^n$ 表系統狀態， $u(k)$ 表控制力。

接著我們考慮一些實際的情況：

1. 我們希望系統狀態 隨著時間流逝 與 控制力的幫助，可以在某個時間點達到某個 指定的目標狀態 $x^1$，亦即考慮 終止狀態 $x(N) := x^1$
2. 由於我們是透過控制力來幫助我們讓系統狀態逐步移動到 指定的目標狀態，考量到一班情況，控制力的出力大小須受到一定程度拘束(不可以有無限大的控制力)，亦即
 \[
|u(k)| \leq M \Leftrightarrow -M \leq u(k) \leq M
\]

現在我們定義目標成本函數 (cost function)
\[
J(u) = \displaystyle \sum_{k=0}^{N-1} | u(k)|
\]

Comments:
1. 上述目標為 讓 控制力最小。簡單來說就是要 可以達到目標狀態的情況下 盡可能省力 (可以想像成要要開車 從 A 到 B地點，且盡可能省油。)

2. 上述cost function 最多只能是 取絕對值 (儘管是非線性但可透過一些技巧將其轉換成LP問題)，超過  一般 2階 (or 以上)的 cost function，比如
\[
J(u) = \displaystyle \sum_{k=0}^{N-1} | u(k)|^2
\]不可使用 Linear Programming。因為上述cost function 不再是線性! 。Forget LP in this case..

故我們手上有了一個標準的最佳化問題：
\[\begin{array}{l}
\min J\left( u \right) = \sum\limits_{k = 0}^{N - 1} {\left| {u\left( k \right)} \right|} \\
s.t.\\
\begin{array}{*{20}{c}}
{}
\end{array}x(k + 1) = Ax(k) + Bu(k)\\
\begin{array}{*{20}{c}}
{}
\end{array}x(N): = {x^1}\\
\begin{array}{*{20}{c}}
{}
\end{array}|u(k)| \le M
\end{array}
\]

首先注意到因為我們的成本函數是對 $u(k)$ 最小化，故上式中的拘束應改寫成由 $u(k)$表示：
故我們先改寫 目標狀態拘束 $x(N) = x^1$ 用 $u(k)$ 表示：

怎麼做呢!? 由 離散時間系統的狀態方程
\[
x(k+1) = A x(k) + B u(k), \ \ \ \ \text{given $x(0)$}
\]我們可以進行 跌代求解如下：
\[\begin{array}{l}
x(1) = Ax(0) + Bu(0)\\
x(2) = Ax(1) + Bu(1) = A\left[ {Ax(0) + Bu(0)} \right] + Bu(1)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = {A^2}x(0) + ABu(0) + Bu(1)\\
x(3) = Ax(2) + Bu(2) = A\left[ {{A^2}x(0) + ABu(0) + Bu(1)} \right] + Bu(2)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = {A^3}x(0) + {A^2}Bu(0) + ABu(1) + Bu(2)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} \vdots \\
x(N) = {A^N}x(0) + {A^{N - 1}}Bu(0) +  \cdots  + ABu(N - 2) + Bu(N - 1)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = {A^N}x(0) + \sum\limits_{k = 0}^{N - 1} {{A^{N - 1 - k}}Bu(k)}
\end{array}
\]又因為 $x(N) := x^1$，故我們得到
\[\begin{array}{l}
{x^1} = {A^N}x(0) + \sum\limits_{k = 0}^{N - 1} {{A^{N - 1 - k}}Bu(k)} \\
 \Rightarrow {x^1} - {A^N}x(0) = \left[ {\begin{array}{*{20}{c}}
{{A^{N - 1}}B}&{{A^{N - 2}}B}& \cdots &{{A^1}B}&{{A^0}B}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{u(0)}\\
{u(1)}\\
 \vdots \\
{u(N - 1)}
\end{array}} \right]
\end{array}
\] 由於上式左方 $x^1$ 與 $x(0)$ 已給定，故我們可以聯合上式與 控制力拘束條件 $ |u(k)| \leq M$，將其改寫成LP問題：

對於每一個固定的 $N$，求解 進行求解 LP問題:
\[\begin{array}{l}
\min J\left( u \right) = \sum\limits_{k = 0}^{N - 1} {\left| {u\left( k \right)} \right|} \\
s.t.\\
\left\{ \begin{array}{l}
\begin{array}{*{20}{c}}
{}
\end{array}{x^1} - {A^N}x(0) = \left[ {\begin{array}{*{20}{c}}
{{A^{N - 1}}B}&{{A^{N - 2}}B}& \cdots &{{A^1}B}&{{A^0}B}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{u(0)}\\
{u(1)}\\
 \vdots \\
{u(N - 1)}
\end{array}} \right]\\
\begin{array}{*{20}{c}}
{}
\end{array}|u(k)| \le M
\end{array} \right.
\end{array}\]

[線性規劃] Minimax Problem in LP format

考慮如下 minimax (non-cooperative game)問題：

\[\begin{array}{l}
\mathop {\min }\limits_x \mathop {\max }\limits_{i = 1,...,N} c_i^Tx\\
s.t.\\
Ax \le b
\end{array}
\]注意到上式 $\displaystyle \mathop {\max }\limits_{i = 1,...,N} c_i^Tx$ 為 凸函數 (Convex function) WHY?。故可求解最佳解(min)時 其Local minimum = global minimum。

現在問題是上述的 minimax 問題該如何將其改寫成LP問題呢?

方法如下：

首先引入一個新的變數 $z$ 並考慮如下 新的 LP問題：
\[\begin{array}{l}
\mathop {\min }\limits_{x,z} z\\
s.t.\\
\left\{ \begin{array}{l}
Ax \le b\\
c_i^Tx \le z,\begin{array}{*{20}{c}}
{}
\end{array}\forall i = 1,...,N
\end{array} \right.
\end{array}
\] 則現在此LP問題求解 等價 求解原本的minimax問題。亦即兩者間最佳解相同。

Proof：omitted


那麼如果現在問題變成 min min problem (cooperative game)
\[\begin{array}{l}
\mathop {\min }\limits_x \mathop {\min }\limits_{i = 1,...,N} c_i^Tx\\
s.t.\\
Ax \le b
\end{array}
\]該如何處理呢?

注意到上述的引入新變數 $z$ 的方法在此會失敗。因為此時 $\displaystyle \mathop {\min }\limits_x \mathop {\min }\limits_{i = 1,...,N} c_i^Tx$ 不再是 凸函數 (convex function)，(亦即convexity 無法保證)。求解最佳解(min)的會有問題 (如果其為 凹函數 (concave function)，則最佳解(minimum)不一定存在!)。

一般而言處理mini min problem的問題是將原本問題改寫成求解 $N$ 組 LP問題：
\[\begin{array}{*{20}{l}}
{\mathop {\min }\limits_{i = 1,...,N} \mathop {\min }\limits_x c_i^Tx}\\
{s.t.}\\
{Ax \le b}
\end{array}
\]亦即左右minimum 對調。(Proof: omitted)

[最佳化] 淺談線性規劃(5)- The LP Tableau

延續前篇，我們現在知道如何從一個 Basic Feasible Solution 移動到 另一個 Basic Feasible Solution ，但問題是我們該如何得知應該選哪一個 Basic Feasible Solution 作為我們下一部移動的目標呢?? 亦即 我們該選誰使得我們可以逐步降低Cost Value。

這次介紹一個極為精簡的方法，就是透過matrix row operation 建立 LP Tableau，方法如下：

現在考慮標準型式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 = [a_1, a_2, ..., a_m] \in \mathbb{R}^{m \times n}$ 矩陣且 $n>m$, $rank(A) = m$，$A$ 沒有全為零的column$；b \geq 0$，

接著透過Row operation，把拘束 $Ax =b$ 改寫成如下：
\[\left\{ \begin{array}{l}
{x_1}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array} + {y_{1,m + 1}}{x_{m + 1}} + {y_{1,m + 2}}{x_{m + 2}} +  \cdots  + {y_{1,n}}{x_n} = {y_{1,0}}\\
\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}{x_2}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array} + {y_{2,m + 1}}{x_{m + 1}} + {y_{2,m + 2}}{x_{m + 2}} +  \cdots  + {y_{2,n}}{x_n} = {y_{2,0}}\\
\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array} \ddots \\
\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}{x_m} + {y_{m,m + 1}}{x_{m + 1}} + {y_{m,m + 2}}{x_{m + 2}} +  \cdots  + {y_{m,n}}{x_n} = {y_{m,0}}
\end{array} \right.
\]透過上式，我們我們可建立如下 LP Tableau：
\[\left[ {\begin{array}{*{20}{c}}
1&0& \cdots &0&{{y_{1,m + 1}}}&{{y_{1,m + 2}}}& \cdots &{{y_{1,n}}}&{{y_{1,0}}}\\
0&1& \cdots &0&{{y_{2,m + 1}}}&{{y_{2,m + 2}}}& \cdots &{{y_{2,n}}}&{{y_{2,0}}}\\
 \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0&0& \cdots &1&{{y_{m,m + 2}}}&{{y_{m,m + 2}}}& \cdots &{{y_{m,n}}}&{{y_{m,0}}}
\end{array}} \right]\]觀察上式，我們可以發現有 一組 Feasible Basic Solution：
\[\begin{array}{*{20}{l}}
{{x_1} = {y_{1,0}}}\\
{{x_2} = {y_{2,0}}}\\
 \vdots \\
\begin{array}{l}
{x_m} = {y_{m,0}}\\
{x_{m + 1}} = 0\\
 \vdots \\
{x_n} = 0
\end{array}
\end{array}\]
那麼由之前文章可知，我們可以從這組 Feasible Basic Soluiton開始，逐步移動到下一個Basic Feasible Solution，但現在問題變成我們應該移動到哪一個才可以在移動過程中使 Cost 也逐步降低呢?

現在觀察我們的Cost function：
\[
\begin{array}{l}
J = {c^T}x = {c_1}{x_1} + {c_2}{x_2} + ...+{c_m}{x_m} + {c_{m + 1}}x_{m+1} + ... + {c_n}x_n \ \ \ \ (*)
\end{array}
\]將 $J$ 用 $x_{m+1}, x_{m+2}, ..., x_{n}$ 表示：亦即
由LP Tableau，可知
\[\begin{array}{l}
\left\{ \begin{array}{l}
{x_1} + {y_{1,m + 1}}{x_{m + 1}} + {y_{1,m + 2}}{x_{m + 2}} +  \cdots  + {y_{1,n}}{x_n} = {y_{1,0}}\\
{x_2} + {y_{2,m + 1}}{x_{m + 1}} + {y_{2,m + 2}}{x_{m + 2}} +  \cdots  + {y_{2,n}}{x_n} = {y_{2,0}}\\
 \vdots \\
{x_m} + {y_{m,m + 1}}{x_{m + 1}} + {y_{m,m + 2}}{x_{m + 2}} +  \cdots  + {y_{m,n}}{x_n} = {y_{m,0}}
\end{array} \right.\\
 \Rightarrow \left\{ \begin{array}{l}
{x_1} = {y_{1,0}} - \left( {{y_{1,m + 1}}{x_{m + 1}} + {y_{1,m + 2}}{x_{m + 2}} +  \cdots  + {y_{1,n}}{x_n}} \right)\\
{x_2} = {y_{2,0}} - \left( {{y_{2,m + 1}}{x_{m + 1}} + {y_{2,m + 2}}{x_{m + 2}} +  \cdots  + {y_{2,n}}{x_n}} \right)\\
 \vdots \\
{x_m} = {y_{m,0}} - \left( {{y_{m,m + 1}}{x_{m + 1}} + {y_{m,m + 2}}{x_{m + 2}} +  \cdots  + {y_{m,n}}{x_n}} \right)
\end{array} \right.
\end{array}
\]將上式代入 Cost function $(*)$可得
\[
\begin{array}{l}
 \Rightarrow J = \underbrace {\left( {{c_1}{y_{1,0}} + {c_2}{y_{2,0}} +  \cdots  + {c_m}{y_{m,0}}} \right)}_{: = {J_0}}\\
\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array} + \left[ {{c_{m + 1}} - \sum\limits_{i = 1}^m {{c_i}{y_{i,m + 1}}} } \right]{x_{m + 1}} +  \cdots  + \left[ {{c_n} - \sum\limits_{i = 1}^m {{c_i}{y_{i,n}}} } \right]{x_n}
\end{array}
\]將上式進一步整理
\[\begin{array}{l}
 \Rightarrow J = \underbrace {\left( {{c_1}{y_{1,0}} + {c_2}{y_{2,0}} +  \cdots  + {c_m}{y_{m,0}}} \right)}_{: = {J_0}}\\
\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array} + \underbrace {\left[ {{c_{m + 1}} - \sum\limits_{i = 1}^m {{c_i}{y_{i,m + 1}}} } \right]}_{: = {r_{m + 1}}}{x_{m + 1}} +  \cdots  + \underbrace {\left[ {{c_n} - \sum\limits_{i = 1}^m {{c_i}{y_{i,n}}} } \right]}_{: = {r_n}}{x_n}\\
 \Rightarrow J = {J_0} + {r_{m + 1}}{x_{m + 1}} + {r_{m + 2}}{x_{m + 2}} +  \cdots  + {r_n}{x_n}\\
 \Rightarrow J = {J_0} + \sum\limits_{j = m + 1}^n {{r_j}{x_j}}
\end{array}
\]
Comment:
1. 上式的 $r_j$ 稱作 Relative cost coefficient；$ J_0$ 為 current cost value。
2. 如果 $r_j <0$ 則我們可以讓 $J$ 降低。 反之如果 $r_j >0$，則 $J$ 變大 (makes things worse)。
3. 如果所有的 $r_j \geq 0$ (都非負)，則Cost 無法再繼續降低，我們說此即為最佳解。

將以上討論寫成如下定理：

=======================
Theorem
一個 Basic Feasible Solution 為最佳解 若且唯若 (if and only if ) 其對應的 Relative Cost Coefficient $r_j \geq 0, \ \forall j$
=======================

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

[最佳化] 淺談線性規劃(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

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

延續前篇，由 Fundamental Theorem of LP，我們得知 Optimal Feasible Solution存在，則必存在Optimal Basic Feasible Solution。現在我們從幾何的觀點來看看這個件事情。

也就是說我們想知道 Optimal Basic Feasible Solution 在幾何中有甚麼意義?
在文中我們會介紹 Basic Feasible Solution 等價標準LP拘束集合的 極點 (Extreme Point, or Vertex)

進行幾何的觀點討論之前，我們需要一些先備概念 (凸性 Convexity)來幫助我們。

以下先給出凸集合 (Convex set)的定義：

=============================
Definition (Convex Set)
我們說一個集合 $\Theta \subset \mathbb{R}^n$ 為一個 Convex set 如果下列條件滿足：
對任意兩向量 $x, y \in \Theta$，且對任意實數 $\alpha \in (0, 1), \alpha \in \mathbb{R}^1$，其凸組合 (convex combination)
\[
\alpha x + (1- \alpha) y \in \Theta
\]=============================

如果用圖形表示的話：考慮 $x,y \in \mathbb{R}^2$，下圖說明甚麼是convex set 什麼不是convex set。

有了Convex set 的概念之後，我們回頭檢驗看看 標準型式LP問題的拘束條件：
現在定義拘束集合
\[
 \Theta := \{x: x\geq 0, Ax =b \}
\] 則第一個問題是，我們這樣的拘束集合有甚麼幾何性質? 他是不是一個 Convex set?

答案是肯定的，我們將其寫作如下 FACT:

=================================
FACT:
標準型式 LP問題的拘束條件所形成的集合
\[
 \Theta := \{x: x\geq 0, Ax =b \}
\] 為 Convex set。
=================================

Proof：
由Convex set的定義，我們給定 $x, y \in \Theta$，且給定任意實數 $\alpha \in (0, 1), \alpha \in \mathbb{R}^1$，

我們要證明線性組合
\[
\alpha x + (1- \alpha) y \in \Theta
\]也就是說任意滿足拘束條件的兩項量經過線性組合之後仍然滿足拘束條件 (落在 $\Theta$ 之中)；亦即要證明

(1). $\alpha x + (1- \alpha) y \geq 0$ 且
(2).  $A (\alpha x + (1- \alpha) y) = b $

故我們首先觀察 (1):
因為 $x,y \in \Theta$ 故 $x, y \geq 0$ 又因為 $\alpha \in (0,1)$；故我們可知
\[\alpha x + (1 - \alpha )y \ge 0\]
接著觀察 (2)：
因為 $x,y \in \Theta$ 故 $Ax =b, Ay =b$ 又因為 $\alpha \in (0,1)$；故我們可知

\[A\left( {\alpha x + (1 - \alpha )y} \right) = \alpha Ax + (1 - \alpha )Ay = \alpha b + (1 - \alpha )b = b\]

至此 (1)、(2) 都滿足，故我們說
\[
\alpha x + (1- \alpha) y \in \Theta
\]亦即標準型式LP的拘束條件所形成的集合 $\Theta$ 為一個Convex Set。 $\square$


Comments:
在更深入的最佳化理論 或者 凸分析理論中，上述集合被稱為 polyhedral。


在知道拘束條件所形成的集合為 Convex Set 之後，我們現在便可以引入 Exterme Point的概念：

==========================
Definition (Extreme Point)
令標準型式 LP問題的拘束條件所形成的集合
\[
 \Theta := \{x: x\geq 0, Ax =b \}
\] ，我們說一個向量 $x \in \Theta$ 為一個 Exterme Point of $\Theta$ 若下列條件成立：
不存在 任意兩向量 $x,y \in \Theta$， $x \neq y$ 使得對 $\alpha \in (0,1)$ 有 凸組合(convex combination)
\[
\alpha x + (1- \alpha) y \in \Theta
\]==========================

簡而言知，就是如果 $x^* \in \Theta$ 為極點(Exterme Point)，則該點無法由其他集合中的任意兩點所構成：也就是說如果我們今天找到了集合中某兩向量 $x,y \in \Theta$ 與 $\alpha \in (0,1)$ 並用Convex combination 把 $x^*$ 寫下：
\[
x= \alpha x + (1- \alpha) y
\]則 $x$ 必須等於 $y$，亦即 $x=y$。

(上述的不存在條件，在證明的時候並不容易使用，我們多會將其用歸謬法推回，亦即說它存在，然後再得到某個矛盾。)


有了 Extreme point 的概念之後，我們現在便可以把 Basic Feasible Solution 與 Exterme Point概念作連結。下面的定理告訴我們此兩者等價。

==========================
Theorem: (Basic feasible solution is Extreme Point)
對標準形式LP問題，定義其拘束條件所形成的集合
\[
 \Theta := \{x: x\geq 0, Ax =b \}
\] 其中 $A \in \mathbb{R}^{m \times n}, m<n$。則 $x$ 為 $\Theta$ 中的 Extreme Point 若且唯若 (if and only if)
$x$ 為 Basic feasible solution of 標準型式LP問題。
==========================
Proof:
先證 $\Leftarrow$
假設 $x$ 為 Basic feasible solution，欲證明 $x$ 為 Extreme point。

我們用歸謬法 (Proof by contradiction)幫忙。
假設  $x$ 為 Basic feasible solution，但 $x$ 不為 Extreme point

則由不是 Extreme point 的定義，我們可以將 $x$ 用拘束集合 $\Theta$ 中任意不同兩點 $v^0, v^1$ 與一個常數 $\lambda \in (0,1)$ 以凸組合(convex combination)表示，亦即
\[
x = (1- \lambda) v^0 + \lambda v^1
\] 又因為 $v^0, v^1 \in \Theta$，故 $v^0, v^1$ 必滿足拘束條件，亦即 $v^0, v^1 \geq 0$ 且
\[
 A v^0 =b, A v^1 =b\\
\Rightarrow A (v^0 - v^1) =0
\]上述向量 $v^0 - v^1$ 的非零部分 必定對應到 $A$ 矩陣中 線性獨立的column  $[a^1, a^2, ... a^m]$ 為，故 $v^0 - v^1 =0 \Rightarrow v^0 = v^1$ 亦即此與一開始假設的不同兩點 相矛盾。故 $x$ 為 Extreme point。

---
現在我們接著證明 $\Rightarrow$

假設 $x$ 為 $\Theta$ 中的 Extreme Point，我們要證明 $x$ 為 Basic Feasible Solution：

注意到 $x \in \Theta$，故其必滿足拘束條件，故 $x$ 為 Feasible。故我們只須證明 $x$ 為Basic Solution。

再度使用歸謬法(Proof by contradiction)幫助我們
假設 $x$ 為 $\Theta$ 中的 Extreme Point，但 $x$ 不為 Basic Solution：

現在令 $x_1, x_2, ..., x_p$ 為 $x$ 非零的部分，由於其為Feasible solution，滿足拘束條件，我們可以寫下：
\[
Ax = b \Rightarrow a^1 x_1 + a^2 x_2 + ... + a^p x_p =b \ \ \ \ (*)
\] 由 非 Basic Solution 定義 ( $x$ 對應到 $A$ 矩陣線性相依的columns $a^1, a^2, ..., a^p$)，故 存在一組非零的純量 $y_1, y_2, ... y_p$ 使得
\[
\displaystyle \sum_{i=1}^{p} y_i a^i = y_1 a^1 + y_2 a^2 + ... + y_p a^p =0
\]現在我們把上式乘上 $\varepsilon >0$
\[
\varepsilon y_1 a^1 + \varepsilon y_2 a^2 + ... + \varepsilon y_p a^p =0
\]
，且將其分別 加/減 到 $(*)$式，
\[\begin{array}{l}
\left( {{x_1} + \varepsilon {y_1}} \right){a^1} + \left( {{x_2} + \varepsilon {y_2}} \right){a^2} + ... + \left( {{x^p} + \varepsilon {y_p}} \right){a^p} = b\\
\left( {{x_1} - \varepsilon {y_1}} \right){a^1} + \left( {{x_2} - \varepsilon {y_2}} \right){a^2} + ... + \left( {{x_p} - \varepsilon {y_p}} \right){a^p} = b
\end{array}
\]我們可以選適當的 $\varepsilon $ (EX: 類似前幾篇文章所定義 $\varepsilon := \min \{ x_i/ y_i: i=1,..,p, y_i >0 \})$ 使得上式每一項都非負 $x_i + \varepsilon y_i \geq0, x_i - \varepsilon \geq 0$，則我們有下列向量：
\[\begin{array}{l}
{z_1}: = {\left[ {\begin{array}{*{20}{c}}
{{x_1} + \varepsilon {y_1}}&{{x_2} + \varepsilon {y_2}}&{...}&{{x_p} + \varepsilon {y_p}}&{0,...,0}
\end{array}} \right]^T}\\
{z_2}: = {\left[ {\begin{array}{*{20}{c}}
{{x_1} - \varepsilon {y_1}}&{{x_2} - \varepsilon {y_2}}&{...}&{{x_p} - \varepsilon {y_p}}&{0,...,0}
\end{array}} \right]^T}
\end{array}
\]上述兩向量都都落在 拘束集合中，且我們觀察 $x = \frac{1}{2} z_1 + \frac{1}{2} z_2$。又由於我們的假設可知 $x$ 為 Extreme point (無法被其他在拘束集合中的任意兩點用凸組合表示)，故 $z_1 = z_2$；亦即 $y_i =0, \forall i$，此與我們之前提及的 非 Basic Solution 定義推得的線性相依
\[
\displaystyle \sum_{i=1}^{p} y_i a^i = y_1 a^1 + y_2 a^2 + ... + y_p a^p =0
\]矛盾。
亦即 $x$ 為 Basic Feasible Solution。 $\square$


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

==============
延伸閱讀

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

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

延續上篇，我們知道了標準型式的Linear Programming 問題若存在feasible solution，則必定存在一個 basic + feasible solution，但我們完全沒有提及到底如何最佳化(在此我們以最小化為主；亦即目標是要盡可能降低cost function的值)，

也就是在從一個feasible solution移動到下一個basic + feasible solution之後，cost function的值是如何被降低的。這次要介紹的是 Optimality Theorem

=========================

Theorem: Optimality Theorem

對具有標準形式的Linear Programming問題，若其存在一個optimal + feasible solution $x^*$，則必定存在一個optimal basic + feasible solution $\tilde x^*$。
=========================

Proof:
考慮下列兩種情況：
1. $x^*$  為 Basic solution
2. $x^*$  不為 Basic solution

對情況1而言 (trivially true)：
假設 $x^*$ 為Basic solution，則由假設我們又知道 $x^*$ 為 optimal + feasible solution；故在此情況下 $x^*$ 為 optimal basic + feasible solution 。

對情況2而言
假設 $x^*$  不為Basic solution，則由Basic Solution 定義可知
-----
一個向量 $x \in \mathbb{R}^n$ 稱作對 $Ax=b$ 的 Basic Solution ，若 $x$中 nonzero components 對應到$A$矩陣的線性獨立 Columns。
-----

故若  $x^*$  不為Basic solution，則表示  $x^*$  中的nonzero components 對應到$A$矩陣 Columns為線性相關 ；故我們進一步改寫此結果：

令   $x_1^*, x_2^*, ..., x_m^*$ 為  $x^*$中 nonzero components；其對應到 $A$ 矩陣Columns:
$a^1, a^2, ..., a^m$ 為線性相關；故由線性相關定義可知必定存在一組 非零純量 $y_i$ 使得
\[
\sum_{i=1}^{m} y_i a^i =0
\]

現在我們定義 $\eta^\varepsilon$ 如下
\[
{\eta _i^\varepsilon  }: = \left\{ \begin{array}{l}
x_i^*  - \varepsilon {y_i}, \ \ i \le m\\
0, \ \ \ \ i > m
\end{array} \right.
\] 則

\[\begin{array}{l}
A{\eta ^\varepsilon } = \left[ {\begin{array}{*{20}{c}}
{{a^1}}&{{a^2}}& \cdots &{{a^m}}&{{a^{m + 1}}}& \cdots &{{a^n}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{x_1^* - \varepsilon {y_1}}\\
{x_2^* - \varepsilon {y_2}}\\
 \vdots \\
{x_m^* - \varepsilon {y_m}}\\
0\\
 \vdots \\
0
\end{array}} \right]\\
 \Rightarrow A{\eta ^\varepsilon } = {a^1}\left( {x_1^* - \varepsilon {y_1}} \right) +  \cdots  + {a^m}\left( {x_m^* - \varepsilon {y_m}} \right)\\
 \Rightarrow A{\eta ^\varepsilon } = \left( {{a^1}x_1^* +  \cdots  + {a^m}x_m^*} \right) - \left( {\varepsilon {a^1}{y_1} +  \cdots  + \varepsilon {a^m}{y_m}} \right)\\
 \Rightarrow A{\eta ^\varepsilon } = \left( {{a^1}x_1^* +  \cdots  + {a^m}x_m^*} \right) - \underbrace {\varepsilon \sum\limits_{i = 1}^m {{a^i}{y_i}} }_{ = 0}\\
 \Rightarrow A{\eta ^\varepsilon } = \underbrace {\left[ {\begin{array}{*{20}{c}}
{{a^1}}&{{a^2}}& \cdots &{{a^m}}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{x_1^*}\\
{x_2^*}\\
 \vdots \\
{x_m^*}
\end{array}} \right]}_{ = b}
\end{array}\]亦即，
\[
A \eta^{\varepsilon} = b
\]因此，如果 $|\varepsilon|$ 足夠小的時候，$\eta^\varepsilon$ 為 feasible solution；故我們說 $|\varepsilon| < \delta$；現在我們回頭檢查 對於Cost function $J = c^T x$ 有甚麼影響 :
\[
c^T \eta^\varepsilon = c^T (x^* - \varepsilon y)= c^T x^* - \varepsilon \cdot c^T y \ \ \ \ (*)
\] 且對 $i>m$的時候， $y_i =0$

觀察上式 $(*)$：可知如果我們有 $ \varepsilon \cdot c^T y >0 $ 則 Cost 就可以被我們降低。故定義 $\varepsilon := \delta \cdot \text{sign}(c^T y)$；則對此$\varepsilon$而言，
\[\begin{array}{l}
{c^T}{\eta ^\varepsilon } = {c^T}{x^*} - \varepsilon  \cdot {c^T}y\;\\
 \Rightarrow {c^T}{\eta ^\varepsilon } = {c^T}{x^*} - \delta \cdot \text{sign}\left( {{c^T}y\;} \right) \cdot {c^T}y\;\\
 \Rightarrow {c^T}{\eta ^\varepsilon } = {c^T}{x^*} - \delta \left| {{c^T}y\;} \right| \le {c^T}{x^*}
\end{array}
\]故我們得到 $\eta^\varepsilon$ 為對於 $|\varepsilon| \leq \delta$最佳解。故Optimality 被保證；亦即
我們現在找到 標準型式的Linear Programming 問題的 feasible solution $\eta^\varepsilon$，接著我們保證了此解的Optimality。
接著我們回憶前一篇得到的結果
----
標準型式的Linear Programming 問題若存在feasible solution，則必定存在一個 basic + feasible solution，
----
故我們得到
對具有標準形式的Linear Programming問題，若其存在一個optimal + feasible solution $x^*$，則必定存在一個optimal basic + feasible solution $\tilde x^*$。 至此證明完畢。 $\square$

============
Comments

一般而言，前篇的定理與Optimality Theorem合稱為 Fundamental Theorem of 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 。
=================================

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

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

延續上一篇 [最佳化] 淺談線性規劃(0)- Standard form of Linear Programming，這次要跟大家介紹 線性規劃(LP)問題的求解。由先前介紹我們知道，對任意含有線性不等式拘束的LP問題都可以將其轉換成標準型式的LP問題。亦即含有 等式拘束的LP問題。

\[\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$，

在介紹之前要先介紹兩種解的概念

============================
Definition: (Feasible solution and Basic solution)
一個向量 $x \in \mathbb{R}^n$ 稱作 可行解(Feasible solution)，如果其滿足拘束條件，亦即 $x \geq 0$ 且 $Ax=b$
一個向量 $x \in \mathbb{R}^n$ 稱作對 $Ax=b$ 的 基本解( Basic Solution) ，若 $x$中 nonzero component 對應到$A$矩陣的線性獨立 Columns。
============================

先給個例子看看這兩種解有甚麼不同

Example
考慮下列拘束條件 $Ax=b$：
\[\left[ {\begin{array}{*{20}{c}}
1&2&{ - 2}\\
1&3&{ - 2}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
{{x_3}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
1\\
1

\end{array}} \right]\]
觀察上式，為三個變數兩個拘束條件，故可以任意其中一個變數可被任意給定。另外我們發現$A$中的第一個column 與 第三個 column 彼此線性相關。故現在如果我們選 $x_2=0$取 第一個column 與 第三個 column ，會得到一個解
\[ \Rightarrow \left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
{{x_3}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
3\\
0\\
1
\end{array}} \right]\]
由於此解$\left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
{{x_3}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
3\\
0\\
1
\end{array}} \right]$滿足拘束條件，故我們說此解為 Feasible solution，但是其中非零的元素
\[\left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{}\\
{{x_3}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
3\\
{}\\
1
\end{array}} \right]\]對應到矩陣$A$的column彼此為線性相關，故此解並非Basic solution。
也就是說 Feasible Solution $\nRightarrow$ Basic Solution。

再來如果我們選 矩陣$A$的第二個 Column 與 第三個Column (彼此線性獨立)，且令 $x_1 =0$，則我們得到 Basic Solution如下
\[\left\{ \begin{array}{l}
{x_1} = 0\\
2{x_2} - 2{x_3} = 1\\
3{x_2} - 2{x_3} = 1
\end{array} \right. \Rightarrow \left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
{{x_3}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
0\\
0\\
{ - 1/2}
\end{array}} \right]\]
但注意到此解第三個element為負
\[\left[ {\begin{array}{*{20}{c}}
{{x_1}}\\
{{x_2}}\\
{{x_3}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
0\\
0\\
{ - 1/2}
\end{array}} \right]\]
亦即，不符合 Feasbility，故可得到

Basic Solution $\nRightarrow$ Feasible Solution

那麼我們要的是甚麼??
我們要的是 Basic 且 Feasible 的Solution。下面的定理告訴我們標準型式的線性規劃問題如何才能確保可以得到 Basic + Feasible的Solution。

=================================
Theorem：
考慮標準型式的線性規劃 (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$，
若其具備一個 Feasible Solution，則必有一個 Basic + Feasible 的解
=================================

Proof
假設$x \in \mathbb{R}^n$ 為 Standard LP的一個Feasible soltuion，我們要證明必有一個 Basic + Feasible的解。

為方便起見，我們說 $x$ 有 p個nonzero 元素，亦即 $x_1, x_2, ...x_p$。因為$x$已為 Feasible，故我們只須證明$x$是Basic solution。亦即須證明 非零的元素對應$A$中線性獨立的Columns $a^1, a^2,...a^p$

現在考慮下面兩種情況

CASE1
若$x$中非零的元素$x_1, x_2, ...x_p$ 對應 $A$中的Columns $a^1, a^2,...a^p$ 為線性獨立。則$x$即為 Feasible + Basic Solution。

CASE2
若$x$中非零的元素$x_1, x_2, ...x_p$ 對應 $A$中的Columns $a^1, a^2,...a^p$ 為線性相關。則由線性相關的定義可知：存在一組不全為零的 $y_1, y_2,...y_p$ 為實數純量使得下列線性組合
\[
\sum_{i=1}^p y_i a^i =0 \ \ \ \ (*)
\]現在令 $\varepsilon >0$，定義下列向量 $\eta^{\varepsilon} $
\[\eta _i^\varepsilon : = \left\{ \begin{array}{l}
{x_i} - \varepsilon {y_i}, \ \text{ for $i \le p$}\\
0, \ \text{for $i > p$}
\end{array} \right.\]
則若$\varepsilon$足夠小的時候，我們說 $\eta _i^\varepsilon $ 為 Feasible

WHY?

因為如果$\varepsilon =0 \Rightarrow \eta _i^\varepsilon = x_i \Rightarrow x_i$ 為 Feasible (by Definition of $x$)
如果  $\varepsilon $ 非常小，則由拘束條件
\[
A \cdot \eta^{\varepsilon} = A (x - \varepsilon y) = Ax - A \varepsilon y
\]
由線性相關的結果 $(*)$可知，$A \varepsilon y =0$，亦即上式變為
\[
A \cdot \eta^{\varepsilon} = Ax = b
\]
符合拘束條件，故若$\varepsilon$足夠小的時候，我們說 $\eta _i^\varepsilon $ 為 Feasible。

所以現在問題變成那麼可以挑選多大的$\varepsilon$仍可使得$\eta^{\varepsilon}$ 為 Feasible?

我們把此$\varepsilon$ 稱作 $\varepsilon^*$
$(\star)$定義
\[\varepsilon^* : = \mathop {\min }\limits_i \left\{ {\frac{{{x_i}}}{{{y_i}}}:{y_i} > 0} \right\}
\]則$\eta^{\varepsilon^*}$為 Feasible，且最多$p-1$非零Columns，
$a^1, a^2, ... a^{p-1}$

若此組 Columns為線性獨立，則$\eta^{\varepsilon^*}$為Basic。亦即
$\eta^{\varepsilon^*}$為Basic + Feasible。則我們得到欲證明的結果。

反之若Columns $a^1, a^2, ... a^{p-1}$ 仍 為線性相關，則我們重複上述的演算步驟 $(\star)$，得到
${{\tilde \eta }^{{\varepsilon ^*}}}$為Feasible且最多$p-2$非零Columns。

不斷重複上述步驟，最終我們會落到某個$x$ 且只有一個非零元素。
又因為 $A$ 沒有全為零的column，故其必為線性獨立。亦即
$x$ 為 Basic Solution。
且由假設 $x$ 為Feasible，故 $x$ 為 Feasible + Basic。至此證明完畢。


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

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

這次要介紹最佳化中一類 重要問題 線性規劃(Linear Programming, LP)：

什麼是線性規劃?

簡單說就是 目標成本函數(Cost function)為線性，且約束條件為線性不等式；欲求解最佳解 (最大or最小化)。亦即：
\[\begin{array}{*{20}{l}}
{\min {c^T}u}\\
{s.t.}\\
{\left\{ {\begin{array}{*{20}{l}}
{Au \le b,}\\
{u \ge 0}
\end{array}} \right.}
\end{array}
\]上式稱為一般 或者 典型LP問題 (Canonical form)。這種典型的線性規劃(LP)問題可以改寫成 LP標準式 (Standard form) 如下：
========================

令 $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$，

========================
Comments:
1. $x \in \mathbb{R}^n$，亦即我們有 $n$個變數，$A$為$m \times n$矩陣表示我們有$m$個拘束條件。$rank(A)=m$，暗示 $n>m$ (n 變數 多於 m 拘束條件) 確保nontrivality，因為如果$n =m$，則我們不需要最佳化問題因為此問題存在唯一解 $x = A^{-1}b$或者無解。

2. $rank(A)=m$ 確保 rows 是線性獨立(也就是各個拘束條件各自獨立)。

3. $c^T x = c_1 x_1 + c_2 x_2 + ... + c_n x_n$
但注意到，並不是每一個LP問題都符合上面的標準形式，故我們需要將其改寫轉換。

4. 關於求解LP問題：一般而言一旦線性規劃問題確立；使用者可以直接透過 MATLAB 指令 linprog 指令進行求解。此指令使用方法並非本文討論目標故在此不再贅述。有興趣讀者可直接參考 MATLAB help 該指令進行查閱。

=======================
下面給出一個簡單的例子來說明如何轉換


Example 1 

考慮下列LP最佳化問題
\[\begin{array}{l}
\min J\left( u \right) = \frac{{{u_1}}}{{30}} + \frac{{{u_1}}}{{15}}\\
s.t.\\
\left\{ \begin{array}{l}
2{u_1} + 2{u_2} \le 10\\
2{u_1} + 2{u_2} \ge 4\\
{u_2} \ge 1.5{u_1}\\
{u_1} \ge 0,{u_2} \ge 0
\end{array} \right.
\end{array}\]
則我們可將上式轉換成標準型式；

首先對拘束條件，我們可改寫為
\[\left\{ \begin{array}{l}
2{u_1} + 2{u_2} \le 10\\
2{u_1} + 2{u_2} \ge 4\\
{u_2} - 1.5{u_1} \ge 0
\end{array} \right. \Rightarrow \left\{ \begin{array}{l}
2{u_1} + 2{u_2} + {y_1} = 10\\
2{u_1} + 2{u_2} - {y_2} = 4\\
{u_2} - 1.5{u_1} - {y_3} = 0
\end{array} \right.\]注意到上式中的 $y_1, y_2, y_3$ 為額外加入的變數且 $y_i \geq 0 \ \forall i$。一般稱之為slack variable (for $+y_1$) 與 surplus variable (for $-y_2, -y_3$)
再者，令
\[x = \left[ {\begin{array}{*{20}{c}}
{{u_1}}&{{u_2}}&{{y_1}}&{{y_2}}&{{y_3}}
\end{array}} \right]^T\]，將拘束條件改寫為矩陣形式 為 $A x = b$ 且 $x \geq 0$的形式
\[\begin{array}{l}
\underbrace {\left[ {\begin{array}{*{20}{c}}
2&2&1&0&0\\
2&2&0&{ - 1}&0\\
{ - 1.5}&1&0&0&{ - 1}
\end{array}} \right]}_A\underbrace {\left[ {\begin{array}{*{20}{c}}
{{u_1}}\\
{{u_2}}\\
{{y_1}}\\
{{y_2}}\\
{{y_3}}
\end{array}} \right]}_x = \underbrace {\left[ {\begin{array}{*{20}{c}}
{10}\\
4\\
0
\end{array}} \right]}_b\\
 \Rightarrow Ax = b
\end{array}\]
且注意到 $x \geq 0$
接著，我們改寫目標函數  $J(u) = \frac{u_2}{30} + \frac{u_1}{15}$ 為 $c^T x$ 的形式
\[\underbrace {\left[ {\begin{array}{*{20}{c}}
{\frac{1}{{30}}}&{\frac{1}{{15}}}&0&0&0
\end{array}} \right]}_{{c^T}}\underbrace {\left[ {\begin{array}{*{20}{c}}
{{u_1}}\\
{{u_2}}\\
{{y_1}}\\
{{y_2}}\\
{{y_3}}
\end{array}} \right]}_x\]
至此我們便完成改寫，也就是把此例轉換為標準型式

======================

現在我們考慮一個稍微複雜一點的例子，看看能否將其轉換為標準型式

Example 2

考慮下列最佳化問題
\[\begin{array}{l}
\min \left| {{u_1}} \right| + \left| {{u_2}} \right| + \left| {{u_3}} \right|\\
s.t.\\
\left\{ \begin{array}{l}
{u_1} + {u_2} \le 1\\
2{u_1} + {u_3} = 3
\end{array} \right.
\end{array}\]

注意到cost function 含有絕對值（非線性函數），看起來似乎希望渺茫？但如果仔細觀察一下絕對值特性，如果可以分段表達擇其仍為線性函數。故現在問題變成我們應該如何才能將絕對值成功改寫呢?

首先定義新的變數
\[\begin{array}{l}
{u_1}^ + : = \left\{ \begin{array}{l}
0, \ \text{if} \ {u_1} \le 0\\
{u_1}, \ \text{if} \ {u_1} > 0
\end{array} \right. \Rightarrow {u_1}^ +  \ge 0\\
{u_1}^ - : = \left\{ \begin{array}{l}
0, \ \text{if} \ {u_1} \ge 0\\
{-u_1}, \ \text{if} \ {u_1} < 0
\end{array} \right. \Rightarrow {u_1}^ -  \ge 0
\end{array}\]則我們得到
\[\begin{array}{l}
{u_1} = u_1^ +  - u_1^ - \\
|{u_1}| = u_1^ +  + u_1^ -
\end{array}\]
同樣的方法定義$u_2^+, u_2^-, u_3^+, u_3^- \geq 0$使得
\[\begin{array}{l}
{u_2} = u_2^ +  - u_2^ - \\
|{u_2}| = u_2^ +  + u_2^ - \\
{u_3} = u_3^ +  - u_3^ - \\
|{u_3}| = u_3^ +  + u_3^ -
\end{array}\]故我們現在可改寫最佳化問題如下
\[\begin{array}{l}
\min \left\{ {u_1^ +  + u_1^ -  + u_2^ +  + u_2^ -  + u_3^ +  + u_3^ - } \right\}\\
s.t.\\
\left\{ \begin{array}{l}
u_1^ +  - u_1^ -  + u_2^ +  - u_2^ -  \le 1\\
2\left( {u_1^ +  - u_1^ - } \right) + u_3^ +  - u_3^ -  = 3\\
u_1^ + ,u_1^ - ,u_2^ + ,u_2^ - ,u_3^ + ,u_3^ -  \ge 0
\end{array} \right. \Rightarrow \left\{ \begin{array}{l}
u_1^ +  - u_1^ -  + u_2^ +  - u_2^ -  + s = 1\\
2\left( {u_1^ +  - u_1^ - } \right) + u_3^ +  - u_3^ -  = 3\\
u_1^ + ,u_1^ - ,u_2^ + ,u_2^ - ,u_3^ + ,u_3^ - ,s \ge 0
\end{array} \right.
\end{array}\]

======================
再來看個應用的例子:

Example 3 (Manufacturing LP)
考慮一個製造商欲生產四種產品 $U_1, U_2, U_3, U_4$，分別對應的賣價為 $\$6, \$4, \$ 7, \$ 5$。

製造商需要三種資源(inputs)來生產這四種產品，分別是

1. 工人工時 (man weeks ) (以周計)
2. 原料A (kilograms of material A) (以公斤計)、
3. 原料B (boxes of material B) (以箱計)。

另外我們考慮每一週的生產排程中，製造商有如下限制：
不能讓工人超過工時且也不能使用過量的兩種原料。相關的條件資訊如下表：

令 $u_1$ 為生產 $U_1$的量 (production level)， $u_2$ 為生產 $U_2$的量， $u_3$ 為生產 $U_3$的量， $u_4$ 為生產 $U_4$的量。

我們可利用上表寫出如下拘束條件
\[\left\{ \begin{array}{l}
1{u_1} + 2{u_2} + 1{u_3} + 2{u_2} \le 20\\
6{u_1} + 5{u_2} + 3{u_3} + 2{u_2} \le 100\\
3{u_1} + 4{u_2} + 9{u_3} + 12{u_2} \le 75
\end{array} \right.
\]且注意到生產量(production level) 不為負值，故我們有額外的拘束 $u_i \geq 0, i=1,2,3,4$

現在若製造商目標為將其利潤最大化，則我們可以定義如下cost function：
\[J\left( u \right) = 6{u_1} + 4{u_2} + 7{u_3} + 5{u_4}
\]故我們有如下最佳化問題
\[\begin{array}{l}
\max J\left( u \right) = 6{u_1} + 4{u_2} + 7{u_3} + 5{u_4}\\
s.t.\\
\left\{ {\begin{array}{*{20}{l}}
{1{u_1} + 2{u_2} + 1{u_3} + 2{u_2} \le 20}\\
{6{u_1} + 5{u_2} + 3{u_3} + 2{u_2} \le 100}\\
{3{u_1} + 4{u_2} + 9{u_3} + 12{u_2} \le 75}
\end{array}} \right.\\
{u_i} \ge 0,i = 1,2,3,4
\end{array}
\]注意到上式並非標準型式，故我們需要進一步改寫成標準型式如下：
\[\begin{array}{l}
\min {c^T}x\\
s.t.\\
\left\{ \begin{array}{l}
Ax = b,\\
x \ge 0
\end{array} \right.
\end{array}
\]引入額外的 Slack variable $y_1, y_2, y_3 \geq 0$，我們得到
\[\begin{array}{l}
\min \left[ { - J\left( u \right)} \right] =  - \left( {6{u_1} + 4{u_2} + 7{u_3} + 5{u_4}} \right)\\
s.t.\\
\left\{ {\begin{array}{*{20}{l}}
{1{u_1} + 2{u_2} + 1{u_3} + 2{u_2} + {y_1} = 20}\\
{6{u_1} + 5{u_2} + 3{u_3} + 2{u_2} + {y_2} = 100}\\
{3{u_1} + 4{u_2} + 9{u_3} + 12{u_2} + {y_3} = 75}
\end{array}} \right.\\
{u_i} \ge 0,i = 1,2,3,4
\end{array}
\]定義
 \[
x := [x_1 \ x_2 \ x_3 \ x_4 \ x_5 \ x_6 \ x_7 ]^T = [u_1 \ u_2 \ u_3 \ u_4 \ y_1 \ y_2 \ y_3 ]^T
\] 將上式進一步改寫成矩陣形式
\[\begin{array}{l}
\min \underbrace {\left[ {\begin{array}{*{20}{c}}
{ - 6}&{ - 4}&{ - 7}&{ - 5}&0&0&0
\end{array}} \right]}_{{c^T}}x\\
s.t.\\
\left[ {\begin{array}{*{20}{c}}
1&2&1&2&1&0&0\\
6&5&3&2&0&1&0\\
3&4&9&{12}&0&0&1
\end{array}} \right]x = \left[ {\begin{array}{*{20}{c}}
{20}\\
{100}\\
{75}
\end{array}} \right]\\
{x_i} \ge 0,i = 1,2,3,4,5,6,7
\end{array}\]

知道怎麼轉換之後，再來我們就要思考一個問題。就是轉換之後 (標準型LP) 所求得的解 根原本未轉換前LP 所求得的解 答案是否一致??
如果是肯定的，這個轉換才顯得有意義? 我們也才能放心求解。

幸好答案是肯定的，前面的工作並沒有白忙一場。
我們將此結果寫成如下定理：

==============================
Theorem
標準型式LP求得的解與 經典型LP等價。亦即其最佳解相同
==============================
Proof: 
首先定義 標準型 與 經典型LP的拘束集合
\[\begin{array}{l}
C: = \left\{ {x :Ax \le b,x \ge 0} \right\}\\
S: = \left\{ {x: Ax +y= b,x \ge 0, y \ge 0} \right\}
\end{array}
\]現在我們要證明兩個等價，亦即需證明 $C = S$。

故首先證明 $C \subset S$
取 $x \in C$，令 $y := b - Ax \ge 0$ ，故 $x \in S$。

在證 $S \subset C$
取 $x \in S$，故存在一組 $y_i \geq 0$ 使得
\[
a_{i1}x_1 + ... +a_{in}x_n + y_i = b_i, i=1,2,...n \\
\Rightarrow a_{i1}x_1 + ... +a_{in}x_n \leq b_i
\]故 $x \in C$ $\square$



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