對偶問題與靈敏度分析(編輯修改稿)
2025-06-20 07:19 本頁面
【文章內容簡介】 2 ≤3 2y1+3y2 ≤5 y1+y2 ≤2 3y1+y2 ≤3 y1,y2 ≥0 對偶問題 y1*=4/5,y2*=3/5 對偶問題的最優(yōu)解 4/52*3/5=2/53 約束條件是松的 也即 ys0,由互補松弛定理知 X(0)ys=0 所以 x2=0 同理， x3=0,x4=0 又 y1*0,而 Y(0)xs=0, 知 xs＝ 0，即原問題第一個約束取等式 同理，第 2個約束也取等式 定理 6 若原問題最優(yōu)解存在，則原問題最優(yōu)單純形表的檢驗數行中， 松弛變量的檢驗數 和 剩余變量的檢驗數的相反數 即為對偶問題最優(yōu)解 對偶最優(yōu)解的經濟含義 —— 影子價格 由對偶定理 ??????miiinjjj ybxcZ1*1**求 z*對 bi的偏導數 **iiybz ???所以對偶最優(yōu)解為原問題各資源的 影子價格 影子價格非資源的市場價格，而是指系統(tǒng) 達到 最優(yōu)狀態(tài)時 ，資源的單位變化引起目標最優(yōu)值的變化 對偶單純形法是求解線性規(guī)劃的另一的基本方法。它是根據對偶原理和單純形法的原理而設計出來的，因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形法。 由對偶理論可以知道，對于一個線性規(guī)劃問題，我們能夠通過求解它的對偶問題來找到它的最優(yōu)解。 什么是對偶單純形法？ 也就是說，求解原問題（ LP）時，可以從（ LP）的一個基本解（并不一定是基可行解）開始，逐步迭代，使目標函數值（ Z=Y b= CB B1b =CX）減少，當迭代到 XB=B1b≥0時，即找到了（ LP）的最優(yōu)解，這就是對偶單純形法。 同原始單純形求法一樣，求解對偶問題（ DP），也可以從（ DP）的一個基本可行解開始，從一個基本可行解（迭代）到另一個基本可行解，使目標函數值減少。 例一、用對偶單純形法求解： ?????????????????????)(01451232102215129m i n321321321321jxxxxxxxxxxxxxZj 解：將模型轉化為 ????????????????????????????????01451232102215129m a x61632153214321321xxxxxxxxxxxxxxxxZ cj 9 12 15 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 0 x4 10 2 2 1 1 0 0 0 x5 12 2 3 1 0 1 0 0 x6 14 1 1 5 0 0 1 (9/ 15/5) Z′ 0 9 12 15 0 0 0 i?cj 9 12 15 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 0 x4 36/5 9/5 9/5 0 1 0 1/5 0 x5 46/5 9/5 14/5 0 0 1 1/5 15 x3 14/5 1/5 1/5 1 0 0 1/5 (30/ .15/1) Z′ 42 6 9 0 0 0 3 i?cj 9 12 15 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 0 x4 9/7 9/14 0 0 1 9/14 1/14 12 x2 23/7 9/14 1 0 0 5/14 1/14 (3/ 33/1) 15 x3 15/7 1/14 0 1 0 1/14 3/14 Z′ 501/7 3/14 0 0 0 45/14 33/14 cj 9 12 15 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 9 x1 2 1 0 0
法律信息相關推薦
鄂ICP備17016276號-1