運籌學 對偶理論和靈敏度分析學習課件

對偶理論和靈敏度分析OperationsResearch,Autumn2017,C.-J.Chang對偶問題的提出什么是對偶？對同一事物（或問題），從不同的角度（或立場）提出相對的兩種不同的表述。EX.在平面內(nèi)，矩形的面積與其周長之間的關(guān)系，有兩種不同的表述方法。周長一定，面積最大的矩形是正方形。面積一定，周長最短的矩形是正方形。這種表述有利于加深對事物的認識和理解。線性規(guī)劃問題也有對偶關(guān)系。23對偶問題的提出以例2-1來看對偶角度的表述。分析獲益狀況來追求利潤最大化

評估生產(chǎn)投入來獲得成本最小化(資源消耗最少)看似不同，但卻是同一件事原問題與對偶問題的關(guān)系對于同一數(shù)據(jù)集(a,c,b)，可以用“≤”不等式約束條件和目標函數(shù)最大化的原問題與“≥”不等式約束條件和目標函數(shù)最小化的對偶問題，建立標準的對應(yīng)關(guān)系。4原問題與對偶問題的關(guān)系5Ex.對偶問題的轉(zhuǎn)換試求下述線性規(guī)劃問題的對偶問題。6x1x2b1284016041223

y1y2y3c1402204381612

不熟練時，可以透過系數(shù)矩陣的轉(zhuǎn)置進行轉(zhuǎn)換極大化的對偶是極小化隨堂練習試求下述標準型式線性規(guī)劃問題的對偶問題。7大于約束條件對偶問題的變換形式8等式約束條件對偶問題的變換形式9非對稱形式的變換關(guān)系10大小變(+)約(+)約(+)變(-)Ex.非對稱對偶問題的轉(zhuǎn)換試求下述線性規(guī)劃問題的對偶問題。11大小變(+)約(+)約(+)變(-)隨堂練習寫出下列線性規(guī)劃問題的對偶問題。12對偶問題的基本性質(zhì)對稱性：對偶問題的對偶是原問題。弱對偶性：若

是原問題的可行解，

是對偶問題的可行解。則存在。無界性：若原問題(對偶問題)為無界解，則其對偶問題(原問題)無可行解。這個性質(zhì)不存在逆。當原問題(對偶問題)無可行解時，其對偶問題(原問題)具有無界解或無可行解。

13原問題對偶問題無界解無可行解無可行解無界解無界性已知線性規(guī)劃問題如下，試用對偶理論證明其無最優(yōu)解(無界解)。14先寫出對偶問題由對偶問題的第一個約束條件可知對偶問題無可行解，原問題應(yīng)為無界解或無可行解。而原問題至少有一可行解X=(0,0,0)T，因此原問題應(yīng)為無界解(無最優(yōu)解)。對偶問題的基本性質(zhì)可行解是最優(yōu)解時的性質(zhì)：設(shè)

是原問題的可行解，

是對偶問題的可行解，當

時，與是最優(yōu)解。對偶定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解；且目標函數(shù)值相等。15原問題與對偶問題解的可能情況兩個問題都有最優(yōu)解，若記為X*和Y*，必有CX*=Y*b一個問題無界，則另一個問題無可行解。兩個問題都無可行解。16對偶問題的基本性質(zhì)互補松弛性：若與分別是原問題和對偶問題的可行解。那么和，當且僅當與為最優(yōu)解。XS與YS分別代表松弛變量向量與剩余變量向量即上面的每對互乘因子中，一個松(不等于)，另一個必緊(等于)，這就所謂的互補松緊。嚴格不等式的約束條件所對應(yīng)的對偶變量必是零；非零的對偶變量所對應(yīng)的約束條件必是等式。17互補松弛性已知線性規(guī)劃問題如下，其對偶問題最優(yōu)解為,

;z=5。試用對偶理論找出原問題的最優(yōu)解。18先寫出對偶問題[2?(4/5+2*(3/5))]=0?≠0≠0≠0=0000?≠0≠0代入所以原問題的最優(yōu)解為X*=(1,0,0,0,1)T;ω=5找出對偶問題中那些約束條件是嚴格不等式，其對應(yīng)的變量為0。代入原問題的約束條件，其應(yīng)為等式。00隨堂練習已知線性規(guī)劃問題如下，其對偶問題的最優(yōu)解為,

，試應(yīng)用對偶問題的性質(zhì)，求原問題的最優(yōu)解。19提示：先寫出對偶問題。透過互補松弛性求解原問題。X*=(0,0,4,4)T;z=44隨堂練習試通過求對偶問題的最優(yōu)解，來求解下列線性規(guī)劃問題之原問題的解。20提示：先轉(zhuǎn)換成對偶問題。使用圖解法求解對偶問題。透過互補松弛性求解原問題。X*=(1,2,0,0,0)T;z=11Y*=(1,3);ω=11隨堂練習試通過求對偶問題的最優(yōu)解，來求解下列線性規(guī)劃問題之原問題的解。21提示：先轉(zhuǎn)換成對偶問題。使用圖解法求解對偶問題。透過互補松弛性求解原問題。X*=(7/5,0,1/5,0)T;z=19/5Y*=(8/5,1/5);ω=19/5單純形法的矩陣描述單純形法的運作方式是由一個初始基可行解，逐步轉(zhuǎn)移至其它基可行解以改善目標函數(shù)值，反復(fù)運作直到找出最佳解為止。

22每組基可行解都對應(yīng)一組基，所以求解過程也就是基的轉(zhuǎn)換。既然單純形運算過程中，轉(zhuǎn)換的是基，那我們是不是可以用基來描繪出單純形表的一般式。單純形法的矩陣描述設(shè)線性規(guī)劃問題可以用如下矩陣形式表示：

目標函數(shù)maxz=CX

約束條件AX≤b

非負條件X≥0約束條件加入松弛變量后，可得到標準型：

maxz=CX+0Xs

AX+IXs=b

(其中I是m×m單位矩陣)

X,Xs≥0系數(shù)矩陣(A,I)可分成基矩陣與非基矩陣(B,N)，問題可改寫成：

maxz=CBXB+CNXN

BXB+NXN=b

XB,XN≥023單純形法的矩陣描述由BXB+NXN=b可得：

BXB+NXN=b→BXB=b?NXN

→XB=B?1(b?NXN)

→XB=B?1b?B?1NXN此時：

z=CBXB+CNXN=CB(B?1b?B?1NXN)+CNXN

=CBB?1b+(CN?CBB?1N)XN令非基變量XN=0，則基變量XB=B?1b，基可行解為(B?1b,0)T，目標函數(shù)z=CBB?1b。24這部份就是我們的檢驗數(shù)cj?zj單純形法的矩陣描述基變量XB非基變量XN等式右邊RHS系數(shù)矩陣IB?1NB?1b檢驗數(shù)0CN?CBB?1N?CBB?1b25一開始是松弛變量的部份B?1?CBB?1對偶問題的基本性質(zhì)原問題檢驗數(shù)與對偶問題解的關(guān)系。設(shè)原問題是

maxz=CX;AX+XS=b;X,XS≥0

對偶問題是

minω=Yb;YA?YS=C;Y,YS≥0

則原問題單純型表的檢驗數(shù)行對應(yīng)其對偶問題的一個基解，其對應(yīng)關(guān)系如下表。

這里YS1是對應(yīng)原問題中基變量XB的剩余變量，YS2是對應(yīng)原問題中非基變量XN的剩余變量。26原問題XBXNXS檢驗數(shù)0CN?CBB-1N?CBB-1對偶問題YS1?YS2?Y原問題與對偶問題在單形表的判讀原問題與對偶問題的目標函數(shù)會有相同的最佳值松弛變量(約束條件為≤)：對偶問題的解是cj?zj的相反數(shù)。剩余變量(約束條件為≥)：對偶問題的解是cj?zj的值。人工變量(約束條件為=)：對偶問題的解是M?(cj?zj)。約束條件為≥也可由人工變量讀出解，從剩余變量與人工變量讀出的解會相同。27原問題與對偶問題的解已知某線性規(guī)劃問題及其最后單形表如下，請分別寫出原始問題與對偶問題的解。28cj5040000θiCBXBbx1x2x3x4x540x212018/250-3/250x4800-8/2513/2550x13010-1/501/5cj-zj00-14/50-26/5y4y5y1y2y3所以原問題的最優(yōu)解為

X*=(30,12,0,8,0)T;z=1980對偶問題的最優(yōu)解為

Y*=(14/5,0,26/5,0,0);ω=1980隨堂練習一線性規(guī)劃問題之原問題如左下；利用單純形法解其對偶問題后所得之最后單形表如右下。請分別寫出原始問題與對偶問題的解。29cj34000θiCBXBBy1y2y3y4y54y21/5012/5-1/503y18/5101/52/500y59/500-7/51/51cj-zj00-11/5-2/50x4x5x1x2x3所以原問題的最優(yōu)解為

X*=(11/5,2/5,0,0,0)T;z=28/5對偶問題的最優(yōu)解為

Y*=(8/5,1/5,0,0,9/5);ω=28/5隨堂練習一線性規(guī)劃問題之原問題如左下；利用單純形法解其對偶問題后所得之最后單形表如右下。請分別寫出原始問題與對偶問題的解。30cj10121200θiCBXBBy1y2y3y4y510y11/410-3/41/4-1/412y27/80119/8-1/85/8cj-zj00-9-1-5所以原問題的最優(yōu)解為

X*=(1,5,0,0,9)T;z=13對偶問題的最優(yōu)解為

Y*=(1/4,7/8,0,0,0);ω=13影子價格以例2-1來看

31z=(產(chǎn)品Ⅰ的利潤)×(產(chǎn)品Ⅰ的數(shù)量x1)+(產(chǎn)品Ⅱ的利潤)×(產(chǎn)品Ⅱ的數(shù)量x2)ω=(設(shè)備的臺時)×(y1)+(原材料A數(shù)量)×(y2)+(原材料B數(shù)量)×(y3)原問題與對偶問題目標函數(shù)的最優(yōu)值相等，量綱也應(yīng)該一致。對偶變量可理解為每個單位資源的價值(價格)，這就是所謂的對偶價格或影子價格。cj23000θiCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/80y1*=1.5,y2*=0.125,y3*=0影子價格的意義影子價格反映資源對目標函數(shù)的邊際貢獻，即資源轉(zhuǎn)換成經(jīng)濟效益的效率。這說明是其他條件不變的情況下，若設(shè)備增加一臺時，該廠按最優(yōu)計劃安排生產(chǎn)可多獲利1.5元；原材料A增加1kg，可多獲利0.125元；原材料B增加1kg，對獲利無影響。32影子價格的意義影子價格反映了資源的稀缺程度。當某種資源的yi*?0，表示這種資源短缺。決策者要增加收入，應(yīng)先增加影子價格高的資源。當某種資源的yi*=0，表示這種資源有剩余，不短缺。影子價格反映出資源的邊際使用價值。假設(shè)該工廠的決策者決定不生產(chǎn)產(chǎn)品Ⅰ、Ⅱ，而將其所有資源出租或外售。影子價格就代表此時工廠決策者對每種資源給出的最低定價或附加額。33請先將下列線性規(guī)劃問題轉(zhuǎn)換成對偶問題，再使用單純形法求解。(須寫出原問題與對偶問題的解)原問題與對偶問題是一體兩面的關(guān)系，一張單形表可以同時找到原問題與對偶問題的解。那可以不轉(zhuǎn)換成對偶問題，直接用原問題的單形表搭配求解對偶問題的邏輯進行求解嗎？隨堂練習34對偶單純形法的思維對偶單純形法是將對偶問題的思維引入單純形法用以解決原問題的一種方法。一般單純形法是從一個基可行解(對偶解為基解)開始進行迭代，目標值逐步上升，進而達到線性規(guī)劃問題的最優(yōu)解(此時對偶解為基可行解)。對偶單純形法則是從一個基解(對偶解為基可行解)開始進行迭代，目標值逐步下降，進而達到線性規(guī)劃問題的最優(yōu)解(此時原問題為基可行解)。35對偶單純形法適合時機可以很容易地得到初始對偶基可行解時B?1b至少存在一個負分量

(≥限制式轉(zhuǎn)換為=限制式時，以松弛變量處理)檢驗數(shù)都為非正(max問題的目標函數(shù)系數(shù)均為負值)36對偶單純形法步驟(針對max問題)對線性規(guī)劃問題進行變換，使列出的初始單純形表中所有的檢驗數(shù)σj≤0(即對偶問題為基可行解)。檢查b列的數(shù)字，若都為非負(≥0)，檢驗數(shù)都為非正(≤0)，則已得到最優(yōu)解；否則應(yīng)繼續(xù)計算。確定換出變量。

選取最小負值的bi為換出變量。確定換入變量。

在單純形表中檢查xi所在行的各系數(shù)aij。若所有aij≥0，則無可行解，停止計算。若存在aij＜0,則選擇正最小比值的(cj?zj)/aij為換入變量。進行迭代計算，得到新的單純形表，并回到步驟2。37對偶單純型法用對偶單純型法求解下列限性規(guī)劃問題。38先改寫問題，以符合初始要求目標函數(shù)系數(shù)皆為負。等式右邊的值至少有一個為負。cj-2-3-400CBXBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301cj-zj-2-3-400建立初始單形表挑選負最多的行1-4/3--挑選出最小比值，分母只考慮aij系數(shù)為負的部份(比值計算后為正)[]進行旋轉(zhuǎn)運算39cj-2-3-400CBXBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301cj-zj-2-3-400[]因為b列數(shù)字皆≥0，檢驗數(shù)皆為非正，故問題已得到最優(yōu)解，X*=(11/5,2/5,0,0,0)T，ω*=2×(11/5)+3×(2/5)=28/5Y*=(8/5,1/5,0,0,9/5),目標值為28/51-4/3--cj-2-3-400CBXBbx1x2x3x4x50x4-10-5/21/21-1/2-2x121-1/23/20-1/2cj-zj0-4-10-1-8/5--2[]cj-2-3-400CBXBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5cj-zj00-9/5-8/5-1/5一般純單形法和對偶單純形法的差異差異項目一般單純形法對偶單純形法cj?zj不受正負限制。必須均為負值。bi必須均為非負值。不受正負限制。最優(yōu)解判斷所有(cj?zj)≥0，若有(cj?zj)<0要繼續(xù)算。所有bi≥0，若有bi<0要繼續(xù)算。換入變量確定選取最大正值的(cj?zj)為換入變量。選取最小負值的bi為換出變量。換出變量確定只考慮換入變量列中，系數(shù)為正的變量為換出變量。換出變量選擇正最小比值的bi/aij。

只考慮換出變量行中，系數(shù)為負的變量為換入變量。換入變量選擇正最小比值的(cj?zj)/aij。運算步驟先確定換入變量，再決定換出變量。先確定換出變量，再決定換出變量。40隨堂練習使用對偶單純型法求解下面的線性規(guī)劃問題：41X*=(5/2,3/2,0,0)T;z=52X*=(2,2,2,0,0,0)T;z=72X*=(1,2,0,0,0)T;z=11靈敏度分析前面討論線性規(guī)劃問題時，假定aij,bi,cj都是常數(shù)。但實際上這些系數(shù)往往是估計值和預(yù)測值。如市場條件發(fā)生變化，cj值就會變化；aij會因工藝條件的改變而改變；bi則根據(jù)資源投入后的經(jīng)濟效果決定的一種決策選擇。因此提出這樣兩個問題：當這些系數(shù)有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化。或者這些系數(shù)在什么范圍內(nèi)變化時，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變。42靈敏度分析當線性規(guī)劃問題中某一個或某幾個系數(shù)發(fā)生變化后，原來已得結(jié)果一般會發(fā)生變化。當然可以用單純型表從頭計算，以便得到新的最優(yōu)解。但這樣做很麻煩也沒有必要。因為單純形法迭代時，每次運算都和基變量的系數(shù)矩陣B有關(guān)，因此可以把發(fā)生變化的個別系數(shù)，經(jīng)過一定計算后直接填入最終計算表中，并進行檢查和分析，再依不同情況處理。43原問題對偶問題結(jié)論或繼續(xù)計算的步驟可行解可行解表中的解仍為最優(yōu)解可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進人工變量，編制新的單純形表，求最優(yōu)解靈敏度分析資源變量bi的變化可行范圍：為了保證基變量非負，bi必須確保b≥0若bi改變使b<0，則須繼續(xù)運算求最優(yōu)解。價值系數(shù)cj的變化最優(yōu)范圍：為了確保當前解為最優(yōu)，cj必須確保檢驗數(shù)≤0若cj改變使檢驗數(shù)>0，則須繼續(xù)運算求最優(yōu)解。技術(shù)系數(shù)的變化新增一種產(chǎn)品：新增一列代表新產(chǎn)品，再繼續(xù)運算求最優(yōu)解原產(chǎn)品的技術(shù)系數(shù)發(fā)生變化：以新的系數(shù)計算最終單形表相應(yīng)的列向量，以取代原來的變量，并繼續(xù)運算求最優(yōu)解。44cjCBCN0CBXBbXBXNXSCBXBB?1bIB?1NB?1cj-zj0CN?CBB?1N?CBB?1靈敏度分析已知線性規(guī)劃問題的最終單形表如下，試問：當約束條件右端項b1與b3保持不變時，b2在什么范圍內(nèi)變化，最優(yōu)基會保持不變。當目標函數(shù)系數(shù)c1保持不變時，c2在什么范圍內(nèi)變動，最優(yōu)解會保持不變。45cj23000θiCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/80資源變量bi的變化46cj23000θiCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/80cj23000θiCBXBbx1x2x3x4x50x38121000x416400100x51204001cj-zj最終單純形表初始單純形表價值系數(shù)cj的變化47cj2c2000θiCBXBbx1x2x3x4x52x141001/400x5400-21/21c2x22011/2-1/80cj-zj00-3/2-1/80最終單純形表靈敏度分析延續(xù)上題，若該廠從其它處抽調(diào)4臺時用于生產(chǎn)產(chǎn)品Ⅰ與Ⅱ，求這時該廠生產(chǎn)產(chǎn)品Ⅰ、Ⅱ的最優(yōu)方案。48cj23000θiCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/80cj23000θiCBXBbx1x2x3x4x52x141001/400x5-400-21/213x24011/2-1/80cj-zj00-3/2-1/80cj23000θiCBXBbx1x2x3x4x52x141001/400x32001-1/4-1/23x2301001/4cj-zj000-1/2-3/4[]所以最優(yōu)解為

x1=4,x2=3;z=4×2+3×3=17使用對偶單純型法繼續(xù)運算新增一種產(chǎn)品延續(xù)前題，若工廠除了產(chǎn)品Ⅰ與Ⅱ外，又開發(fā)了一種新產(chǎn)品Ⅲ。已知生產(chǎn)產(chǎn)品Ⅲ需使用設(shè)備2臺時，原材料A與B各6kg與3kg；每件可獲利5元。問該廠是否應(yīng)生產(chǎn)該產(chǎn)品和生產(chǎn)多少？49cj230005θiCBXBbx1x2x3x4x5xnew2x141001/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/803/221/45/48/328cj230005θiCBXBbx1x2x3x4x5xnew2x11101.5-1/8-3/405xnew200-11/41/213x23/2013/4-3/16-1/80cj-zj00-3/2-7/16-5/80所以最優(yōu)解為

x1=1,x2=1.5,xnew=2;z=16.5[]技術(shù)系數(shù)發(fā)生變化延續(xù)前題，若工廠生產(chǎn)產(chǎn)品Ⅰ的工藝結(jié)構(gòu)有了改進，這時它的技術(shù)系數(shù)向量變?yōu)镻1′=(2,5,