第二章對偶問題課件

線性規(guī)劃的對偶問題問公司應(yīng)每天制造兩種家電各多少件，使獲取的利潤最大。例1

線性規(guī)劃的對偶問題問公司應(yīng)每天制造兩種家電各多少件，使獲取的1問題美佳公司愿意以多大的代價出讓自己所擁有的生產(chǎn)資源？問題美佳公司愿意以多大的代價出讓自己所擁有的生產(chǎn)資源？2設(shè)y1,y2和y3分別表示出讓資源A，B和調(diào)試工序的單價，則美佳公司同意出讓的條件將是同意出讓生產(chǎn)產(chǎn)品I的資源同意出讓生產(chǎn)產(chǎn)品II的資源購買者希望用最少的代價獲得這些資源，因此設(shè)y1,y2和y3分別表示出讓資源A，B和調(diào)試工序的單價，則3這樣得到一個新的線性規(guī)劃問題稱這一問題是原來的LP問題的對偶線性規(guī)劃問題或?qū)ε紗栴}，原來的LP問題也稱為原問題。這樣得到一個新的線性規(guī)劃問題稱這一問題是原來的LP問題的對偶4LP問題的對稱形式變量：所有變量均具有非負約束約束條件：最大化問題所有約束條件都是“≤”型的最小化問題所有約束條件都是“≥”型的LP問題的對稱形式變量：所有變量均具有非負約束5對稱形式下的對偶關(guān)系對稱形式下的對偶關(guān)系6對稱形式的對應(yīng)關(guān)系對偶問題的對偶是原問題，即對偶關(guān)系是相互對稱的關(guān)系對稱形式的對應(yīng)關(guān)系對偶問題的對偶是原問題，即對偶關(guān)系是相互對7非對稱形式下的對偶關(guān)系非對稱形式下的對偶關(guān)系8單純形法的矩陣表示添加松弛變量XS將XB的系數(shù)矩陣化為單位矩陣單純形法的矩陣表示添加松弛變量XS將XB的系數(shù)矩陣化為單位矩9初始單純形表迭代后的單純形表初始單純形表迭代后的單純形表10在初始單純形表中單位矩陣經(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)解在初始單純形表中單位矩陣經(jīng)過迭代后變?yōu)榛仃嘊的逆11原問題最終單純形表對偶問題最終單純形表例1最大化問題檢驗數(shù)的相反數(shù)給出了對偶問題的解原問題最終單純形表對偶問題最終單純形表例1最大化問題檢驗數(shù)的12原本在對偶關(guān)系中，原問題的變量對應(yīng)著對偶問題的約束條件，原問題的約束條件對應(yīng)著對偶變量。但在分別添加了松弛變量和剩余變量后，也可以建立原問題變量與對偶問題變量之間的對應(yīng)關(guān)系注上表中我們將松弛變量與剩余變量統(tǒng)稱為松弛變量原本在對偶關(guān)系中，原問題的變量對應(yīng)著對偶問題的約束條件，原問13對偶問題的基本性質(zhì)弱對偶性原問題可行解的目標函數(shù)不超過對偶問題可行解的目標函數(shù)對偶問題的基本性質(zhì)弱對偶性14弱對偶性的推論（1）原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之對偶問題任一可行解的目標函數(shù)值是原問題目標函數(shù)值的上界。（2）如原問題有可行解且目標函數(shù)無界（即原問題為無界解），則對偶問題無可行解；反之對偶問題有可行解且目標函數(shù)無界，則原問題無可行解。注意該推論的逆命題不成立。（3）若原問題有可行解而對偶問題無可行解，則原問題目標函數(shù)無界；反之對偶問題有可行解而原問題無可行解，則原問題目標函數(shù)無界。弱對偶性的推論（1）原問題任一可行解的目標函數(shù)值是其對偶問題15最優(yōu)性若原問題一個可行解目標函數(shù)等于對偶問題的某個可行解的目標函數(shù),則這兩個可行解分別是原問題和對偶問題的最優(yōu)解強對偶性若原問題和對偶問題都有可行解,則它們都有最優(yōu)解,且最優(yōu)解的目標函數(shù)值相等互補松弛性在線性規(guī)劃問題的最優(yōu)解中,如果對應(yīng)某一約束條件的對偶變量值非零,則其對應(yīng)的約束條件取等式;反之若一個約束條件為嚴格的不等式,則其對應(yīng)的對偶變量為零最優(yōu)性16互補松弛性的另一種表述在線性規(guī)劃問題的最優(yōu)解中,如果對應(yīng)某一約束條件的對偶變量值非零,則該約束條件中松弛變量等于零;反之若一個約束條件中松弛變量非零,則其對應(yīng)的對偶變量為零?；パa松弛性的另一種表述在線性規(guī)劃問題的最優(yōu)解中,如果對應(yīng)某一17例（p76.7）原問題對偶問題將原問題最優(yōu)解X*=(2,2,4,0)代入原問題約束條件中得第一個約束條件：2+6=8，為等式第二個約束條件：4+2=6，為等式第三個約束條件：2+4=6，為等式第四個約束條件：2+2+4<9，為不等式，故y4=0例（p76.7）原問題對偶問題將原問題最優(yōu)解X*=(2,2,18而由x1=2>0,得而由x2=2>0,得而由x3=4>0,得于是得到方程組得對偶問題最優(yōu)解為注：原問題與對偶問題最優(yōu)目標函數(shù)值都是z*=4+8+4=16而由x1=2>0,得而由x2=2>0,得而由x3=4>019第三節(jié)影子價格第三節(jié)影子價格20式中bi是線性規(guī)劃原問題約束條件的右端項，它代表第i種資源的擁有量；對偶變量yi的意義代表在資源最優(yōu)利用的條件下對第i種資源的估價。這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價，為區(qū)別起見，稱為影子價格。設(shè)和分別是原問題和對偶問題的最優(yōu)解，則由對偶性質(zhì)，有式中bi是線性規(guī)劃原問題約束條件的右端項，它代表第i種資源的21資源的影子價格隨企業(yè)的生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)的改變而改變影子價格是資源的邊際價格資源的影子價格也可視為一種機會成本在生產(chǎn)過程中若某種資源未得到充分利用則其影子價格為零；只有在資源得到充分利用時，其影子價格才可能非零利用影子價格可以說明：單純形法中的檢驗數(shù)可以看成生產(chǎn)某種產(chǎn)品的產(chǎn)值與隱含成本的差可以利用影子價格確定企業(yè)內(nèi)部的核算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。資源的影子價格隨企業(yè)的生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)的改變而改變22例1Maxz=2x1+x2s.t.5x2≤156x1+2x2

≤24

x1+x2≤5x1,x2≥0x2=36x1+2x2=24x1+x2=5最優(yōu)解可行域最優(yōu)目標函數(shù)值的變化：8.5變到8.75，增加1/4資源的變化：設(shè)備B的可用時間從增加一小時例1Maxz=2x1+x2x2=36x1+2x2=24x23參考文獻：李慧：資源影子價格分析與經(jīng)營管理決策，系統(tǒng)工程理論與實踐，2003年4月號，22-26參考文獻：24第四節(jié)對偶單純形法按對偶問題與原問題之間的關(guān)系，對最大化問題，在用單純形法求解原問題時，最終表不但給出了原問題的最優(yōu)解，而且其檢驗數(shù)的相反數(shù)就是對偶問題的最優(yōu)解。第四節(jié)對偶單純形法按對偶問題與原問題之間的關(guān)系，對最大化問25單純形法求解的基本思路基可行解檢驗數(shù)非正保持解的可行性對偶單純形法的基本思路對偶問題基可行解（檢驗數(shù)非正）原問題基可行解保持對偶問題解的可行性（檢驗數(shù)非正（對偶問題可行解）單純形法求解的基本思路基可行解檢驗數(shù)非正保持解的可行性對偶單26保持對偶問題有基可行解,而原問題只是基本解,通過迭代,使后者的負分量個數(shù)減少，一旦成為基可行解,則原問題與對偶問題同時實現(xiàn)最優(yōu)解.保持對偶問題有基可行解,而原問題只是基本解,通過迭代,使后者27對偶單純形法計算步驟適應(yīng)于求解這樣的LP問題：標準化后不含初始基變量，但將某些約束條件兩端乘以“-1”后，即可找出初始基變量。要求：初始單純形表中的檢驗數(shù)滿足最優(yōu)性條件對偶單純形法計算步驟適應(yīng)于求解這樣的LP問題：標準化后不含初28對滿足上述條件的LP問題，對偶單純形法的步驟是：旋轉(zhuǎn)運算。然后回到第2步。作出初始單純形表（注意要求）檢查b列的數(shù)據(jù)是否非負，若是，表中已經(jīng)給出最優(yōu)解；否則轉(zhuǎn)下一步確定換出變量：取b列最小的數(shù)對應(yīng)的變量為換出變量確定換入變量：用檢驗數(shù)去除以換出變量行的那些對應(yīng)的負系數(shù)，在除得的商中選取其中最小者對應(yīng)的變量為換入變量對滿足上述條件的LP問題，對偶單純形法的步驟是：旋轉(zhuǎn)運算。然29例用對偶單純形法求解如下的LP問題化成標準形式例用對偶單純形法求解如下的LP問題化成標準形式30將各約束條件兩端同乘“-1”得用對偶單純形法求解得將各約束條件兩端同乘“-1”得用對偶單純形法求解得31最優(yōu)解：x1=0,x2=1/4,x3=1/2,x4=0,x5=0最優(yōu)目標函數(shù)值：w*=-8.5（z*=8.5）注：通常很少直接使用對偶單純形法求解線性規(guī)劃問題。最優(yōu)解：x1=0,x2=1/4,x3=1/2,x4=032靈敏度分析將討論LP問題中的參數(shù)中有一個或幾個發(fā)生改變時問題的最優(yōu)解會有什么變化，或者這些參數(shù)在一個多大的范圍內(nèi)變化時，問題的最優(yōu)解不變靈敏度分析將討論LP問題中的參數(shù)33研究的思路將個別參數(shù)的變化直接在計算得到的最終單純形表中反映出來，這樣就不需要從頭計算，而直接檢查在參數(shù)改變后最終表有什么改變，若仍滿足最終表的條件，則表中仍給出最優(yōu)解，否則從這個表開始進行迭代求改變以后的最優(yōu)解。研究的思路將個別參數(shù)的變化直接在計算得到的最終單純形表中反映34靈敏度分析的步驟將參數(shù)的改變計算反映到最終表上來。具體計算公式可以使用檢查原問題是否仍為可行解檢查對偶問題是否仍為可行解對檢查情況按下表進行處理靈敏度分析的步驟將參數(shù)的改變計算反映到最終表上來。具體計算公35第二章對偶問題課件36價值系數(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ā)生變化價值系數(shù)變化的靈敏度分析例：在第一章美佳公司的例1中37原最終單純形表原最終單純形表38（1）改變后新的最優(yōu)解為：最優(yōu)目標函數(shù)值為：（1）改變后新的最優(yōu)解為：最優(yōu)目標函數(shù)值為：39（2）改變后為使表中的解仍為最優(yōu)解必須因此產(chǎn)品II的利潤變化范圍為（2）改變后為使表中的解仍為最優(yōu)解必須因此產(chǎn)品II的利潤變化40資源常數(shù)變化的靈敏度分析例：在第一章美佳公司的例1中（1）若設(shè)備A與調(diào)試工序的每天能力不變，而設(shè)備B每天的能力增加到32小時，分析公司最優(yōu)計劃的變化；（2）若設(shè)備A和B每天可用能力不變，則調(diào)試工序能力在什么范圍變化時，問題的最優(yōu)基不變資源常數(shù)變化的靈敏度分析例：在第一章美佳公司的例1中41（1）b由(15，24，5)T變?yōu)?15，32，5)T后，相應(yīng)地最終表中b列的數(shù)據(jù)變?yōu)榇朐罱K表（1）b由(15，24，5)T變?yōu)?15，32，5)T42（2）設(shè)現(xiàn)在每天調(diào)試工序的時間為x，則最終表中b列的數(shù)變?yōu)楣室棺顑?yōu)基不變必須（2）設(shè)現(xiàn)在每天調(diào)試工序的時間為x，則最終表中b列的數(shù)變?yōu)楣?3利用Excle求解LP問題，以P45.7(2)為例利用Excle求解LP問題，以P45.7(2)為例44變量，已經(jīng)賦了初值目標函數(shù)值約束條件右端值變量，已經(jīng)賦了初值目標函數(shù)值約束條件右端值45第二章對偶問題課件46第二章對偶問題課件47其他專業(yè)軟件：Lindo與Lingo，WinQSB例如Lingo，啟動Lingo后，按圖中的方式輸入模型，然后點擊求解的圖標。就可得到所需的最優(yōu)解。其他專業(yè)軟件：Lindo與Lingo，WinQSB例如Lin48第二章對偶問題課件492．4對偶問題為由圖解法可得對偶問題最優(yōu)解為將該最優(yōu)解代入對偶問題約束條件可知，第四個約束條件為嚴格不等式，因此在原問題最優(yōu)解中而由于因此將原問題最優(yōu)解代入原問題約束條件，它們成為等式。再由于原問題最優(yōu)目標函數(shù)值等于對偶問題最優(yōu)目標函數(shù)值。于是原問題最優(yōu)解滿足方程組2．4對偶問題為由圖解法可得對偶問題最優(yōu)解為將該最優(yōu)解代入50解方程組得原問題最優(yōu)解：解方程組得原問題最優(yōu)解：512.5對偶線性規(guī)劃為（2）直接觀察可知對偶問題有解對應(yīng)