线性规划的对偶(duality).PPT

第一節　對偶問題 第二節　對偶單形法 第三節　敏感度分析 第一節　對偶問題 線性規劃的對偶 (duality) ：一個線性規劃問題可以從兩個不同的角度來分析，其一，評估每一產品的獲利情況，而使總利潤極大化，另一為評估生產產品所付出的成本，而使總成本極小化，實為一物的兩面，從不同的解度觀察同一問題。 假設某家具製造廠生產桌子及椅子兩種家具，在製造過程中需要經過兩套機器分別加工處理，甲機器每週可以作業 60 小時， 乙機器每週可以作業48 小時。製造一張桌子需要甲機器作業 4小時，需要乙機器作業 2 小時；製造一把椅子需要甲機器作業 1 小時，需要乙機器作業 2 小時。每張桌子的利潤是 5 元，每把椅子的利潤是 4 元。 該廠為求得最大利潤，必須在現有的限制條件下，尋求生產桌子及椅子數目的最適當組合。 Max z = 8x1 + 5x2 s.t. 2x1 + x2 ≦ 16 3x1 + 4x2≦ 20 x1－x2 ≦ 5 x1 + 2x2 ≦15 5x1+ 4x2 ≦25 x1≧0，x2≧0 對偶問題的構建 在將原始線性規劃問題轉換為其對偶問題之前，首先要把原始問題寫成對稱型(Symmetric form)，須滿足 所有變數皆為非負值。 所有結構限制條件皆為不等式。 線性規劃對稱形式之要求 將線性規劃對稱型的原始問題與對偶問題以表格對照如下 對稱型的原始問題與對偶問題之線性規劃以矩陣形式表示如下 原始問題： Max z = CX s.t. AX ≦ b X ≧ 0 對偶問題： Min z = Yb s.t. YA ≧ C Y ≧ 0 其中 A 為 m×n 矩陣，b 為 m × 1 行向量，C 為 1× n列向量，X 為 n × 1 行向量，Y 為1 × m 列向量。X 表示各種產品的生產數量，Y 表示各項資源每單位機會成本或價值。 Max z = 15x1+ 8x2 s.t. x1+2x2 ≧ 5 3x1+2x2 = 12 5x1+4x2 ≦ 15 x1≧0，x2≧0 對偶問題為 Min z = 5y1+12y2+15y3 s.t. y1+3y2+5y3①≧15 2y1+2y2+4y3②≧8 y1③≦0 y2④無符號限制 y3⑤≧0 Min z = 4x1+5x2 s.t. 3x1+2x2 ≦ 15 (a) 4x1-3x2 ≧ 10 (b) x1+ x2 = 6 (c) x1≧0，x2無符號限制 對偶問題為 Max z=15y1+10y2+6y3 s.t. 3y1+4y2+y3 ≦ 4 (∴x1≧0正常；對Max而言“≦”才正常) 2y1-3y2+y3 = 5 (∵x2無符號限制；此式為等式) y1≦0 (∵(a)式 “≦”，對Min而言不正常；∴y1≦ 0 不正常) y2≧0 (∵(b)式 “≧”，對Min而言正常；∴y2 ≧ 0，才正常) y3無符號限制 (∵(c)式為等式，∴y3無符號限制) 原始－對偶問題的性質 (1)對偶問題的對