規(guī)劃數(shù)學(xué)對偶理論和靈敏度分析

關(guān)于規(guī)劃數(shù)學(xué)對偶理論和靈敏度分析第3講對偶理論對偶問題的提出線性規(guī)劃的對偶理論對偶單純形法對偶問題的經(jīng)濟(jì)解釋---影子價格重點(diǎn)：對偶理論，對偶單純形法

難點(diǎn)：對偶理論基本要求：掌握對偶關(guān)系，理解對偶性質(zhì)，掌握對偶單純形法，會求影子價格，第2頁,共40頁，星期六，2024年，5月引例：經(jīng)營策略問題。甲工廠有設(shè)備和原料A、B這些設(shè)備和原料可用于Ⅰ、Ⅱ兩種產(chǎn)品的加工，每件產(chǎn)品加工所需機(jī)時數(shù)，原料A、B消耗量，每件產(chǎn)品的利潤值及每種設(shè)備的可利用的機(jī)時數(shù)如下表。現(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盈利第3頁,共40頁，星期六，2024年，5月自己生產(chǎn)：原問題引例分析：第4頁,共40頁，星期六，2024年，5月設(shè)y1,y2和y3分別表示出租單位設(shè)備臺時的租金和出讓單位原材料A,B的附加額ω=80y1+160y2+120y3出售資源顯然商人希望總的收購價越小越好工廠希望出售資源后所得不應(yīng)比生產(chǎn)產(chǎn)品所得少目標(biāo)函數(shù)min第5頁,共40頁，星期六，2024年，5月例1它的對偶問題是：YA≥Cminω=YbY≥0Y=（y1，y2，y3）第6頁,共40頁，星期六，2024年，5月1.5.1原問題與對偶問題的關(guān)系(對稱形式)線性規(guī)劃的對偶理論第7頁,共40頁，星期六，2024年，5月第8頁,共40頁，星期六，2024年，5月原關(guān)系minw對偶關(guān)系maxzxy原問題與對偶問題的對稱形式第9頁,共40頁，星期六，2024年，5月

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

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

非標(biāo)準(zhǔn)型的對偶變換第12頁,共40頁，星期六，2024年，5月對偶變換的規(guī)則第13頁,共40頁，星期六，2024年，5月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無約束第14頁,共40頁，星期六，2024年，5月（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è)第15頁,共40頁，星期六，2024年，5月(2)弱對偶性:若是原問題的可行解，是對偶問題的可行解。則存在對偶問題(min)的任何可行解Y，其目標(biāo)函數(shù)值總是不小于原問題(max)任何可行解X的目標(biāo)函數(shù)值第16頁,共40頁，星期六，2024年，5月弱對偶定理推論原問題的任何可行解目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下限；對偶問題的任何可行解目標(biāo)函數(shù)值是原問題目標(biāo)函數(shù)值的上限如果原(對偶)問題為無界解，則其對偶(原)問題無可行解如果原(對偶)問題有可行解，其對偶(原)問題無可行解，則原問題為無界解當(dāng)原問題(對偶問題)為無可行解,其對偶問題(原問題)或具有無界解或無可行解第17頁,共40頁，星期六，2024年，5月(3)強(qiáng)對偶性證：由弱對偶定理推論1，結(jié)論是顯然的。

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

可行解是最優(yōu)解的性質(zhì)(最優(yōu)性準(zhǔn)則定理)第18頁,共40頁，星期六，2024年，5月

(4)對偶定理

若原問題和對偶問題兩者皆可行,則兩者均有最優(yōu)解,且此時目標(biāo)函數(shù)值相等.第1部分:證明兩者均有最優(yōu)解證明分兩部分由于原問題和對偶問題均可行,根據(jù)弱對偶性,可知兩者均有界,于是均有最優(yōu)解.第19頁,共40頁，星期六，2024年，5月第2部分:證明有相同的目標(biāo)函數(shù)值設(shè)為原問題的最優(yōu)解它所對應(yīng)的基矩陣是B，則其檢驗(yàn)數(shù)滿足C

CBB

1A0因此有對偶問題目標(biāo)函數(shù)值而原問題最優(yōu)解的目標(biāo)函數(shù)值為顯然

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

為對偶問題的最優(yōu)解.第20頁,共40頁，星期六，2024年，5月對偶定理推論根據(jù)對偶定理第2部分的證明,可以得出:若互為對偶的線性規(guī)劃問題中的任一個有最優(yōu)解,則另一個也有最優(yōu)解,且目標(biāo)函數(shù)值相等.綜上所述,一對對偶問題的解必然是下列三種情況之一:原問題和對偶問題都有最優(yōu)解一個問題具有無界解,另一個問題無可行解原問題和對偶問題都無可行解第21頁,共40頁，星期六，2024年，5月(5)互補(bǔ)松弛定理證：由定理所設(shè)，可知有

設(shè),

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

,

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

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

根據(jù)最優(yōu)解判別定理，分別是原問題和對偶問題最優(yōu)解。反之亦然。證畢。（1）（2）第22頁,共40頁，星期六，2024年，5月maxz=CXs.t. AX+XS=b X,XS≥0minw=Ybs.t.AY-YS=C Y,YS

≥0XYS=0YXS=0mn=YYSA-ICn=AXSIbnmmX原始問題和對偶問題變量、松弛變量的維數(shù)第23頁,共40頁，星期六，2024年，5月原始問題和對偶問題最優(yōu)解之間的互補(bǔ)松弛關(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對偶引進(jìn)松弛變量引進(jìn)松弛變量XYS=0YXS=0互補(bǔ)松弛關(guān)系X，XsY，Ys第24頁,共40頁，星期六，2024年，5月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原始問題的變量對偶問題的松弛變量第25頁,共40頁，星期六，2024年，5月(6)原問題單純形表檢驗(yàn)數(shù)行與對偶問題解的關(guān)系原問題單純形表檢驗(yàn)數(shù)的相反數(shù)對應(yīng)對偶問題的一個基解.顯然,原問題最終單純形表檢驗(yàn)數(shù)的相反數(shù)對應(yīng)對偶問題的一個基可行解0第26頁,共40頁，星期六，2024年，5月證：標(biāo)準(zhǔn)化后的原問題和對偶問題的表達(dá)式為：若B是A中的一個基，A=（B，N）第27頁,共40頁，星期六，2024年，5月原問題解為XB=B-1b，σN=CN-CBB-1N，Z=CBB-1b對偶問題的約束條件：0檢驗(yàn)數(shù)：σB=CB-CBB-1B=0，σN=CN-CBB-1N，σS=CBB-1原問題單純形表檢驗(yàn)數(shù)行與對偶問題解的關(guān)系第28頁,共40頁，星期六，2024年，5月結(jié)論：單純形表中的檢驗(yàn)數(shù)行和對偶問題的解僅差一個符號yi等于原問題的第i個方程中的松弛變量所對應(yīng)的檢驗(yàn)數(shù)的負(fù)數(shù)單純形法迭代時，原問題解為基可行解，相應(yīng)的檢驗(yàn)數(shù)對應(yīng)對偶問題的一個解，在原問題沒有得到最優(yōu)解之前，對偶問題的解為非可行解基可行解基可行解非可行解基可行解目標(biāo)函數(shù)對偶問題原問題無可行解無界解第29頁,共40頁，星期六，2024年，5月例4試用對偶理論證明該線性規(guī)劃問題無最優(yōu)解。證：該問題存在可行解，X=（0，0，0）；對偶問題為：由第一個約束條件可知對偶問題無可行解，因此，原問題有可行解，無最優(yōu)解。第30頁,共40頁，星期六，2024年，5月例5：試用對偶理論找出原問題的最優(yōu)解。解：原問題的對偶問題為：已知其對偶問題的最優(yōu)解為：第31頁,共40頁，星期六，2024年，5月代入對偶問題的約束條件，得2,3,4式為嚴(yán)格不等式，由互補(bǔ)松弛性得因原問題的約束條件應(yīng)取等式為：求解后得到原問題的最優(yōu)解為:第32頁,共40頁，星期六，2024年，5月原問題的最優(yōu)解為:Z*=CBB-1b=CX*=Y*b對偶問題的經(jīng)濟(jì)解釋---影子價格z=CX=CBB-1b+σNXN=CBB-1bσN=CN-CBB-1NY=CBB-1為單純形乘子當(dāng)b為變量的情況下,當(dāng)bi發(fā)生變化:yi的經(jīng)濟(jì)意義是：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化.yi是bi的一種估價,估價是有條件的替代方案.第33頁,共40頁，星期六，2024年，5月1.5.3對偶單純形法單純形法原問題基可行解，對偶問題基解（非可行解）原問題基可行解，對偶問題基可行解….原問題基可行解，對偶問題基可行解原問題基解，對偶問題基可行解….對偶