對偶理論和靈敏度分析(編輯修改稿)

　

【文章內(nèi)容簡介】 二章 對偶理論和靈敏度分析 例：試述下列線性規(guī)劃問題分對偶問題 min z =2x1+3x25x3 +x4 x1+ x23x3 +x4 ≥ 5 2 x1 + 2x3x4 ≤4 x2+x3 +x4 =6 x1≤0。 x2,x3 ≥0。 x4 無約束 Max z’＝ 5y1＋ 4y2＋ 6y3 y1＋ 2y2 ≥2 y1 ＋ y3≤3 － 3y1＋ 2y2＋ y3 ≤－ 5 y1－ y2＋ y3 ＝ 1 y1 ≥ 0， y2 ≤ 0， y3 無約束 福州大學公共管理學院 50 第二章 對偶理論和靈敏度分析 練習： 寫出下面線性規(guī)劃的對偶規(guī)劃 ????????????????????0,01413121110987654..32432121321321321xxxxxxxxxxxtsxxxM i n Z符號不限福州大學公共管理學院 51 哪一個正確？ 前一個。原問題是極小化問題，因此應從原始對偶表的右邊往左邊查！ ?????????????????????0,0,31062139541284..1411732121321321321yyyyyyyyyyytsyyyM a x W符號不限 ?????????????????????0,0,31062139541284..1411732121321321321yyyyyyyyyyytsyyyM a x W符號不限福州大學公共管理學院 52 （二）對偶問題的基本性質(zhì) 對稱性： 對偶問題的對偶是原問題。 弱對偶性 若 一對對稱形式的對偶線性規(guī)劃 ??????0..XbAXtsCXM a x Z（ L） ??????0..YCYAtsbYM i n W和 （ D） 均有可行解 ， 分別為 和 ， 則 C ≤ b。 X~ X~Y~ Y~福州大學公共管理學院 53 證明思路： 弱對偶性推論： ? 極大化問題 的任意一個可行解所對應的目標函數(shù)值是其 對偶問題 最優(yōu)目標函數(shù)值的一個 下界 。極小化問題的任意一個可行解所對應的目標函數(shù)值是其對偶問題最優(yōu)目標函數(shù)值的一個 上界 。 由（ L） bXA ?~ 左乘 ，得 bYXAY ~~~ ?Y~由（ D） CAY ?~ 右乘 ，得 X~ XCXAY ~~~ ?bYXC ~~ ?福州大學公共管理學院 54 第二章 對偶理論和靈敏度分析 ? 如果原 max(min)問題為無界解，則其對偶 min (max)問題無可行解 ? 如果原 max(min)問題有可行解，其對偶 min (max)問題無可行解，則原問題為無界解 ? 注 ：有可能存在原問題和對偶問題同時無可行解的情況。 最優(yōu)性準則定理 若 、 分別為對稱形式對偶線性規(guī)劃的可行解，且兩者目標函數(shù)的相應值相等，即 C ＝ b ，則 ， 分別為原始問題和對偶問題的最優(yōu)解。 X YX YX Y福州大學公共管理學院 55 第二章 對偶理論和靈敏度分析 證明思路：由弱對偶性和已知條件易證。 主對偶 定理 如果原問題和對偶問題都有可行解，則它們都有最優(yōu)解，且它們的最優(yōu)解的目標函數(shù)值相等。 證明要點： 第一部分 ——證明兩者均有最優(yōu)解。 由于原始問題和對偶問題 均可行 ，根據(jù)弱對偶定理知兩者 均有界 ，于是 均有最優(yōu)解 。 第二部分 ——證明在達到最優(yōu)時 ， 兩個問題的目標函數(shù)值相等 。 福州大學公共管理學院 56 第二章 對偶理論和靈敏度分析 設(shè) X0 為原問題的最優(yōu)解，它所對應的基矩陣是 B， X0= B?1 b，則其檢驗數(shù)滿足 C ? CBB?1A ? 0。 令 Y0= CBB?1，則有 Y0 A ? C ；而對原問題松弛變量的檢驗數(shù)有 0 ? CBB?1I ? 0，即 Y0 ? 0 。 顯然 Y0為對偶問題的可行解。因此有對偶問題目標函數(shù)值， g(Y0)=Y0b= CBB?1 b 而原問題最優(yōu)解的目標函數(shù)值為 f(X0)=CX0= CBB?1 b 故由最優(yōu)解判別定理可知 Y0 為對偶問題的最優(yōu)解。 證畢 。 福州大學公共管理學院 57 第二章 對偶理論和靈敏度分析 該定理的證明告訴我們一個非常重要的概念： 對偶變量的最優(yōu)解等于原問題松弛變量的機會成本 即對偶變量的最優(yōu)解是原問題資源的 影子價格 互補松弛 定理 若 X0, Y0分別是原問題和對偶問題的可行解。那么 Y0Xs＝ 0和 X0Ys＝ 0，當且僅當 X0, Y0為最優(yōu)解。 證明： 1） Y0Xs＝ 0和 X0Ys＝ 0時， X0, Y0為最優(yōu)解 2） 當 X0, Y0為最優(yōu)解時， Y0Xs＝ 0， X0Ys＝ 0 福州大學公共管理學院 58 第二章 對偶理論和靈敏度分析 例 4：已知線性規(guī)劃問題 試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解。 證明：上述問題的對偶問題是： 由約束條件可知對偶問題無可行 解，而原問題有可行解。故無 最優(yōu)解。 ??????????????????0,122..32132132121xxxxxxxxxtsxxM a x z?????????????????0,0112..22121212121yyyyyyyytsyyM i n w福州大學公共管理學院 59 第二章 對偶理論和靈敏度分析 例 5：已知線性規(guī)劃問題 已知其對偶問題的最優(yōu)解為 y1*=4/5, y2*=3/5,z=5。 試用對偶理論找出問題的最優(yōu)解。 解： ????????????????????????5, . . . ,2,1,0332432..32532543215432154321jxxxxxxxxxxxtsxxxxxM i nj?福州大學公共管理學院 60 第二章 對偶理論和靈敏度分析 ? 這說明 yi是右端項 bi每增加一個單位對目標函數(shù) Z的貢獻 。 ? 對偶變量 yi在經(jīng)濟上表示原問題第 i種資源的 邊際價值 。 ? 對偶變量的值 yi*所表示的第 i種資源的邊際價值 ， 稱為 影子價值 。 ? 若原問題的價值系數(shù) Cj表示單位產(chǎn)值 ， 則 yi 稱為 影子價格 。 ? 若原問題的價值系數(shù) Cj表示單位利潤 ， 則 yi 稱為 影子利潤 。 五、對偶問題的經(jīng)濟解釋 ? ?? ????njmiiijj ybxcZ1 1?iiybZ ???福州大學公共管理學院 61 第二章 對偶理論和靈敏度分析 ? 影子價格不是資源的實際價格 ， 而是資源配置結(jié)構(gòu)的反映 ，是在其它數(shù)據(jù)相對穩(wěn)定的條件下某種資源增加一個單位導致的目標函數(shù)值的增量變化 。 ? 對資源 i總存量的評估： 購進 or 出讓 ? 對資源 i當前分配量的評估： 增加 or 減少 ① 它表明了當前的資源配置狀況 ， 告訴經(jīng)營者應當優(yōu)先增加何種資源 ， 才能獲利更多 。 ② 告訴經(jīng)營者以怎樣的代價去取得緊缺資源 。 ③ 提示設(shè)備出租或原材料轉(zhuǎn)讓的基價 。 ④ 告訴經(jīng)營者補給緊缺資源的數(shù)量 ， 不要盲目大量補給 。 ⑤ 借助影子價格進行內(nèi)部核算 。 ? 特別注意 福州大學公共管理學院 62 第二章 對偶理論和靈敏度分析 六、對偶單純形法 基本思路 ? 原單純型迭代要求每步都是基礎(chǔ)可行解 ? 達到最優(yōu)解時，檢驗數(shù) cj–zj ?0 (max) 或 cj–zj ?0 (min) ? 但對于 (min, ?)型所加的剩余變量無法構(gòu)成初始基礎(chǔ)可行解，因此通過加人工變量來解決 ? 大 M法和二階段法較繁 ? 能否從 剩余變量構(gòu)成的初始基礎(chǔ)非可行解出發(fā) 迭代，但保證 檢驗數(shù)滿足最優(yōu)條件， cj–zj ?0 (max) 或 cj–zj ?0 (min)，保持對偶問題是基可行解，原問題在非可行解的基礎(chǔ)上，通過逐步迭代達到基可行解。 福州大學公共管理學院 63 第二章 對偶理論和靈敏度分析 對偶單純形的計算步驟如下： 1確定出變量 ? 找非可行解中最小者，即 min{ bi | bi0}，設(shè)第 i*行的最負，則 i*行稱為主行，該行對應的基變量為換出變量 xi* 2確定換入變量 檢查 xl所在行的各系數(shù) alj（ j＝ 1,2…n) ，若所有 alj ≥0，則無可行解，停止計算。若存在 alj≤0， lkkkjijijjj azcaazc ????????????? 0 m i n **?福州大學公共管理學院 64 Xk為換入變量。 以主元 alk 為中心迭代 檢查當前基礎(chǔ)解是否為可行解 若是，則當前解即為最優(yōu)解 否則，返回 步驟 1。 例 :用對偶單純形求解 ???????????????0,43232..432)(m i n321321321321xxxxxxxxxtsxxxxf福州大學公共管理學院 65 解 ： 化原問題為適合對偶解法的標準 建立初始單純形表： ??????????????????????0,453232..432m a x543213214321321xxxxxxxxxxxxxtsxxxz 2 3 4 0 0 序號 C B X B b x 1 x 2 x 3 x 4 x 5 0 x 5 ? 3 ? 1 ? 2 1 1 0 0 x 6 ? 4 2 1 ? 3 0 1 I 初始解 c j? z j? 2 3 4 0 0 福州大學公共管理學院 66 2 3 4 0 0 序號 C B X B b x 1 x 2 x 3 x 4 x 5 0 X 4 ? 1 0 ? 5/ 2 1 /2 1 1 /2 2 X 1 2 1 1 /2 3 /2 0 1 /2 Ⅱ c j? z j? 0 4 － 1 0 － 1 2 3 4 0 0 序號 C B X B b x 1 x 2 x 3 x 4 x 5 － 3 X 4 2/5 0 1 1 / 5 2/5 1 / 5 2 X 1 11/5 1 0 7 / 5 1 /5 2 / 5 Ⅲ c j? z j? 0 0 － 3/ 5 8/5 － 1 /5 福州大學公共管理學院