单形法.PPT

第一節　單形法 第二節　大M法(Big M method) 第三節　極小化問題 第四節　線性規劃解的各種情形 第五節　雙階段法(Two-phase Method) 第六節　其他相關問題 單形法是由美國 George B. Dantzig 教授發展出來的一套方法，是一種重複運算程序，得出最佳解為止。 下述是單形法建立之基礎 各可行解之集合為一凸集合(Convex set)。 若有一可行解存在，則必須有一基礎可行解，該基礎可行解對應於凸集合之一個端點(Extreme point)。 基礎可行解存在的個數為有限個。 若目標函數之極大值(或極小值)為一有限值，則至少有一個最佳解的基礎可行解。 求線性規劃問題解時，求得最佳解的過程反覆計算次 數不會超過　　。 第一節　單形法 單形法解題：將數學模型之標準型以表列方式表示，其單形法表為 單形法相關名詞說明 基礎變數(Basic variable) 非基礎變數(Nonbasic variable) 軸運算(Pivot operation) 基礎解(Basic solution) 基礎可行解(Basic feasible solution) 非退化(Nondegenerate)的基礎可行解 退化的基礎可行解 利用單形法解線性規劃之極大值問題的步驟 第一步：將數學模式寫成標準型。 第二步：找出一個起始基礎可行解。 第三步：檢驗第二步所得的解是否為最佳解── 計算非基礎變數之相對利潤(Relative profit) cj－zj，當此相對利潤 cj－zj 都小於或等於零(即cj－zj≦0)時，則現階段的解就是最佳解，否則進入第四步。 第四步：決定新的代入變數(Entering variable) ── 選取非基礎變數之相對利潤 cj－zj 為最大正數者。在單形法表中，代入變數所在的行稱為樞行(Pivot column)。 第五步：決定新的代出變數(Leaving variable) ── 選出代入變數所在的行除右邊常數項，而其比值為最小非負數者(負數不允考慮)的變數稱為代出變數，此即最小比值法則(Minimum ratio rule)。在單形法表中，代出變數所在的列稱為樞列(Pivot row)。 第六步：決定新的基礎可行解 ── 利用矩陣的基本列運算高斯－喬登 (Gauss-Jordan) 消去法成典型方程組 (Canonical equation)。 第七步：檢驗第六步所得的解是否為最佳解(方法同第三步)，否則回到第四步。 求解下列線性規劃問題。 Max z ＝5x1＋3x2＋x3 s.t. 2x1＋4x2＋x3 ? 8 x1＋2x2＋2x3 ?10 2x1＋x2 ?6 xj ? 0 , j = 1,2,3.? 解：標準型 Max z ＝ 5x1＋3x2＋x3 s.t. 2x1＋4x2＋x3＋s1＝8 x1＋2x2＋2x3＋s2＝10 2x1＋x2 ＋s3＝6 x1, x2, x3 ? 0 s1, s2, s3 ? 0 其解為 (x1, x2 x3, s1, s2, s3) ＝(3, 0, 2, 0, 3, 0) Max z ＝17 表示第一種產品生產 3 單位，第二種產品不生產，第三種產品生產 2 單位，第一種資源和第三種資源全部用完，而第二種資源尚有 3 單位剩餘，此時最大利潤為17。 作業研究．Chapter 3　線性規劃(II) 3-* 作 業 研 究 陳坤茂　著 3 線性規劃(II) 註：在(2-2)式中鬆弛變數式以xn+i表示之，在單形法表內為了區別，決策變數xj，j =1,2,…,n 與鬆弛變數xn+i，i =1,2,…,m，本書以Si，i=1,2,…,m代表鬆弛變數。又Zj值可解釋為所付出的代價，Cj?Zj 可解釋為相對利潤。 單形法解題之流程圖 作作看2