第五章 對偶理論 Duality Theory 作業研究 二版 2009 © 廖慶榮.

Presentation on theme: "第五章 對偶理論 Duality Theory 作業研究 二版 2009 © 廖慶榮."— Presentation transcript:

1 第五章 對偶理論 Duality Theory 作業研究 二版 2009 © 廖慶榮

2 章節大綱 前言 對偶問題的定義 主要與對偶問題關係 對偶的各項性質 由單形表中讀對偶解 陰影價格 對偶問題的經濟解釋 對偶單形法
人工限制式技巧 作業研究 二版 Ch.5 對偶理論

3 5.2 對偶問題的定義 作業研究 二版 Ch.5 對偶理論

4 範例5.1 考慮典型範例的模式如下： 其對偶問題為 作業研究 二版 Ch.5 對偶理論

5 5.3 主要問題與對偶問題的關係 六個對偶關係 (#1與#4為標準形式的對應關係) 作業研究 二版 Ch.5 對偶理論

6 範例5.2 作業研究 二版 Ch.5 對偶理論

7 5.4 對偶的各項性質 作業研究 二版 Ch.5 對偶理論

8 5.4 對偶的各項性質 作業研究 二版 Ch.5 對偶理論

9 5.4 對偶的各項性質 考慮LP標準形式的擴充形式及其對偶問題： 作業研究 二版 Ch.5 對偶理論

10 5.4 對偶的各項性質 作業研究 二版 Ch.5 對偶理論

11 範例5.4 考慮典型範例的P及D： 作業研究 二版 Ch.5 對偶理論

12 問題P與D的互補基解 (範例5.4) 作業研究 二版 Ch.5 對偶理論

13 範例5.4 由上表可觀察兩互補基解間的關係： 兩互補基解的目標函數值相同（互補基解性質） 最佳解發生在兩互補基解均為可行解時（互補寬鬆性質）
除最佳解外，一個可行的基解對應一個不可行的互補基解 除最佳解外，一個次佳的基解對應一個超佳的互補基解 作業研究 二版 Ch.5 對偶理論

14 5.5 由單形表中讀出對偶解 作業研究 二版 Ch.5 對偶理論

15 由寬鬆變數讀出 作業研究 二版 Ch.5 對偶理論

16 由剩餘變數讀出 作業研究 二版 Ch.5 對偶理論

17 由人工變數讀出 作業研究 二版 Ch.5 對偶理論

18 結論 作業研究 二版 Ch.5 對偶理論

19 範例5.6 考慮以下LP： 作業研究 二版 Ch.5 對偶理論

20 範例5.6 作業研究 二版 Ch.5 對偶理論

21 5.6 陰影價格 陰影價格（shadow price） 典型範例 每增加1單位資源可增加的利潤。
5.6 陰影價格 陰影價格（shadow price） 每增加1單位資源可增加的利潤。 典型範例 若M1的資源由目前的10小時增加至11小時，則最佳解改變如下： 原最佳解： 新最佳解： Z的增量： 因此，M1的陰影價格為2.5（即$2,500） 作業研究 二版 Ch.5 對偶理論

22 陰影價格的圖示（典型範例） 作業研究 二版 Ch.5 對偶理論

23 5.7 對偶問題的經濟解釋 以資源分配問題（典型範例）為例： 作業研究 二版 Ch.5 對偶理論

24 5.7 對偶問題的經濟解釋 主要問題的意義：在M1與M2兩項資源的限制下，該公司（以A表示）應分別生產多少數量的新產品P1與P2，才能獲得最大總利潤？ 現在分析對偶問題的意義。假設有家公司（以B表 示）要購買A公司用來生產P1與P2的資源，那麼應 以多少價格購買？ 作業研究 二版 Ch.5 對偶理論

25 5.7 對偶問題的經濟解釋 作業研究 二版 Ch.5 對偶理論

26 5.8 對偶單形法 最佳單形表必須滿足以下三個條件： 主要單形法 對偶單形法 主要可行性（primal feasibility）
5.8 對偶單形法 最佳單形表必須滿足以下三個條件： 主要可行性（primal feasibility） 對偶可行性（dual feasibility） 互補寬鬆性（complementary slackness） 主要單形法 始終保持條件1與3，最後達到條件2 對偶單形法 始終保持條件2與3，最後達到條件1 作業研究 二版 Ch.5 對偶理論

27 對偶單形法步驟（對max問題） 起始步驟 最佳性測試 迭代步驟
尋找一個對偶可行基解（對偶BFS），使得所有列係數均為非負值，但RHS不受正負號限制 最佳性測試 若所有的RHS均為非負值，則停止，否則繼續 迭代步驟 決定離開變數：選擇具最負RHS的BV 決定進入變數：選擇具最小比率的NBV 產生新單形表：利用高斯消去法 返回最佳性測試 作業研究 二版 Ch.5 對偶理論

28 主要單形法和對偶單形法的差異 對max問題 作業研究 二版 Ch.5 對偶理論

29 對偶單形法適合時機 當可很容易地得到起始對偶BFS時 在敏感度分析中主要可行性違反時
對偶單形法可輕易地將≧限制式轉換為=限制式，而以寬鬆變數處理 若max問題的目標函數係數均為負值（或min問題的目標函數係數均為正值），可很容易地得到起始對偶BFS，而採對偶單形法 在敏感度分析中主要可行性違反時 此時可以很方便地以對偶單形法繼續求解 作業研究 二版 Ch.5 對偶理論

30 範例5.8 作業研究 二版 Ch.5 對偶理論

31 範例5.8 作業研究 二版 Ch.5 對偶理論

32 5.9 人工限制式技巧 若目標函數係數有正值（對max問題），則須利用人工限制式技巧（artificial constraint technique）求得起始對偶BFS 步驟（對max問題）： 加上人工限制式如下： 對人工限制式加上寬鬆變數 選擇具最負Z列係數的變數進入，並選擇 離開 經過以上步驟，單形表的Z列係數均將大於等於零，而得到起始對偶BFS 作業研究 二版 Ch.5 對偶理論

33 5.9 人工限制式技巧 繼續以對偶單形法求解，會得到以下結果： 根據對偶基本定理 人工問題之對偶問題的解是無窮解 找到人工問題的最佳解，且
5.9 人工限制式技巧 繼續以對偶單形法求解，會得到以下結果： 人工問題之對偶問題的解是無窮解 找到人工問題的最佳解，且 根據對偶基本定理 情況1表示主要問題無可行解 情況2表示已找到主要問題的最佳解 情況3表示主要問題是無窮解 作業研究 二版 Ch.5 對偶理論

34 範例5.9 先將所有≧限制式的左右兩邊均乘以-1以轉換為≦的形式，並加上寬鬆變數 再加上人工限制式及其寬鬆變數：
作業研究 二版 Ch.5 對偶理論

35 範例5.9 (表1-2) 作業研究 二版 Ch.5 對偶理論

36 範例5.9 (表3-4) 作業研究 二版 Ch.5 對偶理論