第二章對偶問題

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

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