Simplex Method problem

自由自在的方法是其實是「窮舉」﹐與中四教科書上所說的圖解法或者是最優解必在頂點上沒有本質上的不同。但既然版大指明要用「Simplex Method 」單純形法﹐我在這裡嘗試做一次看看。

以下的方法是根據劉實陽「作業研究」一書的程序做的。先將問題化成

Maximise Z - 3x_1 - 2x_2
Subject to
2x_1 + x_2 + x_3 = 18
2x_1 + 3x_2 + x_4 = 42
3x_1 + x_2 + x_5 = 24

然後單純形表就是
B z x_1 x_2 x_3 x_4 x_5 RHS
z 1 -3 -2 0 0 0 0
x_3 0 2 1 1 0 0 18
x_4 0 2 3 0 1 0 42
x_5 0 3 1 0 0 1 24

因-3最小﹐所以選x_1﹐計系數比得(9,21,8),8最小﹐故選x_5出來﹐換入x_1﹐再用高斯消去法重新整理單純形表。

B z x_1 x_2 x_3 x_4 x_5 RHS
z 1 0-1 0 0 1 24
x_3 0 0 1/3 0 0 -2/3 2
x_4 0 07/3 0 0 -2/3 26
x_5 0 11/3 0 0 1/3 8

因-1最小﹐所以選x_2﹐計系數比得6最小﹐故選x_3出來﹐換入x_2﹐再用高斯消去法重新整理單純形表。

B z x_1 x_2 x_3 x_4 x_5 RHS
z 1 0 0 0 0 -1 30
x_2 0 0 1 0 0 -2 6
x_4 0 00 0 0 4 12
x_1 0 10 0 0 1 6

因-1最小﹐所以選x_5﹐計系數比得3最小﹐故選x_4出來﹐換入x_5﹐再用高斯消去法重新整理單純形表。

B z x_1 x_2 x_3 x_4 x_5 RHS
z 1 0 0 0 0 0 33
x_2 0 0 1 0 0 0 12
x_4 0 00 0 0 1 3
x_1 0 10 0 0 0 9

因為沒有係數為負﹐故停止。此時最優解為x_1=9﹐x_2=12﹐z=33。注意到x_4非0﹐即條件二沒有飽和﹐在經濟學上對其有進一步發明﹐但這是另一個story。