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

Posted on 08/20/2013 by ccjou

本文的閱讀等級：中級

考慮線性規劃標準型問題

\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 階矩陣，m<n，且 \hbox{rank}A=m。若 \mathbf{x}\in\mathbb{R}^n 滿足約束條件 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\in\mathbb{R}^m 且 \mathbf{x}_N=\mathbf{0}，使得 A\mathbf{x}=\mathbf{b}，則 \mathbf{x} 稱為基解。如果基解 \mathbf{x} 滿足 \mathbf{x}\ge\mathbf{0}，則稱之為基可行解。可行域是一個有界或無界閉凸集，其邊界由超平面構成。可行域有一個聯繫幾何與代數的重要性質：可行域的每一端點 (頂點) 是一個基可行解，相反的，可行域中任何非端點都不是基可行解 (見“線性規劃 (二)：端點與基解”)。本文將介紹最佳基可行解定理：若線性規劃標準型問題有一個最佳解，則存在一個最佳基可行解 (或者說，最佳端點)。證明此定理前，我們先討論可行域的表達問題。具體地說，若可行域是一個有界閉凸集，則任一可行解可表示為端點的凸組合；若可行域是一個無界閉凸集，則任一可行解可表示為端點的凸組合與某個平移向量之和。

 
令 S=\{\mathbf{x}\vert A\mathbf{x}=\mathbf{b},\mathbf{x}\ge\mathbf{0}\} 表示一個線性規劃標準型問題的可行域。我們先考慮 S 是有界閉凸集的情況，這時 S 為一個多胞形 (有限向量集的凸包)。令 M=\{\mathbf{v}_1,\ldots,\mathbf{v}_k\} 為多胞形 S 的端點形成的集合。任一有界閉凸集 K 等於 K 的所有端點的凸包 (見“多胞形”，定理二)，因此 S=\hbox{conv}(M)。換句話說，任一 \mathbf{x}\in S 皆可表示為 \mathbf{v}_1,\ldots,\mathbf{v}_k 的凸組合 (見“凸組合、凸包與凸集”)：

\displaystyle \mathbf{x}=\sum_{i=1}^k\beta_i\mathbf{v}_i，

其中 \beta_1+\cdots+\beta_k=1 且 \beta_i\ge 0，i=1,\ldots,k。

 
考慮含兩個變數的線性規劃問題：

\displaystyle\begin{array}{rcc} -x_1&+x_2&\le 3\\ -2x_1&+x_2&\le 2\\ x_1& &\le 4\\ &x_1\ge 0,&x_2\ge 0. \end{array}

Bounded feasible set

圖一：有界可行域

圖一的黃色多邊形代表可行域，包含五個端點 \mathbf{v}_1=(0,0)^T，\mathbf{v}_2=(0,2)^T，\mathbf{v}_3=(1,4)^T，\mathbf{v}_4=(4,7)^T，\mathbf{v}_5=(4,0)^T。對於可行解 \mathbf{x}=(1,1)^T，以端點表達的凸組合式不只一種，下為一例：

\displaystyle\begin{aligned} \mathbf{x}&=\frac{1}{4}\mathbf{v}_1+\frac{1}{2}\mathbf{v}_2+\frac{1}{4}\mathbf{v}_5\\ &=\frac{1}{4}\begin{bmatrix} 0\\ 0 \end{bmatrix}+\frac{1}{2}\begin{bmatrix} 0\\ 2 \end{bmatrix}+\frac{1}{4}\begin{bmatrix} 4\\ 0 \end{bmatrix}=\begin{bmatrix} 1\\ 1 \end{bmatrix}.\end{aligned}

加入鬆弛變數 x_3,x_4,x_5，約束條件可轉換為標準型 (見“線性規劃 (一)：標準型問題”)：

\displaystyle\begin{array}{cccccc} -x_1&+x_2&+x_3& & &=3\\ -2x_1&+x_2& &+x_4& &=2\\ x_1& & & &+x_5&=4\\ x_1,&x_2,&x_3,&x_4,&x_5&\ge 0. \end{array}

在標準型下，可行解 \mathbf{x} 轉換為 \hat{\mathbf{x}}=(1,1,3,3,3)^T，可行域的端點則為

\displaystyle\begin{aligned} \hat{\mathbf{v}}_1&=(0,0,3,2,4)^T\\ \hat{\mathbf{v}}_2&=(0,2,1,0,4)^T\\ \hat{\mathbf{v}}_3&=(1,4,0,0,3)^T\\ \hat{\mathbf{v}}_4&=(4,7,0,3,0)^T\\ \hat{\mathbf{v}}_5&=(4,0,7,10,0)^T .\end{aligned}

值得注意的是，\hat{\mathbf{x}} 和 \mathbf{x} 有相同的凸組合表達式：

\displaystyle\begin{aligned} \mathbf{x}&=\frac{1}{4}\hat{\mathbf{v}}_1+\frac{1}{2}\hat{\mathbf{v}}_2+\frac{1}{4}\hat{\mathbf{v}}_5\\ &=\frac{1}{4}\begin{bmatrix} 0\\ 0\\ 3\\ 2\\ 4 \end{bmatrix}+\frac{1}{2}\begin{bmatrix} 0\\ 2\\ 1\\ 0\\ 4 \end{bmatrix}+\frac{1}{4}\left[\!\!\begin{array}{r} 4\\ 0\\ 7\\ 10\\ 0 \end{array}\!\!\right]=\begin{bmatrix} 1\\ 1\\ 3\\ 3\\ 3 \end{bmatrix}.\end{aligned}

這個性質說明不論線性規劃問題是否為標準型，可行域都是一個有界閉凸集 (多胞形)，惟所在的空間不同而已。

 
接著考慮 S 是無界可行域的情況。若每一 \mathbf{x}\in S 和 \alpha\ge 0 都有 \mathbf{x}+\alpha\mathbf{d}\in S，則 \mathbf{d} 稱為 S 的一無界方向 (direction of unboundedness)。因為 \mathbf{x} 和 \mathbf{x}+\alpha\mathbf{d} 都是可行解，

\displaystyle\begin{array}{rl} A\mathbf{x}=\mathbf{b},&\mathbf{x}\ge\mathbf{0},\\ A(\mathbf{x}+\alpha\mathbf{d})=\mathbf{b},&\mathbf{x}+\alpha\mathbf{d}\ge\mathbf{0}. \end{array}

合併上面兩組式子，可得無界方向的充要條件：

\displaystyle A\mathbf{d}=\mathbf{0},~~~\mathbf{d}\ge\mathbf{0}。

用線性代數術語來說，可行域 S 的無界方向即為矩陣 A 的零空間 N(A) 中滿足 \mathbf{d}\ge\mathbf{0} 的非零向量 \mathbf{d}。若 \mathbf{d}_1 和 \mathbf{d}_2 是 S 的無界方向，不難證明 \alpha\mathbf{d}_1 (\alpha>0) 和 \mathbf{d}_1+\mathbf{d}_2 也是 S 的無界方向。設 M=\{\mathbf{v}_1,\ldots,\mathbf{v}_k\} 是無界可行域 S 的端點，明顯地，\hbox{conv}(M)\subset S。若 \mathbf{x}\in\hbox{conv}(M)，則 \mathbf{x} 可表示為所有端點的凸組合。若 \mathbf{x} 是一個可行解且 \mathbf{x}\not\in\hbox{conv}(M)，可以證明存在一個可行解 \mathbf{y}\in\hbox{conv}(M) 與無界方向 \mathbf{d} 使得 \mathbf{x}=\mathbf{d}+\mathbf{y}。所以，任一 \mathbf{x}\in S 可表示為

\displaystyle \mathbf{x}=\mathbf{d}+\sum_{i=1}^k\beta_i\mathbf{v}_i，

其中 \beta_1+\cdots+\beta_k=1 且 \beta_i\ge 0，i=1,\ldots,k。為便於理解，下面以一個例子解說如何獲得可行解的組合式來取代證明。

 
考慮線性規劃問題

\displaystyle\begin{array}{rcc} -x_1&+x_2&\le 3\\ -2x_1&+x_2&\le 2\\ &x_1\ge 0,&x_2\ge 0. \end{array}

圖二顯示可行域是平面上的一個無界閉凸集，包含三個端點 \mathbf{v}_1=(0,0)^T，\mathbf{v}_2=(0,2)^T，\mathbf{v}_3=(1,4)^T。加入鬆弛變數 x_3,x_4，約束條件可轉換為標準型：

\displaystyle\begin{array}{ccccc} -x_1&+x_2&+x_3& &=3\\ -2x_1&+x_2& &+x_4& =2\\ x_1,&x_2,&x_3,&x_4,&\ge 0. \end{array}

可行解 \mathbf{x}=(3,1)^T 不屬於端點形成的凸包，即以 \mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3 為頂點的三角形。由圖可知 (1,1)^T 和 (1,0)^T 的非負線性組合 (組合係數不為負值) 皆為無界方向。隨意設 \mathbf{d}_1=(1,1)^T，令 \mathbf{x} 朝著無界方向的反方向移動，最終 \mathbf{z}=\mathbf{x}-\gamma\mathbf{d}_1 必將撞擊可行域的邊界。觀察可知 \mathbf{z}=\mathbf{x}-\mathbf{d}_1=(2,0)^T。因為 \mathbf{z} 和端點 \mathbf{v}_1 位於同一無界邊界 (x_1 軸)，\mathbf{d}_2=(1,0)^T 是該邊界所指的無界方向，即有 \mathbf{z}=2\mathbf{d}_2+\mathbf{v}_1。合併以上結果，\mathbf{x} 可寫成一個無界方向與 \mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3 的凸組合之和：

\displaystyle \mathbf{x}=\mathbf{d}_1+\mathbf{z}=(\mathbf{d}_1+2\mathbf{d}_2)+\mathbf{v}_1。

如果 \mathbf{z}=\mathbf{x}-\gamma\mathbf{d}_1 撞擊可行域的有界邊界，即連結 \mathbf{v}_1 和 \mathbf{v}_2　的線段或連結 \mathbf{v}_2 和 \mathbf{v}_3 的線段，則 \mathbf{z} 可直接表示為所有端點的凸組合。

Unbounded feasible set

圖二：無界可行域

 
接下來我們利用可行解的表達式來證明一個非常重要的定理，它為線性規劃演算法提供了穩固的理論基礎。

最佳基可行解定理：若線性規劃標準型問題有一個 (有限數值) 最佳解，則存在一個最佳基可行解。

證明於下。假設一線性規劃標準型問題有一個最佳解 \mathbf{x}，即目標函數值最小。令 \mathbf{v}_1,\ldots,\mathbf{v}_k 是可行域 S 的端點。使用可行解表達式，

\displaystyle \mathbf{x}=\mathbf{d}+\sum_{i=1}^k\beta_i\mathbf{v}_i，

其中 \beta_1+\cdots+\beta_k=1 且 \beta_i\ge 0，i=1,\ldots,k。上式中，\mathbf{d}=\mathbf{0} 或 \mathbf{d}\ge\mathbf{0}。將上式代入目標函數，

\displaystyle \mathbf{c}^T\mathbf{x}=\mathbf{c}^T\mathbf{d}+\sum_{i=1}^k\beta_i\mathbf{c}^T\mathbf{v}_i。

下面證明 \mathbf{c}^T\mathbf{d}=0。如果 \mathbf{c}^T\mathbf{d}<0，則當 \alpha>1，\mathbf{x}_\alpha=\alpha\mathbf{d}+\sum_{i=1}^k\beta_i\mathbf{v}_i 的目標函數值為

\displaystyle \mathbf{c}^T\mathbf{x}_\alpha=\alpha\mathbf{c}^T\mathbf{d}+\sum_{i=1}^k\beta_i\mathbf{c}^T\mathbf{v}_i<\mathbf{c}^T\mathbf{x}。

可行解 \mathbf{x}_\alpha 的目標函數值小於 \mathbf{x} 的目標函數值，這與假設矛盾。如果 \mathbf{c}^T\mathbf{d}>0，則

\displaystyle \mathbf{c}^T\mathbf{x}>\mathbf{c}^T\left(\sum_{i=1}^k\beta_i\mathbf{v}_i\right)。

但 \mathbf{y}=\sum_{i=1}^k\beta_i\mathbf{v}_i 是一個可行解，同樣與假設矛盾。故推論 \mathbf{c}^T\mathbf{d}=0，即有 \mathbf{c}^T\mathbf{x}=\mathbf{c}^T\mathbf{y}。設 \mathbf{c}^T\mathbf{v}_j=\min_i\mathbf{c}^T\mathbf{v}_i，使用凸組合性質，

\displaystyle \mathbf{c}^T\mathbf{y}=\sum_{i=1}^k\beta_i\mathbf{c}^T\mathbf{v}_i\ge\sum_{i=1}^k\beta_i\mathbf{c}^T\mathbf{v}_j=\mathbf{c}^T\mathbf{v}_j。

因為 \mathbf{y} 是一個最佳解，迫使 \mathbf{c}^T\mathbf{y}=\mathbf{c}^T\mathbf{v}_j，即知端點 \mathbf{v}_j 是一個最佳解，故證明存在最佳基可行解。

 
最佳基可行解定理表明：求解一個線性規劃問題僅需檢視基可行解，也就是可行域的端點。反過來說，是否必須逐一檢查可行域的所有端點才能找出最佳解？答案是：無此必要，原因在於我們所處理最佳化問題具備凸性。這將是我們下一回要探討的主題。

繼續閱讀：
This entry was posted in 線性代數專欄, 應用之道 and tagged , , , , , , , . Bookmark the permalink.

Leave a comment