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