線性規劃的其他演算法 Special Simplex Method

Presentation on theme: "線性規劃的其他演算法 Special Simplex Method"— Presentation transcript:

1 線性規劃的其他演算法 Special Simplex Method
第四章 線性規劃的其他演算法 Special Simplex Method 作業研究 二版 2009 © 廖慶榮

2 章節大綱 前言 單形表的矩陣形式 修正單形法 反函數的乘積形式 上限技巧 作業研究 二版 Ch.4 線性規劃的其他演算法

3 4.2 單形表的矩陣形式 作業研究 二版 Ch.4 線性規劃的其他演算法

4 4.2 單形表的矩陣形式 作業研究 二版 Ch.4 線性規劃的其他演算法

5 4.2 單形表的矩陣形式 作業研究 二版 Ch.4 線性規劃的其他演算法

6 4.2 單形表的矩陣形式 作業研究 二版 Ch.4 線性規劃的其他演算法

7 單形表的矩陣形式I 根據式(3)與(5)，可建立矩陣形式I 作業研究 二版 Ch.4 線性規劃的其他演算法

8 單形表的矩陣形式II 作業研究 二版 Ch.4 線性規劃的其他演算法

9 單形表中各項係數的含意 範例4.1 作業研究 二版 Ch.4 線性規劃的其他演算法

10 直接建立特定BV的單形表(1/4) 範例4.2 此問題是否有以（ ）為基變數的基解？若有，建立該基解的單形表，並判斷是否為BFS，以及是否為最佳解。 須特別注意基變數的順序，因其會影響結果 作業研究 二版 Ch.4 線性規劃的其他演算法

11 直接建立特定BV的單形表(2/4) 作業研究 二版 Ch.4 線性規劃的其他演算法

12 直接建立特定BV的單形表(3/4) 作業研究 二版 Ch.4 線性規劃的其他演算法

13 直接建立特定BV的單形表(4/4) 因Z列係數已無負值，所以是最佳單形表 作業研究 二版 Ch.4 線性規劃的其他演算法

14 4.3 修正單形法 由單形表的矩陣形式I，可發覺： Z欄始終不變，所以可不必寫出。 欄的係數固定，所以可不必寫出。
4.3 修正單形法 由單形表的矩陣形式I，可發覺： Z欄始終不變，所以可不必寫出。 欄的係數固定，所以可不必寫出。 欄除了Z列係數外，僅會使用到進入變數的係數，其餘不會用到。 因此，單形表可簡化為修正單形表（revised simplex tableau） 作業研究 二版 Ch.4 線性規劃的其他演算法

15 範例4.3（修正單形法） 解答： 表1： 作業研究 二版 Ch.4 線性規劃的其他演算法

16 範例4.3（修正單形法） 計算所有NBV的Z列係數： 因仍有負值，非最佳解。選擇 為進入變數，並計算：
因仍有負值，非最佳解。選擇 為進入變數，並計算： 我們可將此進入變數的係數寫在修正單形表的右方（參見表1）。選擇具最小比率的為離開變數。 作業研究 二版 Ch.4 線性規劃的其他演算法

17 範例4.3（修正單形法） 建立2nd修正單形表： 表2： ■ 表3: (opt) 方法1：高斯消去法 方法2：矩陣
作業研究 二版 Ch.4 線性規劃的其他演算法

18 4.4 反函數的乘積形式 反函數的乘積形式 大多數的LP電腦軟體採用修正單形法，並用 反函數的乘積形式
4.4 反函數的乘積形式 反函數的乘積形式 product form of the inverse 計算 的特殊技巧 大多數的LP電腦軟體採用修正單形法，並用 反函數的乘積形式 作業研究 二版 Ch.4 線性規劃的其他演算法

19 4.4 反函數的乘積形式 作業研究 二版 Ch.4 線性規劃的其他演算法

20 4.4 反函數的乘積形式 計算上式等號右方的第一個反矩陣： 因此 作業研究 二版 Ch.4 線性規劃的其他演算法

21 4.4 反函數的乘積形式 由於 ，因此 上式稱為反函數的乘積形式 作業研究 二版 Ch.4 線性規劃的其他演算法

22 4.4 反函數的乘積形式 若 （第一欄改變），則 （第三欄改變），則 作業研究 二版 Ch.4 線性規劃的其他演算法

23 範例4.4 若 及 ，則 因此 作業研究 二版 Ch.4 線性規劃的其他演算法

24 4.5 上限技巧 作業研究 二版 Ch.4 線性規劃的其他演算法

25 4.5 上限技巧 當進入變數增加時，要同時考慮三種情況：
4.5 上限技巧 當進入變數增加時，要同時考慮三種情況： 一個BV降為零 一個BV增至其上限 進入變數本身增至其上限 然後選擇最先發生的變數為離開變數。 因BV有可能增至上限（情況2）而成為NBV， 所以當該BV有上限限制時，進入變數欄內負的 係數亦要考慮 作業研究 二版 Ch.4 線性規劃的其他演算法

26 範例4.5 使用上限技巧僅需2個限制式，否則需4個 作業研究 二版 Ch.4 線性規劃的其他演算法

27 範例4.5 /表1-2 作業研究 二版 Ch.4 線性規劃的其他演算法

28 範例4.5 /表3-4 作業研究 二版 Ch.4 線性規劃的其他演算法

29 範例4.6 作業研究 二版 Ch.4 線性規劃的其他演算法

30 範例4.6 作業研究 二版 Ch.4 線性規劃的其他演算法