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