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

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

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

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

5、那么原始問題和對偶問題的最優解之間有什么關系呢? 對偶問題共有四個基本性質,分別是弱對偶性、弱對偶性、最優性、強對偶性和互補松弛性最優性、強對偶性和互補松弛性. 如果一點關系都沒有, 我們在討論原始問題時就沒必要考慮其對偶問題了; 如果有關系, 有什么樣的關系呢? 設原始問題 max: ,0Tc xAxb x的可行域為 : ,0nDxRAxb x, 對偶問題 min:, 0TTb y A yc y的可行域為 1: ,0mTDyRA yc y性質一性質一. (弱對偶性弱對偶性) 原始問題的目標函數值不超過對偶問題的目標函數值, 即 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性質二性質二. (最優性) 設1,xD yD使得TTc xb y, 即對應的目標函數值相等, 則 x是原始問

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

8、xim則對偶問題且對應的最優值相同. 設 *n mxR是標準形式的最優解且對應的基為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進而有*TA yc因此,*y是對偶問題的可行解.由1*0B bx可推出*1*()TTTTBc xc B bybb y由性質二知,*y是對偶問題的最優解.性質四性質四. (互補松弛性) 設x是原始問題 max:, 0Tc x Axb x的最優解,y是對偶問題min:, 0TTb y A yc y的最優解. 0iy (1) 若, 則1nijjija xb(2) 若1nijjija xb, 則0iy 證明證明. 顯然1,xD yD. 由性質一的證明, 知1111nmnmTTjj