【文章內容簡介】 二章 對偶理論和靈敏度分析 例：試述下列線性規(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 （二）對偶問題的基本性質 對稱性： 對偶問題的對偶是原問題。 弱對偶性 若 一對對稱形式的對偶線性規(guī)劃 ??????0..XbAXtsCXM a x Z（ L） ??????0..YCYAtsbYM i n W和 （ D） 均有可行解 ， 分別為 和 ， 則 C ≤ b。 X~ X~Y~ Y~福州大學公共管理學院 53 證明思路： 弱對偶性推論： ? 極大化問題 的任意一個可行解所對應的目標函數值是其 對偶問題 最優(yōu)目標函數值的一個 下界 。極小化問題的任意一個可行解所對應的目標函數值是其對偶問題最優(yōu)目標函數值的一個 上界 。 由（ L） bXA ?~ 左乘 ，得 bYXAY ~~~ ?Y~由（ D） CAY ?~ 右乘 ，得 X~ XCXAY ~~~ ?bYXC ~~ ?福州大學公共管理學院 54 第二章 對偶理論和靈敏度分析 ? 如果原 max(min)問題為無界解，則其對偶 min (max)問題無可行解 ? 如果原 max(min)問題有可行解，其對偶 min (max)問題無可行解，則原問題為無界解 ? 注 ：有可能存在原問題和對偶問題同時無可行解的情況。 最優(yōu)性準則定理 若 、 分別為對稱形式對偶線性規(guī)劃的可行解，且兩者目標函數的相應值相等，即 C ＝ b ，則 ， 分別為原始問題和對偶問題的最優(yōu)解。 X YX YX Y福州大學公共管理學院 55 第二章 對偶理論和靈敏度分析 證明思路：由弱對偶性和已知條件易證。 主對偶 定理 如果原問題和對偶問題都有可行解，則它們都有最優(yōu)解，且它們的最優(yōu)解的目標函數值相等。 證明要點： 第一部分 ——證明兩者均有最優(yōu)解。 由于原始問題和對偶問題 均可行 ，根據弱對偶定理知兩者 均有界 ，于是 均有最優(yōu)解 。 第二部分 ——證明在達到最優(yōu)時 ， 兩個問題的目標函數值相等 。 福州大學公共管理學院 56 第二章 對偶理論和靈敏度分析 設 X0 為原問題的最優(yōu)解，它所對應的基矩陣是 B， X0= B?1 b，則其檢驗數滿足 C ? CBB?1A ? 0。 令 Y0= CBB?1，則有 Y0 A ? C ；而對原問題松弛變量的檢驗數有 0 ? CBB?1I ? 0，即 Y0 ? 0 。 顯然 Y0為對偶問題的可行解。因此有對偶問題目標函數值， g(Y0)=Y0b= CBB?1 b 而原問題最優(yōu)解的目標函數值為 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每增加一個單位對目標函數 Z的貢獻 。 ? 對偶變量 yi在經濟上表示原問題第 i種資源的 邊際價值 。 ? 對偶變量的值 yi*所表示的第 i種資源的邊際價值 ， 稱為 影子價值 。 ? 若原問題的價值系數 Cj表示單位產值 ， 則 yi 稱為 影子價格 。 ? 若原問題的價值系數 Cj表示單位利潤 ， 則 yi 稱為 影子利潤 。 五、對偶問題的經濟解釋 ? ?? ????njmiiijj ybxcZ1 1?iiybZ ???福州大學公共管理學院 61 第二章 對偶理論和靈敏度分析 ? 影子價格不是資源的實際價格 ， 而是資源配置結構的反映 ，是在其它數據相對穩(wěn)定的條件下某種資源增加一個單位導致的目標函數值的增量變化 。 ? 對資源 i總存量的評估： 購進 or 出讓 ? 對資源 i當前分配量的評估： 增加 or 減少 ① 它表明了當前的資源配置狀況 ， 告訴經營者應當優(yōu)先增加何種資源 ， 才能獲利更多 。 ② 告訴經營者以怎樣的代價去取得緊缺資源 。 ③ 提示設備出租或原材料轉讓的基價 。 ④ 告訴經營者補給緊缺資源的數量 ， 不要盲目大量補給 。 ⑤ 借助影子價格進行內部核算 。 ? 特別注意 福州大學公共管理學院 62 第二章 對偶理論和靈敏度分析 六、對偶單純形法 基本思路 ? 原單純型迭代要求每步都是基礎可行解 ? 達到最優(yōu)解時，檢驗數 cj–zj ?0 (max) 或 cj–zj ?0 (min) ? 但對于 (min, ?)型所加的剩余變量無法構成初始基礎可行解，因此通過加人工變量來解決 ? 大 M法和二階段法較繁 ? 能否從 剩余變量構成的初始基礎非可行解出發(fā) 迭代，但保證 檢驗數滿足最優(yōu)條件， cj–zj ?0 (max) 或 cj–zj ?0 (min)，保持對偶問題是基可行解，原問題在非可行解的基礎上，通過逐步迭代達到基可行解。 福州大學公共管理學院 63 第二章 對偶理論和靈敏度分析 對偶單純形的計算步驟如下： 1確定出變量 ? 找非可行解中最小者，即 min{ bi | bi0}，設第 i*行的最負，則 i*行稱為主行，該行對應的基變量為換出變量 xi* 2確定換入變量 檢查 xl所在行的各系數 alj（ j＝ 1,2…n) ，若所有 alj ≥0，則無可行解，停止計算。若存在 alj≤0， lkkkjijijjj azcaazc ????????????? 0 m i n **?福州大學公共管理學院 64 Xk為換入變量。 以主元 alk 為中心迭代 檢查當前基礎解是否為可行解 若是，則當前解即為最優(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 福州大學公共管理學院