simplex method 變形

大於、等於的處理

使用 M

Minimization 最小目標

1. +M
2. Cj-Zj改為判斷最小值 
(同時停止目標變成 >=0 時)

Alternate Optima 多重解

• 說明:

找到兩個 basic feasible solution

• 注意:

解到最後一張表之後
當底下Cj-Zj有發現"非"當時basic variable 也為0時
表示可以在”增益為0“的情況下進行代換
既然"增益為0"，也表示最佳解被"保持一樣的值"
但我們可透過代換找到不同的數字也得到"一樣的最大值"
所以為多重解

Unbounded solution 最大值無限大，無法找到

• 說明:

解在開放區域
解到theta皆為負

• 注意:

theta為負表示資源可以不受限制的取用，
這樣的話我們可以無限的使最大值增加，
這樣的題目本身是不合理的(最大資源量應該有限制)，
此為Unbounded solution(並非無解，而是解可以到無限大)

infeasible problems 無解問題

• 說明:

解完，M未消失

• 注意:

M未消失，表示為infeasible，點在解區域外，為無解。

unrestricted variables 無限制答案範圍的解

• 說明:

當變數可有負數解時
X1 = X11 - X12, X11,X12 >= 0

two-phase method 二階解(另解)

• 說明:

可以視為 simplex method 的另解

• Q:為什麼要有這個另解?

A:在很多時候我們很難去定義M到底是什麼，或說M到底有多大
這在某些狀況會產生很大的問題，例如你要怎麼告訴電腦M是什麼?

★Phase1 - 處理人工變數(單純來說就是在沒用M的情況下照解)

利用Min必須為最小的特性(逆向操作：Max不可為負)，
當只有人工變數係數為正，為了使答案最小，人工變數的值必須為0

★銜接Phase2 - 判斷情況

1. Min不等於0 - 此題無解
2. Min等於0，人工變數答案為0 - 此題有解(進入Phase2階段)
3. Min等於0，人工變數答案不為0 - 此題有解(進入Phase2階段)，且有冗限制式(不重要的限制式)

★Phase2 - 因為M在Phase1被處理掉了，我們可以回歸正常的解法