第2章線性規(guī)劃的對(duì)偶問題ppt課件

1、第二章第二章 線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論與靈敏度分析與靈敏度分析 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題 對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì) 影子價(jià)格影子價(jià)格 對(duì)偶單純形法對(duì)偶單純形法 靈敏度分析靈敏度分析 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃2.1 線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題一、對(duì)偶問題的提出一、對(duì)偶問題的提出支持對(duì)偶理論的基本思想是：每一個(gè)線性規(guī)劃問題都存在一個(gè)與其對(duì)偶的問題。在求一個(gè)問題的解的同時(shí)，也給出了另一個(gè)問題的解。例：二、對(duì)稱形式下對(duì)偶問題的一般形式二、對(duì)稱形式下對(duì)偶問題的一般形式線性規(guī)劃問題具有對(duì)稱形式，若： 變量非負(fù) 目標(biāo)函數(shù)求極大值時(shí)，約束方程均為 目標(biāo)函數(shù)求極小值

2、時(shí)，約束方程均為二、對(duì)稱形式下對(duì)偶問題的一般形式二、對(duì)稱形式下對(duì)偶問題的一般形式對(duì)稱形式的LP問題(LP1)：nnxcxcxcZ2211Max 11212111bxaxaxann22222121bxaxaxann. .tsmnmnmmbxaxaxa22110,21nxxx mmybybybW2211Min 11221111cyayayamm22222112cyayayamm. .tsnmmnnncyayaya22110,21myyy 其對(duì)偶問題為(LP2) ：注：對(duì)稱形式的注：對(duì)稱形式的LP問問題題,對(duì)對(duì)b沒有非負(fù)要求。沒有非負(fù)要求。二、對(duì)稱形式下對(duì)偶問題的一般形式二、對(duì)稱形式下對(duì)偶問題的一般

3、形式njjjxcZ1Max . t . snjijijbxa1 mi, 2 , 10 jxnj, 2 , 1miiiybW1Min . t . smijiijcya1 nj, 2 , 10 iymi, 2 , 1 LP1：LP2：CXZ Max . t . sbAX 0 X . t . sA CY 0 YbYMin二、對(duì)稱形式下對(duì)偶問題的一般形式二、對(duì)稱形式下對(duì)偶問題的一般形式項(xiàng)目原問題對(duì)偶問題A約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置b資源向量?jī)r(jià)格系數(shù)C價(jià)格系數(shù)資源向量目標(biāo)函數(shù)max z=CXmin w=Yb約束條件AXbAY C決策變量X0Y0二、對(duì)稱形式下對(duì)偶問題的一般形式二、對(duì)稱形式下對(duì)偶問題的

4、一般形式練習(xí):給出下述LP問題的對(duì)偶問題:08023402260243.342max31321321321321xxxxxxxxxxstxxxz03222434223.804060min31321321321321yyyyyyyyyystyyyw三、非對(duì)稱形式的原三、非對(duì)稱形式的原-對(duì)偶問題的關(guān)系對(duì)偶問題的關(guān)系 非對(duì)稱轉(zhuǎn)化為對(duì)稱LP問題的步驟目標(biāo)函數(shù)及變量約束的轉(zhuǎn)化同標(biāo)準(zhǔn)形式的轉(zhuǎn)化；約束方程若為等式則令:約束方程若為” ”， 則兩側(cè)同乘以“-1”，injjijbxa1njijijnjijijbxabxa11injjijbxa1injjijbxa1三、非對(duì)稱形式的原三、非對(duì)稱形式的原-對(duì)偶問題的

5、關(guān)系對(duì)偶問題的關(guān)系P50 例題2. 線性規(guī)劃原問題同對(duì)偶問題的對(duì)應(yīng)關(guān)系如下： 原問題 對(duì)偶問題 目標(biāo)函數(shù) Max 目標(biāo)函數(shù) Min m 個(gè) m 個(gè) 0 0約束條件 =無約束 決 策 變 量 n 個(gè) n 個(gè) 0 0 決策變量 無約束 = 約 束 條 件 資源向量 b 價(jià)值系數(shù) b 價(jià)值系數(shù) C 資源向量 C約束條件系數(shù)矩陣A 約束條件系數(shù)矩陣A三、非對(duì)稱形式的原三、非對(duì)稱形式的原-對(duì)偶問題的關(guān)系對(duì)偶問題的關(guān)系練習(xí):給出下述LP問題的對(duì)偶問題:0, 06325324.32max321321321321321xxxxxxxxxxxxstxxxz無約束無約束321321321321321, 0, 03

6、332221.654minyyyyyyyyyyyystxyyw2.2 對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì)njjjxcZ1Max . t . snjijijbxa1 mi, 2 , 10 jxnj, 2 , 1miiiybW1Min . t . smijiijcya1 nj, 2 , 10 iymi, 2 , 1LP1：LP2：本節(jié)討論的問題假定原問題及對(duì)偶問題為對(duì)稱形式對(duì)稱形式的線性規(guī)劃問題：093124.3max3132432132131xxxxxxxxxxstxxz-3010000CB基bx1x2x3x4x5x6x70 x5411101000 x61-21-1-10100 x790310

7x50000-1/211/2-1/20 x23011/30001/3-3x11102/31/20-1/21/600300-3/21/2jj0-3010000CB基bx5x2x1x3x4x5x6x70 x54111101000 x6101-2-1-10100 x790301000100-3100000 x501000-1/211/2-1/20 x230101/30001/3-3x110012/31/20-1/21/6000300-3/21/2jjBB-1一、單純形算法的矩陣描述一、單純形算法的矩陣描述CXZ Max . t . sbAX 0 X 對(duì)稱形式的LP：加上松馳

8、變量Xs后為(LP2)：sXCXZ0Max . t . sbIXAXs 00 sXX一、單純形算法的矩陣描述一、單純形算法的矩陣描述LP2的初始單純形表及經(jīng)過若干步迭代后某一步的單純形表如下：項(xiàng)目非基變量基變量XBXNXS0XSbBNIcj-zjCBCN0項(xiàng)目XBXNXSCBXBB-1bIB-1NB-1cj-zj0基變量非基變量B為某步單純形表中基變量在初始單純形中對(duì)應(yīng)的矩陣N由A中去掉B后剩下的列向量組成表表1表表2CN-CB B-1N-CB B-1一、單純形算法的矩陣描述一、單純形算法的矩陣描述1. 為xj在表2中的系數(shù)， 為xj在表1中的系數(shù)，則有：jpjjpBp12. 若表2為最終單純

9、形表，則有：jp0011BCNBCCBBN由C=CB CN A=B N，上式可改為：0011BCABCCBB結(jié)論：(2.1)一、單純形算法的矩陣描述一、單純形算法的矩陣描述結(jié)論：3. 令 ，則2.1式可以寫為；1BCYB0YCYA說明 為對(duì)偶問題的可行解。1BCYB將這個(gè)解代入對(duì)偶問題的目標(biāo)函數(shù)，有：zbBCbYB1即原問題有最優(yōu)解，則對(duì)偶問題存在可行解，且它們的目標(biāo)函值相等。稱CBB-1為單純形乘子二、對(duì)偶問題的基本性質(zhì)二、對(duì)偶問題的基本性質(zhì) 對(duì)稱性 弱對(duì)偶性推論： 原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的下界；反之對(duì)偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。 如原

10、問題有可行解且目標(biāo)函數(shù)值無界，則其對(duì)偶問題無可行解；反之對(duì)偶問題有可行解且目標(biāo)函數(shù)值無界，則其原問題無可行解。(1)如原問題有可行解而對(duì)偶問題無可行解，則原問題目標(biāo)函數(shù)值無界；反之對(duì)偶問題有可行解而其原問題無可行解，則對(duì)偶問題的目標(biāo)函數(shù)值無界。二、對(duì)偶問題的基本性質(zhì)二、對(duì)偶問題的基本性質(zhì)(2)如原問題有可行解且目標(biāo)函數(shù)值無界，則其對(duì)偶問題無可行解；反之對(duì)偶問題有可行解且目標(biāo)函數(shù)值無界，則其原問題無可行解。(3)如原問題有可行解而對(duì)偶問題無可行解，則原問題目標(biāo)函數(shù)值無界；反之對(duì)偶問題有可行解而其原問題無可行解，則對(duì)偶問題的目標(biāo)函數(shù)值無界。(2)如原問題有可行解且目標(biāo)函數(shù)值無界，則其對(duì)偶問題無如原

11、問題有可行解且目標(biāo)函數(shù)值無界，則其對(duì)偶問題無可行解；可行解；反之對(duì)偶問題有可行解且目標(biāo)函數(shù)值無界，則反之對(duì)偶問題有可行解且目標(biāo)函數(shù)值無界，則其原問題無可行解。其原問題無可行解。(3)如原問題有可行解而對(duì)偶問題無可行解，則原問題目標(biāo)如原問題有可行解而對(duì)偶問題無可行解，則原問題目標(biāo)函數(shù)值無界；函數(shù)值無界；反之對(duì)偶問題有可行解而其原問題無可行反之對(duì)偶問題有可行解而其原問題無可行解，則對(duì)偶問題的目標(biāo)函數(shù)值無界。解，則對(duì)偶問題的目標(biāo)函數(shù)值無界。原問題有可行解，則原問題目標(biāo)函數(shù)原問題有可行解，則原問題目標(biāo)函數(shù)無界的無界的充要條件充要條件是對(duì)偶問題無可行解。是對(duì)偶問題無可行解。(2)如原問題有可行解且目標(biāo)函

12、數(shù)值無界，則其對(duì)偶問題無如原問題有可行解且目標(biāo)函數(shù)值無界，則其對(duì)偶問題無可行解；可行解；反之對(duì)偶問題有可行解且目標(biāo)函數(shù)值無界，則反之對(duì)偶問題有可行解且目標(biāo)函數(shù)值無界，則其原問題無可行解。其原問題無可行解。(3)如原問題有可行解而對(duì)偶問題無可行解，則原問題目標(biāo)如原問題有可行解而對(duì)偶問題無可行解，則原問題目標(biāo)函數(shù)值無界；函數(shù)值無界；反之對(duì)偶問題有可行解而其原問題無可行反之對(duì)偶問題有可行解而其原問題無可行解，則對(duì)偶問題的目標(biāo)函數(shù)值無界。解，則對(duì)偶問題的目標(biāo)函數(shù)值無界。對(duì)偶問題有可行解，則對(duì)偶問題目標(biāo)函對(duì)偶問題有可行解，則對(duì)偶問題目標(biāo)函數(shù)無界的數(shù)無界的充要條件充要條件是原問題無可行解。是原問題無可行解

13、。二、對(duì)偶問題的基本性質(zhì)二、對(duì)偶問題的基本性質(zhì)3. 最優(yōu)性4. 強(qiáng)對(duì)偶性5. 互補(bǔ)松馳性注: 上述針對(duì)對(duì)稱形式證明的對(duì)偶問題的性質(zhì), 同樣適用于非對(duì)稱形式的LP問題.二、對(duì)偶問題的基本性質(zhì)二、對(duì)偶問題的基本性質(zhì)6. 非對(duì)稱形式的LP問題的互補(bǔ)松馳性 設(shè) 為原問題的最優(yōu)解 為對(duì)偶問題的最優(yōu)解), 2 , 1(njxj), 2 , 1(miyi若 , 則有: 若 , 則有: 若 , 則有: 若 , 則有: 0iynjijijbxa1mijiijcya10jx0jxnjijijbxa1mijiijcya10iy2.4 對(duì)偶單純形法對(duì)偶單純形法12526.52415max5321432321yyyyy

14、yystyyyw解：將問題化為：12526.52415max5321432321yyyyyyystyyyw 列出滿足對(duì)偶問題為可行解滿足對(duì)偶問題為可行解的初始單純形表 若所有bi（i=1,2,m）均大于等于0,則單純形表中的解即為原問題的最優(yōu)解，否則轉(zhuǎn)下一步。 2. 確定換出基變量出基變量：br=minbi|bi0 xr為換出基變量為換出基變量 3. 確定換入基變量入基變量： xs為換入基變量為換入基變量 4. 用換入變量替換換出變量，得到一個(gè)新的基基，對(duì)這個(gè)基進(jìn)行初等行變換為單位陣，對(duì)新的基再檢查是否所有bi大于等于0，是，則得到原問題的最優(yōu)解，否則，轉(zhuǎn)第2步。rsssrjrjjjjazca

15、azc0|min一、對(duì)偶單純形法計(jì)算步驟0.maxxbAxstcxz例1：用對(duì)偶單純形法求解下列LP問題12526.52415min32132321yyyyystyyyw在確定換入、換出基變量時(shí)，必須保證對(duì)偶問題的解為可行解，即檢驗(yàn)數(shù)小于等于0，下面證明證明 的選取可以的選取可以保證對(duì)偶問題解的可行性。保證對(duì)偶問題解的可行性。)()()()(rsssrjjjrjssrsrjjjjjazcazcazcaazczc二、對(duì)偶單純形法的概念在對(duì)偶可行基的基礎(chǔ)上進(jìn)行的單純形法，稱為對(duì)偶單純形法。優(yōu)點(diǎn)：省去了引入人工變量的麻煩缺點(diǎn)：對(duì)偶問題的基可行解不易找到作用：靈敏度分析的工具使用前提：初始單純形表各中

16、檢驗(yàn)數(shù)非正練習(xí)：用對(duì)偶單純形法求解下述LP問題：)4 , 3 , 2 , 1(024232.34min43214321421ixxxxxxxxxstxxxwi-1-40-300 x1x2x3x4x5x60 x5-3-1-21-1100 x6-221-4-101-1-40-300-1x1312-11-100 x6-80-3-2-3210-2-1-2-10-1x1717/205/2-2-1/20 x3403/213/2-1-1/20-1/20-1/2-2-1/2jjj42134maxxxxw目標(biāo)函數(shù)變換為:3. 確定換入基入基變量： xs為換入基變量為換入基變量rsssrjrjjjjazcaazc

17、0|max注: 若LP問題的標(biāo)準(zhǔn)形式為:0.minxbAxstcxz其對(duì)偶單純形法的求解步驟確定換入基變量的原則如下:其它步驟同目標(biāo)函數(shù)為極大值情況其它步驟同目標(biāo)函數(shù)為極大值情況1524500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101152450024y21/3011/6-1/600y5-1/3-50-2/3 -1/3115014024y21/4-5/410-1/45y31/215/2011/2-3/215/2007/23/2jjj12526.52415min5321432321yyyyyyystyyyw例1:2.5 靈敏度分析靈敏度分析一、靈敏度分析的含義

18、指對(duì)系統(tǒng)或事務(wù)因周圍條件的變化顯示出來的敏感程度的分析。二、靈敏度分析的步驟1. 將參數(shù)（cj,aij,bi）的改變通過計(jì)算反映到最終單純形表最終單純形表中；2. 檢查原問題的解是否仍為可行的；3. 檢查對(duì)偶問題的解是否仍為可行的；4. 按下表所列情況得出結(jié)論或決定繼續(xù)計(jì)算的步驟。最優(yōu)解不變最優(yōu)解不變單純形法迭代單純形法迭代對(duì)偶單純形法迭代對(duì)偶單純形法迭代引入人工變量，重新迭代計(jì)算引入人工變量，重新迭代計(jì)算可行解非可行解可行解非可行解可行解可行解非可行解非可行解結(jié)論或繼續(xù)計(jì)算的步驟結(jié)論或繼續(xù)計(jì)算的步驟對(duì)偶問題對(duì)偶問題原問題原問題表 2-9三、分析cj的變化四、分析bi的變化五、增加一個(gè)變量xj

19、的分析六、分析aij的變化七、增加一個(gè)約束條件的分析三、分析cj的變化線性規(guī)劃目標(biāo)函數(shù)中變量系數(shù)cj的變化僅僅影響到檢驗(yàn)數(shù)，所以將cj的變化直接反映到最終單純形表中，只可能出現(xiàn)表2-9中的第一、二一、二兩種情況。例5：在美佳公司例子中，(1) 若家電的利潤降至1.5元/件, 而家電的利潤增至2元/件, 美佳公司最優(yōu)生產(chǎn)計(jì)劃有何變化?(2) 若家電的利潤不變, 而家電的利潤在什么范圍內(nèi)變化時(shí), 該公司的最優(yōu)生產(chǎn)計(jì)劃不發(fā)生變化。四、分析bi的變化右端項(xiàng) bi 的變化在實(shí)際問題中反映為可用資源數(shù)量的變化，bi的變化反映到最終單純形表中將引起b列數(shù)字變化，可能出現(xiàn)表2-9中的第一一、三三兩種情況。例6

20、：在美佳公司例子中，(1) 若設(shè)備A和調(diào)試工序的每天可用能力不變, 而設(shè)備B每天的可用能力增加到32h, 分析公司最優(yōu)計(jì)劃的變化。(2) 若設(shè)備A和設(shè)備B每天可用能力不變, 則調(diào)試工序可用能力在什么范圍內(nèi)變化時(shí), 問題的最優(yōu)基不變。五、增加一個(gè)變量xj的分析增加一個(gè)變量在實(shí)際問題中反映為增加一種新的產(chǎn)品，可能出現(xiàn)表2-9中的第一、二一、二兩種情況。 計(jì)算新增加變量在最終單純形表中的列變量； 計(jì)算新增加變量的檢驗(yàn)數(shù)； 若檢驗(yàn)數(shù)小于等于零，則只需將計(jì)算得到的列向量和檢驗(yàn)數(shù)寫入最終單純形表；若檢驗(yàn)數(shù)大于零，則按照單純形法繼續(xù)迭代計(jì)算。例7：在美佳公司例子中，設(shè)該公司又計(jì)劃推出新型號(hào)的家電，生產(chǎn)一件所

21、需設(shè)備進(jìn)制 A，B 及調(diào)試工序的時(shí)間分別為 3h, 4h, 2h，該產(chǎn)品的預(yù)期盈利為3元/件，試分析該種產(chǎn)品是否值得投產(chǎn), 該公司的最優(yōu)生產(chǎn)計(jì)劃有何變化。解：設(shè)該公司生產(chǎn)家電 x6件cj 2 1 0 0 0 CB 基 b x1 x2 x3 x4 x5 0 x3 15/2 2 x1 7/2 1 x2 3/2 0 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/23x6-7021 0 x3 51/4 2 x1 7/2 3 x6 3/4 0 7/2 1 3/8 -9/4 0 1 0 0 1/4 -1/2 0 0 1/2 0 -1/8

22、 3/4 1 0 -1/2 0 -1/8 -5/4 0jj六、分析aij的變化aij的變化使線性規(guī)劃的約束系統(tǒng)矩陣A發(fā)生變化。若變量xj在最終單純形表中為非基變量非基變量，其約束條件中系數(shù)aij的變化可參照增加一個(gè)變量的情況進(jìn)行處理。若變量在最終單純形表中為基變量基變量，則aij的變化將使B及 B-1發(fā)生變化。因此有可能引起原問題和對(duì)偶問題均為非可行解。 可能出現(xiàn)表2-9中的所有可能的情況。例8：在美佳公司例子中，若家電每件需設(shè)備A，B及調(diào)試工時(shí)變?yōu)?h、4h、1h，該產(chǎn)品的利潤變?yōu)?元/件，試重新確定該公司最優(yōu)生產(chǎn)計(jì)劃。解：先將生產(chǎn)工時(shí)變化后的新家電看作是一種新產(chǎn)品，生產(chǎn)量為 ，仿例7的步驟

23、直接計(jì)算檢驗(yàn)數(shù)和列向量，將其反映到最終單純形表。2xcj21000CB基bx1x2x3x4x5021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2cj-zj000-1/4-1/23/211/21/21/232x因x2已變換為 ，故用單純形算法將 替換出基變量中的x2，并在下一個(gè)表中不再保留x2 ，得下表。2x2xcj21000CB基bx1x2x3x4x5021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2cj-zj000-1/4-1/22x3/211/21/21/232x3cj23000CB基bx1

24、x2x3x4x5021x3x1x2-92301000110041/2-1/2-24-23cj-zj0001/2-52x2x3原問題與對(duì)偶問題均為非可行解，故先設(shè)法使原問題變?yōu)榭尚薪?。?行的約束可寫為：9244543xxx兩端同乘以-1，再加上人工變量x6得：92446543xxxx100-1/61/60-1/24-1/121/80010103/811/415/8x5x1x20210-1/3-5/2400cj-zj2x3-M+5/241/241/12-1/8cj23000CB基bx1x2x3x4x5-M21x6x1x2923010001-100-41/2-1/224-23cj-zj00-M1/2-4M-5+24M2x2x392446543xxxx0100-M6x七、增加一個(gè)約束條件的分析增加一個(gè)約束條件在實(shí)