跳到主要內容

[最佳化] 淺談線性規劃(4)- How to move from one Basic Feasible solution to another- An Example

延續前篇,我們現在手上有了 LP問題的基本定理:

=================================
Theorem (Fundamental Theorem of LP):
考慮標準型式的線性規劃 (Standard 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$ 為 $m \times n$ 矩陣且 $n>m$, $rank(A) = m$,$A$ 沒有全為零的column$;b \geq 0$,
1. 若其存在一個 Feasible Solution,則必存在一個 Basic + Feasible 的解
2. 若其存在一個optimal + feasible solution,則必定存在一個optimal basic + feasible solution 。
=================================

現在我們來看看線性規劃的一些例子:

Example:
考慮如下 LP 問題:
\[\begin{array}{l}
\max \left( {3{u_1} + 5{u_2}} \right)\\
s.t.\\
\left\{ \begin{array}{l}
{u_1} + 5{u_2} \le 40\\
2{u_1} + {u_2} \le 20\\
{u_1} + {u_2} \le 12
\end{array} \right.\\
{u_i} \ge 0,i = 1,2
\end{array}
\]首先將其改寫成標準型式LP問題: (引入 slack variable $y_3, y_4, y_5 \geq 0$)
\[\begin{array}{l}
\min \left( { - 3{u_1} - 5{u_2}} \right)\\
s.t.\\
\left\{ \begin{array}{l}
{u_1} + 5{u_2} + {y_3} = 40\\
2{u_1} + {u_2} + \begin{array}{*{20}{c}}
{}
\end{array}{y_4} = 20\\
{u_1} + {u_2} + \begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}{y_5} = 12
\end{array} \right.\\
{u_i} \ge 0,i = 1,2,3,4,5
\end{array}\]定義 $x := [x_1 \ x_2 \ x_3 \ x_4 \ x_5 ]^T = [u_1 \ u_2 \ y_1 \ y_2 \ y_3 ]^T $ 我們得到標準型LP問題如下
\[\begin{array}{l}
\min \left( { - 3{x_1} - 5{x_2}} \right)\\
s.t.\\
\left\{ \begin{array}{l}
{x_1} + 5{x_2} + {x_3} = 40\\
2{x_1} + {x_2} + \begin{array}{*{20}{c}}
{}
\end{array}{x_4} = 20\\
{x_1} + {x_2} + \begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}\begin{array}{*{20}{c}}
{}
\end{array}{x_5} = 12
\end{array} \right.\\
{x_i} \ge 0,i = 1,2,3,4,5
\end{array}\]
注意到我們可以把拘束條件改寫為
\[\begin{array}{l}
{x_1}\left[ {\begin{array}{*{20}{c}}
1\\
2\\
1
\end{array}} \right] + {x_2}\left[ {\begin{array}{*{20}{c}}
5\\
1\\
1
\end{array}} \right] + {x_3}\left[ {\begin{array}{*{20}{c}}
1\\
0\\
0
\end{array}} \right] + {x_4}\left[ {\begin{array}{*{20}{c}}
0\\
1\\
0
\end{array}} \right] + {x_5}\left[ {\begin{array}{*{20}{c}}
0\\
0\\
1
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{40}\\
{20}\\
{12}
\end{array}} \right]\\
{x_i} \ge 0,i = 1,2,3,4,5
\end{array}
\]且 $x= [0, 0, 40, 20, 12]^T$ 為一個 feasible solution 且 為一個 Extreme point (由之前文章的定理可知Exterme Point $\Leftrightarrow$ Basic Feasible Solution)。但是如果我們選此 $x$則我們的cost :$-3 x_1 - 5 x_2 = -3 \cdot 0 + -5 \cdot 0 =0$。亦即此cost並不是minimum,故我們需要在其他 Extreme Point 中尋找最佳解。

想法: 從一個 Extreme Point 移動到另一個 Exterme Point 使得我們的cost 可以逐步降低。

故由 $x= [0, 0, 40, 20, 12]^T$ 開始,我們有
\[{0\underbrace {\left[ {\begin{array}{*{20}{c}}
1\\
2\\
1
\end{array}} \right]}_{{a_1}} + 0\underbrace {\left[ {\begin{array}{*{20}{c}}
5\\
1\\
1
\end{array}} \right]}_{{a_2}} + 40\underbrace {\left[ {\begin{array}{*{20}{c}}
1\\
0\\
0
\end{array}} \right]}_{{a_3}} + 20\underbrace {\left[ {\begin{array}{*{20}{c}}
0\\
1\\
0
\end{array}} \right]}_{{a_4}} + 12\underbrace {\left[ {\begin{array}{*{20}{c}}
0\\
0\\
1
\end{array}} \right]}_{{a_5}} = \left[ {\begin{array}{*{20}{c}}
{40}\\
{20}\\
{12}
\end{array}} \right]} \\
\Rightarrow 0 a_1 + 0 a_2 + 40 a_3 +20 a_4 + 12 a_5 = b
\]現在為了要選取下一個鄰近的 Extreme Point,我們選 $a_1$ column 做為新的基底。然後我們需要把現有的舊的基底 $a_3, a_4, a_5$ 中剔除一個。那麼該怎麼做呢? 方法如下:

首先把 $a_1$ 用舊基底線性組合來表示:
\[
a_1 = 1 a_3 + 2 a_4 + 1 a_5
\]對上式兩邊同乘 $\varepsilon_1 >0$,我們可得
\[{{\varepsilon _1}{a_1} = {\varepsilon _1}{a_3} + 2{\varepsilon _1}{a_4} + {\varepsilon _1}{a_5}}
\]現在把上式加到 $(*)$ 並整理如下:
\[\begin{array}{l}
\left( {{\varepsilon _1}{a_1} - {\varepsilon _1}{a_3} - 2{\varepsilon _1}{a_4} - 1{\varepsilon _1}{a_5}} \right) + \left( {0{a_1} + 0{a_2} + 40{a_3} + 20{a_4} + 12{a_5}} \right) = 0 + b\\
 \Rightarrow \left( {{\varepsilon _1} + 0} \right){a_1} + 0{a_2} + \left( {40 - {\varepsilon _1}} \right){a_3} + \left( {20 - 2{\varepsilon _1}} \right){a_4} + \left( {12 - 1{\varepsilon _1}} \right){a_5} = b
\end{array}
\] 那麼現在我們想要選 $\varepsilon_1$ 使得 上式的係數都非負,且同時舊的基底 $a_3, a_4, a_5$ 其中一個的係數變成零 (這樣我們就可以把舊的基底其中一個換成新基底 $a_1$)。觀察上式可以發現選舊的基底 $a_3, a_4, a_5$ 對應的係數中最小的, 亦即我們要選 $\varepsilon_1 = 10$ (替換 $a_4$ 基底)。故得到
\[
 \Rightarrow 10{a_1} + 0{a_2} + 30{a_3} + 0{a_4} + 2{a_5} = b
\]其對應的 Basic Feasible Solution (Extreme Point) 為
\[
[10, 0, 30, 0, 2]^T
\]且此時我們的Cost: $-3 x_1 - 5 x_2 = -30$,亦即從原本的 $0$ 降低到 $-30$。

接著我們重複上述步驟在移動到下一個鄰近的Extreme Point,希望可以再降低我們的Cost 。這次我們選 $a_2$ 做為新的基底,故我們讓 $a_2$ 用現有的基底 $a_1, a_3, a_5$表示:
\[
a_2 = 1/2 a_1 + 9/2 a_3 + 1/2 a_5 \ \ \ \ (**)
\]接著對上式兩邊同乘 $\varepsilon_2 >0$,我們可得
\[{{\varepsilon _2}{a_2} = \frac{1}{2}{\varepsilon _2}{a_1} + \frac{9}{2}{\varepsilon _2}{a_3} + \frac{1}{2}{\varepsilon _2}{a_5}}
\]把上式 與 $(**)$ 相加
\[ \Rightarrow \left( {10 - \frac{1}{2}{\varepsilon _2}} \right){a_1} + {\varepsilon _2}{a_2} + \left( {30 - \frac{9}{2}{\varepsilon _2}} \right){a_3} + 0{a_4} + \left( {2 - \frac{1}{2}{\varepsilon _2}} \right){a_5} = b
\]同之前步驟,我們需要把 現有基底 $a_1, a_3, a_5$ 中踢出一個,故應選 $\varepsilon_2$ 使得 上式的係數都非負,且同時舊的基底 $a_1, a_3, a_5$ 其中一個的係數變成零;觀察上式發現應選 $\varepsilon_2 = 4$,我們得到
\[ \Rightarrow 8{a_1} + 4{a_2} + 12{a_3} + 0{a_4} + 0{a_5} = b
\]此時對應的解為
\[
[8, 4, 12, 0, 0]^T
\]且對應的 Cost: $ -3 x_1 -5 x_2 = -44$亦即又比剛剛的 $-30$ 更小。現在我們再重複上述例子,這次我們選 $a_4$做為新的替換基底並將其用舊的基底表示為
\[
a_4 = a_1 - a_2 +4 a_3
\]接著對上式兩邊同乘 $\varepsilon_3 >0$,並將其與原有的基底相加可得
\[
(8-\varepsilon_3) a_1 + (4 + \varepsilon_3) a_2 +(12 - 4 \varepsilon_3) a_3 + \varepsilon_3 a_4 = b
\]觀察上式,我們應選 $\varepsilon_3 = 3$,故得到
\[
5 a_1 + 7 a_2 +0 a_3 + 3 a_4 = b
\]故對應的解為
\[
[5, 7, 0, 3, 0]^T
\]此時對應的 Cost 為 $ -3 x_1 -5 x_2 = -50$且此即為對此 標準LP問題的最佳解,故我們的最佳解對原本問題即為 $x^* = [x_1, x_2]= [u_1, u_2] = [5, 7]$。 $\square$

上述的方法:從一個Extreme point 到另一個 Extreme Point的方法,亦會在之後的 Simplex Method 中再做詳細的介紹。

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

留言

這個網誌中的熱門文章

[數學分析] 什麼是若且唯若 "if and only if"

數學上的 if and only if  ( 此文不討論邏輯學中的 if and only if,只討論數學上的 if and only if。) 中文翻譯叫做  若且唯若 (or 當且僅當) , 記得當初剛接觸這個詞彙的時候,我是完全不明白到底是甚麼意思,查了翻譯也是愛莫能助,畢竟有翻跟沒翻一樣,都是有看沒有懂。 在數學上如果看到 if and only if  這類的句子,其實是表示一種 雙條件句 ,通常可以直接將其視為" 定義(Definition)" 待之,今天要分享的是這樣的一個句子如何用比較直觀的方法去看他 假設我們現在有 兩個邏輯陳述句 A 與  B. 注意到,在此我們不必考慮這兩個陳述句到底是什麼,想表達什麼,或者到底是否為真(true),這些都不重要。只要知道是兩個陳述即可。 現在,考慮新的陳述:  "A if and only if B" 好了,現在主角登場,我們可以怎麼看待這個句子呢? 事實上我們可以很直覺的把這句子拆成兩部分看待,也就是 "( A if B ) and ( A only if B )" 那麼先針對第一個部分  A if B  來看, 其實這句就是說  if B then A, 更直白一點就是 "if B is true, then A is also true".  在數學上等價可以寫為 "B implies A" .  或者更常用一個箭頭符號來表示 "B $\Rightarrow$  A"  現在針對第二個部分  A only if B 此句意指  "If B is not true, then A is also not true". 所以如果已知 A is true,  那麼按照上句不難推得 B is also true 也就是說  A only if B  等價為 "If A is true then B is also true". 同樣,也可以寫作   "A implies B"   或者用箭頭表示  "A   $\Rightarrow$     B".

[數學分析] 淺談各種基本範數 (Norm)

這次要介紹的是數學上一個重要的概念: Norm: 一般翻譯成 範數 (在英語中 norm 有規範的意思,比如我們說normalization就是把某種東西/物品/事件 做 正規化,也就是加上規範使其正常化),不過個人認為其實翻譯成 範數 也是看不懂的...這邊建議把 Norm 想成長度就好 (事實上norm是長度的抽象推廣), 也許讀者會認為好端端的長度不用,為何又要發明一個 norm 來自討苦吃?? 既抽象又艱澀。 事實上想法是這樣的: 比如說現在想要比較兩個數字 $3$ , $5$ 之間的大小,則我們可以馬上知道 $ 3 < 5 $;同樣的,如果再考慮小數與無理數如 $1.8753$ 與 $\pi$,我們仍然可以比較大小 $1.8753 < \pi = 3.1415...$ 故可以發現我們有辦法對 "純量" 做明確的比大小,WHY? 因為前述例子中 $3$, $5$, $1.8753$ or $\pi$ 其各自的大小有辦法被 "measure "! 但是如果是現在考慮的是一組數字 我們如何去measure 其大小呢?? 比如說 \[x:=[1, -2, 0.1, 0 ]^T \]上式的大小該是多少? 是 $1$? $-2$? $0.1$??? 再者如果更過分一點,我們考慮一個矩陣 \[A = \left[ {\begin{array}{*{20}{c}} 1&2\\ 3&4 \end{array}} \right] \],想要知道這個矩陣的大小又該怎麼辦?? 是 $1$ ? $2$ 還是 $4$ ?..其實現階段我們說不清楚。 也正是如此,可以發現我們確實需要新的 "長度" 的定義來幫助我們如何去 measure 矩陣/向量/甚至是函數的大小。 故此,我們首先定義甚麼是Norm,(也就是把 "長度" or "大小" 的本質抽離出來) ================== Definition: Norm 考慮 $V$ 為一個向量空間(Vector space),則我們說  Norm 為一個函數 $||\cdot|| : V \rightarrow \mathbb{R}$ 且滿足下列性質