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

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

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

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

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

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

6、原始問題max : , 0Tc xAxb x的第 i 個(gè)約束: 1 11, 1,nijjiinnija xa xa xbim任取1yD, 考慮對(duì)偶問題min : , 0TTb yA yc y的第 j 個(gè)約束: 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, 即對(duì)應(yīng)的目標(biāo)函數(shù)值相等, 則 x是原始問

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