solve LP problems
exterme points
- 概念:畫圖求解
basic solutions
- 概念:變數嘗試代點0
simplex method
由George B. Dantzig.所提出
-> Hill-Climbing Method
例題:
Max f. = 12X1+8X2
5X1+2X2<=150
2X1+3X2<=100
4X1+2X2<=80
ROUND1
步驟1:以上面敘述建表
步驟2:完成zi,Ci-zi欄,判斷是否找到解
- 運算規則:
1.Ca那個column乘上右側Xi,加總後得zi
2.Xi上方數字減zi得到Ci-zi
- 判斷解:
Ci-zi那一個row如果還有數字為正,表示還能夠再增加(未找到最佳解)
- 概念:
增加效益為正,為負表示硬增加只會讓Max更少
- 範例(藍色部分):
1. zi = 0*5+0*2+0*4 = 0
2. Ci-zi = 12-0 = 12
步驟3:(如果還未找到最佳解)挑選pivot column(藍色),計算Θ,再找pivot row(綠色)
- 運算規則:
- 找pivot column(藍色):找Ci-zi的row最大數字
- 觀念:
我們希望能找到能讓目標增加最大的變數(如同跑得快的車子會比跑得慢的車子更快到達終點),我們這裡挑選X1,因為他一次(增加1)就能幫我們增加12,而X2一次(增加1)只能幫我們增加8,我們優先挑增加最多的,當然能比較快達到目標。
- 計算Θ,再找pivot row(綠色):pivot column乘上Θ等於b
- 觀念:
雖然是選擇最快的車,但也不代表我們可以無限的衝刺,原先的限制式幫我們限制了X1能增加的極限,如同上面的例子中:
X3 row:X1*30=150
X4 row:X1*50=100
X5 row:X1*20=80
算出來就是Θ,表示如果那行全部投資在X1可以達到的上限,我們可以發現X1最多就是增加20(再多就會超過X5 row的限制了),而X5 row在此就成為我們的pivot row(綠色)
- 補充:
theta<0 的意義為 “這個限制式讓你有足夠的餘裕,你可以無限的增加”
theta=0 的意義為 “這個限制式我不影響你”
步驟4:我們利用最後所找到的pivot column與pivot row再次重新出發
以上面例子來說,我們找到的是 X1(pivot column) 與 X5(pivot row),
我們將這兩個做交換如下(注意Ca有變),
交換後因為Θ、zi、Ci-zi的資訊是屬於舊的,我們可以直接刪去以免造成計算上的混亂 :
步驟5:玩弄你的數學!透過矩陣運算,將屬於Xa那個column的對應係數都調成1且其他係數為0
詳細過程我們做了什麼?
1. X1 row /4
2. X3 row - (新X1 row*5)
3. X4 row - (新X1 row*2)
好的,這回合我們找到了解 (X1,X2,X3,X4,X5) = (20,0,50,60,0),
我們沒有找到最佳解,但沒關係,我們已經離解答接近了一步,
我們利用最後所找到的pivot column與pivot row再次重新出發。
ROUND2
步驟1:我們現在的表長這樣
步驟2:完成zi,Ci-zi欄,判斷是否找到解
- 運算規則:
1.Ca那個column乘上右側Xi,加總後得zi
2.Xi上方數字減zi得到Ci-zi
- 判斷解:
Ci-zi那一個row如果還有數字為正,表示還能夠再增加(未找到最佳解)
- zi(黃色部份):只有12有值,只需特別計算那個row(藍色部分)
- Ci-zi(綠色部分):等於圖上紅色部分減黃色部分
補充:
Ci-zi為增加的效益
上方我們找到 12 , 8
但此處我們找到 卻不是8而是2
因為限制式開始讓我們想增加購買X2的量時
必須付出相對的代價
我們拿一個X2確實增加了8
但也必須付出代價6
所以實際拿一個X2變成只能增加2的效益
步驟3:(如果還未找到最佳解)挑選pivot column(藍色),計算Θ,再找pivot row(綠色)
- 運算規則:
- 找pivot column(藍色):找Ci-zi的row最大數字
我們找到了2
- 計算Θ,再找pivot row(綠色):pivot column乘上Θ等於b
X3 row:X2*X3Θ=50
-1/2*X3Θ=50
X3Θ = -100
X4 row:X2*X4Θ=60
2*X4Θ=60
X4Θ = 30
X1 row:X2*X1Θ=20
1/2*X1Θ=20
X1Θ = 40
算出來的Θ,我們可以發現X2最多就是增加30(再多就會超過X4 row算式的限制了),而X4 row在此就成為我們的pivot row(綠色)
步驟4:我們利用最後所找到的 pivot column 與 pivot row 再次重新出發
以上面例子來說,我們找到的是X2(pivot column)與X4(pivot row),
我們將這兩個做交換如下(注意Ca有變),
交換後因為Θ、zi、Ci-zi的資訊是屬於舊的,我們可以直接刪去以免造成計算上的混亂 :
步驟5:玩弄你的數學!透過矩陣運算,將屬於Xa那個column的對應係數都調成1且其他係數為0
詳細過程我們做了什麼?
1. X2 row /2
2. X3 row + (新X2 row*1/2)
3. X1 row - (新X2 row*1/2)
好的,這回合我們找到了解 (X1,X2,X3,X4,X5) = (5,30,65,0,0),
這回合我們沒有找到最佳解,但沒關係,我們已經離解答又更接近了一步,
我們利用最後所找到的pivot column與pivot row再次重新出發。
ROUND3
步驟1:我們現在的表長這樣
步驟2:完成zi,Ci-zi欄,判斷是否找到解
- 運算規則:
1. Ca那個column乘上右側Xi,加總後得zi
2. Xi上方數字減zi得到Ci-zi
- 判斷解:
Ci-zi那一個row如果還有數字為正,表示還能夠再增加(未找到最佳解)
好的,我們發現Ci-zi那一個row的數值已經都小於0,這也表示無法再增加值(無法找到更好的解)
所以我們找到了解 (X1,X2,X3,X4,X5) = (5,30,65,0,0),
也表示我們找到了答案,答案為X1=5,X2=30(紫色部分)