第3章 北理工運籌學課件

1、1第三章 線性規(guī)劃問題的對偶與靈敏度分析w線性規(guī)劃的對偶問題概念、理論及經(jīng)濟意義w線性規(guī)劃的對偶單純形法w線性規(guī)劃的靈敏度分析本章內(nèi)容重點21.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題 對偶原理 對偶問題定義 線性規(guī)劃問題寫出其對偶問題，要掌握在對稱形式和非對稱情況下由原問題寫出對偶問題的方法。 對偶定理 只需了解原問題與對偶問題解的關(guān)系，證明從略。3 1.對偶問題： 若第二章例2.1問題的設(shè)備都用于外協(xié)加工，工廠收取加工費。試問：設(shè)備 A、B、C 每工時各如何收費才最有競爭力？ 設(shè) y1 ，y2 ，y3 分別為每工時設(shè)備 A、B、C 的收取費用。1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題4線性規(guī)劃

2、原問題線性規(guī)劃原問題 例2.1:某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示。求獲最大利潤的方案。 產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3 32 26565設(shè)備B2 21 14040設(shè)備C0 03 37575利潤（元/件）1500150025002500 5 Max z = 1500 x1 + 2500 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 原問題原問題 3x2 75 x1 ,x2 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1

3、500 （不少于甲產(chǎn)品的利潤） 2y1+y2+3y3 2500 對偶問題對偶問題 （不少于乙產(chǎn)品的利潤） y1, y2 , y3 01.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題6 2、對偶定義 對稱形式： 互為對偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題7 一對對稱形式的對偶規(guī)劃之間具有下面的對應(yīng)關(guān)系。 (1)若一個模型為目標求“極大”，約束為“小于等于”的不等式，則它的對偶模型為目標求“極小”，約束是“大于等于”的不等式。即“max

4、，”和“min，”相對應(yīng)。1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題8 (2)從約束系數(shù)矩陣看：一個模型中為，則另一個模型中為AT。一個模型是m個約束，n個變量，則它的對偶模型為n個約束，m個變量。 (3)從數(shù)據(jù)b、C的位置看：在兩個規(guī)劃模型中，b和C的位置對換。 (4)兩個規(guī)劃模型中的變量皆非負。1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題9 非對稱形式的對偶規(guī)劃 一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃。 對于非對稱形式的規(guī)劃，可以按照下面 的對應(yīng)關(guān)系直接給出其對偶規(guī)劃。 （1）將模型統(tǒng)一為“max，”或“min，” 的形式，對于其中的等式約束按下面（2）、（3）中的方法處理；

5、（2）若原規(guī)劃的某個約束條件為等式約束，則在對偶規(guī)劃中與此約束對應(yīng)的那個變量取值沒有非負限制；1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題1x2x3x0jx1y11a12a13a1b2y21a22a23a2b3y31a32a33a3b4y41a42a43a4b0jy1c2c3c1x2x3x0jx1y11a12a13a1b2y21a22a23a2b3y31a32a33a3b4y41a42a43a4b0jy1c2c3c1x2x3x0jx1y11a12a13a1b2y21a22a23a2b3y31a32a33a3b4y41a42a43a4b0jy1c2c3c10 （3）若原規(guī)劃的某個變量的值沒有非負限

6、制，則在對偶問題中與此變量對應(yīng)的那個 約束為等式。 下面對關(guān)系（2）作一說明。對于關(guān)系（3） 可以給出類似的解釋。 設(shè)原規(guī)劃中第一個約束為等式： a11x1 + + a1nxn = b1 那么，這個等式與下面兩個不等式等價1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題111.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題1111111111.bxaxabxaxannnn這樣，原規(guī)劃模型可以寫成mjxbxaxabxaxabxaxaxcxcZjmnmnmnnnnnn, 2 , 1, 0max11111111111111121.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題 此時已轉(zhuǎn)化為對稱形式，直接寫出對偶規(guī)劃沒有非負限制

7、121111112211211211111111221111,0, , minyyyyycyayayacyayayacyayayaybybybybfmnmmnnnmmmmmm這里，把 y1 看作是 y1 = y1 - y1，于是 y1 沒有非負限制，關(guān)系（2）的說明完畢。131.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題 例3.1 寫出下面線性規(guī)劃的對偶規(guī)劃模型解 先將約束條件變形為“”形式?jīng)]有非負限制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ141.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題沒有非負限制432144321

8、4314321,0,051030422602722523xxxxxxxxxxxxxxxx 再根據(jù)非對稱形式的對應(yīng)關(guān)系，直接寫出對偶規(guī)劃151.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題0,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf沒有非負限制16 3.對偶定理(原問題與對偶問題解的關(guān)系）考慮（LP）和（DP） 定理3-1 (弱對偶定理） 若 x, y 分別為（LP) 和（DP）的可行解，那么cTx bTy。 推論 若（LP）可行，那么（LP）無有限最優(yōu)解的充分必要條件是（LD）無可行解。1.1.線性規(guī)劃對

9、偶問題線性規(guī)劃對偶問題17 定理3-2 (最優(yōu)性準則定理) 若x,y分別(LP),(DP)的可行解,且cTx=bTy ，那么x,y分別為(LP)和(DP)的最優(yōu)解。 定理3-3 (主對偶定理) 若(LP)和(DP)均可行 那么(LP)和(DP)均有最優(yōu)解,且最優(yōu)值相等。 以上定理、推論對任意形式的相應(yīng)性規(guī)劃的對偶均有效1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題18 4. 4.影子價格影子價格 是一個向量，它的分量表示最優(yōu)目標值隨相應(yīng)資源數(shù)量變化的變化率。 若x*,y* 分別為（LP）和（DP）的最優(yōu)解， 那么， cT x* = bT y* 。 根據(jù) f = bTy*=b1y1*+b2y2*+bm

10、ym* 可知 f / bi = yi* yi* 表示 bi 變化1個單位對目標 f 產(chǎn)生的影響，稱 yi* 為 bi的影子價格。 注意：注意：若 B 是最優(yōu)基， y* = (BT)-1 cB 為影子價格向量。1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題19 影子價格的經(jīng)濟含義 (1)影子價格是對現(xiàn)有資源實現(xiàn)最大效益時的一種估價 企業(yè)可以根據(jù)現(xiàn)有資源的影子價格，對資源的使用有兩種考慮：第一，是否將設(shè)備用于外加工或出租，若租費高于某設(shè)備的影子價格，可考慮出租該設(shè)備，否則不宜出租。第二，是否將投資用于購買設(shè)備，以擴大生產(chǎn)能力，若市價低于某設(shè)備的影子價格，可考慮買進該設(shè)備，否則不宜買進。1.1.線性規(guī)劃對

11、偶問題線性規(guī)劃對偶問題201.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題 （2） 影子價格表明資源增加對總效益產(chǎn)生的影響。根據(jù)推論推論“設(shè)x0和y0分別為原規(guī)劃（P）和對偶規(guī)劃（D）的可行解，當cx0=bTy0時，x0、y0分別是兩個問題的最優(yōu)解”可知，在最優(yōu)解的情況下，有關(guān)系 因此，可以將z*看作是bi,i=1,2， ,m的函數(shù)，對bi求偏導數(shù)可得到 這說明，如果右端常數(shù)增加一個單位，則目標函數(shù)值的增量將是*22*11*mmybybybfZmiybZii,2,1,*miyi,2,1,*21 影子價格反映了不同的局部或個體的增量可以獲得不同的整體經(jīng)濟效益。如果為了擴大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從

12、影子價格高的設(shè)備入手。這樣可以用較少的局部努力，獲得較大的整體效益。1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題22 需要指出，影子價格不是固定不變的，當約束條件、產(chǎn)品利潤等發(fā)生變化時，有可能使影子價格發(fā)生變化。另外，影子價格的經(jīng)濟含義（2），是指資源在一定范圍內(nèi)增加時的情況，當某種資源的增加超過了這個“一定的范圍”時，總利潤的增加量則不是按照影子價格給出的數(shù)值線性地增加。這個問題還將在靈敏度分析一節(jié)中討論。1.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題23 5.由最優(yōu)單純形表求對偶問題最優(yōu)解 標準形式： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2x

13、1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 01.1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題2450100000CBXBx1x2x3x4x5i0 x3300111003000 x4400210104000 x52500(1)001250-z050100*0000 x350(1)010-1500 x41502001-175100 x225001001-z-2500050*000-10050 x1501010-10 x45000-211100 x225001001-z-2750000-500-50-c-cB BT TB B-1-1I IB B=(

14、p p1 1, p, p4 4,p,p2 2 )oTB B-1-1最優(yōu)解 x1 = 50 x2 = 250 x4 = 50影子價格影子價格 y y1 1 = 50 = 50 y y2 2 = 0 = 0 y y3 3 = 50 , = 50 , B B-1-1對應(yīng)的檢驗數(shù)對應(yīng)的檢驗數(shù) T T = = c cB BT TB B-1-1 。 1. 1.線性規(guī)劃對偶問題線性規(guī)劃對偶問題25 對偶單純形法的基本思想 對偶單純形法的基本思想是：從原規(guī)劃的一個基本解基本解出發(fā)，此基本解不一定可行，但它對應(yīng)著一個對偶對偶可行解可行解（檢驗數(shù)非正），所以也可以說是從一個對偶可行解出發(fā)；然后檢驗原規(guī)劃的基本解是

15、否可行，即是否有負的分量，如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應(yīng)著另一個對偶可行解（檢驗數(shù)非正）。2.2.對偶單純形法對偶單純形法26 如果得到的基本解的分量皆非負則該基本解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚校斖瑫r得到對偶規(guī)劃與原 規(guī)劃的可行解時，便 得到原規(guī)劃的最優(yōu)解。2.2.對偶單純形法對偶單純形法27 對偶單純形法在什么情況下使用 ： 應(yīng)用前提：有一個基，其對應(yīng)的基滿足: 單純形表的檢驗數(shù)行全部非正（對偶可行）； 變量取值可有負數(shù)（非可行解）。 注：通過矩陣行變換運算，使所有相應(yīng)

16、變量取值均為非負數(shù)即得到最優(yōu)單純形表。2.2.對偶單純形法對偶單純形法28w 1.建立初始對偶單純形表,對應(yīng)一個基本解,所有檢驗數(shù)均非正,轉(zhuǎn)2； 2.若b0,則得到最優(yōu)解,停止;否則,若有bk0則選k行的基變量為出基變量,轉(zhuǎn)3 3.若所有akj0( j = 1,2,n )，則原問題無可行解,停止;否則,若有akj0 則選 =minj / akjakj0=r/akr那么 xr為進基變量,轉(zhuǎn)4； 4.以akr為轉(zhuǎn)軸元,作矩陣行變換使其變?yōu)?,該列其他元變?yōu)?,轉(zhuǎn)2。 對偶單純形法求解線性規(guī)劃問題對偶單純形法求解線性規(guī)劃問題過程：過程：2.2.對偶單純形法對偶單純形法29例3.2：求解線性規(guī)劃問題：

17、求解線性規(guī)劃問題： 標準化：標準化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 2.2.對偶單純形法對偶單純形法30w表格對偶單純形法CI-2-3-400CBXBbX1X2X3X4X50 X4-3-1-2-1100 X5-4-21-301j-2-3-4000 X4-10-5/21/21-1/2-2 X121-1/23/2

18、0-1/2j0-4-10-1-3 X22/501-1/5-2/51/5-2 X111/5107/5-1/5-2/5j00-9/5-8/5-1/52.2.對偶單純形法對偶單純形法31單純形法和對偶單純形法步驟是是是是否否否否所有所有得到最優(yōu)解計算計算典式對應(yīng)原規(guī)劃的基本解是可行的典式對應(yīng)原規(guī)劃的基本解的檢驗數(shù)所有所有計算計算以為中心元素進行迭代以為中心元素進行迭代停沒有最優(yōu)解沒有最優(yōu)解單純形法對偶單純形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min0csMinj/asjasj0brMin-bi/airair03.3.

19、靈敏度分析靈敏度分析46 例3.5: 上例最優(yōu)單純形表如下 C i23000CBX BBX 1X 2X 3X 4X 52 X 141001/400 X 5400-21/213 X 22011/2-1/80j00-1.5-1/803.3.靈敏度分析靈敏度分析47 0 0.25 0 這里 B B-1 = -2 0.5 1 0.5 -0.125 0 各列分別對應(yīng) b1、b2、b3 的單一變化因此，設(shè) b1 增加 4，則 x1 ,x5 ,x2分別變?yōu)椋?+04=4, 4+(-2)4=-40, 2+0.54=4用對偶單純形法進一步求解，可得：x* = ( 4, 3, 2, 0, 0 )T f* = 173.3.靈敏度分析靈敏度分析48 增加一個變量 增加變量 xn+1 則有相應(yīng)的pn+1 ,cn+1 。 那么 計算出B B-1pn+1 , n+1=cn+1-cri ari n+1 填入最優(yōu)單純形表, 若 n+1 0 則 最優(yōu)解不變； 否則，進一步用單純形法求解。3.3.靈敏度分析靈敏度分析49例3.6:例3.4增加x6 , p6=( 2, 6, 3 )T, c6=5 計算得到Ci230005CBXBbX1X2X3X4X5X62 X141001/401.50 X5400-21/2