運(yùn)籌學(xué)-對偶問題課件

第二章

LP的對偶理論與靈敏度分析線性規(guī)劃的對偶問題III每天可用能力設(shè)備A（h）設(shè)備B（h）調(diào)試工序（h）06152115245利潤（元）21問公司應(yīng)每天制造兩種家電各多少件，使獲取的利潤最大。例1

問題美佳公司愿意以多大的代價(jià)出讓自己所擁有的生產(chǎn)資源？這樣得到一個(gè)新的線性規(guī)劃問題稱這一問題是原來的LP問題的對偶線性規(guī)劃問題或?qū)ε紗栴}，原來的LP問題也稱為原問題。LP問題的對稱形式變量：所有變量均具有非負(fù)約束約束條件：最大化問題所有約束條件都是“≤”型的最小化問題所有約束條件都是“≥”型的對稱形式下的對偶關(guān)系項(xiàng)目原問題對偶問題AbC目標(biāo)函數(shù)約束條件決策變量約束條件系數(shù)矩陣約束條件右端項(xiàng)向量目標(biāo)函數(shù)系數(shù)向量maxz=CXAX≤bX≥0約束條件系數(shù)矩陣轉(zhuǎn)置目標(biāo)函數(shù)的系數(shù)向量約束條件的右端項(xiàng)向量minw=Yb’A’Y≥C’Y≥0非對稱形式下的對偶關(guān)系原問題（對偶問題）maxz對偶問題（原問題）minwn個(gè)決策變量m個(gè)約束條件n個(gè)約束條件m個(gè)決策變量約束條件“≤”型約束條件“≥”型約束條件“=”型決策變量≥0決策變量≤0決策變量無約束決策變量≥0決策變量≤0決策變量無約束約束條件“≥”型約束條件“≤”型約束條件“=”型單純形法的矩陣表示添加松弛變量XS將XB的系數(shù)矩陣化為單位矩陣CBCN0XBXNXS0XSbBNICBCN0CBCN0XBXNXSCBXBB-1bIB-1NB-10CN–CBB-1N–CBB-1初始單純形表迭代后的單純形表項(xiàng)目原問題變量原問題松弛變量x1x2x3x4x5x315/20015/415/2x17/21001/4-1/2x23/2010-1/43/2-σj0001/41/2對偶問題剩余變量對偶問題變量y4y5y1y2y3項(xiàng)目對偶問題變量對偶問題剩余變量y1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2σj15/2007/23/2原問題松弛變量原問題變量x3x4x5x1x2原問題最終單純形表對偶問題最終單純形表例1最大化問題檢驗(yàn)數(shù)的相反數(shù)給出了對偶問題的解原本在對偶關(guān)系中，原問題的變量對應(yīng)著對偶問題的約束條件，原問題的約束條件對應(yīng)著對偶變量。但在分別添加了松弛變量和剩余變量后，也可以建立原問題變量與對偶問題變量之間的對應(yīng)關(guān)系原問題對偶問題第i個(gè)約束條件中添加的松弛變量第i個(gè)對偶變量第j個(gè)變量第j個(gè)約束條件中添加的松弛變量注上表中我們將松弛變量與剩余變量統(tǒng)稱為松弛變量對偶問題的基本性質(zhì)弱對偶性原問題可行解的目標(biāo)函數(shù)不超過對偶問題可行解的目標(biāo)函數(shù)最優(yōu)性若原問題一個(gè)可行解目標(biāo)函數(shù)等于對偶問題的某個(gè)可行解的目標(biāo)函數(shù),則這兩個(gè)可行解分別是原問題和對偶問題的最優(yōu)解強(qiáng)對偶性若原問題和對偶問題都有可行解,則它們都有最優(yōu)解,且最優(yōu)解的目標(biāo)函數(shù)值相等互補(bǔ)松弛性在線性規(guī)劃問題的最優(yōu)解中,如果對應(yīng)某一約束條件的對偶變量值非零,則其對應(yīng)的約束條件取等式;反之若一個(gè)約束條件為嚴(yán)格的不等式,則其對應(yīng)的對偶變量為零互補(bǔ)松弛性的另一種表述在線性規(guī)劃問題的最優(yōu)解中,如果對應(yīng)某一約束條件的對偶變量值非零,則該約束條件中松弛變量等于零;反之若一個(gè)約束條件中松弛變量非零,則其對應(yīng)的對偶變量為零。例（p76.7）原問題對偶問題將原問題最優(yōu)解X*=(2,2,4,0)代入原問題約束條件中得第一個(gè)約束條件：2+6=8，為等式第二個(gè)約束條件：4+2=6，為等式第三個(gè)約束條件：2+4=6，為等式第四個(gè)約束條件：2+2+4<9，為不等式，故y4=0第三節(jié)影子價(jià)格式中bi是線性規(guī)劃原問題約束條件的右端項(xiàng)，它代表第i種資源的擁有量；對偶變量yi的意義代表在資源最優(yōu)利用的條件下對第i種資源的估價(jià)。這種估價(jià)不是資源的市場價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價(jià)，為區(qū)別起見，稱為影子價(jià)格。設(shè)和分別是原問題和對偶問題的最優(yōu)解，則由對偶性質(zhì)，有資源的影子價(jià)格隨企業(yè)的生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)的改變而改變影子價(jià)格是資源的邊際價(jià)格資源的影子價(jià)格也可視為一種機(jī)會成本在生產(chǎn)過程中若某種資源未得到充分利用則其影子價(jià)格為零；只有在資源得到充分利用時(shí)，其影子價(jià)格才可能非零利用影子價(jià)格可以說明：單純形法中的檢驗(yàn)數(shù)可以看成生產(chǎn)某種產(chǎn)品的產(chǎn)值與隱含成本的差可以利用影子價(jià)格確定企業(yè)內(nèi)部的核算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。參考文獻(xiàn)：李慧：資源影子價(jià)格分析與經(jīng)營管理決策，系統(tǒng)工程理論與實(shí)踐，2003年4月號，22-26第四節(jié)對偶單純形法按對偶問題與原問題之間的關(guān)系，對最大化問題，在用單純形法求解原問題時(shí)，最終表不但給出了原問題的最優(yōu)解，而且其檢驗(yàn)數(shù)的相反數(shù)就是對偶問題的最優(yōu)解。對偶單純形法計(jì)算步驟適應(yīng)于求解這樣的LP問題：標(biāo)準(zhǔn)化后不含初始基變量，但將某些約束條件兩端乘以“-1”后，即可找出初始基變量。要求：初始單純形表中的檢驗(yàn)數(shù)滿足最優(yōu)性條件對滿足上述條件的LP問題，對偶單純形法的步驟是：旋轉(zhuǎn)運(yùn)算。然后回到第2步。作出初始單純形表（注意要求）檢查b列的數(shù)據(jù)是否非負(fù)，若是，表中已經(jīng)給出最優(yōu)解；否則轉(zhuǎn)下一步確定換出變量：取b列最小的數(shù)對應(yīng)的變量為換出變量確定換入變量：用檢驗(yàn)數(shù)去除以換出變量行的那些對應(yīng)的負(fù)系數(shù)，在除得的商中選取其中最小者對應(yīng)的變量為換入變量例用對偶單純形法求解如下的LP問題化成標(biāo)準(zhǔn)形式將各約束條件兩端同乘“-1”得用對偶單純形法求解得最優(yōu)解：x1=0,x2=1/4,x3=1/2,x4=0,x5=0最優(yōu)目標(biāo)函數(shù)值：w*=-8.5（z*=8.5）注：通常很少直接使用對偶單純形法求解線性規(guī)劃問題。靈敏度分析將討論LP問題中的參數(shù)中有一個(gè)或幾個(gè)發(fā)生改變時(shí)問題的最優(yōu)解會有什么變化，或者這些參數(shù)在一個(gè)多大的范圍內(nèi)變化時(shí)，問題的最優(yōu)解不變研究的思路將個(gè)別參數(shù)的變化直接在計(jì)算得到的最終單純形表中反映出來，這樣就不需要從頭計(jì)算，而直接檢查在參數(shù)改變后最終表有什么改變，若仍滿足最終表的條件，則表中仍給出最優(yōu)解，否則從這個(gè)表開始進(jìn)行迭代求改變以后的最優(yōu)解。靈敏度分析的步驟將參數(shù)的改變計(jì)算反映到最終表上來。具體計(jì)算公式可以使用檢查原問題是否仍為可行解檢查對偶問題是否仍為可行解對檢查情況按下表進(jìn)行處理原問題對偶問題結(jié)論或繼續(xù)計(jì)算步驟可行解可行解問題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新的單純形表重新計(jì)算價(jià)值系數(shù)變化的靈敏度分析例：在第一章美佳公司的例1中（1）若產(chǎn)品I的利潤降至1.5元/件，而產(chǎn)品 II的利潤增至2元/件，美佳公司的最優(yōu)生產(chǎn)計(jì)劃有何改變；（2）若產(chǎn)品I的利潤不變，則產(chǎn)品II的利潤在什么范圍變化時(shí)，該公司的最優(yōu)生產(chǎn)計(jì)劃不發(fā)生變化原最終單純形表（1）改變后新的最優(yōu)解為：最優(yōu)目標(biāo)函數(shù)值為：（2）改變后為使表中的解仍為最優(yōu)解必須因此產(chǎn)品II的利潤變化范圍為資源常數(shù)變化的靈敏度分析例：在第一章美佳公司的例1中（1）若設(shè)備A與調(diào)試工序的每天能力不變，而設(shè)備B每天的能力增加到32小時(shí)，分析公司最優(yōu)計(jì)劃的變化；（2）若設(shè)備A和B每天可用能力不變，則調(diào)試工序能力在什么范圍變化時(shí)，問題的最優(yōu)基不變（1）b由(15，24，5)T變?yōu)?15，32，5)T后，相應(yīng)地最終表中b列的數(shù)據(jù)變?yōu)榇朐罱K表（2）設(shè)現(xiàn)在每天調(diào)試工序的時(shí)間為x，則最終表中b列的數(shù)變?yōu)楣室棺顑?yōu)基不變必須利用Excle求解LP問題，以P45.7(2)為例變量，已經(jīng)賦了初值目標(biāo)函數(shù)值約束條件右端值其他專業(yè)軟件：Lindo與Lingo，WinQSB例如Lingo，啟動Lingo后，按圖中的方式輸入模型，然后點(diǎn)擊求解的圖標(biāo)。就可得到所需的最優(yōu)解。2．4對偶問題為由圖解法可得對偶問題最優(yōu)解為將該最優(yōu)解代入對偶問題約束條件可知，第四個(gè)約束條件為嚴(yán)格不等式，因此在原問題最優(yōu)解中而由于因此將原問題最優(yōu)解代入原問題約束條件，它們成為等式。再由于原問題最優(yōu)目標(biāo)函數(shù)值等于對偶問題最優(yōu)目標(biāo)函數(shù)值。于是原問題最優(yōu)解滿