對(duì)偶問(wèn)題3(共56張PPT)

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

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