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

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

難點(diǎn)：對(duì)偶理論基本要求：掌握對(duì)偶關(guān)系，理解對(duì)偶性質(zhì)，掌握對(duì)偶單純形法，會(huì)求影子價(jià)格，第2頁,共40頁，星期六，2024年，5月引例：經(jīng)營(yíng)策略問題。甲工廠有設(shè)備和原料A、B這些設(shè)備和原料可用于Ⅰ、Ⅱ兩種產(chǎn)品的加工，每件產(chǎn)品加工所需機(jī)時(shí)數(shù)，原料A、B消耗量，每件產(chǎn)品的利潤(rùn)值及每種設(shè)備的可利用的機(jī)時(shí)數(shù)如下表。現(xiàn)在乙廠和甲廠協(xié)商，打算租用甲廠的設(shè)備購(gòu)買資源A和B。問甲廠采取哪種經(jīng)營(yíng)策略，是自己生產(chǎn)產(chǎn)品還是出租設(shè)備、出讓原材料？如果出租設(shè)備、出讓原材料，在和乙廠協(xié)商時(shí)出租設(shè)備和出讓原材料A,B的底價(jià)應(yīng)是多少？對(duì)偶問題的提出

Ⅰ

Ⅱ設(shè)

備原料A原料B140204

80臺(tái)時(shí)

160kg120kg23盈利第3頁,共40頁，星期六，2024年，5月自己生產(chǎn)：原問題引例分析：第4頁,共40頁，星期六，2024年，5月設(shè)y1,y2和y3分別表示出租單位設(shè)備臺(tái)時(shí)的租金和出讓單位原材料A,B的附加額ω=80y1+160y2+120y3出售資源顯然商人希望總的收購(gòu)價(jià)越小越好工廠希望出售資源后所得不應(yīng)比生產(chǎn)產(chǎn)品所得少目標(biāo)函數(shù)min第5頁,共40頁，星期六，2024年，5月例1它的對(duì)偶問題是：YA≥Cminω=YbY≥0Y=（y1，y2，y3）第6頁,共40頁，星期六，2024年，5月1.5.1原問題與對(duì)偶問題的關(guān)系(對(duì)稱形式)線性規(guī)劃的對(duì)偶理論第7頁,共40頁，星期六，2024年，5月第8頁,共40頁，星期六，2024年，5月原關(guān)系minw對(duì)偶關(guān)系maxzxy原問題與對(duì)偶問題的對(duì)稱形式第9頁,共40頁，星期六，2024年，5月

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

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

非標(biāo)準(zhǔn)型的對(duì)偶變換第12頁,共40頁，星期六，2024年，5月對(duì)偶變換的規(guī)則第13頁,共40頁，星期六，2024年，5月maxω=5y1+4y2+6y3≥≤≤y1+2y2y1+y3-3y1+2y2+y3y1-y2+y3=23-5

1y1≥

0，y2≤0,y3無約束對(duì)偶問題例3寫出線性規(guī)劃問題的對(duì)偶問題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）對(duì)稱性：對(duì)偶的對(duì)偶就是原始問題minω’=-CXs.t.-AX≥-b X≥0maxz’=-Ybs.t.-YA≤-C Y≥0minω=Ybs.t.YA≥CY≥0maxz=CXs.t.AX≤bX≥0對(duì)偶的定義對(duì)偶的定義1.5.2對(duì)偶問題的基本性質(zhì)

為了便于討論，下面不妨總是假設(shè)第15頁,共40頁，星期六，2024年，5月(2)弱對(duì)偶性:若是原問題的可行解，是對(duì)偶問題的可行解。則存在對(duì)偶問題(min)的任何可行解Y，其目標(biāo)函數(shù)值總是不小于原問題(max)任何可行解X的目標(biāo)函數(shù)值第16頁,共40頁，星期六，2024年，5月弱對(duì)偶定理推論原問題的任何可行解目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的下限；對(duì)偶問題的任何可行解目標(biāo)函數(shù)值是原問題目標(biāo)函數(shù)值的上限如果原(對(duì)偶)問題為無界解，則其對(duì)偶(原)問題無可行解如果原(對(duì)偶)問題有可行解，其對(duì)偶(原)問題無可行解，則原問題為無界解當(dāng)原問題(對(duì)偶問題)為無可行解,其對(duì)偶問題(原問題)或具有無界解或無可行解第17頁,共40頁，星期六，2024年，5月(3)強(qiáng)對(duì)偶性證：由弱對(duì)偶定理推論1，結(jié)論是顯然的。

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

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

(4)對(duì)偶定理

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

CBB

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

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

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

設(shè),

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

,

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

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

根據(jù)最優(yōu)解判別定理，分別是原問題和對(duì)偶問題最優(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原始問題和對(duì)偶問題變量、松弛變量的維數(shù)第23頁,共40頁，星期六，2024年，5月原始問題和對(duì)偶問題最優(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對(duì)偶引進(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

對(duì)偶問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0原始問題的變量對(duì)偶問題的松弛變量第25頁,共40頁，星期六，2024年，5月(6)原問題單純形表檢驗(yàn)數(shù)行與對(duì)偶問題解的關(guān)系原問題單純形表檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)對(duì)偶問題的一個(gè)基解.顯然,原問題最終單純形表檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)對(duì)偶問題的一個(gè)基可行解0第26頁,共40頁，星期六，2024年，5月證：標(biāo)準(zhǔn)化后的原問題和對(duì)偶問題的表達(dá)式為：若B是A中的一個(gè)基，A=（B，N）第27頁,共40頁，星期六，2024年，5月原問題解為XB=B-1b，σN=CN-CBB-1N，Z=CBB-1b對(duì)偶問題的約束條件：0檢驗(yàn)數(shù)：σB=CB-CBB-1B=0，σN=CN-CBB-1N，σS=CBB-1原問題單純形表檢驗(yàn)數(shù)行與對(duì)偶問題解的關(guān)系第28頁,共40頁，星期六，2024年，5月結(jié)論：?jiǎn)渭冃伪碇械臋z驗(yàn)數(shù)行和對(duì)偶問題的解僅差一個(gè)符號(hào)yi等于原問題的第i個(gè)方程中的松弛變量所對(duì)應(yīng)的檢驗(yàn)數(shù)的負(fù)數(shù)單純形法迭代時(shí)，原問題解為基可行解，相應(yīng)的檢驗(yàn)數(shù)對(duì)應(yīng)對(duì)偶問題的一個(gè)解，在原問題沒有得到最優(yōu)解之前，對(duì)偶問題的解為非可行解基可行解基可行解非可行解基可行解目標(biāo)函數(shù)對(duì)偶問題原問題無可行解無界解第29頁,共40頁，星期六，2024年，5月例4試用對(duì)偶理論證明該線性規(guī)劃問題無最優(yōu)解。證：該問題存在可行解，X=（0，0，0）；對(duì)偶問題為：由第一個(gè)約束條件可知對(duì)偶問題無可行解，因此，原問題有可行解，無最優(yōu)解。第30頁,共40頁，星期六，2024年，5月例5：試用對(duì)偶理論找出原問題的最優(yōu)解。解：原問題的對(duì)偶問題為：已知其對(duì)偶問題的最優(yōu)解為：第31頁,共40頁，星期六，2024年，5月代入對(duì)偶問題的約束條件，得2,3,4式為嚴(yán)格不等式，由互補(bǔ)松弛性得因原問題的約束條件應(yīng)取等式為：求解后得到原問題的最優(yōu)解為:第32頁,共40頁，星期六，2024年，5月原問題的最優(yōu)解為:Z*=CBB-1b=CX*=Y*b對(duì)偶問題的經(jīng)濟(jì)解釋---影子價(jià)格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的一種估價(jià),估價(jià)是有條件的替代方案.第33頁,共40頁，星期六，2024年，5月1.5.3對(duì)偶單純形法單純形法原問題基可行解，對(duì)偶問題基解（非可行解）原問題基可行解，對(duì)偶問題基可行解….原問題基可行解，對(duì)偶問題基可行解原問題基解，對(duì)偶問題基可行解….對(duì)偶