線性規劃 (二)：端點與基解

本文的閱讀等級：中級

線性規劃的標準型問題具有下列形式：

$\begin{array}{lll} \min& z=\mathbf{c}^T\mathbf{x} \\ \hbox{subject to}& A\mathbf{x}=\mathbf{b}, ~~\mathbf{x}\ge\mathbf{0}, \end{array}$

其中 $A$ 是一個 $m\times n$ 階矩陣， $\mathbf{b}$ 是 $m$ 維向量， $\mathbf{c}$ 是 $n$ 維向量， $\mathbf{x}$ 是 $n$ 維未知向量 (見“線性規劃 (一)：標準型問題”)。如果 $A\mathbf{x}=\mathbf{b}$ 無解，線性規劃問題即不成立。因為這個緣故，我們要求 $m\le n$ ，即約束等式的數目不多於未知數的數目。如果 $A$ 有線性相關的列向量 (row vector)，表示系統存在冗餘的約束條件 (可將多餘條件刪除)，譬如， $2x_1+x_2=10$ ， $6x_1+3x_2=30$ ，或約束條件彼此矛盾 (此時系統無解)，譬如， $2x_1+x_2=10$ ， $6x_1+3x_2=20$ 。為了避免捲入這些無謂的情況，以下假設 $A$ 有 $m$ 個線性獨立的列向量，即 $\mbox{rank}A=m$ ，且 $m<n$ (若 $m=n$ ，則 $A\mathbf{x}=\mathbf{b}$ 有唯一解)。

我們先看一個例子：

$\begin{array}{lrl} \min& z=-x_1-2x_2 & \\ \hbox{subject to}&x_1+x_2&\le 4\\ &3x_1+x_2&\le 8\\ &x_2&\le 3\\ & x_1\ge 0,&~x_2\ge 0. \end{array}$

加入鬆弛變數 $x_3, x_4, x_5$ ，將問題轉換為標準型：

$\begin{array}{lrrllll} \min& z=&-x_1-&2x_2 &&& \\ \hbox{subject to}&x_1 &+x_2 &+x_3 & & &= 4\\ &3x_1&+x_2&&+x_4& &= 8\\ & & x_2& & &+x_5&= 3\\ & x_1, &x_2, &x_3, &x_4, & x_5\ge 0.& \end{array}$

從線性代數角度出發，或許我們設想：何不先解出線性方程組 $A\mathbf{x}=\mathbf{b}$ 的通解？於是寫出增廣矩陣，使用高斯消去法化簡 (見“高斯消去法”)，

$\begin{bmatrix} 1&1&1&0&0&\vline&4\\ 3&1&0&1&0&\vline&8\\ 0&1&0&0&1&\vline&3 \end{bmatrix}\to \left[\!\!\begin{array}{crrrccr} 1&1&1&0&0&\vline&4\\ 0&1&0&0&1&\vline&3\\ 0&0&-3&1&2&\vline&2 \end{array}\!\!\right]$

故得等價的梯形陣式：

$\begin{array}{llllll} x_1 & +x_2 & +x_3 & & &=4\\ & x_2 & & &+x_5 &=3\\ & &-3x_3 &+x_4 & +2x_5 &= 2. \end{array}$

每一個方程式的領先變數被該方程式鎖定，稱為軸變數 (pivot variable)；其他的變數未受限制，稱為自由變數 (free variable)。上式中， $x_1, x_2, x_3$ 是軸變數， $x_4, x_5$ 是自由變數。係數矩陣 $A$ 的軸行 (對應軸變數的行向量) $\begin{bmatrix} 1\\ 3\\ 0 \end{bmatrix}, \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}, \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}$ 是線性獨立的，也就是說， $\begin{bmatrix} 1&1&1\\ 3&1&0\\ 0&1&0 \end{bmatrix}$ 是可逆矩陣。設定自由變數為任意參數，線性方程的通解 (即解集合) 可表示為

$\begin{aligned} x_1&=-\frac{1}{3}\alpha+\frac{1}{3}\beta+\frac{5}{3} \\ x_2&=3-\beta\\ x_3&=\frac{1}{3}\alpha+\frac{2}{3}\beta-\frac{2}{3}\\ x_4&=\alpha\\ x_5&=\beta, \end{aligned}$

其中 $\alpha$ 和 $\beta$ 是任意數。給定 $\alpha$ 和 $\beta$ 的數值，我們便得到一個特解。如果特解滿足所有不等式 $x_i\ge 0$ ， $i=1,\ldots,5$ ，便稱該特解為可行解 (feasible solution)。我們要解決的問題是：從包含無窮多成員的可行解集合，稱為可行域 (feasible set)，找出一個使目標函數最小化的可行解。這個問題似乎不屬於線性代數的範疇，那麼接下來該怎麼辦呢？

波利亞 (George Polya) 說^[1]：「如果你解不出手邊的問題，試著先解決其他的相關問題。」問題可以更換，方法也可以改變。當代數方法暫時走不通時，何妨嘗試幾何方法？回到我們的例子，圖一顯示給定的5個不等式交集成的可行域 (橘色區域)，不難確認可行域的邊界為超平面 $x_i=0$ ， $i=1,\ldots,5$ (見“超平面”)。每一不等式 $x_i\ge 0$ 描述一個閉半空間，也就是無界凸集。因為凸集的交集仍為一個凸集 (見“凸組合、凸包與凸集”)，所有不等式交集而成的可行域是一個有界或無界閉凸集。由圖一可知上例的可行域是一個有界閉凸集，其邊界都是平的，稱為多胞形。

圖一：可行域與約束等式

對於凸集 $S$ ，我們稱 $\mathbf{x}\in S$ 是一個端點 (extreme point)，若不存在兩相異點 $\mathbf{y}$ 和 $\mathbf{z}$ 屬於 $S$ 使得 $\mathbf{x}=\alpha\mathbf{y}+(1-\alpha)\mathbf{z}$ ，其中 $0<\alpha<1$ 。換句話說，不位於凸集中任何線段內的點即是端點。上圖顯示可行域 (多邊形) 的頂點都是端點。給定目標函數 $z=-x_1-2x_2$ ，最佳解發生在端點 $(x_1,x_2)=(1,3)$ ，見圖二。這並不是一個特例。事實上，對於任一非空有界閉凸集 $S\in\mathbb{R}^n$ ，必定存在 $S$ 的一端點 $\mathbf{v}$ 使得 $f(\mathbf{v})=\min_{\mathbf{x}\in S}f(\mathbf{x})$ ，其中 $f(\mathbf{x})=\mathbf{c}^T\mathbf{x}$ 是目標函數 (見“多胞形”，定理三)。我們有了重大突破：若可行域是一個有界閉凸集，只要求出所有的端點並逐一代入目標函數計算即可得到最佳解。(這是截至目前為止我們想出的唯一一個方法，但未必是一個好方法。)

圖二：可行域端點與最佳解

接下來，我們想知道如何計算可行域的端點。比較圖一與圖二，可知最佳解所在的端點發生於 $x_3=0$ 和 $x_5=0$ 。將兩式代入約束等式，

$\begin{array}{rc} x_1+x_2&=4\\ x_2&=3\\ x_4 &=2. \end{array}$

對應此線性方程組的 $3\times 3$ 階係數矩陣可逆，故得唯一解 $(x_1,x_2,x_4)=(1,3,2)$ 。這個結果衍生出一個新概念。考慮 $A\mathbf{x}=\mathbf{b}$ ，其中 $A$ 是一個 $m\times n$ 階矩陣， $\hbox{rank}A=m$ 。挑選 $A$ 的 $m$ 個線性獨立行向量 (即 $\mathbb{R}^m$ 的一組基底)，將它們組成一 $m\times m$ 階可逆矩陣 $B$ 。對應 $B$ 的行向量的 $m$ 個變數稱為基變數 (basic variable)，其餘 $n-m$ 個變數稱為非基變數 (nonbasic variable)。設所有非基變數等於零，可得唯一一組基變數解，此解稱為基解 (basic solution)。上例中， $x_1,x_2,x_4$ 是基變數， $x_3, x_5$ 是非基變數， $(x_1, x_2, x_3, x_4, x_5)=(1,3,0,2,0)$ 是一個基解。下面解釋基解的計算過程。令 $\mathbf{x}$ 是 $A\mathbf{x}=\mathbf{b}$ 的任一基解。一旦選擇了一組基變數，我們可以重新排列變數使基變數置前，非基變數置後，如下：

$\mathbf{x}=\begin{bmatrix} \mathbf{x}_B\\ \mathbf{x}_N \end{bmatrix}$ ，

其中 $\mathbf{x}_B$ 表示 $m$ 個基變數， $\mathbf{x}_N$ 表示 $n-m$ 個非基變數。重新排列的約束矩陣具有分塊形式

$A=\begin{bmatrix} B&N \end{bmatrix}$ ，

其中 $m\times m$ 階 $B$ 和 $m\times (n-m)$ 階 $N$ 分別是對應 $\mathbf{x}_B$ 和 $\mathbf{x}_N$ 的係數矩陣。對於基解 $\mathbf{x}$ ，我們要求 $B$ 可逆且 $\mathbf{x}_N=\mathbf{0}$ 。使用此條件，

$A\mathbf{x}=\begin{bmatrix} B&N \end{bmatrix}\begin{bmatrix} \mathbf{x}_B\\ \mathbf{x}_N \end{bmatrix}=B\mathbf{x}_B+N\mathbf{x}_N=B\mathbf{x}_B=\mathbf{b}$ ，

故 $\mathbf{x}_B=B^{-1}\mathbf{b}$ ，基解即為 $\mathbf{x}=\begin{bmatrix} B^{-1}\mathbf{b}\\ \mathbf{0} \end{bmatrix}$ 。

若 $\mathbf{x}$ 是一個基解且 $\mathbf{x}\ge\mathbf{0}$ ，我們稱屬於可行域的基解 $\mathbf{x}$ 為一個基可行解 (basic feasible solution)。對於 $m\times n$ 階約束矩陣 $A$ ，因為我們要求對應基變數的 $m\times m$ 階子陣 $B$ 可逆，基解總數不大於 $n$ 取 $m$ 的組合數，即二項式係數

$\displaystyle \binom{n}{m}=\frac{n!}{m!(n-m)!}$ 。

如果加上不等條件 $\mathbf{x}\ge\mathbf{0}$ ，實際的基可行解總數要比二項式係數給出的上界來的小。下面的定理說明基可行解與端點是等價的代數與幾何概念。

基可行解─端點定理：若 $\mathbf{x}$ 是約束集 $\{\mathbf{x}\in\mathbb{R}^n\vert A\mathbf{x}=\mathbf{b}, \mathbf{x}\ge\mathbf{0}\}$ 的一個基可行解，則 $\mathbf{x}$ 是一端點，反之亦然。

證明於下。若 $\mathbf{x}$ 是一個基可行解，則 $\mathbf{x}$ 是一個可行解。將 $m$ 個基變數置前，即有 $\mathbf{x}=\begin{bmatrix} \mathbf{x}_B\\ \mathbf{x}_N \end{bmatrix}=\begin{bmatrix} \mathbf{x}_B\\ \mathbf{0} \end{bmatrix}$ 。令 $B$ 表示對應基變數的可逆係數矩陣。使用反證法。假設 $\mathbf{x}$ 不是端點，則存在兩相異可行解 $\mathbf{y}$ 和 $\mathbf{z}$ 使得 $\mathbf{x}=\alpha\mathbf{y}+(1-\alpha)\mathbf{z}$ ，其中 $0<\alpha<1$ 。將 $\mathbf{y}$ 和 $\mathbf{z}$ 表示為 $\mathbf{y}=\begin{bmatrix} \mathbf{y}_B\\ \mathbf{y}_N \end{bmatrix}$ 和 $\mathbf{z}=\begin{bmatrix} \mathbf{z}_B\\ \mathbf{z}_N \end{bmatrix}$ 。因為 $\mathbf{y}$ 和 $\mathbf{z}$ 都是可行解， $\mathbf{y}\ge\mathbf{0}$ 且 $\mathbf{z}\ge\mathbf{0}$ 。但 $\mathbf{0}=\mathbf{x}_N=\alpha\mathbf{y}_N+(1-\alpha)\mathbf{z}_N$ ， $0<\alpha<1$ ，可知等號右邊的所有項皆不為負，故推論 $\mathbf{y}_N=\mathbf{z}_N=\mathbf{0}$ 。又因為 $\mathbf{x}, \mathbf{y}, \mathbf{z}$ 都是可行解，故滿足 $\displaystyle B\mathbf{x}_B=B\mathbf{y}_B=B\mathbf{z}_B=\mathbf{b}$ 。但 $B$ 可逆，推得 $\mathbf{x}_B=\mathbf{y}_B=\mathbf{z}_B$ ，即有 $\mathbf{x}=\mathbf{y}=\mathbf{z}$ ，這與 $\mathbf{y}\neq\mathbf{z}$ 矛盾，因此證明 $\mathbf{x}$ 是一個端點。

再看相反方向的論證。假設 $\mathbf{x}$ 是一個端點。我們知道端點 $\mathbf{x}$ 必定是可行解，使得 $A\mathbf{x}=\mathbf{b}$ 且 $\mathbf{x}\ge\mathbf{0}$ 。同樣地，排列變數使得非零變數置於前， $\mathbf{x}=\begin{bmatrix} \mathbf{x}_B\\ \mathbf{x}_N \end{bmatrix}$ ，其中 $\mathbf{x}_B>\mathbf{0}$ 且 $\mathbf{x}_N=\mathbf{0}$ 。寫出 $A=\begin{bmatrix} B&N \end{bmatrix}$ ，這裡 $B$ 和 $N$ 對應 $\mathbf{x}_B$ 和 $\mathbf{x}_N$ 。不過， $B$ 未必是一個方陣，設 $B$ 為 $m\times k$ 階矩陣。如果 $B$ 有線性獨立的行向量，則 $\mathbf{x}$ 是一個基解，證明即告結束。使用反證法。假設 $B$ 的行向量不是線性獨立的，將 $B$ 以其行向量表示為 $B=\begin{bmatrix} \mathbf{b}_1&\cdots&\mathbf{b}_k \end{bmatrix}$ 。因為 $\{\mathbf{b}_1,\ldots,\mathbf{b}_k\}$ 是一個線性相關集，可知存在一非零向量 $\mathbf{d}=(d_1,\ldots,d_k)^T$ 使得

$\displaystyle B\mathbf{d}=\begin{bmatrix} \mathbf{b}_1&\cdots&\mathbf{b}_k \end{bmatrix}\begin{bmatrix} d_1\\ \vdots\\ d_k \end{bmatrix}=d_1\mathbf{b}_1+\cdots+d_k\mathbf{b}_k=\mathbf{0}$ 。

對於任意 $\alpha$ ，則有

$\displaystyle B(\mathbf{x}_b\pm\alpha\mathbf{d})=B\mathbf{x}_b\pm\alpha B\mathbf{d}=B\mathbf{x}_b=\mathbf{b}$ 。

因為 $\mathbf{x}_B>\mathbf{0}$ ，故存在極小的正數 $\epsilon$ 使得 $\mathbf{x}_B+\epsilon\mathbf{d}>\mathbf{0}$ 且 $\mathbf{x}_B-\epsilon\mathbf{d}>\mathbf{0}$ 。令

$\displaystyle \mathbf{y}=\begin{bmatrix} \mathbf{x}_B+\epsilon\mathbf{d}\\ \mathbf{x}_N \end{bmatrix},~~\mathbf{z}=\begin{bmatrix} \mathbf{x}_B-\epsilon\mathbf{d}\\ \mathbf{x}_N \end{bmatrix}$ 。

以上結果表明 $\mathbf{y}$ 和 $\mathbf{z}$ 是異於 $\mathbf{x}$ 的可行解，然而， $\mathbf{x}=\frac{1}{2}\mathbf{y}+\frac{1}{2}\mathbf{z}$ ，這與 $\mathbf{x}$ 是一端點相矛盾，故證得所求。

我們要求基可行解的非基變數等於零，但基變數也可能為零。如果基解的一個或多個基變數等於零，我們稱該基解為退化 (degenerate) 基解，這時我們無法從基解的數值來判斷某變數究竟是基變數還是非基變數。見下例，

$A\mathbf{x}=\begin{bmatrix} 1&1&0&0\\ 2&0&1&0\\ 3&0&0&1 \end{bmatrix}\begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4 \end{bmatrix}=\left[\!\!\begin{array}{r} 4\\ 11\\ 12 \end{array}\!\!\right]=\mathbf{b}$ 。

對於基可行解 $\mathbf{x}=(4,0,3,0)^T\ge\mathbf{0}$ ，基變數與非基變數可能有兩種情況：(1) $\mathbf{x}_B=(x_1,x_2,x_3)^T$ 且 $\mathbf{x}_N=(x_4)$ ，(2) $\mathbf{x}_B=(x_1,x_3,x_4)$ 且 $\mathbf{x}_N=(x_2)$ 。退化發生的原因在於線性系統存在多餘的限制。對應上面線性方程組的約束不等式為

$\begin{aligned} x_1&\le 4\\ 2x_1&\le 11\\ 3x_1&\le 12. \end{aligned}$

顯然，第一式和第三式相等，刪除其中之一並不會影響結果。

下文我們將探討可行域的表述問題，並證明線性規劃的一個基本定理：若線性規劃標準型問題有一個最佳解，則存在一個最佳基可行解。

引用來源：
[1] G. Polya，How to Solve It，1957年出版，頁114。原文是 “If you cannot solve the proposed problem, try to solve first some related problem.”

繼續閱讀：

線性規劃 (三)：最佳基可行解定理

5 Responses to 線性規劃 (二)：端點與基解

chenlogy says:

05/28/2013 at 8:57 pm

教授,我現在有個問題! 如果是多維向量空間,在不投影的情況下,可以比大小或找最佳解嗎?

- ccjou says:
  
  05/28/2013 at 9:54 pm
  
  最佳解必須針對一目標函數才有意義，但不知目標函數為何？
  
張盛東 says:

08/16/2013 at 2:47 am

老師，請問這專題還會出後續嗎？

- ccjou says:
  
  08/16/2013 at 7:06 am
  
  當然會有後續。不只這個專題，其他幾個也都還沒寫完。
  
蔡俊傑 says:

04/04/2014 at 10:39 am

感謝教授的分享，對於學習線性規劃的我，非常受用。^_^

	xmj on 內積的定義
	Ning ChingSan on 線性代數的第一堂課──矩陣乘法的定義
	momo on 兩岸線性代數用詞參照
	訪客 on 克拉瑪公式的簡易幾何證明
	悟 on 條件機率與貝氏定理
	jeremy on 內積與外積是怎麼來的？