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