第三章-線性規(guī)劃的對偶理論和靈敏度分析

1、第三章第三章 線性規(guī)劃的對偶理論和靈敏度分析線性規(guī)劃的對偶理論和靈敏度分析 求解線性規(guī)劃問題的方法一般分為三步求解線性規(guī)劃問題的方法一般分為三步: 第一步第一步:對實(shí)際問題進(jìn)行細(xì)致分析, 建立適當(dāng)?shù)木€性規(guī)劃模型; 第二步第二步:求解這個線性規(guī)劃模型, 得到最優(yōu)解和最優(yōu)值; 第三步第三步:對最優(yōu)解進(jìn)行分析. 對決策者來說, 進(jìn)行第三步工作極為重要。通過靈敏度分析研究系數(shù)的變化對最優(yōu)解 的影響。 3.1.對偶問題的提出對偶問題的提出 問題問題 3.1.2. 3.1.2. 四海機(jī)械廠為擴(kuò)大生產(chǎn)規(guī)模, 想租借常山機(jī)械廠的設(shè)備資源. 問: 常山廠愿意以每小時什么價格出租設(shè)備呢? 問題建模問題建模. 設(shè)常

2、山廠每小時出租C D E , 三種設(shè)備的價格分別是123,y yy對常山廠來說, 出租設(shè)備所帶來的利潤應(yīng)不小于自己生產(chǎn)所帶來的利潤, 故有約束 和12242yy13255yy對四海廠來說, 一方面租金越少越好; 另一方面, 對租來的設(shè)備使用率越高越好, 故目標(biāo)函數(shù)應(yīng)為123min 121615yyy因此, 可建立如下線性規(guī)劃模型: 由于模型(3.1.2)是通過模型(3.1.1)引申出來的, 故稱模型(3.1.1)為原始模型原始模型, 稱對應(yīng)的實(shí)際問題為原始問題原始問題; 稱模型(3.1.2)為對偶模型對偶模型, 稱對應(yīng)的問題為對偶問題對偶問題. 從(3.1.3)式可以看出:1. 原始模型是極大

3、化極大化問題, 對偶模型是極小化極小化問題;2. 對偶模型中決策變量的個數(shù)決策變量的個數(shù)是原始模型中不等式不等式約束的個數(shù)約束的個數(shù);3. 對偶模型中不等式約束不等式約束的個數(shù)是原始模型中決決策變量策變量的個數(shù);4. 對偶模型中的約束矩陣是原始模型中約束矩陣的轉(zhuǎn)置轉(zhuǎn)置;5. 原始模型是小于等于小于等于的不等式約束, 對偶模型是大于等于大于等于的不等式約束;6. 原始模型的常向量常向量是對偶模型的價值向量價值向量. 對偶模型的常向量常向量是原始模型的價值向量價值向量. 對一般的線性規(guī)劃模型, 我們也可根據(jù)這六條規(guī)律, 寫出另一個線性規(guī)劃模型, 這時, 稱第一個線性規(guī)劃模型為原始模型原始模型, 第

4、二個線性規(guī)劃模型為對偶模型對偶模型. 例例 3.1.3. 3.1.3. 寫出下述線性規(guī)劃模型的對偶模型及對偶模型的對偶模型: 123123123123123max 563 . . 235, -53, 4738, ,0.xxxst xxxxxxxxxx x x結(jié)論：結(jié)論：模型(3.1.8)等價于原始模型(3.1.4), 這說明原始模型(3.1.4)和其對偶模型(3.1.6)互為對偶模型. 對一般的線性規(guī)劃問題, 我們也有此規(guī)律, 即原始模型和對偶模型互為對偶模型。原始模型和對偶模型互為對偶模型。 3.2 3.2 對偶問題的基本性質(zhì) 任意一個線性規(guī)劃問題都存在著與其對應(yīng)的對偶問題, 且互為對偶,

5、那么原始問題和對偶問題的最優(yōu)解之間有什么關(guān)系呢? 對偶問題共有四個基本性質(zhì),分別是弱對偶性、弱對偶性、最優(yōu)性、強(qiáng)對偶性和互補(bǔ)松弛性最優(yōu)性、強(qiáng)對偶性和互補(bǔ)松弛性. 如果一點(diǎn)關(guān)系都沒有, 我們在討論原始問題時就沒必要考慮其對偶問題了; 如果有關(guān)系, 有什么樣的關(guān)系呢? 設(shè)原始問題 max: ,0Tc xAxb x的可行域為 : ,0nDxRAxb x, 對偶問題 min:, 0TTb y A yc y的可行域為 1: ,0mTDyRA yc y性質(zhì)一性質(zhì)一. (弱對偶性弱對偶性) 原始問題的目標(biāo)函數(shù)值不超過對偶問題的目標(biāo)函數(shù)值, 即 1, ,TTc xb yxDyD 證明證明. 任取 xD, 考慮

6、原始問題max : , 0Tc xAxb x的第 i 個約束: 1 11, 1,nijjiinnija xa xa xbim任取1yD, 考慮對偶問題min : , 0TTb yA yc y的第 j 個約束: 111, 1,mijijmjmjia ya ya ycjn顯然,0 x y 且 1111111111(),().nnmmnTjjijijijjijjiijmmnmnTiiijjiijjiiijijc xc xa y xa x yb yb ya xya x y 因此有TTc xb y性質(zhì)二性質(zhì)二. (最優(yōu)性) 設(shè)1,xD yD使得TTc xb y, 即對應(yīng)的目標(biāo)函數(shù)值相等, 則 x是原始問

7、題的最優(yōu)解，y是對偶問題的最優(yōu)解.證明證明. 設(shè) *x是原始問題的最優(yōu)解, *y是對偶問題的最優(yōu)解, 則 *, TTTTc xc xb yb y由性質(zhì)一知*TTTTTc xc xb yb yc x. 故*TTc xc x和* TTb yb y這說明x是原始問題的最優(yōu)解，y是對偶問題的最優(yōu)解.性質(zhì)三性質(zhì)三. (強(qiáng)對偶性) 若原始問題max:, 0Tc x Axb x有最優(yōu)解, min:,0TTb y A yc y一定有最優(yōu)解, 證明證明. 不妨設(shè)常向量0b . 通過引入松弛變量, 可將原始問題化成標(biāo)準(zhǔn)形式:1max . . , 1, 0, 0,1, .Tnijjiijic xsta xxbimx

8、xim則對偶問題且對應(yīng)的最優(yōu)值相同. 設(shè) *n mxR是標(biāo)準(zhǔn)形式的最優(yōu)解且對應(yīng)的基為B，則1*,0B bx10B b且10,1,TjjBjcc Bpjmn對松弛變量來說, 有110TTTBmBcc B Ic B 松松, 從而10TBc B令*1()TTByc B則*myR且*0.y 對非松弛變量來說, 有1*()0TTTTxBcc B AcyA進(jìn)而有*TA yc因此,*y是對偶問題的可行解.由1*0B bx可推出*1*()TTTTBc xc B bybb y由性質(zhì)二知,*y是對偶問題的最優(yōu)解.性質(zhì)四性質(zhì)四. (互補(bǔ)松弛性) 設(shè)x是原始問題 max:, 0Tc x Axb x的最優(yōu)解,y是對偶問題min:, 0TTb y A yc y的最優(yōu)解. 0iy (1) 若, 則1nijjija xb(2) 若1nijjija xb, 則0iy 證明證明. 顯然1,xD yD. 由性質(zhì)一的證明, 知1111nmnmTTjj