對偶問題3(共56張PPT)

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

第二頁，共56頁。問題美佳公司愿意以多大的代價出讓自己所擁有的生產(chǎn)資源？第三頁，共56頁。設(shè)y1,y2和y3分別表示出讓資源A，B和調(diào)試工序的單價，則美佳公司同意出讓的條件將是同意出讓生產(chǎn)產(chǎn)品I的資源同意出讓生產(chǎn)產(chǎn)品II的資源購買者希望用最少的代價獲得這些資源，因此第四頁，共56頁。這樣得到一個新的線性規(guī)劃問題稱這一問題是原來的LP問題的對偶線性規(guī)劃問題或?qū)ε紗栴}，原來的LP問題也稱為原問題。第五頁，共56頁。LP問題的對稱形式變量：所有變量均具有非負(fù)約束約束條件：最大化問題所有約束條件都是“≤”型的最小化問題所有約束條件都是“≥”型的第六頁，共56頁。對稱形式下的對偶關(guān)系項目原問題對偶問題AbC目標(biāo)函數(shù)約束條件決策變量約束條件系數(shù)矩陣約束條件右端項向量目標(biāo)函數(shù)系數(shù)向量maxz=CXAX≤bX≥0約束條件系數(shù)矩陣轉(zhuǎn)置目標(biāo)函數(shù)的系數(shù)向量約束條件的右端項向量minw=Yb’A’Y≥C’Y≥0第七頁，共56頁。原問題maxz對偶問題minwn個決策變量m個約束條件n個約束條件m個決策變量約束條件“≤”型決策變量≥0決策變量≥0約束條件“≥”型對稱形式的對應(yīng)關(guān)系對偶問題的對偶是原問題，即對偶關(guān)系是相互對稱的關(guān)系第八頁，共56頁。非對稱形式下的對偶關(guān)系原問題（對偶問題）maxz對偶問題（原問題）minwn個決策變量m個約束條件n個約束條件m個決策變量約束條件“≤”型約束條件“≥”型約束條件“=”型決策變量≥0決策變量≤0決策變量無約束決策變量≥0決策變量≤0決策變量無約束約束條件“≥”型約束條件“≤”型約束條件“=”型第九頁，共56頁。單純形法的矩陣表示添加松弛變量XS將XB的系數(shù)矩陣化為單位矩陣第十頁，共56頁。CBCN0XBXNXS0XSbBNICBCN0CBCN0XBXNXSCBXBB-1bIB-1NB-10CN–CBB-1N–CBB-1初始單純形表迭代后的單純形表第十一頁，共56頁。在初始單純形表中單位矩陣經(jīng)過迭代后變?yōu)榛仃嘊的逆在初始單純形表給出的解中基變量Xs=b,而在迭代后的表給出的解中基變量XB=B-1b系數(shù)矩陣的變化:[A,I]B-1[A,I]在初始單純形表中變量xj的系數(shù)為Pj經(jīng)過迭代后變?yōu)镻j′,并且Pj′=B-1Pj若迭代后的單純形表為最終表則該表也同時給出對偶問題的最優(yōu)解第十二頁，共56頁。項目原問題變量原問題松弛變量x1x2x3x4x5x315/20015/415/2x17/21001/4-1/2x23/2010-1/43/2-σj0001/41/2對偶問題剩余變量對偶問題變量y4y5y1y2y3項目對偶問題變量對偶問題剩余變量y1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2σj15/2007/23/2原問題松弛變量原問題變量x3x4x5x1x2原問題最終單純形表對偶問題最終單純形表例1最大化問題檢驗數(shù)的相反數(shù)給出了對偶問題的解第十三頁，共56頁。原本在對偶關(guān)系中，原問題的變量對應(yīng)著對偶問題的約束條件，原問題的約束條件對應(yīng)著對偶變量。但在分別添加了松弛變量和剩余變量后，也可以建立原問題變量與對偶問題變量之間的對應(yīng)關(guān)系原問題對偶問題第i個約束條件中添加的松弛變量第i個對偶變量第j個變量第j個約束條件中添加的松弛變量注上表中我們將松弛變量與剩余變量統(tǒng)稱為松弛變量第十四頁，共56頁。對偶問題的基本性質(zhì)弱對偶性原問題可行解的目標(biāo)函數(shù)不超過對偶問題可行解的目標(biāo)函數(shù)第十五頁，共56頁。弱對偶性的推論（1）原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下界；反之對偶問題任一可行解的目標(biāo)函數(shù)值是原問題目標(biāo)函數(shù)值的上界。（2）如原問題有可行解且目標(biāo)函數(shù)無界（即原問題為無界解），則對偶問題無可行解；反之對偶問題有可行解且目標(biāo)函數(shù)無界，則原問題無可行解。注意該推論的逆命題不成立。（3）若原問題有可行解而對偶問題無可行解，則原問題目標(biāo)函數(shù)無界；反之對偶問題有可行解而原問題無可行解，則原問題目標(biāo)函數(shù)無界。第十六頁，共56頁。最優(yōu)性若原問題一個可行解目標(biāo)函數(shù)等于對偶問題的某個可行解的目標(biāo)函數(shù),則這兩個可行解分別是原問題和對偶問題的最優(yōu)解強(qiáng)對偶性若原問題和對偶問題都有可行解,則它們都有最優(yōu)解,且最優(yōu)解的目標(biāo)函數(shù)值相等互補(bǔ)松弛性在線性規(guī)劃問題的最優(yōu)解中,如果對應(yīng)某一約束條件的對偶變量值非零,則其對應(yīng)的約束條件取等式;反之若一個約束條件為嚴(yán)格的不等式,則其對應(yīng)的對偶變量為零第十七頁，共56頁?；パa(bǔ)松弛性的另一種表述在線性規(guī)劃問題的最優(yōu)解中,如果對應(yīng)某一約束條件的對偶變量值非零,則該約束條件中松弛變量等于零;反之若一個約束條件中松弛變量非零,則其對應(yīng)的對偶變量為零。第十八頁，共56頁。例（p76.7）原問題對偶問題將原問題最優(yōu)解X*=(2,2,4,0)代入原問題約束條件中得第一個約束條件：2+6=8，為等式第二個約束條件：4+2=6，為等式第三個約束條件：2+4=6，為等式第四個約束條件：2+2+4<9，為不等式，故y4=0第十九頁，共56頁。而由x1=2>0,得而由x2=2>0,得而由x3=4>0,得于是得到方程組得對偶問題最優(yōu)解為注：原問題與對偶問題最優(yōu)目標(biāo)函數(shù)值都是z*=4+8+4=16第二十頁，共56頁。第三節(jié)影子價格第二十一頁，共56頁。式中bi是線性規(guī)劃原問題約束條件的右端項，它代表第i種資源的擁有量；對偶變量yi的意義代表在資源最優(yōu)利用的條件下對第i種資源的估價。這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價，為區(qū)別起見，稱為影子價格。設(shè)和分別是原問題和對偶問題的最優(yōu)解，則由對偶性質(zhì)，有第二十二頁，共56頁。資源的影子價格隨企業(yè)的生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)的改變而改變影子價格是資源的邊際價格資源的影子價格也可視為一種機(jī)會成本在生產(chǎn)過程中若某種資源未得到充分利用則其影子價格為零；只有在資源得到充分利用時，其影子價格才可能非零利用影子價格可以說明：單純形法中的檢驗數(shù)可以看成生產(chǎn)某種產(chǎn)品的產(chǎn)值與隱含成本的差可以利用影子價格確定企業(yè)內(nèi)部的核算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。第二十三頁，共56頁。例1Maxz=2x1+x2s.t.5x2≤156x1+2x2

≤24

x1+x2≤5x1,x2≥0x2=36x1+2x2=24x1+x2=5最優(yōu)解可行域最優(yōu)目標(biāo)函數(shù)值的變化：8.5變到8.75，增加1/4資源的變化：設(shè)備B的可用時間從增加一小時第二十四頁，共56頁。參考文獻(xiàn)：李慧：資源影子價格分析與經(jīng)營管理決策，系統(tǒng)工程理論與實踐，2003年4月號，22-26第二十五頁，共56頁。第四節(jié)對偶單純形法按對偶問題與原問題之間的關(guān)系，對最大化問題，在用單純形法求解原問題時，最終表不但給出了原問題的最優(yōu)解，而且其檢驗數(shù)的相反數(shù)就是對偶問題的最優(yōu)解。第二十六頁，共56頁。單純形法求解的基本思路基可行解檢驗數(shù)非正保持解的可行性對偶單純形法的基本思路對偶問題基可行解（檢驗數(shù)非正）原問題基可行解保持對偶問題解的可行性（檢驗數(shù)非正（對偶問題可行解）第二十七頁，共56頁。保持對偶問題有基可行解,而原問題只是基本解,通過迭代,使后者的負(fù)分量個數(shù)減少，一旦成為基可行解,則原問題與對偶問題同時實現(xiàn)最優(yōu)解.第二十八頁，共56頁。對偶單純形法計算步驟適應(yīng)于求解這樣的LP問題：標(biāo)準(zhǔn)化后不含初始基變量，但將某些約束條件兩端乘以“-1”后，即可找出初始基變量。要求：初始單純形表中的檢驗數(shù)滿足最優(yōu)性條件第二十九頁，共56頁。對滿足上述條件的LP問題，對偶單純形法的步驟是：旋轉(zhuǎn)運(yùn)算。然后回到第2步。作出初始單純形表（注意要求）檢查b列的數(shù)據(jù)是否非負(fù)，若是，表中已經(jīng)給出最優(yōu)解；否則轉(zhuǎn)下一步確定換出變量：取b列最小的數(shù)對應(yīng)的變量為換出變量確定換入變量：用檢驗數(shù)去除以換出變量行的那些對應(yīng)的負(fù)系數(shù)，在除得的商中選取其中最小者對應(yīng)的變量為換入變量第三十頁，共56頁。例用對偶單純形法求解如下的LP問題化成標(biāo)準(zhǔn)形式第三十一頁，共56頁。將各約束條件兩端同乘“-1”得用對偶單純形法求解得第三十二頁，共56頁。最優(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ī)劃問題。第三十三頁，共56頁。靈敏度分析將討論LP問題中的參數(shù)中有一個或幾個發(fā)生改變時問題的最優(yōu)解會有什么變化，或者這些參數(shù)在一個多大的范圍內(nèi)變化時，問題的最優(yōu)解不變第三十四頁，共56頁。研究的思路將個別參數(shù)的變化直接在計算得到的最終單純形表中反映出來，這樣就不需要從頭計算，而直接檢查在參數(shù)改變后最終表有什么改變，若仍滿足最終表的條件，則表中仍給出最優(yōu)解，否則從這個表開始進(jìn)行迭代求改變以后的最優(yōu)解。第三十五頁，共56頁。靈敏度分析的步驟將參數(shù)的改變計算反映到最終表上來。具體計算公式可以使用檢查原問題是否仍為可行解檢查對偶問題是否仍為可行解對檢查情況按下表進(jìn)行處理第三十六頁，共56頁。原問題對偶問題結(jié)論或繼續(xù)計算步驟可行解可行解問題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新的單純形表重新計算第三十七頁，共56頁。XB=B-1bCBCN001第四十六頁，共56頁。同意出讓生產(chǎn)產(chǎn)品I的資源例：在第一章美佳公司的例1中0-1/43/2第三個約束條件：2+4=6，為等式反之對偶問題有可行解而原問題無可行解，則原問題目標(biāo)函數(shù)無界。第四十六頁，共56頁。第三十七頁，共56頁。購買者希望用最少的代價獲得這些資源，因此其他專業(yè)軟件：Lindo與Lingo，WinQSB反之對偶問題任一可行解的目標(biāo)函數(shù)值是原問題目標(biāo)函數(shù)值的上界。檢查對偶問題是否仍為可行解Maxz=2x1+x2價值系數(shù)變化的靈敏度分析例：在第一章美佳公司的例1中（1）若產(chǎn)品I的利潤降至1.5元/件，而產(chǎn)品 II的利潤增至2元/件，美佳公司的最優(yōu)生產(chǎn)計劃有何改變；（2）若產(chǎn)品I的利潤不變，則產(chǎn)品II的利潤在什么范圍變化時，該公司的最優(yōu)生產(chǎn)計劃不發(fā)生變化第三十八頁，共56頁。原最終單純形表第三十九頁，共56頁。（1）改變后新的最優(yōu)解為：最優(yōu)目標(biāo)函數(shù)值為：第四十頁，共56頁。（2）改變后為使表中的解仍為最優(yōu)解必須因此產(chǎn)品II的利潤變化范圍為第四十一頁，共56頁。資源常數(shù)變化的靈敏度分析例：在第一章美佳公司的例1中（1）若設(shè)備A與調(diào)試工序的每天能力不變，而設(shè)備B每天的能力增加到32小時，分析公司最優(yōu)計劃的變化；（2）若設(shè)備A和B每天可用能力不變，則調(diào)試工序能力在什么范圍變化時，問題的最優(yōu)基不變第四十二頁，共56頁。（1）b由(15，24，5)T變?yōu)?15，32，5)T后，相應(yīng)地最終表中b列的數(shù)據(jù)變?yōu)榇朐罱K表第四十三頁，共56頁。（2）設(shè)現(xiàn)在每天調(diào)試工序的時間為x，則最終表中b列的數(shù)變?yōu)楣室棺顑?yōu)基不變必須第四十四頁，共