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(紫色部分)
