運(yùn)籌學(xué)對偶原理

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

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

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

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

約束條件x1

8s.t.

2x2

123x1+2x2

36

x1，x2

0

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

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

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

≤maxbACTCATbT≥minmnmn原始問題Primalproblem對偶問題DualproblemP1D13.1.2

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

≥0y2≤0y3

無約束

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

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對偶的定義對偶的定義2弱對偶性：極大化原問題的任一可行解的目標(biāo)函數(shù)值，不大于其對偶問題任意可行解的目標(biāo)函數(shù)值3最優(yōu)性：X°、Y°分別為原問題與對偶問題的可行解，且CX°=Y°b，則兩者均為最優(yōu)解。P774對偶定理：LP問題的P和D問題1）若一個問題有最優(yōu)解，則另一問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。2）原問題無界，對偶問題無可行解。5兼容性原始問題的檢驗矢給出對偶問題的一個基本解6、原始問題和對偶問題最優(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對偶引進(jìn)松弛變量Y，YsX，Xs引進(jìn)松弛變量互補(bǔ)松弛關(guān)系y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

對偶問題的變量對偶問題的松弛變量

原始問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對變量中，其中一個大于0，另一個一定等于0[例4]求解下列LP問題，并給出對偶問題的最優(yōu)解MaxZ=x1+2x22x1+2x2≤80x1+2x2≤4x1,x2≥0對偶問題為: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對偶的經(jīng)濟(jì)解釋原始問題是利潤最大化的生產(chǎn)計劃問題單位產(chǎn)品的利潤（元/件）產(chǎn)品產(chǎn)量（件）總利潤（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）W=yb=(y1…ym)b1bm…=b1y1+b2y2+…+bmymbi：

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

Z

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