对偶单形法步骤课件.ppt

1、第五章第五章對偶理論對偶理論 Duality Theory 廖慶榮作業研究 二版 2009p.2/36章節大綱章節大綱1.前言2.對偶問題的定義3.主要與對偶問題關係4.對偶的各項性質5.由單形表中讀對偶解6.陰影價格7.對偶問題的經濟解釋8.對偶單形法9.人工限制式技巧作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.3/365.2 對偶問題的定義對偶問題的定義 作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.4/36範例範例5.1o 考慮典型範例的模式如下：n 其對偶問題為12P:Max 78Zxx121122 s.t

2、.2103218xxyxxy12,0 x x 012D:Min 1018yyy121122 s.t.37228yyxyyx12,0y y p.5/365.3 主要問題與對偶問題的關係主要問題與對偶問題的關係o 六個對偶關係(#1與#4為標準形式的對應關係)作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.6/36範例範例5.2 作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.7/365.4 對偶的各項性質對偶的各項性質 作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.8/365.4 對偶的各項性質對偶的各項性質 作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論

3、p.9/365.4 對偶的各項性質對偶的各項性質o 考慮LP標準形式的擴充形式及其對偶問題：作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.10/365.4 對偶的各項性質對偶的各項性質 作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.11/36範例範例5.4o 考慮典型範例的P及D：作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.12/36問題問題P與與D的互補基解的互補基解(範例範例5.4)作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.13/36範例範例5.4o 由上表可觀察兩互補基解間的關係：

4、由上表可觀察兩互補基解間的關係：n 兩互補基解的目標函數值相同（互補基解性質）n 最佳解發生在兩互補基解均為可行解時（互補寬鬆性質）n 除最佳解外，一個可行的基解對應一個不可行的互補基解n 除最佳解外，一個次佳的基解對應一個超佳的互補基解p.14/365.5 由單形表中讀出對偶解由單形表中讀出對偶解 作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.15/36由寬鬆變數讀出由寬鬆變數讀出 作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.16/36由剩餘變數讀出由剩餘變數讀出 作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.17/36由人工變數讀出由人工變數讀出 作業

5、研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.18/36結論結論 作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.19/36範例範例5.6o 考慮以下LP：作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.20/36範例範例5.6 作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.21/365.6 陰影價格陰影價格o 陰影價格（shadow price）n 每增加1單位資源可增加的利潤。o 典型範例n 若M1的資源由目前的10小時增加至11小時，則最佳解改變如下：原最佳解：新最佳解：Z的增量：n 因此，M1的陰影價格為2.5（即$2,500）124,3,52x

6、xZ123.5,3.75,54.5xxZ2.5Z作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.22/36陰影價格的圖示（典型範例）陰影價格的圖示（典型範例）作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.23/365.7 對偶問題的經濟解釋對偶問題的經濟解釋o 以資源分配問題（典型範例）為例：作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.24/365.7 對偶問題的經濟解釋對偶問題的經濟解釋o 主要問題的意義：在M1與M2兩項資源的限制下，該公司（以A表示）應分別生產多少數量的新產品P1與P2，才能獲得最大總利潤？o 現在分析對偶問題的意義。假設有家公司（以B

7、表示）要購買A公司用來生產P1與P2的資源，那麼應以多少價格購買？作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.25/365.7 對偶問題的經濟解釋對偶問題的經濟解釋 作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.26/365.8 對偶單形法對偶單形法o 最佳單形表必須滿足以下三個條件：n 主要可行性（primal feasibility）n 對偶可行性（dual feasibility）n 互補寬鬆性（complementary slackness）o 主要單形法n 始終保持條件1與3，最後達到條件2o 對偶單形法n 始終保持條件2與3，最後達到條件1作業研究作業研究

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

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

10、範例5.8 p.32/365.9 人工限制式技巧人工限制式技巧o 若目標函數係數有正值（對max問題），則須利用人工限制式技巧（artificial constraint technique）求得起始對偶BFSo 步驟（對max問題）：n 加上人工限制式如下：n 對人工限制式加上寬鬆變數 n 選擇具最負Z列係數的變數進入，並選擇 離開 經過以上步驟，單形表的Z列係數均將大於等於零，而得到起始對偶BFS1nx1nxNBVjjxxM作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.33/365.9 人工限制式技巧人工限制式技巧o 繼續以對偶單形法求解，會得到以下結果：n 人工問題之對偶問題

11、的解是無窮解n 找到人工問題的最佳解，且n 找到人工問題的最佳解，且o 根據對偶基本定理n 情況1表示主要問題無可行解n 情況2表示已找到主要問題的最佳解n 情況3表示主要問題是無窮解10nx10nx作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.34/36範例範例5.9o 先將所有限制式的左右兩邊均乘以-1以轉換為的形式，並加上寬鬆變數o 再加上人工限制式及其寬鬆變數：125xxxM作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.35/36範例範例5.9(表1-2)作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論p.36/36範例範例5.9(表3-4)作業研究作業研究 二版二版 Ch.5 對偶理論對偶理論