中南大學線性規(guī)劃課件4

2-1線性規(guī)劃的對偶理論例2.1生產(chǎn)計劃問題（資源利用問題）

勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價50元/個，椅子銷售價格30/個，生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種。生產(chǎn)一個桌子需要木工4小時，油漆工2小時。生產(chǎn)一個椅子需要木工3小時，油漆工1小時。該廠每個月可用木工工時為120小時，油漆工工時為50小時。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？數(shù)學模型

maxg=50x1+30x2s.t.4x1+3x2120(2.1)2x1+x250x1,x20

如果我們換一個角度，考慮另外一種經(jīng)營問題。假如有一個企業(yè)家有一批等待加工的訂單，有意利用該家具廠的木工和油漆工資源來加工他的產(chǎn)品。因此，他要同家具廠談判付給該廠每個工時的價格?？梢詷嬙煲粋€數(shù)學模型來研究如何既使家具廠覺得有利可圖肯把資源出租給他，又使自己付的租金最少？

假設y1,y2分別表示每個木工和油漆工工時的租金，則所付租金最小的目標函數(shù)可表示為：

mins=120y1+50y2目標函數(shù)中的系數(shù)120，50分別表示可供出租的木工和油漆工工時數(shù)。

該企業(yè)家所付的租金不能太低，否則家具廠的管理者覺得無利可圖而不肯出租給他。因此他付的租金應不低于家具廠利用這些資源所能得到的利益：

4y1+2y2503y1+y230y1,y20

得到另外一個數(shù)學模型：

mins=120y1+50y2s.t.4y1+2y250(2.2)3y1+y230y1,y20模型(2.1)和模型(2.2)

既有區(qū)別又有聯(lián)系。聯(lián)系在于它們都是關于家具廠的模型并且使用相同的數(shù)據(jù)，區(qū)別在于模型反映的實質(zhì)內(nèi)容是不同的。模型(2.1)是站在家具廠經(jīng)營者立場追求銷售收入最大，模型(2.2)是則站在家具廠對手的立場追求所付的租金最少。如果模型(2.1)稱為原問題，則模型(2.2)稱為對偶問題。任何線性規(guī)劃問題都有對偶問題，而且都有相應的意義。例2.2營養(yǎng)配餐問題

假定一個成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場價格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費用最小？各種食物的營養(yǎng)成分表序號食品名稱熱量(千卡)蛋白質(zhì)(克)鈣(毫克)價格(元)1豬肉100050400142雞蛋8006020063大米9002030034白菜200105002解：設xj為第j種食品每天的購入量，則配餐問題的線性規(guī)劃模型為：

minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，

x3，x40

(2.3)該問題的對偶問題：maxg=3000y1+55y2+800y3s.t.1000y1+50y2+400y314(2.4)800y1+60y2+200y36900y1+20y2+300y33200y1+10y2+500y32y1，y2，y30該問題的對偶問題(2.4)經(jīng)濟意義可解釋為：市場上有一廠商生產(chǎn)三種可代替食品中的熱量、蛋白質(zhì)和鈣的營養(yǎng)素，該廠商希望它的產(chǎn)品既有市場競爭力，又能帶來最大利潤，因此需要構造一個模型來研究定價問題。以上模型的變量為各營養(yǎng)素單位營養(yǎng)量的價格，目標函數(shù)反映廠商利潤最大的目標，約束條件反映市場的競爭條件，即：用于購買與某種食品營養(yǎng)價值相同的營養(yǎng)素的價格應小于該食品的市場價格。線性規(guī)劃的對偶關系：（I）MaxS=CtXs.t.AXbX0(II)Ming=Ybs.t.YACY0（2.3)(2.4)稱作互為對偶問題。其中一個稱為原問題，另一個稱為它的對偶問題。(2.3)(2.4)

a11a12….a1nb1A=a21a22….a2nb

=

b2

。。。。。。。。。。。。。。。

am1am2….amnbm

c1x10y1c2x20y2Ct=X=0=Yt=……………..…..cnxn0ym原始問題maxs=CtXs.t. AX≤b X≥0對偶問題ming=Ybs.t.YA≥C Y≥0≤maxbACtCAtbt≥minmnmn例2-3：寫出下列線性規(guī)劃問題的對偶問題minS=12x1+8x2+16x3+12x4s.t.2x1+x2+4x3

22x1+2x2+4x43x1，x2，

x3，x40minS=12x1+8x2+16x3+12x4

s.t.2x1+x2+4x3

2

y1

2x1+2x2+4x43

y2

x1，x2，

x3，x40min

S=12x1+8x2+16x3+12x4s.t.2x1+x2+4x3

2

y1

2x1+2x2+4x4

3

y2

x1,x2,

x3,

x40解：該問題的對偶問題：

maxg=2y1+3y2

s.t.

2y1+2y212y1+2y284y1164y212

y1,y20例2-4：寫出下列線性規(guī)劃問題的對偶問題maxS=10x1+x2+2x3s.t.X1+x2+2x3

10y14x1+2x2-x320

y2

x1，x2，

x30解：該問題的對偶問題：

ming=10y1+20y2s.t.y1+4y210y1+2y212y1-y22y1，y2

0maxS=10x1+x2+2x3s.t.X1+x2+2x3

10y14x1+2x2-x320y2

x1,x2,

x30例2-5：寫出下列線性規(guī)劃問題的對偶問題

minS=x1+2x2+3x3s.t.2x1+3x2+5x3

2

3x1+x2+7x33x1，x2，

x30解：用（-1）乘以第二個約束方程兩邊

minS=x1+2x2+3x3s.t.2x1+3x2+5x3

2

y1

-3x1-x2-7x3-3y2x1，x2，

x30該問題的對偶問題：

maxg=2y1-3y2s.t.2y1-3y213y1-y225y1-

7y23y1，y20例2-6：寫出下列線性規(guī)劃問題的對偶問題

minS=2x1+3x2-5x3s.t.x1+x2-x3

5

2x1

+x3=4

x1，x2，

x30解：將原問題的約束方程寫成不等式約束形式：

minS=2x1+3x2-5x3

x1+x2-x3

5

y1

2x1

+x34

y2’

-2x1

-x3-4y2”

x1,x2,

x30引入變量y1,y2’，y2”

寫出對偶問題

maxg=5y1+4y2’-4y2”

s.t.y1+2y2’-2y2”

2y1

3-y1+y2’-y2”

-5y1，y2’，y2”

0令y2=y2’-y2”

得到

maxg=5y1+4y2s.t.y1+2y22y1

3-y1+y2-5y10，y2無非負約束此類問題稱為非對稱型對偶問題。前面的問題稱為對稱型對偶問題。原問題:2x1+x3=4根據(jù)對偶規(guī)劃的對稱性,若原規(guī)劃某個變量無非負限制,則與之對應的對偶約束為等式約束.若原規(guī)劃中有等式約束,則與之對應的對偶變量無非負限制.例2-7：寫出下列線性規(guī)劃問題的對偶問題

minS=3x1-2x2+x3s.t.x1+2x2=1

2x2

-x3-2

2x1+x33x1-2x2+3x34x1，x20

，

x3無非負限制不等式兩邊乘(-1)

ming=3x1-2x2+x3s.t.

x1+2x2=1

y1

-2x2+x32y22x1+x33y3x1-2x2+3x34y4x1，x20

，

x3無非負限制解:

綜合運用對偶原則得到

maxZ=y1+2y2+3y3+4y4s.t.y1+2y3+y43x12y1-2y2-2y4-2x2

y2+y3+3y4=1

x3y2,y3,y40，y1無非負約束x3

無非負限制x1+2x2=1對偶問題的基本定理定理2.0:(對稱性定理)

對偶問題的對偶就是原問題.minz’=-CTXs.t.-AX≥-b

X≥0maxg’=-Ybs.t.-YA≤-C Y≥0ming=Ybs.t.YA≥C Y≥0maxz=CTXs.t.AX≤

b

X≥0對偶的定義對偶的定義定理2.1:(弱對偶定理)

對于互為對偶問題(I)(II)中的任意的可行解X(0),Y(0),都有

CTX(0)≤Y(0)b

用非線性函數(shù)馬鞍面說明定理的含義（鞍點）。但是線性規(guī)劃是線性函數(shù)。馬鞍面z=x2/4-y2/6鞍點YZXZYX在Y=0的平面上鞍點是z=f(0,y)的極大值點XYZ在X=0的平面上鞍點是z=f(0,y)的極小值點馬鞍面z=x2/4-y2/6鞍點YZX對偶問題的基本定理推理一:對偶問題中,任意一個可行解,都產(chǎn)生了另一個問題的目標函數(shù)的界。推理二:若原問題和對偶問題都有可行解,則它們都有最優(yōu)解。推理三:若互為對偶問題中任意一個有可行解,但無最優(yōu)解,則另一個就無可行解。對偶問題的基本定理定理2.2(最優(yōu)準則)

若原問題的某一個可行解與對偶問題的某一可行解的目標函數(shù)值相等,則它們分別是原問題與對偶問題的最優(yōu)解.對偶問題的基本定理定理2.3(對偶定理)

若原問題有最優(yōu)解,則對偶問題也有最優(yōu)解,且最優(yōu)值相等.對偶問題的基本定理定理2.3(對偶定理)

若原問題有最優(yōu)解,則對偶問題也有最優(yōu)解,且最優(yōu)值相等。推理:對偶問題的最優(yōu)解為原問題最優(yōu)表中,相應的松駛變量檢驗數(shù)的相反數(shù)。定理2.3(互補松弛性)maxz=CTXs.t.AX+XS=bX,XS≥0ming=Ybs.t.YA-YS=CY,YS≥0maxz

=

CTXs.t.AX≤bX≥0ming=Ybs.t.YA≥CY≥0對偶引進松弛變量引進松弛變量XTYS=0YTXS=0互補松弛關系X，XsY，Ysmaxz=CTXs.t. AX+XS=b X,XS≥0ming=Ybs.t.YA-YS=C Y,YS

≥0XTYS=0YTXS=0mn=YYSATICn=AXS-IbnmmX原始問題和對偶問題變量、松弛變量的維數(shù)

y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

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

原始問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0(i=1,2,…,m;j=1,2,…,n)在一對變量中，其中一個大于0，另一個一定等于0原問題與對偶問題解的對應關系2-2對偶解的經(jīng)濟解釋

如果把線性規(guī)劃的約束看成廣義資源約束，右邊項則代表某種資源的可用量。對偶解的經(jīng)濟含義是資源的單位改變量引起目標函數(shù)值的改變量。通常稱為影子價格。影子價格表明對偶解是對系統(tǒng)內(nèi)部資源的客觀估計，又表明它是一種虛擬的價格而不是真實價格。原始問題是利潤最大化的生產(chǎn)計劃問題單位產(chǎn)品的利潤（元/件）產(chǎn)品產(chǎn)量（件）總利潤（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）資源限量（噸）資源價格（元/噸）總利潤（元）對偶問題是資源定價問題，對偶問題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價格(ShadowPrice)原始和對偶問題都取得最優(yōu)解時，最大利潤maxz=ming0yyyyyycyyayayacyyayayacyyayaya.t.sybybybgminnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm22113=-++=-++=-++++=++++++LLLLLLLLLLLLay1y2ym產(chǎn)品的機會成本機會成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤增加單位資源可以增加的利潤減少一件產(chǎn)品可以節(jié)省的資源0xxxxbxaxaxaxabxaxaxaxabxaxxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj22113￡+++￡+++￡++++++=LLLLLLLLLLLLLLLLL機會成本利潤差額成本產(chǎn)品的差額成本（ReducedCost）差額成本=機會成本-利潤影子價格的特征：影子價格是對系統(tǒng)資源的最優(yōu)估計，只有系統(tǒng)達到最優(yōu)狀態(tài)時才可能賦于資源這種價值。因此，也稱為最優(yōu)價格。影子價格的特征：影子價格是對系統(tǒng)資源的最優(yōu)估計，只有系統(tǒng)達到最優(yōu)狀態(tài)時才可能賦與資源這種價值。因此，也稱為最優(yōu)價格。影子價格的取值與系統(tǒng)的價值取向有關，并受系統(tǒng)狀態(tài)變化的影響。系統(tǒng)內(nèi)部資源數(shù)量和價格的變化，它是一種動態(tài)的價格體系。影子價格的特征：對偶解——影子價格的大小客觀反映了資源在系統(tǒng)內(nèi)的稀缺程度。如果某資源在系統(tǒng)內(nèi)供大于求，盡管它有市場價格，但它的影子價格等于零。增加這種資源的供應不會引起系統(tǒng)目標的任何變化。如果某資源是稀缺資源，其影子價格必然大于零。影子價格越高，這種資源在系統(tǒng)中越稀缺。影子價格的特征：影子價格是一種邊際價值，它與經(jīng)濟學中邊際成本的概念相同。因而在經(jīng)濟管理中有十分重要的價值。企業(yè)管理者可以根據(jù)資源在企業(yè)內(nèi)部影子價格的大小決定企業(yè)的經(jīng)營策略。例2-13：某企業(yè)生產(chǎn)A，B二種產(chǎn)品。A產(chǎn)品需要消耗2個單位原料和1個小時人工；B產(chǎn)品需要消耗3個單位原料和2個小時人工；A產(chǎn)品銷售價格23元，B產(chǎn)品銷售價格40元。該企業(yè)每天可利用生產(chǎn)原料25單位和15個人工。每單位原料的采購成本為5元，每小時人工工資為10元。問該企業(yè)如何組織生產(chǎn)才能使銷售利潤最大？解：（模型一）目標函數(shù)系數(shù)直接使用計算好的銷售利潤，成本數(shù)據(jù)不直接反映在模型中。

maxg=3x1+5x2s.t.2x1+3x225x1+2x215x1,x20最優(yōu)解X=（5,5）最優(yōu)值Z=40對偶解Y=（1,1）解：（模型二）目標函數(shù)系數(shù)使用未經(jīng)過處理的數(shù)據(jù)，成本數(shù)據(jù)直接反映在模型中。

maxg=23x1+40x2-5

x3-10x4s.t.2x1+3x2-x3=0x1+2x2-x4=0x325x415x1,x2,

x3,

x40（模型二）最優(yōu)解X=(5,5,0,0)最優(yōu)值Z=40對偶解Y=(6,11,1,1)一般來講，如果模型顯性地處理所有資源的成本計算（模型二）則對偶解與影子價格相等，我們按以下原則考慮企業(yè)的經(jīng)營策略：如果某資源的影子價格高于市場價格，表明該資源在系統(tǒng)內(nèi)有獲利能力，應買入該資源。一般來講，如果模型顯性地處理所有資源的成本計算（模型二）則對偶解與影子價格相等，我們按以下原則考慮企業(yè)的經(jīng)營策略：如果某資源的影子價格高于市場價格，表明該資源在系統(tǒng)內(nèi)有獲利能力，應買入該資源。如果某資源的影子價格低于市場價格，表明該資源在系統(tǒng)內(nèi)無獲利能力，應賣出該資源。一般來講，如果模型顯性地處理所有資源的成本計算（模型二）則對偶解與影子價格相等，我們按以下原則考慮企業(yè)的經(jīng)營策略：如果某資源的影子價格高于市場價格，表明該資源在系統(tǒng)內(nèi)有獲利能力，應買入該資源。如果某資源的影子價格低于市場價格，表明該資源在系統(tǒng)內(nèi)無獲利能力，應賣出該資源。如果某資源的影子價格等于市場價格，表明該資源在系統(tǒng)內(nèi)處于平衡狀態(tài)，既不用買入，也不必賣出該資源。一般來講，如果模型隱性地處理所有資源的成本計算（模型一）則影子價格應等于對偶解與資源的成本之和，我們按以下原則考慮企業(yè)的經(jīng)營策略：如果某資源的對偶解大于零，表明該資源在系統(tǒng)內(nèi)有獲利能力，應買入該資源。一般來講，如果模型隱性地處理所有資源的成本計算（模型一）則影子價格應等于對偶解與資源的成本之和，我們按以下原則考慮企業(yè)的經(jīng)營策略：如果某資源的對偶解大于零，表明該資源在系統(tǒng)內(nèi)有獲利能力，應買入該資源。如果某資源的對偶解小于零，表明該資源在系統(tǒng)內(nèi)無獲利能力，應賣出該資源。一般來講，如果模型隱性地處理所有資源的成本計算（模型一）則影子價格應等于對偶解與資源的成本之和，我們按以下原則考慮企業(yè)的經(jīng)營策略：如果某資源的對偶解大于零，表明該資源在系統(tǒng)內(nèi)有獲利能力，應買入該資源。如果某資源的對偶解小于零，表明該資源在系統(tǒng)內(nèi)無獲利能力，應賣出該資源。如果某資源的對偶解等于零，表明該資源在系統(tǒng)內(nèi)處于平衡狀態(tài)，既不用買入，也不必賣出。2-3對偶單純形法原始單純形法其基本思路：在換基迭代過程中，始終保持基變量值非負，逐步使檢驗數(shù)變成非正，最后求得最優(yōu)解或判斷無最優(yōu)解。對偶單純形法其基本思路：在換基迭代過程中，始終保持檢驗數(shù)非正，逐步使基變量值變成非負，最后求得最優(yōu)解或判斷無最優(yōu)解。例2-9：用對偶單純形法解下列線性規(guī)劃問題

minS=x1+4x2+3x4s.t.x1+2x2-x3+x43-2x1-x2+4x3+x4

2x1，x2，

x3，x40解：此題可用人工變量方法求，但也可用對偶單純形法。

maxS’=-x1-4x2-3x4s.t.-x1-2x2+x3-x4+x5=-32x1+x2-4x3-x4+x6=

-2x1，x2，

x3，x4，x5

，x6

0計算檢驗數(shù)全為非正，稱為對偶可行；而常數(shù)項全是負數(shù)，稱為原始不可行。常數(shù)項是負數(shù)且最小，確定出基變量x5。用出基變量x5行的所有負數(shù)分別去除對應的檢驗數(shù)，最小值對應的為進基變量x1，交叉元素為主元（-1）主元運算：第一行乘（-1）主元運算：第二行加上第一行（-2）計算檢驗數(shù)確定出基變量X6確定進基變量X3，主元（-2）主元運算：第二行乘（-1/2）主元運算：第一行加第二行計算檢驗數(shù)：全為非正。但此時常數(shù)b已全大于零,最優(yōu)解=（7,0,4,0