運籌學第2章-線性規(guī)劃的對偶理論

1、7/25/2022第2章 線性規(guī)劃的對偶理論1目錄7/25/20222.1 線性規(guī)劃的對偶問題2.2 對偶理論2.3 影子價格2.4 對偶單純形法2.5 靈敏度分析 CONTENTS22.1 線性規(guī)劃的對偶問題在第1章的例1.1中，我們討論了如下的生產(chǎn)計劃模型：假定現(xiàn)有一公司想把該工廠的生產(chǎn)資源收購過來，那么它至少應付出多大的代價，才能使該工廠愿意放棄生產(chǎn)活動，出讓自己的資源？現(xiàn)在從另一個角度來討論這個問題：7/25/20222.1.1 對偶問題的提出例1.1 生產(chǎn)計劃問題問產(chǎn)品A, B各生產(chǎn)多少, 可獲最大利潤? A B 備用資源 鋼材（噸） 1 2 30 勞動力（工時） 3 2 60特種設

2、備（臺時） 0 2 24 利潤（元/件） 40 504設用 y1, y2, y3 分別表示鋼材、勞動力和特種設備這三種資源的單位定價。因為用1個單位的鋼材和3個單位的勞動力可以生產(chǎn)一件產(chǎn)品A，從而獲得40元利潤。那么生產(chǎn)每件產(chǎn)品A的資源出讓所得應不低于生產(chǎn)一件產(chǎn)品A的利潤，即y1 + 3y2 40同理，將可以生產(chǎn)每件產(chǎn)品B的資源出讓的所得應不低于生產(chǎn)一件產(chǎn)品B的利潤，即2y1 + 2y2 + 2y3 507/25/20222.1.1 對偶問題的提出5要把所有的資源都收購需付出：W = 30y1 + 60y2 + 24y3當然收購公司希望用最小的代價把工廠的全部資源收買過來，故有：min W =

3、 30y1 + 60y2 + 24y3s.t. y1 + 3y2 40 2y1 + 2y2 + 2y3 50 y1 , y2 , y3 0對偶問題(DUAL)7/25/20222.1.1 對偶問題的提出6問最經(jīng)濟的配食方案是什么？維生素的銷售商換個角度例1.2 混合配料問題 飼料 A B C 每單位成本 飼料1 4 1 0 2 飼料2 6 1 2 5 飼料3 1 7 1 6 飼料4 2 5 3 8 每天維生素 12 14 8 的最低需求維生素/mg2.1.1 對偶問題的提出7/25/20227“對稱型”對偶問題 min w=bTyATy c y0A 矩陣y, b 列向量c 列向量max z=c

4、Tx Ax b x0A 矩陣x, b 列向量c 列向量原問題7/25/20222.1.2 線性規(guī)劃原問題與對偶問題的表達形式87/25/2022原始問題max z=cTxs.t. Ax b x 0對偶問題min w=bTys.t. ATy c y 0maxbAcTmncATbTminmn2.1.2 線性規(guī)劃原問題與對偶問題的表達形式9min z=-cTxs.t. -Ax -b x 0max w=-bTys.t. -ATy -cy 0min w=bTys.t. ATy c y 0max z=cTxs.t. Ax b x 0對偶的定義對偶的定義對偶問題的對偶就是原始問題！7/25/20222.1.

5、2 線性規(guī)劃原問題與對偶問題的表達形式10“非對稱型”2.1.2 線性規(guī)劃原問題與對偶問題的表達形式2.1.2 線性規(guī)劃原問題與對偶問題的表達形式012對偶關(guān)系對應表 （P） （D）目標函數(shù)maxmin目標系數(shù)Cb約束右端bC系數(shù)矩陣AAT函數(shù)約束與變量約束第k個約束 第k個變量約束個數(shù)=變量個數(shù)（非）規(guī)范約束 非負（正）變量等式約束 自由變量7/25/20222.1.2 線性規(guī)劃原問題與對偶問題的表達形式13例2.1 寫出對偶規(guī)劃：min z= 4x1 +2x2 3x3 x1+2x2 62x1 +3x3 9 x1 +5x2 2x3 = 4x1自由, x2 0, x3 0 y1+2y2 + y

6、3 = 42y1 +5y3 2 3y2 2y3 3y1 0 , y2 0 , y3自由max w= 6y1 +9y2 +4y3 7/25/20222.1.2 線性規(guī)劃原問題與對偶問題的表達形式142.2 對偶理論證明： 7/25/20222.2.1 弱對偶性16由弱對偶性，可得出以下的推論： 原問題有可行解且目標函數(shù)值無界，則其對偶問題無可行解；反之，對偶問題有可行解且目標函數(shù)值無界，則其原問題無可行解。（注意：逆命題不成立） 若原問題有可行解而對偶問題無可行解，則原問題目標函數(shù)值無界；反之，對偶問題有可行解而原問題無可行解，則對偶問題的目標函數(shù)值無界。7/25/20222.2.1 弱對偶性1

7、7證明： 再由弱對偶性：7/25/20222.2.2 最優(yōu)性18若原問題與其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們的最優(yōu)解的目標函數(shù)值相等。證明：由于兩者均有可行解，根據(jù)弱對偶性推論，原問題的目標函數(shù)值具有上界，對偶問題的目標函數(shù)值具有下界。因此，兩者均具有最優(yōu)解。由前面的討論知，當原問題為最優(yōu)解，即 B 為最優(yōu)基時，YT = CBB-1 是其對偶問題的可行解，且兩者目標函數(shù)值相等。由最優(yōu)性條件，得此 Y 即為最優(yōu)解。7/25/20222.2.3 強對偶性（對偶定理）19在線性規(guī)劃問題的最優(yōu)解中，如果對應某一約束條件的對偶變量值為非零，則該約束條件條件取嚴格等式；反之，如果約束條件取

8、嚴格不等式，則其對應的對偶變量為零。原問題：max z=cTx Ax + xs =b x, xs 0 x =x1xnxs=xs1xsm7/25/20222.2.4 互補松弛性（松緊定理）20證明：7/25/20222.2.4 互補松弛性（松緊定理）217/25/20222.2.4 互補松弛性的應用例2.2 已知線性規(guī)劃問題min z = 2x1+ 3x2 + 5x3 + 2x4 + 3x5 x1+ x2 + 2x3 + x4 +3x5 4 2x1- x2 + 3x3 + x4 + x5 3 x1, x2 , x3 , x4 , x5 0其對偶問題的最優(yōu)解為 y1=4/5, y2=3/5，試應用

9、對偶理論求原問題的解。222.2.4 互補松弛性的應用將 y1=4/5, y2 =3/5的值代入，得知 為嚴格不等式，于是由互補松馳性，必有 x2= x3 = x4=0 解：寫出對偶問題：Max S = 4y1+ 3y2 y1+ 2y2 2 y1- y2 3 2y1+ 3y2 5 y1+ y2 2 3y1+ y2 3 y1, y2 0又因 y1, y2 0，故原問題的兩個約束條件必為緊約束，即有 x1+ 3x5 =4 2x1+ x5 =3 解得 x1=x5 =1 即 X*=(1,0,0,0,1)T, Z*=50237/25/20222.2.5 對偶問題解與原問題解的關(guān)系則原問題單純形表的檢驗數(shù)

10、行對應其對偶問題的一個可行解設原問題：max z = cTxs.t. Ax+xs=b x, xs0其對偶問題： min w = bTy s.t. ATy- ys=c y, ys0 ys1 是對應原問題中基變量 XB 的剩余變量 ys2 是對應原問題中非基變量XN 的剩余變量XBXNXs0CN -CBB-1N-CBB-1-ys1-ys2-y松弛變量剩余變量檢驗數(shù)24項 目非基變量XB XN基變量Xs0 Xs bB NIcj - zjCB CN 0項 目基變量XB非基變量 XN XsCB XB B-1 bIB-1N B-1cj - zj0CN -CB B-1N -CB B-1初始單純形表：當?shù)?/p>

11、基變量為 XB 時：當 B 為最優(yōu)基時： 0 0CB CBB-1B= 02.2.5 對偶問題解與原問題解的關(guān)系025CB CBB-1B = 0CN -CB B-1N 0C - CB B-1A 0-CB B-1 0ATy C y 0令 yT = CBB-1由此可見，y 是對偶問題的一個可行解。將這個解代入對偶問題的目標函數(shù)，有w = bTy = yTb = CBB-1b = CBXB = z即當原問題為最優(yōu)解時，這時對偶問題為可行解，且兩者具有相同的目標函數(shù)值。7/25/20222.2.5 對偶問題解與原問題解的關(guān)系26產(chǎn)品A，B產(chǎn)量x1，x2，Z為利潤3x1 +x2 +x3=483x1 +4x

12、2 +x4=120 x1 x40Max Z= 5x1 +6x2 3x1 +x2 483x1 +4x2 120 x1 , x2 0機器臺時勞動工時7/25/20222.2.5 對偶問題解與原問題解的關(guān)系例：27X=(8,24)T Z =184 5 6 0 0 XB b x1 x2 x3 x40 x3 48 3 1 1 00 x4 120 3 (4) 0 1 0 5 6 0 00 x3 18 (9/4) 0 1 -1/46 x2 30 3/4 1 0 1/4 180 1/2 0 0 -3/25 x1 8 1 0 4/9 -1/96 x2 24 0 1 -1/3 1/3 184 0 0 -2/9 -

13、13/9B-1B0282.2.5 對偶問題解與原問題解的關(guān)系3y1+3y2 5 y1 +4y2 6 y1 , y2 0Min W=48y1+120y23y1+3y2 -y3+y5 =5 y1 +4y2 -y4+y6= 6Min W=48y1+120y2 +My5 +My6Max Z= 5x1 +6x2 3x1 +x2 483x1 +4x2 120 x1 , x2 0機器臺時勞動工時對偶問題？0292.2.5 對偶問題解與原問題解的關(guān)系 48 120 0 0 M M yB y1 y2 y3 y4 y5 y6M y5 5 3 3 -1 0 1 0 M y6 6 1 4 0 -1 0 1 11M 4

14、8-4M 120-7M M M 0 0M y5 1/2 9/4 0 -1 3/4 1 -3/4120 y2 3/2 1/4 1 0 -1/4 0 1/4 180+1/2M 18-9/4M 0 M 30-3/4M 0 -30+7/4M48 y1 2/9 1 0 -4/9 1/3 4/9 -1/3120 y2 13/9 0 1 1/9 -1/3 -1/9 1/3y=(2/9,13/9), Z=184 184 0 0 8 24 M-8 M-240302.2.5 對偶問題解與原問題解的關(guān)系2.3 影子價格z= CBB-1b + (CN - CBB-1 N)XN ()z= z(b) b為資源數(shù)對()求偏

15、導： z b=CBB-1=YT對偶解Y b 的單位改變量所引起的目標函數(shù)值的改變量。7/25/20222.3.1 對偶解的經(jīng)濟意義32w = ( y1 ym )b1bm= b1 y1 + b2 y2 + + bm ymbi ：第 i 種資源的數(shù)量； yi ：對偶解；yi ：反映bi 的邊際效益(邊際成本)當 bi 增加 bi ,其它資源數(shù)量不變時,目標函數(shù)的增量Z =bi yi7/25/20222.3.1 對偶解的經(jīng)濟意義33由前面的經(jīng)濟解釋可知，yi 的大小與系統(tǒng)內(nèi)資源對目標的貢獻有關(guān)，是資源的一種估價，稱為影子價格。(Shadow Price)注：這種估價不是資源的市場價格。市場價格是已知

16、數(shù)，相對較穩(wěn)定；而影子價格則有賴于資源的利用情況，是未知數(shù)。當企業(yè)的生產(chǎn)任務、產(chǎn)品結(jié)構(gòu)等等發(fā)生變化時，資源的影子價格也會隨之改變，它是一種動態(tài)價格。7/25/20222.3.2 影子價格34即某資源對偶解0，該資源有利可圖，可增加此種資源量；某資源對偶解為0，則不增加此種資源量。 影子價格的大小客觀地反映了資源在系統(tǒng)內(nèi)的稀缺程度根據(jù)互補松弛定理的條件，如果某一資源在系統(tǒng)內(nèi)供大于求，其影子價格就為零。即增加該資源的供應不會引起系統(tǒng)目標的任何變化。如果某一資源是稀缺資源（即相應約束條件的剩余變量為零），則影子價格必然大于零。影子價格越高，資源在系統(tǒng)中越稀缺。7/25/20222.3.2 影子價格的

17、應用35即直接用影子價格與市場價格相比較，進行決策，是否買入該資源。 影子價格實際上是一種機會成本在完全市場經(jīng)濟條件下，當某種資源的市場價格低于影子價格時，企業(yè)應買進該資源用于擴大再生產(chǎn)；而當某種資源的市場價格高于影子價格時，企業(yè)應賣掉已有資源。隨著資源的買進賣出，其影子價格也將發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡。7/25/20222.3.2 影子價格的應用362.4 對偶單純形法單純形法的基本思路：找基 B，滿足 B-1b 0，但 C - CBB-1 A（即檢驗數(shù)）不全 0。迭代保持 B-1b 0，使 C -CBB-1 A 0，即 CBB-1 A C對偶單純形法的基

18、本思路：迭代保持 C -CBB-1 A 0，使 B-1b 0找基 B，滿足 C - CBB-1 A 0，但 B-1b 不全 0。對偶問題的可行基7/25/20222.4.1 基本思路38(1) 作初始表，要求全部 cj - zj 0(2) 判定：B-1 b 全 0，停。否則，取其對應變量 xr 為換出基的變量。(3) 確定換入變量 若第 r 行的 arj 全 0 ，停，原問題無可行解。7/25/20222.4.2 計算步驟39 若第 r 行的 arj 有 arj 0 , 則求其對應變量 xs 為換入基的變量(3) 確定換入變量(4) 以 ars 為主元，換基迭代，得到新的單純形表重復1-4的步

19、驟，直到找到最優(yōu)解7/25/20222.4.2 計算步驟40關(guān)于的解釋：第 r 個方程即0某 xj 從 0，xr不能變 007/25/20222.4.2 計算步驟步驟(3)的兩個注釋41關(guān)于的解釋：下一個表中的檢驗數(shù)為為保持可行，必須(a) 對 arj 0, 因 cj zj 0 (b) 對 arj 0，需用單純形法繼續(xù)迭代求解。7/25/20222.5.2 價值系數(shù)cj的靈敏度分析 8 -4/3 -5/3 2/351為使表中的解仍為最優(yōu)解，應有C2在什么范圍變化的時候，最優(yōu)解不變？2.5.2 價值系數(shù)cj的靈敏度分析052右端項 bi 的變化在實際問題中為可用資源數(shù)量的變化。bi 的變化反映到

20、最終單純形表上將引起 b 列數(shù)字的變化，可能有下面兩種情況：問題的最優(yōu)基不變，變化后的 b 列值為最優(yōu)解； （即生產(chǎn)產(chǎn)品的品種不變，但數(shù)量及最優(yōu)值會變化）原問題不可行但對偶問題可行，用對偶單純形繼續(xù)迭代求最優(yōu)解。B-1bB-1A-CB B-1bC -CB B-1A7/25/20222.5.3 資源系數(shù)bi的靈敏度分析5315-3初始表最終表75B-1b2.5.3 資源系數(shù)bi的靈敏度分析054B-1對偶單純形2.5.3 資源系數(shù)bi的靈敏度分析15-3初始表最終表B-1B-1b若最優(yōu)基不變，那么b2的變化范圍是多少？2.5.3 資源系數(shù)bi的靈敏度分析056增加一個變量 xj 在實際問題中反映為增加一種新的產(chǎn)品。技術(shù)系數(shù)矩陣多增加一列 Pj檢驗數(shù)多增加一個 j最終單純形表中它們的值如何得到？原最優(yōu)解不變按單純形法繼續(xù)迭代計算找出最優(yōu)解7/25/20222.5.4 增加一個決策變量xj的靈敏度分析57 2.5 x6 3 2 2.5若工廠計劃推出一種新