➣ Reading Time: 9 minutes

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(綠色)

  • 運算規則:
  1. 找pivot column(藍色):找Ci-zi的row最大數字
  • 觀念:

我們希望能找到能讓目標增加最大的變數(如同跑得快的車子會比跑得慢的車子更快到達終點),我們這裡挑選X1,因為他一次(增加1)就能幫我們增加12,而X2一次(增加1)只能幫我們增加8,我們優先挑增加最多的,當然能比較快達到目標。

  1. 計算Θ,再找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(綠色)

  • 運算規則:
  1. 找pivot column(藍色):找Ci-zi的row最大數字

我們找到了2

  1. 計算Θ,再找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(紫色部分)

⭐管理科學/作業研究 MS/OR – 相關文章連結整理⭐:
1.【管理科學】 LP 問題, LP problem, LP solution procedure 第一次期中考筆記
2.【管理科學】 IP problem, 條件式 IP problems (either-or, if-then problem) 第一次期中考筆記
3.【管理科學】 solve LP problems, simplex method 詳細步驟與觀念 圖文說明講解 第二次期中考筆記
4.【管理科學】 simplex method 變形, two-phase method 二階解(另解) 第二次期中考筆記
5.【管理科學】 Duality & Postoptimality Analysis (敏感度分析) 期末考筆記
6.【管理科學】 運輸問題 (Transportation problem) 期末考筆記
⭐【喜歡我的文章嗎? 歡迎幫我按讚~ 讓基金會請創作者喝一杯咖啡!
如果喜歡我的文章,請幫我在下方【按五下Like】 (Google, Facebook 免註冊),會由 「LikeCoin」 贊助作者鼓勵繼續創作,讀者們「只需幫忙按讚,完全不用出錢」哦!

likecoin-steps