【正文】 0 因 CB－ YTB = 0， 故 C－ YT A ≤0， 即 AT Y ≥CT ， 說明 Y是 D的可行解 max z=CX . AX ≤b X ≥ 0 此時目標函數(shù)值 w =bTY=YTb= CBB1b 原問題的最優(yōu)值 z＊ = CB1b= CBB1b 由最優(yōu)性定理知， Y是 D的最優(yōu)解。 定理：若原問題有最優(yōu)解 ， 則其對偶問題也一定具有最優(yōu)解 ， 且目標函數(shù)的最優(yōu)值相等 。 第 41頁 強對偶性 （對偶定理） 推論：若一對對偶問題都有可行解 ， 則它們都有最優(yōu)解 ，且目標函數(shù)的最優(yōu)值必相等 。 定理：若原問題有最優(yōu)解 ， 則其對偶問題也一定具有最優(yōu)解 ， 且目標函數(shù)的最優(yōu)值相等 。 互為對偶的兩個問題，只會出現(xiàn)以下三種關(guān)系： ① 都有最優(yōu)解，且最優(yōu)值相等 ② 一個有無界解，另一個無可行解； ③ 兩個都無可行解。 * * * *11nmj j i ijiz c x b y w??? ? ???無界解無可行解無可行解無界解對偶問題原問題第 42頁 判斷下列說法是否正確，為什么？ 如果線性規(guī)劃問題存在可行解 ， 則其對偶問題也一定存在可行解 。 如果線性規(guī)劃問題的對偶問題無可行解，則原問題也一定無可行解。 如果線性規(guī)劃問題的原問題和對偶問題都具有可行解 ，則該線性規(guī)劃一定具有有限最優(yōu)解 。 第 43頁 對偶問題的基本性質(zhì) 一個問題 max 另一問題 min 應用 有最優(yōu)解 有最優(yōu)解 強對偶性 無界解 （有可行解） 無可行解 無界性 （證無最優(yōu)解） 無可行解 無界解 （有可行解） 已知最優(yōu)解 求最優(yōu)解 互補松弛性 第 44頁 原問題與對偶問題單純形表間的性質(zhì)？ XB I 0 CB CN B N XB XN 非基變量 基變量 Xs I jjcz?0 基變量 基變量 基可 系數(shù) 行解 0 Xs b 基變量 非基變量 XB jjcz?基變量 基變量 基可 系數(shù) 行解 CN－ CBB1N B1N B1 XN Xs B1b CB YT= CBB1 － CBB1 第 45頁 Duality Theory ? 線性規(guī)劃的對偶問題 ? 對偶問題的經(jīng)濟解釋 —— 影子價格 ? 對偶單純形法 ? 靈敏度分析 ? 對偶問題的基本性質(zhì) 第二章 線性規(guī)劃的對偶理論 第 46頁 ? 對偶問題的經(jīng)濟解釋 —— 影子價格 Duality Theory ? 線性規(guī)劃的對偶問題 ? 對偶單純形法 ? 靈敏度分析 ? 對偶問題的基本性質(zhì) 第二章 線性規(guī)劃的對偶理論 第 47頁 1 2 3m in 6 8 3w y y y? ? ?121 2 31 2 3 324, , 0yyy y yy y y????? ? ??? ?? .D bi 代表第 i種資源的擁有量； yi*代表在資源最優(yōu)利用條件下對第 i種資源的單位估價 。 這種估價不是資源的市場價格 ， 而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價 。 一、影子價格的概念 386供應量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙設 xj 表示第 j 種產(chǎn)品每天的產(chǎn)量 設 yj 表示第 j 種原料的收費單價 12m a x 3 4z x x??1212212 628 3,0xxxxxxx??????????? ?? .P1m inmiiiw b y?? ?1 1 , ,0 1 , ,mi j i jiia y c j ny i m?????? （ ）（ ） .（ D ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）???njjj xcz1m a x1 1 , ,0 1 , ,nij j ijja x b i mx j n?????? （ ）（ ） .（ P ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ） 由對偶定理知當 P問題求得最優(yōu)解 X*時 ， D問題也得到最優(yōu)解 Y*， 且有 * * * *11nmj j i ijiz c x b y w??? ? ???影子價格 第 48頁 若 ，則 * 0iy ?*1nij j ija x b???*1nij j ija x b???若 ，則 * 0iy ?當某個右端常數(shù) bi bi+1時 一、影子價格的概念 **1miiiz b y?? ?由 得 **iiz yb? ??說明 的值相當于在資源得到最優(yōu) 利用的生產(chǎn)條件下 ， 每增加一個 單位時目標函數(shù) z的增量 *iyib* * * *11 i i m mz b y b y b y? ? ? ? ?* * * *11 ( 1 )i i m mz b y b y b y? ? ? ? ? ? ?* * * *11 i i m m ib y b y b y y? ? ? ? ? ?**izy??邊際價格 說明若某資源 未被充分利用 ，則該種資源的影子價格為 0； ib若某資源的影子價格不為 0， 則說明已有資源在已消耗完畢 。 第 49頁 二、在經(jīng)營管理中的應用 386供應量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙12m a x 3 4z x x??1212212 628 3,0xxxxxxx??????????? ?? .P1x 2x 3x 4x 5xjc ?BC 基 bjjcz??i3403 4 0 0 01x2x5x42110001021?11?11?0010 0 2? 1? 0y1* = 2 y2* = 1 y3* = 0 Y*T= CBB1 － CBB1 第 50頁 二、在經(jīng)營管理中的應用 386供應量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙 y1* = 2 y2* = 1 y3* = 0 若原料 A增加 1單位 ， 該廠按最優(yōu)計劃安排生產(chǎn)可多獲利 200元； 若原料 B增加 1單位 ， 可多獲利 100元 。 原料 C本已剩余 ， 再增加不會帶來收益 。 指示企業(yè)內(nèi)部挖潛的方向 影子價格能說明增加哪種資源對增加經(jīng)濟效益最有利 第 51頁 二、在經(jīng)營管理中的應用 386供應量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙 y1* = 2 y2* = 1 y3* = 0 在企業(yè)經(jīng)營決策中的作用 當某種資源的影子價 格高于市場價格時： 當某種資源的影子價 格低于市場價格時： 企業(yè)經(jīng)營決策者可通過把本企業(yè)資源的影子價格與當時的市場價格進行比較 ， 決定資源的買賣 ， 以獲取較大利潤 。 買進 賣出 特別是影子價格為零時 第 52頁 二、在經(jīng)營管理中的應用 386供應量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙 y1* = 2 y2* = 1 y3* = 0 在新產(chǎn)品開發(fā)決策中的應用 利用影子價格 ， 通過分析新產(chǎn)品使用資源的經(jīng)濟效果 ，以決定新產(chǎn)品是否應該投產(chǎn) 。 假設該企業(yè)計劃生產(chǎn)一類新產(chǎn)品 ， 單件消耗三種原料的數(shù)量為 （ 2,3,2） ， 則新產(chǎn)品的單位利潤必須大于 2 2 + 1 3 + 0 2 = 7（百元） 才能增加公司的收益 ， 否則生產(chǎn)是不合算的 。 第 53頁 二、在經(jīng)營管理中的應用 386供應量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙 y1* = 2 y2* = 1 y3* = 0 分析現(xiàn)有產(chǎn)品價格變動對資源緊缺情況的影響 若甲產(chǎn)品提價 ， 單位利潤增至 4， 則影子價格改變 ， 由 Y*T= CBB1 2 1 0( 4 , 4 , 0 ) 1 1 01 1 1????????????(4, 0, 0)?說明如果甲產(chǎn)品提價的話 ， 資源 A將變得更緊俏 . 第 54頁 二、在經(jīng)營管理中的應用 386供應量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙 y1* = 2 y2* = 1 y3* = 0 分析工藝改變后對資源節(jié)約的收益 若企業(yè)革新技術(shù) ， 改進工藝過程后使資源 A能節(jié)約 2%， 則帶來的經(jīng)濟收益每天將是 2 6 2% = （ 百元 ） 第 55頁 二、在經(jīng)營管理中的應用 386供應量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙 y1* = 2 y2* = 1 y3* = 0 注意 : 以上分析都是在最優(yōu)基不變的條件下進行的 應對影子價格有更為廣義的理解 若增加產(chǎn)量 約束 x1+ x2 ≤40： 產(chǎn)量不超過市場需求量 若 y4*較大，則說明擴大銷路能比增加資源帶來更大的經(jīng)濟效益 Y*T= CBB1 第 56頁 Duality Theory ? 線性規(guī)劃的對偶問題 ? 對偶問題的經(jīng)濟解釋 —— 影子價格 ? 對偶單純形法 ? 靈敏度分析 ? 對偶問題的基本性質(zhì) 第二章 線性規(guī)劃的對偶理論