第三章對(duì)偶原理3.1LP的對(duì)偶關(guān)系DUAL3.1.1問(wèn)題的提出例1:某工廠擁有A、B、C三個(gè)車(chē)間，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用生產(chǎn)能力時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三個(gè)車(chē)間可利用的時(shí)數(shù)如下表所示：

產(chǎn)品甲x1產(chǎn)品乙x2

生產(chǎn)能力（工時(shí)/天）A108B0212C3436利潤(rùn)（百元/件）35

目標(biāo)函數(shù)Maxz=3x1+5x2

約束條件x1

8s.t.

2x2

123x1+2x2

36

x1，x2

0

設(shè)有，y1,y2,y3

分別為出售A，B，C工時(shí)所得利潤(rùn)（百元/工時(shí)），w為總盈利額（百元）對(duì)偶的定義線性規(guī)劃問(wèn)題在形式上，可以形成一對(duì)對(duì)稱問(wèn)題，對(duì)任何線性規(guī)劃求最大值問(wèn)題，都有一個(gè)與之對(duì)稱的求最小值問(wèn)題，這兩個(gè)有關(guān)的約束條件的系數(shù)矩陣，具有相同的數(shù)據(jù)，僅形式互為轉(zhuǎn)置，并且目標(biāo)函數(shù)與約束右端項(xiàng)互換，其目標(biāo)函數(shù)的最優(yōu)值也是彼此相等的，我們把線性規(guī)劃的這個(gè)對(duì)稱問(wèn)題稱為對(duì)偶問(wèn)題。原始問(wèn)題maxz=CTXs.t. AX≤b X≥0對(duì)偶問(wèn)題

minw=bTYs.t.ATY≥C Y≥0

≤maxbACTCATbT≥minmnmn原始問(wèn)題Primalproblem對(duì)偶問(wèn)題DualproblemP1D13.1.2

對(duì)偶關(guān)系關(guān)系1規(guī)范對(duì)偶關(guān)系對(duì)稱對(duì)偶關(guān)系2標(biāo)準(zhǔn)性LP問(wèn)題的對(duì)偶關(guān)系非對(duì)稱對(duì)偶自由Y關(guān)系3一般對(duì)偶關(guān)系原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù)MaxZ目標(biāo)函數(shù)MinW約束條件數(shù)：m個(gè)第i個(gè)約束條件類型為“≤”第i個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“=”對(duì)偶變量數(shù)：m個(gè)第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量是自由變量決策變量數(shù)：n個(gè)第j個(gè)變量≥0第j個(gè)變量≤0第j個(gè)變量是自由變量約束條件數(shù)：n第i個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“≤”第i個(gè)約束條件類型為“=”關(guān)系3一般對(duì)偶關(guān)系minz=CTXs.t. AX≤b X≥0maxw=bTYs.t.ATY≤CY≤0幾種形式的對(duì)偶關(guān)系maxz=CTXs.t. AX≤b X≥0

minw=bTYs.t.ATY≥CY≥0

maxz=CTXs.t. AX=b X≥0

minw=bTYs.t.ATY≥CY：自由求對(duì)偶問(wèn)題例題maxω=7y1+4y2-2y3minZ=3x1+2x2-6x3+x52y1+y2-y3

≤32x1+x2-4x3+x4+3x5

≥7y1+3y3≤2x1+2x3-x4≤

4-4y1+2y2

≤-6-x1+3x2-x4+x5=-2y1-y2-y3

≥

0x1，x2，x3

≥0;3y1+y3=1x4≤

0;x5無(wú)限制y1

≥0y2≤0y3

無(wú)約束

3.2對(duì)偶問(wèn)題的基本性質(zhì)1對(duì)稱性：對(duì)偶問(wèn)題的對(duì)偶問(wèn)題是原問(wèn)題對(duì)偶的對(duì)偶就是原始問(wèn)題

minz’=-CTXs.t.-AX

≥

-b X≥0

maxw`=-bTYs.t.-ATY≤-C Y≥0

minw=bTYs.t.ATY≥C Y≥0maxz=CTXs.t.AX≤b X≥0對(duì)偶的定義對(duì)偶的定義2弱對(duì)偶性：極大化原問(wèn)題的任一可行解的目標(biāo)函數(shù)值，不大于其對(duì)偶問(wèn)題任意可行解的目標(biāo)函數(shù)值3最優(yōu)性：X°、Y°分別為原問(wèn)題與對(duì)偶問(wèn)題的可行解，且CX°=Y°b，則兩者均為最優(yōu)解。P774對(duì)偶定理：LP問(wèn)題的P和D問(wèn)題1）若一個(gè)問(wèn)題有最優(yōu)解，則另一問(wèn)題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。2）原問(wèn)題無(wú)界，對(duì)偶問(wèn)題無(wú)可行解。5兼容性原始問(wèn)題的檢驗(yàn)矢給出對(duì)偶問(wèn)題的一個(gè)基本解6、原始問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解之間的互補(bǔ)松弛關(guān)系minz=CTXs.t.AX≥bX≥0maxy=bTYs.t.ATY≤CY≥0minz=CTXs.t.AX-XS=bX,XS≥0maxy=bTYs.t.ATY+YS=CY,YS≥0XTYS=0YTXS=0對(duì)偶引進(jìn)松弛變量Y，YsX，Xs引進(jìn)松弛變量互補(bǔ)松弛關(guān)系y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

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

原始問(wèn)題的變量原始問(wèn)題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0[例4]求解下列LP問(wèn)題，并給出對(duì)偶問(wèn)題的最優(yōu)解MaxZ=x1+2x22x1+2x2≤80x1+2x2≤4x1,x2≥0對(duì)偶問(wèn)題為:Minw=8y1+4y22y1+0y2≥12y1+2y2≥2y1,y2≥0最優(yōu)解為:x1=2,x2=2,x3=0,x4=0

y1=1/2,y2=1/2,

y3=0,y4=0Cj 1 2 0 0 Cb xB b x1 x2 x3 x4

0 x3

0 x4

00 2 0 12 2 1 084y3y4y1y24/2=2/8/2=44/2=2Min20101/2

-100102x3x22101/2-1/220101/2

001/21/2-1-2004201-1x1x2y3y4y1y212y3y4y1y2

4

63.3對(duì)偶的經(jīng)濟(jì)解釋原始問(wèn)題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題單位產(chǎn)品的利潤(rùn)（元/件）產(chǎn)品產(chǎn)量（件）總利潤(rùn)（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）W=yb=(y1…ym)b1bm…=b1y1+b2y2+…+bmymbi：

第i種資源的數(shù)量yi：對(duì)偶解bi增加bi,其它資源數(shù)量不變時(shí),目標(biāo)函數(shù)的增量Z=biyi3.3對(duì)偶的經(jīng)濟(jì)解釋

Z

bi=yi對(duì)偶解y：b的單位改變量所引起的目標(biāo)函數(shù)改變量。也為第I種資源的邊際價(jià)值(影子價(jià)格)Zz`=421/2影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0用影子價(jià)格與市場(chǎng)價(jià)格相比較，幫助決策是否買(mǎi)入該資源對(duì)偶變量的經(jīng)濟(jì)解釋(影子價(jià)格(ShadowPrice)目標(biāo)函數(shù)Maxz=3x1+5x2

約束條件

x1

+

8s.t.

2x2

123x1+2x2

36

x1，x2

0

目標(biāo)函數(shù)

Maxz=3x1+5x2

約束條件

x1

+x3=8s.t.

2x2