對偶理論及靈敏度分析ppt課件

1、第三章 對偶實際及靈敏度分析3.1.1 線性規(guī)劃對偶問題3.1.2 對偶問題的根本性質(zhì)3.1.3 影子價錢3.1.4 對偶單純形法3.2.1 靈敏度問題及其圖解法3.2.2 靈敏度分析3.2.3 參數(shù)線性規(guī)劃n一、對偶問題的提出一、對偶問題的提出n二、原問題與對偶問題的數(shù)學(xué)模型二、原問題與對偶問題的數(shù)學(xué)模型n三、原問題與對偶問題的對應(yīng)關(guān)系三、原問題與對偶問題的對應(yīng)關(guān)系實例：某家電廠家利用現(xiàn)有資源消費兩種實例：某家電廠家利用現(xiàn)有資源消費兩種 產(chǎn)品，產(chǎn)品， 有關(guān)數(shù)據(jù)如下表：有關(guān)數(shù)據(jù)如下表： 設(shè)備設(shè)備A 設(shè)備設(shè)備B調(diào)試工序調(diào)試工序利潤元利潤元0612521115時時24時時 5時時產(chǎn)品產(chǎn)品產(chǎn)品產(chǎn)品D

2、一、對偶問題的提出一、對偶問題的提出如何安排消費，如何安排消費，使獲利最多？使獲利最多？廠廠家家設(shè)設(shè) 產(chǎn)量產(chǎn)量 產(chǎn)量產(chǎn)量1x2x 0, 5 2426 155 2max 212121221xxxxxxxs.t.xxz 設(shè)：設(shè)備設(shè)：設(shè)備A A 元時元時 設(shè)備設(shè)備B B 元時元時 調(diào)試工序調(diào)試工序 元時元時1y2y3y收收購購 付出的代價最小，付出的代價最小， 且對方能接受。且對方能接受。出讓代價應(yīng)不低于出讓代價應(yīng)不低于用同等數(shù)量的資源用同等數(shù)量的資源本人消費的利潤。本人消費的利潤。 設(shè)備設(shè)備A 設(shè)備設(shè)備B調(diào)試工序調(diào)試工序利潤元利潤元0612521115時時24時時 5時時Dn廠家能接受的條件：廠家

3、能接受的條件：n收買方的志愿：收買方的志愿：32152415minyyyw單位產(chǎn)品單位產(chǎn)品出租出租收入不低于收入不低于2 2元元單位產(chǎn)品單位產(chǎn)品出租出租收入不低于收入不低于1 1元元出讓代價應(yīng)不低于出讓代價應(yīng)不低于用同等數(shù)量的資源用同等數(shù)量的資源本人消費的利潤。本人消費的利潤。1252632132yyyyy廠廠家家0, 5 2426 155 2max212121221xxxxxxxs.t.xxz0,y 125 26.32132132yyyyyyyts32152415minyyyw對對偶偶問問題題原原問問題題收收購購廠廠家家一對對偶問題一對對偶問題0 min bAX 0X . .CXz max

4、YC s.t. YAYb wts),(21ccC 21xxX)(ijaA ),y,y(yY321321bbbb3 3個約束個約束2 2個變量個變量2 2個約束個約束 3 3個變量個變量原問題原問題對偶問題對偶問題普通規(guī)律 特點：特點： 1 2限定向量限定向量b 價值向量價值向量C 資源向量資源向量 3一個約束一個約束 一個變量。一個變量。 4 的的LP約束約束“ 的的 LP是是“ 的約束。的約束。 5變量都是非負限制。變量都是非負限制。 min max z maxzmin 其它方式其它方式的對偶的對偶? ?二、原問題與對偶問題的數(shù)學(xué)模型二、原問題與對偶問題的數(shù)學(xué)模型n1對稱方式的對偶對稱方式的

5、對偶n 當(dāng)原問題對偶問題只含有不等式約束當(dāng)原問題對偶問題只含有不等式約束時，稱為對稱方式的對偶。時，稱為對稱方式的對偶。0 min bAX 0X . .CXz max YC s.t. YAYb wts原問題原問題對偶問題對偶問題情形一：情形一：0Y CA . min0X bAX .maxYtsYbwtsCXz原問題原問題對偶問題對偶問題)(YY化為規(guī)范對稱型化為規(guī)范對稱型情形二：情形二：證明證明0Y CA .min0X bAX .maxYtsbYwtsCXz對偶對偶n2、 非對稱方式的對偶非對稱方式的對偶n 假設(shè)原問題的約束條件是等式，假設(shè)原問題的約束條件是等式，那么那么無約束min0maxY

6、CYAYbwXbAXCXz原問題原問題對偶問題對偶問題推導(dǎo)推導(dǎo): : 0 maxXbAXbAXCX z 0 max XbbXAACX z原問題原問題 根據(jù)對稱方式的對偶模型根據(jù)對稱方式的對偶模型,可直接寫出可直接寫出上述問題的對偶問題上述問題的對偶問題:-bb),Y(Yw21min0,0(2121Y YCAA),YY , YYC A)Y(Yb )Y(Yw00min 212121無約束YCYAYb w max令令 ，得對偶問題為：，得對偶問題為：21YYY證畢。證畢。三、原問題與對偶問題的對應(yīng)關(guān)系三、原問題與對偶問題的對應(yīng)關(guān)系 約束條件的限定向量目標函數(shù)的價值向量自由變量變量變量個變量約束約束約

7、束個約束目標函數(shù) 00 maxmn z原問題或?qū)ε紗栴}原問題或?qū)ε紗栴}對偶問題或原問題對偶問題或原問題目標函數(shù)的價值向量約束條件的限定向量約束約束約束個約束自由變量變量變量個變量目標函數(shù) 00minmn w zmax zminn例例:無約束,x x,xxxxxxxxxxs.txxxx z432143214321432101023428854235max對偶問題為對偶問題為無約束21,0428233402521212121yyyyyyyyyys.t.21108minyywn引例引例n對稱性對稱性n弱對偶性弱對偶性n最優(yōu)性最優(yōu)性n對偶性強對偶性對偶性強對偶性n互補松弛性互補松弛性0, 5 2426

8、 155 2max212121221xxxxxxxs.t.xxz0,y 125 26.32132132yyyyyyyts32152415minyyyw對對偶偶問問題題原原問問題題收收購購廠廠家家n引例引例 32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/15yyyyyxxxxxxxxjjzc 原問題原問題的變量的變量原問題松弛變量原問題松弛變量對偶問題對偶問題剩余變量剩余變量對偶問題的變量對偶問題的變量化為極小問題原問題化為極小問題，最終單純形表：原問題化為極小問題，最終單純形表：2154332543212/32/7002/1

9、52/32/1102/152/14/14/1014/54/1xxxxxyyyyyyyjjzc 原問題的變量原問題的變量原問題松弛變量原問題松弛變量對偶問題剩余變量對偶問題剩余變量對偶問題的變量對偶問題的變量對偶問題用兩階段法求解的最終的單純形表對偶問題用兩階段法求解的最終的單純形表 32154213543212/14/10002/34/10102/32/14/10012/72/154/51002/15yyyyyxxxxxxxxjjzc 原問題原問題的變量的變量原問題松弛變量原問題松弛變量對偶問題對偶問題剩余變量剩余變量對偶問題的變量對偶問題的變量化為極小問題化為極小問題原問題原問題最優(yōu)解最優(yōu)解

10、對偶問題對偶問題最優(yōu)解最優(yōu)解原問題化為極小問題，最終單純形表：原問題化為極小問題，最終單純形表：n兩個問題作一比較兩個問題作一比較: :n1.1.兩者的最優(yōu)值一樣兩者的最優(yōu)值一樣n2.2.變量的解在兩個單純形表中相互包含變量的解在兩個單純形表中相互包含n原問題最優(yōu)解決策變量原問題最優(yōu)解決策變量n對偶問題最優(yōu)解決策變量對偶問題最優(yōu)解決策變量14 wz2/3, 2/721xx 對偶問題的松弛變量2/ 1, 4/ 1, 0321yyy原問題的松弛變量原問題的松弛變量實際證明：實際證明：原問題與對偶問題解的關(guān)系原問題與對偶問題解的關(guān)系NoImage一、對稱定理：一、對稱定理： 定理：定理： 對偶問題的

11、對偶是原問題。對偶問題的對偶是原問題。設(shè)原問題設(shè)原問題1 1 對偶問題對偶問題2 20. .maxXbAXtsCXz0. .minYCYAtsYbw二、弱對偶性定理：二、弱對偶性定理： 假設(shè)假設(shè) 和和 分別是原問題分別是原問題1 1及對偶問題及對偶問題2 2的可行解，那么有的可行解，那么有 bYXAYXCXCXAYCAYbYXAYbXA證明：證明：YXbYXCn1 1極大化問題原問題的任一可行解所極大化問題原問題的任一可行解所對應(yīng)的目的函數(shù)值是對偶問題最優(yōu)目的函數(shù)值對應(yīng)的目的函數(shù)值是對偶問題最優(yōu)目的函數(shù)值的下界。的下界。n2 2極小化問題對偶問題的任一可行解極小化問題對偶問題的任一可行解所對應(yīng)

12、的目的函數(shù)值是原問題最優(yōu)目的函數(shù)值所對應(yīng)的目的函數(shù)值是原問題最優(yōu)目的函數(shù)值的上界。的上界。n3 3假設(shè)原問題可行，但其目的函數(shù)值無界，假設(shè)原問題可行，但其目的函數(shù)值無界，那么對偶問題無可行解。那么對偶問題無可行解。n4 4假設(shè)對偶問題可行，但其目的函數(shù)值無假設(shè)對偶問題可行，但其目的函數(shù)值無界，那么原問題無可行解。界，那么原問題無可行解。n5 5假設(shè)原問題有可行解而其對偶問題無可假設(shè)原問題有可行解而其對偶問題無可行解，那么原問標題的函數(shù)值無界。行解，那么原問標題的函數(shù)值無界。n6 6對偶問題有可行解而其原問題無可行解，對偶問題有可行解而其原問題無可行解，那么對偶問題的目的函數(shù)值無界。那么對偶問題

13、的目的函數(shù)值無界。原問題原問題對偶問題對偶問題bYXCbYCX三、最優(yōu)性定理：三、最優(yōu)性定理： 假設(shè)假設(shè) 和和 分別是分別是1 1和和2 2的的 可行解，且有可行解，且有 那么那么 分別分別是是1 1和和2 2的最優(yōu)解的最優(yōu)解 。 YXYXbYCX,那么那么 為為1 1的最優(yōu)解，的最優(yōu)解，反過來可知：反過來可知： 也是也是2 2的最優(yōu)解。的最優(yōu)解。XYbYCXbYXC,證明：由于證明：由于1的任一可行解的任一可行解 均滿足均滿足X證明：證明：原問題與對偶問題的解普通有三種情況：原問題與對偶問題的解普通有三種情況：一個有有限最優(yōu)解一個有有限最優(yōu)解 另一個有有限最優(yōu)另一個有有限最優(yōu)解。解。一個有無

14、界解一個有無界解 另一個無可行解。另一個無可行解。兩個均無可行解。兩個均無可行解。四、對偶定理強對偶性：四、對偶定理強對偶性： 假設(shè)原問題及其對偶問題均具有可行假設(shè)原問題及其對偶問題均具有可行解，那么兩者均具有最優(yōu)解，且它們最優(yōu)解的解，那么兩者均具有最優(yōu)解，且它們最優(yōu)解的目的函數(shù)值相等。目的函數(shù)值相等。YX,SSYX ,YXXYXYSS,0, 0為最優(yōu)解為最優(yōu)解00,0000)(01iiisiinjjijisiisiiSybXAxbxaXAxyxyXAbYXY原問題第原問題第i條約束條約束 A的第i行 闡明：在線性規(guī)劃問題的最優(yōu)解中，假設(shè)對應(yīng)某一約束條件的對偶變量值為非零，那么該約束條件去嚴厲

15、等式；反之假設(shè)約束條件取嚴厲不等式，那么其對應(yīng)的對偶變量一定為零。000 )(0)(0jjjjjjjjjSxcPYcPYxxcPYXCAYXY另一方面：另一方面：對偶問題的第對偶問題的第j條約束條約束在單純形法的每步迭代中，目的函數(shù)取值 ，和檢驗數(shù) 中都有乘子 ，那么Y的經(jīng)濟意義是什么？ bBCzB1NBCCBN11BCYBn 當(dāng)線性規(guī)劃原問題求得最優(yōu)解n時，其對偶問題也得到最優(yōu)解 n，且代入各自的目的函數(shù)后有：), 1(*njxj), 1(*miyi是線性規(guī)劃原問題約束條件的右端項，它代表第 種資源的擁有量；ibinjmiijwybxczij11*3 對偶變量 的意義代表在資源最優(yōu)利用條件下

16、對單位第 種資源的估價，這種估價不是資源的市場價錢，而是根據(jù)資源在消費中作出的奉獻而作的估價，為區(qū)別起見，稱為影子價錢shadow price)。*iyin1資源的市場價錢是知數(shù)，相對比較穩(wěn)定，而它的影子價錢那么有賴于資源的利用情況，是未知數(shù)。由于企業(yè)消費義務(wù)、產(chǎn)品構(gòu)造等情況發(fā)生變化，資源的影子價錢也隨之改動。市場價錢影子價錢市場企業(yè)n2影子價錢是一種邊沿價錢。n 在3式中， 。 n 闡明 的值相當(dāng)于在資源得到最優(yōu)利用的消費條件下， 每添加一個單位時目的函數(shù) 的增量。z*iybzi*iyib3，315/4，5/4,z=8.75242621 xx7/2，3/2，z=8.5252621xx3資源的

17、影子價錢實踐上又是一種時機本錢. 在純市場經(jīng)濟條件下,當(dāng)?shù)?種資源的市場價錢低于1/4時，可以買進這種資源；相反當(dāng)市場價錢高于影子價錢時，就會賣出這種資源。隨著資源的買進賣出，它的影子價錢也將隨之發(fā)生變化，不斷到影子價錢與市場價錢堅持同等程度時，才處于平衡形狀。n4在對偶問題的互補松弛性質(zhì)中有n n n 這闡明消費過程中假設(shè)某種資源 未得到充分利用時，該種資源的影子價錢為零；又當(dāng)資源的影子價錢不為零時，闡明該種資源在消費中已耗費終了。 ijijijijbxa;ybxanjiinj110y 0時，時，當(dāng)當(dāng)ibn5從影子價錢的含義上調(diào)查單純形表的n 檢驗數(shù)的經(jīng)濟意義。miijjjijjBaycPB

18、Cc114jc第j種產(chǎn)品的產(chǎn)值miijiay1消費第j中產(chǎn)品所耗費各項資源的影子價錢的總和。即隱含本錢可見，產(chǎn)品產(chǎn)值可見，產(chǎn)品產(chǎn)值隱含本錢隱含本錢 可消費該產(chǎn)品；可消費該產(chǎn)品；否那么，不安排消費。否那么，不安排消費。檢驗數(shù)的經(jīng)濟意義檢驗數(shù)的經(jīng)濟意義n6普通說對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解那么是確定對資源的恰當(dāng)估價，這種估價直接涉及到資源的最有效利用。經(jīng)濟學(xué)研討如何管理本人的稀缺資源n 對偶單純形法的根本思緒對偶單純形法的根本思緒n 對偶單純形法的計算步驟對偶單純形法的計算步驟0jjjzc01bBb對偶問題的可行解對偶問題的可行解對偶問題對偶問題最優(yōu)解判別最優(yōu)

19、解判別n線性規(guī)劃問題0maxXbAXCXz 無妨設(shè) 為對偶問題的初始可行基，那么 。),(21mPPPB0zcjj 假設(shè) ，即表中原問題和對偶問題均為最優(yōu)解，否那么換基。mibi, 2 , 1, 0確定換出基變量 對應(yīng)變量 為換出基的變量0miniiirbbbrx確定換入基變量 為主元素， 為換入基變量rsssrjrjjjjazcaazc0minrsasx初始可行基0,y 125 26.32132132yyyyyyyts32152415minyyyw0,y 125 26.5215321432yyyyyyyyyts32152415maxyyyw0,y 125- 26.5215321432yyyy

20、yyyyyts32152415maxyyyw對偶問題的初始可行基2/32/7002/152/32/1102/152/154/14/1014/54/12404101513/13/2053/1006/16/1103/124005241510125100116020005241532525454321yyyyyyyyyyybYCBBjcjjzc使對偶問題基變量可行,0,0, 1414a505406242y換出 換出42) 1, 2min(y換出換出2/32/7002/152/32/1102/152/154/14/1014/54/12404101513/13/2053/1006/16/1103/124

21、005241510125100116020005241532525454321yyyyyyyyyyybYCBBjjzcjjzc2/32/7002/152/32/1102/152/154/14/1014/54/12404101513/13/2053/1006/16/1103/124005241510125100116020005241532525454321yyyyyyyyyyybYCBBjjzcjjzcjjzc最優(yōu)解最優(yōu)解運用。運用。練習(xí)n用對偶單純形法求解線性規(guī)劃問題：用對偶單純形法求解線性規(guī)劃問題：3 ,2, 1,043232.432min321321321ixxxxxxxtsxxxwi3

22、.2.1 靈敏度問題及其圖解法靈敏度問題及其圖解法靈敏度問題靈敏度問題靈敏度分析靈敏度分析圖解法圖解法 靈敏度問題n背景：n 線性規(guī)劃問題中， 都是常數(shù)，但這些系數(shù)是估計值和預(yù)測值。n 市場的變化 值變化；n 工藝的變化 值變化；n 資源的變化 值變化。jiijcba,jcibijan問題：n當(dāng)這些系數(shù)中的一個或多個發(fā)生變化時，原最優(yōu)解會怎樣變化？n當(dāng)這些系數(shù)在什么范圍內(nèi)變化時，原最優(yōu)解仍堅持不變？n假設(shè)最優(yōu)解發(fā)生變化，如何用最簡單的方法找到現(xiàn)行的最優(yōu)解？n研討內(nèi)容：n 研討線性規(guī)劃中， 的變化對最優(yōu)解的影響。jiijcba,l研討方法：研討方法：l圖解法圖解法l對偶實際分析對偶實際分析僅適用

23、于含僅適用于含2個變量個變量的線性規(guī)劃問題的線性規(guī)劃問題在單純形表中在單純形表中進展分析進展分析線性規(guī)劃模型線性規(guī)劃模型x218 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)4x1+ 6x2=48 2x1+ 2x2 =1818 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE目的函數(shù)的系數(shù)目的函數(shù)的系數(shù)34x1 + 40 x2 = Z40 x2 =

24、- 34x1 + Zx2 = -+34x1Z404018 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE目的函數(shù)的系數(shù)目的函數(shù)的系數(shù)34x1 + 40 x2 = Z40 x2 =- 34x1 + Zx2 = -+c1x1Zc2c218 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE目的函數(shù)的系數(shù)目的函數(shù)的系數(shù)34x1 + 40 x2 = Z40 x2 =- 34x1 + Z

25、x2 = -+c1x1Zc2c218 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE(斜率斜率 = - 1)( (斜率斜率 = - 2/3) = - 2/3)最優(yōu)解不變的范圍最優(yōu)解不變的范圍設(shè)設(shè)c1固定固定c2可變可變51343234122cc3.2.1 靈敏度問題及其圖解法靈敏度問題及其圖解法 3.2.2 靈敏度分析v 一、分析一、分析 的變化的變化v 二、分析二、分析 的變化的變化v 三、添加一個變量三、添加一個變量 的分析的分析v 四、添加一個約束條件的分析四、添加一個約束條件

26、的分析v 五、分析五、分析 的變化的變化jcibjxijan研討內(nèi)容：n 研討線性規(guī)劃中， 的變化對最優(yōu)解的影響。jiijcba,jjjBjjPYcPBCcPBPPBPbBbbBb11111,l常用公式：常用公式：實例： 某家電廠家利用現(xiàn)有資源消費兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下表： 設(shè)備設(shè)備A 設(shè)備設(shè)備B調(diào)試工序調(diào)試工序利潤元利潤元0612521115時時24時時 5時時D如何安排消費，如何安排消費，使獲利最多？使獲利最多？廠廠家家設(shè)設(shè) 產(chǎn)量產(chǎn)量 產(chǎn)量產(chǎn)量1x2x0, 5 2426 155 2max 212121221xxxxxxxs.t.xxz32154213543212/14/10002/34/1

27、0102/32/14/10012/72/154/51002/1500012yyyyyxxxxxxxxjjzc 原問題最優(yōu)解對偶問題最優(yōu)解相差負號一、分析 的變化n 的變化僅影響 的變化。jcjcjjjzc 設(shè)備設(shè)備A 設(shè)備設(shè)備B調(diào)試工序調(diào)試工序利潤元利潤元0612521115時時24時時 5時時D1.52問題1：當(dāng) 該公司最優(yōu)生 產(chǎn)方案有何變化？2, 5 . 121cc最終單純形表4/98/10002/34/10102/322/14/10012/75 . 12/154/51002/15000025 . 121354321xxxxxxxxbXCBBjcjjzc 05/41.5 1/4+ 2 -1

28、/4-1/80-1/8=jjBjjBjjPYcPCcPBCc 1最終單純形表4/98/10002/34/10102/322/14/10012/75 . 12/154/51002/15000025 . 121354321xxxxxxxxbXCBBjcjjzc 換基后單純形表為2/3010/100005/11032105/10125 . 1615/4006000025 . 121454321xxxxxxxxbXCBBjcjjzc 最優(yōu)解 問題2：設(shè)產(chǎn)品II利潤為 ， 求原最優(yōu)解不變時 的范圍。)1 ( 的變化僅影響的變化僅影響 的變化；的變化；在最后一張單純形表中求出變化在最后一張單純形表中求出變

29、化的的 ；原最優(yōu)解不變，即原最優(yōu)解不變，即 ；由上述不等式可求出由上述不等式可求出 的范圍。的范圍。2cjj0j方法：方法：232141410002/34/ 10102/312/ 14/ 10012/722/154/51002/1500001221354321xxxxxxxxbXCBBjcjjzc 13102321, 04141即即產(chǎn)品產(chǎn)品II利潤為利潤為 時的最終單純形表時的最終單純形表)1 (二、分析 的變化ib 的變化僅影響 ，即原最優(yōu)解的可行性能夠會變化：可行性不變，那么原最優(yōu)解不變?？尚行圆蛔?，那么原最優(yōu)解不變。可行性改動，那么原最優(yōu)解改動，可行性改動，那么原最優(yōu)解改動，用對偶單純形

30、法，找出最優(yōu)解。用對偶單純形法，找出最優(yōu)解。ibib問題3：設(shè)備B的才干添加到32小時， 原最優(yōu)方案有何變化？2/12/112/35532152/34/102/14/102/154/511bBb2/14/10002/34/10102/112/14/10012/1122/154/51002/3500001221354321xxxxxxxxbXCBBjcjjzc 代入單純形表中代入單純形表中主元主元2001061040201001152001501500001241354321xxxxxxxxbXCBBjcjjzc 新的最優(yōu)解新的最優(yōu)解換基迭代得：換基迭代得：問題4：設(shè)調(diào)試工序可用時間為 小時，求

31、 ，原最優(yōu)解堅持不變。)5(?2/3)1 (2/ )7(2/15)1 (524152/34/ 102/ 14/ 102/154/511bBb11,0b原最優(yōu)解堅持不變，那么原最優(yōu)解堅持不變，那么三、添加一個變量 的分析 添加一個變量相當(dāng)于添加一種產(chǎn)品。分析步驟：1、計算2、計算3、假設(shè) ，原最優(yōu)解不變； 假設(shè) ，那么按單純形表繼續(xù)迭代 計算找出最優(yōu)解。jxjjjjjPYczcjjPBP10j0j問題5：設(shè)消費第三種產(chǎn)品，產(chǎn)量為 件， 對應(yīng)的 求最優(yōu)消費方案。6xTPc)2 , 4 , 3(, 3661)2 , 4 , 3()2/1 , 4/1 , 0(36T2072432/34/102/14/

32、102/154/516P解：解：代入最終原單純形表中2/ 14/ 10002/34/ 10102/312/ 14/ 10012/722/154/51002/1500001221354321xxxxxxxxbXCBBjcjjzc 120736x主元主元換基后有：4/58/ 102/ 104/38/ 102/ 104/332/ 14/ 10012/724/98/312/704/300001261354321xxxxxxxxbXCBBjcjjzc 010036x四、添加一個約束條件的分析 添加一個約束條件相當(dāng)于增添一道工序。分析方法：分析方法：將最優(yōu)解代入新的約束中將最優(yōu)解代入新的約束中1假設(shè)滿足要

33、求，那么原最優(yōu)解不變；假設(shè)滿足要求，那么原最優(yōu)解不變；2假設(shè)不滿足要求，那么原最優(yōu)解改動，假設(shè)不滿足要求，那么原最優(yōu)解改動，將新增的約束條件添入最終的將新增的約束條件添入最終的單純形表中繼續(xù)分析。單純形表中繼續(xù)分析。五、分析 的變化ija假設(shè)假設(shè) 對應(yīng)的對應(yīng)的 變量變量 為基變量，為基變量，B將改動。需引入人工變量求出將改動。需引入人工變量求出可行解，再用單純形法求解。可行解，再用單純形法求解。ijajxijajx假設(shè) 對應(yīng)的變量 為非基變量，參見三的分析。靈敏度分析的步驟歸納如下：1將參數(shù)的改動計算反映到最終 單純形表上；2檢查原問題能否仍為可行解；3檢查對偶問題能否仍為可行解；4按下表所列

34、情況得出結(jié)論和決 定繼續(xù)計算的步驟。原問題原問題 對偶問題對偶問題 結(jié)論或繼續(xù)計算的步驟結(jié)論或繼續(xù)計算的步驟可行解可行解 可行解可行解 問題的最優(yōu)解或最優(yōu)基不變問題的最優(yōu)解或最優(yōu)基不變可行解可行解 非可行解非可行解 用單純形法繼續(xù)迭代用單純形法繼續(xù)迭代非可行解非可行解 可行解可行解 用對偶單純形法繼續(xù)迭代用對偶單純形法繼續(xù)迭代非可行解非可行解 非可行解非可行解 編制新的單純形表重新計算編制新的單純形表重新計算總之練習(xí)： 某廠方案消費甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品單位利潤及消費產(chǎn)品所需資料、勞動力如下表：單位產(chǎn)品單位產(chǎn)品 甲甲 乙乙 丙丙 可運用資源量可運用資源量 勞動力勞動力 1/3 1/3

35、1/3 1 資料資料 1/3 4/3 7/3 3利潤元利潤元 2 3 1 1確定最優(yōu)的消費方案；2當(dāng) 增大至多少時，丙產(chǎn)品安排消費；3添加3個勞動力，最優(yōu)解能否改動？4勞動力在哪個范圍內(nèi)變化，對利潤值 的改動有利；5添加新的產(chǎn)品丁，需1個勞動力，1個 單位原料，利潤3元。確定最優(yōu)的消費方案。6添加新約束： 最優(yōu)解能否改動？3c102321xxx42321xxx解：初始及最終單純形表為00132103/13/43/130013/13/13/110001325454321xxxxxxxbXCBB1530011210231410112001322154321xxxxxxxbXCBB3.2.2 3.2

36、.2 靈敏度分析靈敏度分析 3.2.3 參數(shù)線性規(guī)劃目的函數(shù)的系數(shù)含有參數(shù) 的線性規(guī)劃問題約束條件右端的常數(shù)項含有約束條件右端的常數(shù)項含有參數(shù)的線性規(guī)劃問題參數(shù)的線性規(guī)劃問題參數(shù)線性規(guī)劃概念 當(dāng)參數(shù)當(dāng)參數(shù) 或或 沿某一方向延沿某一方向延續(xù)變動時，目的函數(shù)值續(xù)變動時，目的函數(shù)值z將隨將隨 或或 的變動而呈線性變動，的變動而呈線性變動，z是這個是這個變動參數(shù)的線性函數(shù)，因此稱為參變動參數(shù)的線性函數(shù)，因此稱為參數(shù)線性規(guī)劃。數(shù)線性規(guī)劃。jcibjcib模型目的函數(shù)的系數(shù)含有參數(shù)的線性規(guī)劃模型約束條件右端的常數(shù)項含有參數(shù)的約束條件右端的常數(shù)項含有參數(shù)的LP模型模型0)()(maxXbAXXCCz0)(m

37、axXbbAXCXzCC：價值向量：變動向量：參數(shù) ：資源向量 ：變動向量 ：參數(shù) bb參數(shù)線性規(guī)劃問題的分析步驟：1令 求解得最終單純形表；2將 或 項反映到最終單純形表中去；3隨 值的增大或減小，察看原問題或?qū)ε?問題。4反復(fù)第3步，不斷到 值繼續(xù)增大或減小 時，表中的解基不再出現(xiàn)變化時為止。確定現(xiàn)有解基允許的確定現(xiàn)有解基允許的 的變動范圍；的變動范圍；當(dāng)當(dāng) 的變動超出這個范圍時，用單純的變動超出這個范圍時，用單純形法或?qū)ε紗渭冃畏ㄇ笮碌慕狻Ｐ畏ɑ驅(qū)ε紗渭冃畏ㄇ笮碌慕狻?Cb舉例分析目的函數(shù)的系數(shù) 含有參數(shù)的線性規(guī)劃問題 分析 值變化時，下述參數(shù)線性規(guī)劃問題最優(yōu)解的變化。0,5242615

38、5)21 ()2()(max212121221xxxxxxxxxz 先令先令 求得最優(yōu)求得最優(yōu) 解，然后解，然后將將 反映在最終單純形表中，見下表：反映在最終單純形表中，見下表：0C25214140002/ 34/ 10102/ 3212/ 14/ 10012/722/154/51002/15000021221354321xxxxxxxxbXCBBjcjjzc 最優(yōu)解堅持不變的條件213217151z25214140002/ 34/ 10102/ 3212/ 14/ 10012/722/154/51002/15000021221354321xxxxxxxxbXCBBjcjjzc 當(dāng)當(dāng) 時時1檢驗數(shù)檢驗數(shù)非負非負20515100005/ 110321105/ 10122615/4006000021221454321xxxxxxxxbXCB