【正文】 原問題與對偶問題單純形表間的性質(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頁 ? 第一步：找到一個滿足最優(yōu)檢驗的初始基本解； ? 第二步：檢驗當前解是否可行。若可行，已得到最優(yōu)，否則轉(zhuǎn)入下一步。 ? 第三步：選擇 b最小一行的變量作為換出變量 ? 第四步：換入變量 min{cjzj/aij}(負數(shù)和零不參與比較 ) ? 第五步：迭代運算，到第二步。 對偶單純形法 第 47頁 對偶單純形法 ??????????????????????j,0102641212120632153214321對一切jxxxxxxxxxxxxx? Max z=6x13x22x3 例： 第 48頁 cj 6 3 2 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 0 x4 20 1 1 1 1 0 0 0 x5 6 1/2 1/2 1/4 0 1 0 0 x6 10 2 1 1 0 0 1 zj 0 0 0 0 0 0 cjzj 6 3 2 0 0 0 對偶單純形法 找到一個滿足最優(yōu)檢驗的初始基本解 檢驗當前解不可行，選擇 b最小一行的變量作為換出變量；換入變量 min{cjzj/aij} 第 49頁 cj 6 3 2 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 2 x3 20 1 1 1 1 0 0 0 x5 1 1/4 1/4 0 1/4 1 0 0 x6 10 1 0 0 1 0 1 zj 2 2 2 2 0 0 cjzj 4 1 0 2 0 0 對偶單純形法 檢驗當前解不可行，選擇 b最小一行的變量作為換出變量；換入變量 min{cjzj/aij} 第 50頁 cj 6 3 2 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 2 x3 16 0 0 1 2 4 0 3 x2 4 1 1 0 1 4 0 0 x6 10 1 0 0 1 0 1 zj 3 3 2 1 4 0 cjzj 3 0 0 1 4 0 對偶單純形法 第 51頁 ? 對偶問題的經(jīng)濟解釋 —— 影子價格 Duality Theory ? 線性規(guī)劃的對偶問題 ? 對偶單純形法 ? 靈敏度分析 ? 對偶問題的基本性質(zhì) 第二章 線性規(guī)劃的對偶理論 第 52頁 1 2 3m i n 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供應(yīng)量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙設(shè) xj 表示第 j 種產(chǎn)品每天的產(chǎn)量 設(shè) 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 ax1 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??? ? ???影子價格 第 53頁 若 ，則 * 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， 則說明已有資源在已消耗完畢 。 第 54頁 二、在經(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?3403 4 0 0 01x2x5x42110001021?11?11?0010 0 2? 1? 0y1* = 2 y2* = 1 y3* = 0 Y*T= CBB1 － CBB1 第 55頁 二、在經(jīng)營管理中的應(yīng)用 386供應(yīng)量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)濟效益最有利 第 56頁 二、在經(jīng)營管理中的應(yīng)用 386供應(yīng)量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙 y1* = 2 y2* = 1 y3* = 0 在企業(yè)經(jīng)營決策中的作用 當某種資源的影子價 格高于市場價格時： 當某種資源的影子價 格低于市場價格時： 企業(yè)經(jīng)營決策者可通過把本企業(yè)資源的影子價格與當時的市場價格進行比較 ， 決定資源的買賣 ， 以獲取較大利潤 。 買進 賣出 特別是影子價格為零時 第 57頁 二、在經(jīng)營管理中的應(yīng)用 386供應(yīng)量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙 y1* = 2 y2* = 1 y3* = 0 在新產(chǎn)品開發(fā)決策中的應(yīng)用 利用影子價格 ， 通過分析新產(chǎn)品使用資源的經(jīng)濟效果 ，以決定新產(chǎn)品是否應(yīng)該投產(chǎn) 。 假設(shè)該企業(yè)計劃生產(chǎn)一類新產(chǎn)品 ， 單件消耗三種原料的數(shù)量為 （ 2,3,2） ， 則新產(chǎn)品的單位利潤必須大于 2 2 + 1 3 + 0 2 = 7（百元） 才能增加公司的收益 ， 否則生產(chǎn)是不合算的 。 第 58頁 二、在經(jīng)營管理中的應(yīng)用 386供應(yīng)量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將變得更緊俏 . 第 59頁 二、在經(jīng)營管理中的應(yīng)用 386供應(yīng)量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙 y1* = 2 y2* = 1 y3* = 0 分析工藝改變后對資源節(jié)約的收益 若企業(yè)革新技術(shù) ， 改進工藝過程后使資源 A能節(jié)約 2%， 則帶來的經(jīng)濟收益每天將是 2 6 2% = （ 百元 ） 第 60頁 二、在經(jīng)營管理中的應(yīng)用 386供應(yīng)量34011211甲乙單位利潤（百元）CBA 原料產(chǎn)品甲乙 y1* = 2 y2* = 1 y3* = 0 注意 : 以上分析都是在最優(yōu)基不變的條件下進行的 應(yīng)對影子價格有更為廣義的理解 若增加產(chǎn)量 約束 x1+ x2 ≤40： 產(chǎn)量不超過市場需求量 若 y4*較大，則說明擴大銷路能比增加資源帶來更大的經(jīng)濟效益 Y*T= CBB1 第 61頁 Duality Theory ? 線性規(guī)劃的對偶問題 ? 對偶問題的經(jīng)濟解釋 —— 影子價格 ? 對偶單純形法 ? 靈敏度分析 ? 對偶問題的基本性質(zhì) 第二章 線性規(guī)劃的對偶理論