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

本文的閱讀等級:中級

考慮線性規劃標準型問題

\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 0i=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}_2S 的無界方向,不難證明 \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 0i=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 0i=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 是一個最佳解,故證明存在最佳基可行解。

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

繼續閱讀:
Advertisements
本篇發表於 線性代數專欄, 應用之道 並標籤為 , , , , , , , 。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s