【正文】 1/2 0 1 0 [1/4] 3/2 cjzj 0 0 0 1/4 1/2 0 x3 15 0 5 1 0 0 2 x1 5 1 1 0 0 1 0 x4 2 0 4 0 1 6 cjzj 0 1 0 0 2 080b????????????11 5 / 4 1 5 / 2 0 1 039。 的步驟。 。 更進一步 ，為了防止在各類狀況發(fā)生時 ， 來不及隨時對其變化作出反應 ， 即所謂 “ 計劃不如變化快 ” ， 企業(yè)應當預先了解 ， 當各項因素變化時 ， 應當作出什么樣的反應 。 1 5 2 4 5 0 062. . 5 2 10 ( 1 , . . . , 5 )iw y y y y yy y ys t y y y yyi? ? ? ? ? ?? ? ? ? ???? ? ? ? ? ??? ???cj→ 15 24 5 0 0 CB 基 b y1 y2 y3 y4 y5 0 y4 2 0 [6] 1 1 0 0 y5 1 5 2 1 0 1 cjzj 15 24 5 0 0 24 y2 1/3 0 1 1/6 1/6 0 0 y3 1/3 5 0 [2/3] 1/3 1 cjzj 15 0 1 4 0 24 y2 1/4 5/4 1 0 1/4 1/4 5 y3 1/2 15/2 0 1 1/2 3/2 cjzj 15/2 0 0 7/2 3/2 對偶單純形法舉例 對偶單純形法 ? 練習：用對偶單純形法求解 1 2 31 2 31 2 31 2 3m i n 5 2 43 2 4. . 6 3 5 10, , 0z x x xx x xs t x x xx x x? ? ?? ? ???? ? ?????線性規(guī)劃的對偶問題與靈敏度分析 ? 線性規(guī)劃的對偶問題 ? 對偶問題的基本性質(zhì) ? 影子價格 ? 對偶單純形法 ? 靈敏度分析 ? 參數(shù)線性規(guī)劃 靈敏度分析 在生產(chǎn)計劃問題的一般形式中 ， A代表企業(yè)的技術(shù)狀況 ， b代表企業(yè)的資源狀況 ， 而 C代表企業(yè)產(chǎn)品的市場狀況 ， 在這些因素不變的情況下企業(yè)的最優(yōu)生產(chǎn)計劃和最大利潤由線性規(guī)劃的最優(yōu)解和最優(yōu)值決定 。 反之 ， 則取相應行的基變量為出基變量； ③ 為保證能對基的可行性有所改進 ， 則將來的主元應該為負數(shù)；為保證下一個基還能是對偶可行基 ， 應使檢驗數(shù)仍為非正的 。若是，又基變量中無非零人工變量，即找到了問題最優(yōu)解；若為否，再找出相鄰的目標函數(shù)值更大的基可行解，并繼續(xù)判別，只要最優(yōu)解存在，就一直循環(huán)進行到找出最優(yōu)解為止。 如果有客戶以高于 5/3的價格購買工時，則可以出售一些工時，反之則反 線性規(guī)劃的對偶問題與靈敏度分析 ? 線性規(guī)劃的對偶問題 ? 對偶問題的基本性質(zhì) ? 影子價格 ? 對偶單純形法 ? 靈敏度分析 ? 參數(shù)線性規(guī)劃 對偶單純形法 ? 對偶單純形法并不是求解對偶問題解的方法，而是利用對偶理論求解原問題的解的方法。 影子價格舉例 A B C 擁有量 工 時 1 1 1 3 材 料 1 4 7 9 單件利潤 2 3 3 ?????????21)9,3(m inyyW???????????????????????????????????????????????0332714111..2121yyyyts y1=5/3, y2=1/3 即工時的影子價格為 5/3，材料的影子價格為 1/3。 ? 影子價格反映單純形表中各個檢驗數(shù)的經(jīng)濟意義。隨著資源的買進賣出，其影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。 ? 影子價格是一種邊際價格。 影子價格 ? 資源的市場價格是其價值的客觀體現(xiàn)，相對比較穩(wěn)定，而它的影子價格則有賴于資源的利用情況，是未知數(shù)。 其含義是在目前已給定的情況下，最優(yōu)目標值隨資源數(shù)量變化的變化率； 其經(jīng)濟含義是為約束條件所付出的代價。 對偶問題的基本性質(zhì) ? 互補松弛性 在線性規(guī)劃問題的最優(yōu)解中，如果對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其對應的對偶變量一定為零。 對偶問題的基本性質(zhì) 對偶問題的基本性質(zhì) ? 最優(yōu)性 如果 (j=1,...,n)是原問題的可行解，(i=1,...,m)是其對偶問題的可行解，且有 j?xi?y? ?nmj j i ij = 1 i = 1c x = b y??則 (j=1,...,n)是原問題的最優(yōu)解， (i=1,...,m)是其對偶問題的最優(yōu)解。 注意：本點性質(zhì)的逆不成立，當對偶問題無可行解時，其原問題或具有無界解或無可行解，反之亦然。 進一步迭代 ,新的單純形表如下： 對偶問題的基本性質(zhì) 項目 基變量 非基變量 XB XN Xs CB XB B1b I B1N B1 cjzj 0 CNCBB1N –CBB1 ? 對應初始單純形表中的單位矩陣 I，迭代后的單純形 表中為 B1 ?初始單純形表中基變量 Xs=b，迭代后的表中 XB=B1b ?初始單純形表中約束系數(shù)矩陣為 [A,I]=[B,N,I]， 迭代后的表中約束系數(shù)矩陣為 [B1A,B1I]=[B1B,B1N,B1I]=[I,B1N,B1] ?若初始矩陣中變量 xj的系數(shù)向量為 Pj，迭代后為 Pj′，則有 Pj′=B1Pj ?當 B為最優(yōu)基時，表中應有 CNCBB1N≤0,CBB1≤0 對偶問題的基本性質(zhì) ? 例 25 參看例 21中的原問題和對偶問題，并分別加上松弛變量和剩余變量，如下： 1 2 3 4 5m a x 2 0 0 0z x x x x x? ? ? ? ?231 2 41 2 55 156 2 24..50( 1 , ... , 5 )jxxx x xstx x xxj???? ? ? ???? ? ??? ???1 2 3 4 5m i n 1 5 2 4 5 0 0w y y y y y? ? ? ? ?2 3 41 2 3 562. . 5 2 10( 1 , ..., 5 )iy y ys t y y y yyi? ? ???? ? ? ??? ???對偶變量 y1 y2 y3 對偶變量 x1 x2 對偶問題的基本性質(zhì) 兩個問題的最終單純形表如下： 項目 原問題變量 原問題松弛變量 x1 x2 x3 x4 x5 x3 15/2 0 0 1 5/4 15/2 x1 7/2 1 0 0 1/4 1/2 x2 3/2 0 1 0 1/4 3/2 zjcj 0 0 0 1/4 1/2 變量 對偶問題的剩余變量 對偶問題變量 y4 y5 y1 y2 y3 項目 對偶問題變量 對偶問題剩余變量 y1 y2 y3 y4 y5 y2 1/4 5/4 1 0 1/4 1/4 y3 1/2 15/2 0 1 1/2 3/2 cjzj 15/2 0 0 7/2 3/2 變量 原問題松弛變量 原問題變量 x3 x4 x5 x1 x2 對偶問題的基本性質(zhì) 如果 xj（ j=1， ...， n）是原問題的可行解，yi（ i=1， ...， m）是其對偶問題的可行解，則恒有 11jjnmiijic x