什麼是線性規劃?
簡單說就是 目標成本函數(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) 如下：
========================
\[\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)來生產這四種產品，分別是
- 工人工時 (man weeks ) (以周計)
- 原料A (kilograms of material A) (以公斤計)、
- 原料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
沒有留言:
張貼留言