单形表的矩阵形式.PPT

作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 範例4.6 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 範例4.6 作業研究 二版 Ch.4 線性規劃的其他演算法 作業研究 二版 Ch.4 線性規劃的其他演算法 作業研究 二版 Ch.4 線性規劃的其他演算法 第四章 線性規劃的其他演算法 Special Simplex Method ? 廖慶榮 作業研究 二版 2009 p.*/30 章節大綱 前言 單形表的矩陣形式 修正單形法 反函數的乘積形式 上限技巧 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 4.2 單形表的矩陣形式 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 4.2 單形表的矩陣形式 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 4.2 單形表的矩陣形式 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 4.2 單形表的矩陣形式 作業研究 二版 Ch.4 線性規劃的其他演算法 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 單形表的矩陣形式I 根據式(3)與(5)，可建立矩陣形式I 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 單形表的矩陣形式II 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 單形表中各項係數的含意 範例4.1 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 直接建立特定BV的單形表(1/4) 範例4.2 此問題是否有以（ ）為基變數的基解？若有，建立該基解的單形表，並判斷是否為BFS，以及是否為最佳解。 須特別注意基變數的順序，因其會影響結果 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 直接建立特定BV的單形表(2/4) 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 直接建立特定BV的單形表(3/4) 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 直接建立特定BV的單形表(4/4) 因Z列係數已無負值，所以是最佳單形表 p.*/30 4.3 修正單形法 由單形表的矩陣形式I，可發覺： Z欄始終不變，所以可不必寫出。 欄的係數固定，所以可不必寫出。 欄除了Z列係數外，僅會使用到進入變數的係數，其餘不會用到。 因此，單形表可簡化為修正單形表（revised simplex tableau） 作業研究 二版 Ch.4 線性規劃的其他演算法 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 範例4.3（修正單形法） 解答： 表1： 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 範例4.3（修正單形法） 計算所有NBV的Z列係數： 因仍有負值，非最佳解。選擇 為進入變數，並計算： 我們可將此進入變數的係數寫在修正單形表的右方（參見表1）。選擇具最小比率的為離開變數。 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 範例4.3（修正單形法） 建立2nd修正單形表： 方法1：高斯消去法 方法2：矩陣 表2： ■ 表3: (opt) p.*/30 4.4 反函數的乘積形式 反函數的乘積形式 product form of the inverse 計算 的特殊技巧 大多數的LP電腦軟體採用修正單形法，並用反函數的乘積形式 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 4.4 反函數的乘積形式 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 4.4 反函數的乘積形式 計算上式等號右方的第一個反矩陣： 因此 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 4.4 反函數的乘積形式 由於 ，因此 上式稱為反函數的乘積形式 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 4.4 反函數的乘積形式 若 （第一欄改變），則 若 （第三欄改變），則 作業研究 二版 Ch.4 線性規劃的其他演算法 作業研究 二版 Ch.4 線性規劃的其他演算法 p.*/30 範例4.4 若