➣ Reading Time: 4 minutes

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被處理掉了,我們可以回歸正常的解法

 ⭐管理科學/作業研究 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) 期末考筆記