第二章 對(duì)偶理論

第二章對(duì)偶理論第一頁(yè)，共二十八頁(yè)，2022年，8月28日原始問(wèn)題minz=CTXs.t. AX≥b X≥0對(duì)偶問(wèn)題Maxw=bTys.t.ATy≤C y≥0≥minbACTCATbT≤maxmnmn一、對(duì)偶的定義第二頁(yè)，共二十八頁(yè)，2022年，8月28日對(duì)偶的定義當(dāng)原問(wèn)題為求極小值時(shí)，對(duì)偶問(wèn)題為求極大值。原始問(wèn)題中目標(biāo)函數(shù)的系數(shù)變成對(duì)偶問(wèn)題中約束條件的右端；原始問(wèn)題中約束條件的右端變成對(duì)偶問(wèn)題中目標(biāo)函數(shù)的系數(shù)。原始問(wèn)題約束條件系數(shù)矩陣的轉(zhuǎn)置對(duì)應(yīng)對(duì)偶問(wèn)題中約束條件的系數(shù)矩陣。原始問(wèn)題的約束條件個(gè)數(shù)決定對(duì)偶問(wèn)題變量的個(gè)數(shù)；原始問(wèn)題變量個(gè)數(shù)，決定對(duì)偶問(wèn)題的約束個(gè)數(shù)。原始問(wèn)題的約束方程的匹配形式?jīng)Q定對(duì)偶問(wèn)題變量的符號(hào)；原始問(wèn)題決策變量的符號(hào)決定所對(duì)應(yīng)對(duì)偶問(wèn)題的約束方程的匹配形式。第三頁(yè)，共二十八頁(yè)，2022年，8月28日原始問(wèn)題（prime)與對(duì)偶問(wèn)題之間的關(guān)系極小化問(wèn)題（min)極大化問(wèn)題（max)

變量Xj≥0約束∑aijwj

≤bi

Xj:unr∑aijwj=biXj

≤0∑aijwj

≥bi約束∑aijxj

≥bi變量wj

≥0∑aijxj

=biwj:unr

∑aijxj

≤biwj

≤0第四頁(yè)，共二十八頁(yè)，2022年，8月28日對(duì)偶問(wèn)題的形成minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≤≥=≥unr≤≥≥=≤≥x1≥0x2≤0x3:unr原始問(wèn)題變量的個(gè)數(shù)(3)等于對(duì)偶問(wèn)題約束條件的個(gè)數(shù)(3)；原始問(wèn)題約束條件的個(gè)數(shù)(4)等于對(duì)偶問(wèn)題變量的個(gè)數(shù)(4)。原始問(wèn)題變量的性質(zhì)影響對(duì)偶問(wèn)題約束條件的性質(zhì)，用

表示原始問(wèn)題約束條件的性質(zhì)影響對(duì)偶問(wèn)題變量的性質(zhì)，用表示第五頁(yè)，共二十八頁(yè)，2022年，8月28日對(duì)偶問(wèn)題的解p84當(dāng)原始問(wèn)題有最優(yōu)解時(shí)，對(duì)偶問(wèn)題也有最優(yōu)解，而且兩者相等；原問(wèn)題的最優(yōu)解和對(duì)偶問(wèn)題的最優(yōu)解構(gòu)成互補(bǔ)松弛關(guān)系；原問(wèn)題最優(yōu)表中松弛變量的檢驗(yàn)數(shù)的反號(hào)就是對(duì)偶問(wèn)題的最優(yōu)解；對(duì)偶問(wèn)題最優(yōu)表中松弛變量的檢驗(yàn)數(shù)的反號(hào)就是原問(wèn)題的最優(yōu)解。第六頁(yè)，共二十八頁(yè)，2022年，8月28日1、對(duì)偶的對(duì)偶就是原始問(wèn)題maxz’=-CTXs.t.-AX≤-b X≥0Minw’=-bTys.t.-ATy≥-C

y

≥0maxw=bTys.t.ATy≤C

y

≥0minz=CTXs.t.AX≥b X≥0對(duì)偶的定義對(duì)偶的定義二、對(duì)偶問(wèn)題的性質(zhì)第七頁(yè)，共二十八頁(yè)，2022年，8月28日2、可行解的目標(biāo)函數(shù)值之間的關(guān)系

設(shè)XF、y

F分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行解

z=CTXF≥yTAXF≥yTb=w3、最優(yōu)解的目標(biāo)函數(shù)值之間的關(guān)系

設(shè)Xo、yo分別是原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解

z=CTXo=yoTAXo=yoTb=w第八頁(yè)，共二十八頁(yè)，2022年，8月28日4、原始問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解之間的互補(bǔ)松弛關(guān)系minz=CTXs.t.AX-u=bX,u≥0maxw=bTys.t.ATy+v=Cy,v≥0minz=CTXs.t.AX≥bX≥0maxw=bTys.t.ATy≤Cy≥0對(duì)偶引進(jìn)松弛變量引進(jìn)松弛變量XTv=0yTu=0互補(bǔ)松弛關(guān)系X，uy，v第九頁(yè)，共二十八頁(yè)，2022年，8月28日minz=CTXs.t. AX-u=b X,u≥0maxw=bTys.t.ATy+v=C y,v≥0XTv=0yTu=0mn=yvATICn=Au-IbnmmX原始問(wèn)題和對(duì)偶問(wèn)題變量、松弛變量的維數(shù)第十頁(yè)，共二十八頁(yè)，2022年，8月28日y1yiymvm+1vm+jvn+m

x1xjxnun+1un+iun+m

對(duì)偶問(wèn)題的變量對(duì)偶問(wèn)題的松弛變量

原始問(wèn)題的變量原始問(wèn)題的松弛變量xjvm+j=0 yiun+i=0 (i=1,2,…,m;j=1,2,…,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0第十一頁(yè)，共二十八頁(yè)，2022年，8月28日1、單純形表最優(yōu)基必須同時(shí)滿足兩個(gè)條件右端列中的所有Ъi≥0可行性條件全部檢驗(yàn)數(shù)σj≤0最優(yōu)性條件（1）（2）三、對(duì)偶單純形法第十二頁(yè)，共二十八頁(yè)，2022年，8月28日單純形法的迭代過(guò)程Ъi≤

0σj≤0

Ъi≥0

σj≥0

Ъi≥0σj≤0對(duì)偶單純形法的迭代過(guò)程Ъi≥0σj≤0第十三頁(yè)，共二十八頁(yè)，2022年，8月28日2、對(duì)偶單純形法例題1minω=15y1+5y2+11y3s.t.3y1+2y2+2y3≥55y1+y2+2y3≥4y1，y2，y3≥0解:將每個(gè)不等式兩邊乘以-1,再引入松馳變量S1和S2,則上述問(wèn)題化為:直接寫(xiě)成標(biāo)準(zhǔn)式時(shí)有-S1和-S2,則無(wú)法有初始基,因此乘個(gè)-1minω=15y1+5y2+11y3s.t.-3y1-2y2-2y3+S1=-5-5y1-y2-2y3+S2=-4y1，y2，y3,S1,S2,≥0第十四頁(yè)，共二十八頁(yè)，2022年，8月28日對(duì)偶單純形法2

建立該問(wèn)題的初始單純形表

y1y2y3s1s2右端ω-15-5-11

0

0

0s1-3-2-210

-5s2-5-1-2

01-4

由表知β1的兩個(gè)基變量均取負(fù)值,故它不是可行基,從而不能從β1出發(fā)應(yīng)用單純形法。但由于表(I)中所有σj≤0,我們目的是要保證全部檢驗(yàn)數(shù)始終為非正的前提下,逐步使全部基變量取的值≥0,為此要按以下方法換基.

(I)第十五頁(yè)，共二十八頁(yè)，2022年，8月28日

對(duì)偶單純形法3出基變量確定：可選任何一個(gè)取負(fù)值的基變量（通常選取值最小的一個(gè)）為出基變量入基變量的確定：考慮出基變量行中那些取負(fù)值的σij,對(duì)每個(gè)這樣的σij,作比式σj/aij令：?=min{?j/aij︱aij﹤0}=?s/ais則取xs為入基變量。

(I)

y1y2y3s1s2右端ω-15-5-11

0

0

0s1-3-2-210

-5s2-5-1-2

01-4第十六頁(yè)，共二十八頁(yè)，2022年，8月28日然后進(jìn)行單純形迭代,得表（II）(III)ω-15/20-6-5/2

025/2y23/211-1/2

05/2s2-7/2

0-1-1/21-3/2(II)ω0

0-27/7-10/7-15/7110/7y2014/7-5/73/713/7y1102/71/7-2/73/7得最優(yōu)解：y1=3/7,y2=13/7,y3=s1=s2=0第十七頁(yè)，共二十八頁(yè)，2022年，8月28日對(duì)偶單純形法對(duì)偶單純形法用來(lái)求解最優(yōu)性條件滿足，可行性條件不滿足的問(wèn)題。對(duì)偶單純形法的步驟Step0：從一個(gè)最優(yōu)性條件滿足，可行性條件不滿足的解出發(fā)，確定基變量、非基變量，列出單純形表，轉(zhuǎn)Step1。Step1：如果右邊常數(shù)全為非負(fù)，得到最優(yōu)解，算法終止。否則，選擇右邊常數(shù)為負(fù)數(shù)，絕對(duì)值最大的基變量離基，轉(zhuǎn)Step2。Step2：在離基變量行中，選擇系數(shù)為負(fù)數(shù)并且和目標(biāo)函數(shù)行的比值最小的元素作為主元，確定進(jìn)基變量。Step3：對(duì)單純形表進(jìn)行行變換，使主元為1，主元所在列的其他元素為0，轉(zhuǎn)Step1。第十八頁(yè)，共二十八頁(yè)，2022年，8月28日1、原始問(wèn)題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題單位產(chǎn)品的利潤(rùn)（元/件）產(chǎn)品產(chǎn)量（件）總利潤(rùn)（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）四、對(duì)偶的經(jīng)濟(jì)解釋第十九頁(yè)，共二十八頁(yè)，2022年，8月28日2、對(duì)偶問(wèn)題資源限量（噸）資源價(jià)格（元/噸）總租金（元）對(duì)偶問(wèn)題是資源定價(jià)問(wèn)題，對(duì)偶問(wèn)題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價(jià)格（ShadowPrice）原始和對(duì)偶問(wèn)題都取得最優(yōu)解時(shí)，最大利潤(rùn)maxz=minw第二十頁(yè)，共二十八頁(yè)，2022年，8月28日3、資源影子價(jià)格的性質(zhì)影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0第二十一頁(yè)，共二十八頁(yè)，2022年，8月28日4、互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋wixn+i=0如果wi>0，則xn+i=0如果xn+i>0，則wi=0邊際利潤(rùn)大于0的資源，在最優(yōu)生產(chǎn)計(jì)劃條件下沒(méi)有剩余wm+jxj=0如果wm+j>0，則xj=0如果xj>0，則wm+j=0最優(yōu)生產(chǎn)計(jì)劃條件下有剩余的資源，其邊際利潤(rùn)等于0差額成本大于0（機(jī)會(huì)成本大于利潤(rùn)）的產(chǎn)品，不安排生產(chǎn)安排生產(chǎn)的產(chǎn)品，差額成本等于0（機(jī)會(huì)成本等于利潤(rùn)）第二十二頁(yè)，共二十八頁(yè)，2022年，8月28日maxz=4x1+3x2+5x3s.t.2x1+x2+3x3≤200x1+2x2+2x3≤3503x1+4x2+x3≤2202x1+3x2+2x3≤400x1，x2，x3≥0產(chǎn)品1產(chǎn)品2產(chǎn)品3資源限量資源12.01.03.0200資源21.02.02.0350資源33.04.01.0220資源42.03.02.0400利潤(rùn)4.03.05.0第二十三頁(yè)，共二十八頁(yè)，2022年，8月28日引進(jìn)松弛變量x4,x5,x6，x7≥0,得到：maxz=4x1+3x2+5x3s.t.2x1+x2+3x3+x4=200x1+2x2+2x3+x5=3503x1+4x2+x3+x6=2202x1+3x2+2x3+x7=400xi≥0第二十四頁(yè)，共二十八頁(yè)，2022年，8月28日得到最優(yōu)解：X1=0,x2=460/11=41.82,x3=580/11(件），最大利潤(rùn)z=389.09(萬(wàn)元），可以得到資源的剩余量：X4=200-(2x1+x2+3x3)=0(t)X5=350-(x1+2x2+2x3)=1770/11=160.9(t)X6=220-(3x1+4x2+x3)=0X7=400-(2x1+3x2+2x3)=1860/11=169.9第二十五頁(yè)，共二十八頁(yè)，2022年，8月28日這個(gè)問(wèn)題的對(duì)偶問(wèn)題是：Miny=200w1+350w2+220w3+400w4S.t2w1+w2+3w3+2w4-w5=4w1+2w2+4