第2章789對偶理論

1本節(jié)研究、解決三個問題：1、如何寫出對偶問題；2、原問題與對偶問題之間的關(guān)系；3、對偶單純形法（解線性規(guī)劃問題的第4種方法）22.5.1對偶問題的提出例1——生產(chǎn)計劃問題某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：產(chǎn)品A產(chǎn)品B資源限量勞動力設(shè)備原材料9434510360200300利潤（元/kg）701203例1——模型問題：如何安排生產(chǎn)計劃，使得獲利最多？步驟：1、確定決策變量：設(shè)生產(chǎn)A產(chǎn)品x1kg，B產(chǎn)品x2kg2、確定目標(biāo)函數(shù)：maxZ=70X1+120X23、確定約束條件：人力約束9X1+4X2≤360

設(shè)備約束4X1+5X2

≤200

原材料約束3X1+10X2

≤300

非負(fù)性約束X1≥0X2≥04例1——另一角度分析：成本角度

利潤大的另一方面是什么：成本越??！因此，我們可以試著從成本角度來分析生產(chǎn)決策者的心態(tài)！現(xiàn)在資源的數(shù)量已經(jīng)定了，那么我們可以從價格來著手！產(chǎn)品A產(chǎn)品B資源限制勞動力設(shè)備原材料9434510360200300單位利潤701205目標(biāo)分析設(shè)勞動力每個工時收費Y1元，設(shè)備臺時費用Y2元，原材料附加費Y3元?，F(xiàn)在我們的目標(biāo)變成下面這個式子：

minw=360y1+200y2+300y3那么約束條件是什么呢？6約束條件分析單個因素的收入最大：即投入于產(chǎn)品A的資源收入要大于A的銷售收入，投入于產(chǎn)品B的資源收入要大于B的銷售收入，即

9y1+4y2+3y3≥704y1+5y2+10y3

≥120從整個問題來看，1、總的投入最低，2、投入品的價值也要得到合理體現(xiàn)！綜合起來得到問題模型！7問題模型Minw=360y1+200y2+300y3s.t.9y1+4y2+3y3≥70

4y1+5y2+10y3

≥120y1，y2，y30這個線性規(guī)劃問題稱為例1的（稱為原問題）對偶問題。8一般形式的線性規(guī)劃問題，寫出其對偶問題的規(guī)則是什么？課堂講解第44頁；要求：看到原問題，能立即寫出其對偶形式；9原問題與對偶問題比較原問題：對偶問題：maxZ=70X1+120X2

minω=360y1+200y2+300y3

9X1+4X2≤3609y1+4y2+3y3

≥70(1)4X1+5X2

≤2004y1+5y2+10y3

≥120(2)3X1+10X2

≤300X1≥0X2≥0y1≥0,

y2≥0,

y3≥0102.5.2對偶問題表示根據(jù)上述例題可見，對于形如如下形式的線性規(guī)劃問題：我們可以馬上得出它的對偶問題：其中：AT、bT

分別是原LP中的約束條件矩陣A的轉(zhuǎn)置矩陣與約束條件中右端向量的轉(zhuǎn)置(即為行向量)。11線性規(guī)劃問題與其對偶問題的相關(guān)性原問題的約束條件的個數(shù)m就是對偶問題的變量的個數(shù)；原問題的變量的個數(shù)n就是對偶問題的約束條件的個數(shù)；若原問題的目標(biāo)函數(shù)是Max型，則對偶問題的目標(biāo)函數(shù)必是Min型。它們二者的最優(yōu)目標(biāo)函數(shù)值相等。122.5.3一般LP的對偶問題

（書本P45定義2.5.1）原問題（P）：對偶問題（D）：mincTxmaxbTys.t.aiTx

=bii=1,…,ps.t.y0

aiTx

≥bii=p+1,…,my≥0xj≥0j=1,…,qAjTy

cxj

0j=q+1,…,nAjTy=c><><13對偶規(guī)則原問題有m個約束條件

對偶問題有m個變量原問題有n個變量

對偶問題有n個約束條件原問題的價值系數(shù)

對偶問題的右端項原問題的右端項

對偶問題的價值系數(shù)原問題的系數(shù)矩陣轉(zhuǎn)置后為對偶問題系數(shù)矩陣14對偶規(guī)則對偶問題原問題目標(biāo)函數(shù)maxmin目標(biāo)函數(shù)約束條件

≤

≥

=≥變量≤無約束

≥變量≤

無約束≥

≤

約束條件

=152.5.4對偶問題的基本性質(zhì)對偶定理2.5.1：若一個LP問題有最優(yōu)解，則它的對偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。對稱性：對偶問題與原問題互為對偶。無界性：原問題無界，對偶問題無可行解原問題與對偶問題：原始對偶有最優(yōu)解問題無界無可行解有最優(yōu)解1XX問題無界XX3無可行解X32162.5.5對偶變量的經(jīng)濟解釋對偶變量yi在經(jīng)濟上表示原問題第i種資源的邊際貢獻，即當(dāng)?shù)趇種資源增加一個單位時，相應(yīng)的目標(biāo)值z的增量。對偶問題的最優(yōu)解yi*是原問題第i種資源的影子價格應(yīng)用:1.出租資源或設(shè)備時，租金價格的設(shè)定(至少高于該資源在企業(yè)內(nèi)的影子價格)2.企業(yè)內(nèi)資源I的存量設(shè)定(當(dāng)資源I的影子價格

市場價格時，可買進該資源；否則賣出)3.調(diào)整資源的分配量以增加利潤172.5（1）對偶問題要求：了解LP對偶問題的實際意義掌握對偶問題的建立規(guī)則與基本性質(zhì)了解對偶最優(yōu)