【文章內(nèi)容簡介】 原問題目標(biāo)函數(shù)值無界；反之對偶問題有可行解而其原問題無可行解，則對偶問題的目標(biāo)函數(shù)值無界。 對偶問題的基本性質(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)解。 j?xi?y對偶問題的基本性質(zhì) ? 強對偶性 (或稱對偶定理 ) 若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。 對偶問題的基本性質(zhì) ? 互補松弛性 在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對應(yīng)的對偶變量一定為零。也即 i?y若 0，則有 ，即 1?nij j ija x b???? 0six ?若 ，即 ，則有 1?nij j ija x b??? ? 0six ?? 0iy ?因此一定有 ， ?six ? 0iy ?線性規(guī)劃的對偶問題與靈敏度分析 ? 線性規(guī)劃的對偶問題 ? 對偶問題的基本性質(zhì) ? 影子價格 ? 對偶單純形法 ? 靈敏度分析 ? 參數(shù)線性規(guī)劃 影子價格 對偶最優(yōu)解的經(jīng)濟含義 ―― 影子價格 **22*11* mm ybybybZ ???? ? 代表著當(dāng)?shù)?i個右端常數(shù)增加一個單位時，最優(yōu)目標(biāo)函數(shù)值的相應(yīng)增量。 其含義是在目前已給定的情況下，最優(yōu)目標(biāo)值隨資源數(shù)量變化的變化率； 其經(jīng)濟含義是為約束條件所付出的代價。 當(dāng) B是原問題的最優(yōu)基時， Y=CBB1就是影子價格向量 。 影子價格 ? 資源的市場價格是其價值的客觀體現(xiàn)，相對比較穩(wěn)定，而它的影子價格則有賴于資源的利用情況，是未知數(shù)。因企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價格也隨之改變。 ? 影子價格是一種邊際價格。 ? 資源的影子價格實際上又是一種機會成本。隨著資源的買進賣出，其影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。 影子價格 ? 生產(chǎn)過程中如果某種資源未得到充分利用時，該種資源的影子價格為零；又當(dāng)資源的影子價格不為零時，表明該種資源在生產(chǎn)中已耗費完畢。 ? 影子價格反映單純形表中各個檢驗數(shù)的經(jīng)濟意義。 ? 一般說對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當(dāng)估價，這種估價直接涉及資源的最有效利用。 影子價格舉例 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。 如果目前市場上材料的價格低于 1/3， 則企業(yè)可以購進材料來擴大生產(chǎn) ， 反之可以賣掉部分材料 。 如果有客戶以高于 5/3的價格購買工時，則可以出售一些工時，反之則反 線性規(guī)劃的對偶問題與靈敏度分析 ? 線性規(guī)劃的對偶問題 ? 對偶問題的基本性質(zhì) ? 影子價格 ? 對偶單純形法 ? 靈敏度分析 ? 參數(shù)線性規(guī)劃 對偶單純形法 ? 對偶單純形法并不是求解對偶問題解的方法，而是利用對偶理論求解原問題的解的方法。 ? 求解單純形法的基本思路： 對原問題的一個基可行解，判別是否所有檢驗數(shù) cjzj≤0(j=1,…,n) 。若是，又基變量中無非零人工變量，即找到了問題最優(yōu)解；若為否，再找出相鄰的目標(biāo)函數(shù)值更大的基可行解，并繼續(xù)判別，只要最優(yōu)解存在，就一直循環(huán)進行到找出最優(yōu)解為止。 對偶單純形法 對于標(biāo)準(zhǔn)線性規(guī)劃問題： 可行基 B 若 B對應(yīng)的基本解是可行解 最優(yōu)基 B 若 B對應(yīng)的基本解是 最優(yōu) 解 對偶可行基 B 若 CBB1是對偶問題可行解 即 CCBB1A≤0 或 檢驗數(shù) ≤0 CXZ ?m a xCYAts ?..?????0..XbAXtsYbW ?m in對偶單純形法 對于標(biāo)準(zhǔn)線性規(guī)劃問題： CXZ ?m a xCYAts ?..?????0..XbAXtsYbW ?m in最優(yōu)基 B 可行基 B 對偶可行基 B 單純形法 可行基 B 保持可行性 對偶可行基 B 對偶單純形法 可行基 B 保持對偶可行性 對偶可行基 B 對偶單純形法 對于標(biāo)準(zhǔn)線性規(guī)劃問題： CXZ ?m a x?????0..XbAXts對偶單純形法 可行基 B 保持對偶可行性 對偶可行基 B ① 找一個基 ， 建立初始對偶單純形表 ， 檢驗數(shù)全部非正； ② 若 b列元素非負 ， 則已經(jīng)是最優(yōu)基 。 反之 ， 則取相應(yīng)行的基變量為出基變量； ③ 為保證能對基的可行性有所改進 ， 則將來的主元應(yīng)該為負數(shù)；為保證下一個基還能是對偶可行基 ， 應(yīng)使檢驗數(shù)仍為非正的 。 ④ 主元變換 對偶單純形法舉例 1 2 3231 2 31 2 3m in 1 5 2 4 562. . 5 2 1, , 0w y y yyys t y y yy y y? ? ?????? ? ??? ??例 2－ 6 用對偶單純形法求解： 1 2 3 4 52 3 41 2 3 5m a x 39。 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 對偶單純形法舉例 對偶單純形法 ? 練習(xí)：用對偶單純形法求解 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ī)劃 靈敏度分析