對偶理論和靈敏分析詳解2

對偶理論和靈敏度分析詳解演示文稿1現(xiàn)在是1頁\一共有34頁\編輯于星期一優(yōu)選對偶理論和靈敏度分析2現(xiàn)在是2頁\一共有34頁\編輯于星期一引例：經(jīng)營策略問題。甲工廠有設(shè)備和原料A、B這些設(shè)備和原料可用于Ⅰ、Ⅱ兩種產(chǎn)品的加工，每件產(chǎn)品加工所需機時數(shù)，原料A、B消耗量，每件產(chǎn)品的利潤值及每種設(shè)備的可利用的機時數(shù)如下表?，F(xiàn)在乙廠和甲廠協(xié)商，打算租用甲廠的設(shè)備購買資源A和B。問甲廠采取哪種經(jīng)營策略，是自己生產(chǎn)產(chǎn)品還是出租設(shè)備、出讓原材料？如果出租設(shè)備、出讓原材料，在和乙廠協(xié)商時出租設(shè)備和出讓原材料A,B的底價應(yīng)是多少？對偶問題的提出

Ⅰ

Ⅱ設(shè)

備原料A原料B140204

80臺時

160kg120kg23盈利3Chapter1現(xiàn)在是3頁\一共有34頁\編輯于星期一自己生產(chǎn)：原問題引例分析：4Chapter1現(xiàn)在是4頁\一共有34頁\編輯于星期一設(shè)y1,y2和y3分別表示出租單位設(shè)備臺時的租金和出讓單位原材料A,B的附加額ω=80y1+160y2+120y3出售資源對偶問題顯然商人希望總的收購價越小越好工廠希望出售資源后所得不應(yīng)比生產(chǎn)產(chǎn)品所得少目標函數(shù)min5Chapter1現(xiàn)在是5頁\一共有34頁\編輯于星期一例1它的對偶問題是：YA≥Cminω=YbY≥0Y=（y1，y2，y3）6Chapter1現(xiàn)在是6頁\一共有34頁\編輯于星期一1.5.1原問題與對偶問題的關(guān)系(對稱形式)線性規(guī)劃的對偶理論7Chapter1現(xiàn)在是7頁\一共有34頁\編輯于星期一8Chapter1現(xiàn)在是8頁\一共有34頁\編輯于星期一

原關(guān)系minw對偶關(guān)系maxzxy原問題與對偶問題的對稱形式9Chapter1現(xiàn)在是9頁\一共有34頁\編輯于星期一

標準(max,)型的對偶變換目標函數(shù)由max型變?yōu)閙in型對應(yīng)原問題每個約束行有一個對偶變量yi，i=1,2,…,m對偶問題約束為型，有n

行原問題的價值系數(shù)C變換為對偶問題的右端項原問題的右端項b變換為對偶問題的價值系數(shù)原問題的技術(shù)系數(shù)矩陣A轉(zhuǎn)置后成為對偶問題的技術(shù)系數(shù)矩陣原問題與對偶問題互為對偶對偶問題可能比原問題容易求解對偶問題還有很多理論和實際應(yīng)用的意義10Chapter1現(xiàn)在是10頁\一共有34頁\編輯于星期一原問題與對偶問題的結(jié)構(gòu)關(guān)系原問題與對偶問題中的目標函數(shù)的優(yōu)化方向相反（前者為極大，后者為極?。┰瓎栴}的每個約束條件對應(yīng)于對偶問題的一個決策變量，且約束條件的資源系數(shù)（右端的常數(shù)項）為相應(yīng)決策變量的價值系數(shù)原問題的每個決策變量對應(yīng)于對偶問題的一個約束條件，且決策變量的價值系數(shù)為相應(yīng)約束條件的右端常數(shù)項對偶問題中的系數(shù)矩陣為原問題中的系數(shù)矩陣的轉(zhuǎn)置原問題約束條件中的小于等于符號對應(yīng)于對偶問題中的對偶變量取非負約束，原問題中決策的對偶問題非負約束在對偶問題中體現(xiàn)為相應(yīng)的約束條件取大于等于符號11Chapter1現(xiàn)在是11頁\一共有34頁\編輯于星期一

非標準型的對偶變換12Chapter1現(xiàn)在是12頁\一共有34頁\編輯于星期一

對偶變換的規(guī)則13Chapter1現(xiàn)在是13頁\一共有34頁\編輯于星期一maxω=5y1+4y2+6y3≥≤≤y1+2y2y1+y3-3y1+2y2+y3y1-y2+y3=23-5

1y1≥

0，y2≤0,y3無約束對偶問題例3寫出線性規(guī)劃問題的對偶問題minz=2x1+3x2-5x3+x4原問題

x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4=6x1

≤0,x2,x3≥0,x4無約束14Chapter1現(xiàn)在是14頁\一共有34頁\編輯于星期一（1）對稱性：對偶的對偶就是原始問題minω’=-CXs.t.-AX≥-b X≥0maxz’=-Ybs.t.-YA≤-C Y≥0minω=Ybs.t.YA≥CY≥0maxz=CXs.t.AX≤bX≥0對偶的定義對偶的定義1.5.2對偶問題的基本性質(zhì)

為了便于討論，下面不妨總是假設(shè)15Chapter1現(xiàn)在是15頁\一共有34頁\編輯于星期一(2)弱對偶性:若是原問題的可行解，是對偶問題的可行解。則存在對偶問題(min)的任何可行解Y，其目標函數(shù)值總是不小于原問題(max)任何可行解X的目標函數(shù)值16Chapter1現(xiàn)在是16頁\一共有34頁\編輯于星期一

弱對偶定理推論原問題的任何可行解目標函數(shù)值是其對偶問題目標函數(shù)值的下限；對偶問題的任何可行解目標函數(shù)值是原問題目標函數(shù)值的上限如果原(對偶)問題為無界解，則其對偶(原)問題無可行解如果原(對偶)問題有可行解，其對偶(原)問題無可行解，則原問題為無界解當原問題(對偶問題)為無可行解,其對偶問題(原問題)或具有無界解或無可行解17Chapter1現(xiàn)在是17頁\一共有34頁\編輯于星期一(3)強對偶性證：由弱對偶定理推論1，結(jié)論是顯然的。

若是原問題的可行解，是對偶問題可行解，當 ,,分別是相應(yīng)問題的最優(yōu)解是使目標函數(shù)取最小值的解，因此是最優(yōu)解

可行解是最優(yōu)解的性質(zhì)(最優(yōu)性準則定理)18Chapter1現(xiàn)在是18頁\一共有34頁\編輯于星期一

(4)對偶定理

若原問題和對偶問題兩者皆可行,則兩者均有最優(yōu)解,且此時目標函數(shù)值相等.第1部分:證明兩者均有最優(yōu)解證明分兩部分由于原問題和對偶問題均可行,根據(jù)弱對偶性,可知兩者均有界,于是均有最優(yōu)解.19Chapter1現(xiàn)在是19頁\一共有34頁\編輯于星期一第2部分:證明有相同的目標函數(shù)值設(shè)為原問題的最優(yōu)解它所對應(yīng)的基矩陣是B，則其檢驗數(shù)滿足CCBB1A0因此有對偶問題目標函數(shù)值而原問題最優(yōu)解的目標函數(shù)值為顯然

為對偶問題的可行解。證畢故由最優(yōu)解準則定理可知

為對偶問題的最優(yōu)解.20Chapter1現(xiàn)在是20頁\一共有34頁\編輯于星期一對偶定理推論根據(jù)對偶定理第2部分的證明,可以得出:若互為對偶的線性規(guī)劃問題中的任一個有最優(yōu)解,則另一個也有最優(yōu)解,且目標函數(shù)值相等.綜上所述,一對對偶問題的解必然是下列三種情況之一:原問題和對偶問題都有最優(yōu)解一個問題具有無界解,另一個問題無可行解原問題和對偶問題都無可行解21Chapter1現(xiàn)在是21頁\一共有34頁\編輯于星期一

(5)互補松弛定理證：由定理所設(shè)，可知有

設(shè),

分別是原問題和對偶問題的可行解，為原問題的松弛變量的值，為對偶問題剩余變量的值。

,

分別是原問題和對偶問題最優(yōu)解的充分必要條件是分別以左乘(1)式，以

右乘(2)式后，兩式相減，得

根據(jù)最優(yōu)解判別定理，分別是原問題和對偶問題最優(yōu)解。反之亦然。證畢。（1）（2）22Chapter1現(xiàn)在是22頁\一共有34頁\編輯于星期一maxz=CXs.t. AX+XS=b X,XS≥0minw=Ybs.t.AY-YS=C Y,YS

≥0XYS=0YXS=0mn=YYSA-ICn=AXSIbnmmX原始問題和對偶問題變量、松弛變量的維數(shù)23Chapter1現(xiàn)在是23頁\一共有34頁\編輯于星期一原始問題和對偶問題最優(yōu)解之間的互補松弛關(guān)系maxz=CX

s.t.AX+XS=bX,XS≥0minw=bYs.t.AY-YS=CY,YS≥0maxz=CXs.t.AX≤bX≥0minw=bYs.t.AY≥CY≥0對偶引進松弛變量引進松弛變量XYS=0YXS=0互補松弛關(guān)系X，XsY，Ys24Chapter1現(xiàn)在是24頁\一共有34頁\編輯于星期一y1

yiym

ym+1ym+jyn+m

x1xjxn

xn+1xn+ixn+m

對偶問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對變量中，其中一個大于0，另一個一定等于0原始問題的變量對偶問題的松弛變量25Chapter1現(xiàn)在是25頁\一共有34頁\編輯于星期一(6)原問題單純形表檢驗數(shù)行與對偶問題解的關(guān)系原問題單純形表檢驗數(shù)的相反數(shù)對應(yīng)對偶問題的一個基解.顯然,原問題最終單純形表檢驗數(shù)的相反數(shù)對應(yīng)對偶問題的一個基可行解026Chapter1現(xiàn)在是26頁\一共有34頁\編輯于星期一證：標準化后的原問題和對偶問題的表達式為：若B是A中的一個基，A=（B，N）27Chapter1現(xiàn)在是27頁\一共有34頁\編輯于星期一原問題解為XB=B-1b，σN=CN-CBB-1N，Z=CBB-1b對偶問題的約束條件：0檢驗數(shù)：σB=CB-CBB-1B=0，σN=CN-CBB-1N，σS=CBB-1原問題單純形表檢驗數(shù)行與對偶問題解的關(guān)系28Chapter1現(xiàn)在是28頁\一共有34頁\編輯于星期一結(jié)論：單純形表中的檢驗數(shù)行和對偶問題的解僅差一個符號yi等于原問題的第i個方程中的松弛變量所對應(yīng)的檢驗數(shù)的負數(shù)單純形法迭代時，原問題解為基可行解，相應(yīng)的檢驗數(shù)對應(yīng)對偶問題的一個解，在原問題沒有得到最優(yōu)解之前，對偶問題的解為非可行解基可行解基可行解非可行解基可行解目標函數(shù)對偶問題原問題無可行解無界解原問題為可行解時，對偶問題不一定有可行解，當原問題為最優(yōu)解，對偶問題一定有最優(yōu)解29Chapter1現(xiàn)在是29頁\一共有34頁\編輯于星期一例4試用對偶理論證明該線性規(guī)劃問題無最優(yōu)解。證：該問題存在可行解，X=（0，0，0）；對偶問題為：由第一個約束條件可知對偶問題無可行解，因此，原問題有可行解，無最優(yōu)解。30Chapter1現(xiàn)在是30頁\一共有34頁\編輯于星期一例5：試用對偶理論找出原問題的最優(yōu)解。解：原問題的對偶問題為：已知其對偶問題的最優(yōu)解為：31Chapter1現(xiàn)在是31頁\一共有34頁\編輯于星期一代入對偶問題的約束條件，得2,3,4式為嚴格不等式，由互補松弛性得因原問題的約束條件應(yīng)取等式為：求解后得到原問題的最優(yōu)解為:32Chapter1現(xiàn)在是32頁\一共有34頁\編輯于星期一原問題的最優(yōu)解為:Z*=CBB-1b=CX*=Y*b對偶問題的經(jīng)濟解釋---影子價格z=CX=CBB-1b+σNXN=CBB-1bσN=CN-CBB-1NY=CBB-1為