第六章單純形法的靈敏度分析與對(duì)偶

1、管理運(yùn)籌學(xué)管理運(yùn)籌學(xué)第六章第六章 單純形法的靈敏度分析與對(duì)偶單純形法的靈敏度分析與對(duì)偶單純形表的靈敏度分析單純形表的靈敏度分析線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶單純形法種特殊情況對(duì)偶單純形法種特殊情況本章內(nèi)容本章內(nèi)容1234單純形表的靈敏度分析單純形表的靈敏度分析本章內(nèi)容本章內(nèi)容1線性規(guī)劃的對(duì)偶問題線性規(guī)劃的對(duì)偶問題對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶單純形法種特殊情況對(duì)偶單純形法種特殊情況234 1單純形表的靈敏度分析單純形表的靈敏度分析一、目標(biāo)函數(shù)中變量系數(shù)一、目標(biāo)函數(shù)中變量系數(shù) ck 靈敏度分析靈敏度分析1、在最終的單純形表里，xk是非基變量

2、非基變量由于進(jìn)行行初等變換，約束方程增廣矩陣不變基變量系數(shù)cB不變zj都不變，包括zkjBjzcpkkkccckkc 0kkc kkkkkkkkczcczc kkkccc 若要原來的最優(yōu)解不變 1單純形表的靈敏度分析單純形表的靈敏度分析2在最終的單純形表中，xk 是基變量基變量由于進(jìn)行行初等變換，約束方程增廣矩陣不變基變量系數(shù)cB變化變化對(duì)所有的對(duì)所有的zj都都變化變化，包括zkjBjzcp假設(shè)cB=(cB1, cB2, ck ,cBm) (cB1, cB2, ck+ ck ,cBm)6 1 原最優(yōu)單純形表可表示如下。單純形表的靈敏度分析單純形表的靈敏度分析迭代迭代次數(shù)次數(shù) 基變基變量量cBx

3、kxjb比值bi/aijckcjxB1cB1ak1aj1xB2cB2ak2aj2xkckakkajkxBmcBmakmajmzsckzjs=cs-zs0j+kc+jkkac -jkkac 1單純形表的靈敏度分析單純形表的靈敏度分析 cB=(cB1, cB2, ck ,cBm) (cB1, cB2, ck+ ck ,cBm)1122() = jBjBjkkkjBmmjjkkjzcacaccacazc a () =jjjjjkkjjkkjczczc ac a由于j = cj zj 1單純形表的靈敏度分析單純形表的靈敏度分析 0 0 0 jkjkkjjjkjkkjacaaca 當(dāng)jk時(shí)，當(dāng)j=k時(shí)，

4、0, 1 = 0 =kkkkxkkkkkakkkkkkcczcczc a 為基變量max0 min0jjkjkkjkjkjacaaa =jjkkjc a若要最優(yōu)解不變 1單純形表的靈敏度分析單純形表的靈敏度分析 例 用單純形表求解下列線性規(guī)劃問題（第二章例1） 目標(biāo)函數(shù)： max z = 50 x1 + 100 x2 約束條件： x1 + x2 300, 2x1 + x2 400, x2 250, x1 , x2 0. 最優(yōu)單純表如下表：迭代迭代次數(shù)次數(shù)基變基變量量cBx1x2s1s2s3b比值比值50100000bi/aij2x1501010-150s2000-21150 x21000100

5、1250zj501005005027500j=cj-zj00-500-50 1單純形表的靈敏度分析單純形表的靈敏度分析迭代迭代次數(shù)次數(shù)基變基變量量cBx1x2s1s2s3b比值比值50100000bi/aij2x1501010-150s2000-21150 x210001001250zj501005005027500j=cj-zj00-500-50 先對(duì)非基變量 s1的目標(biāo)函數(shù)的系數(shù) c3 進(jìn)行靈敏度分析。 這里3 = 50，所以當(dāng) c3 的增量 c3 50 時(shí)，c3 50時(shí)，最優(yōu)解不變。 3c3c 1單純形表的靈敏度分析單純形表的靈敏度分析當(dāng)當(dāng)50 c150 ，即在，即在 0 c1100 時(shí)

6、最優(yōu)解不變。時(shí)最優(yōu)解不變。 迭代迭代次數(shù)次數(shù)基變基變量量cBx1x2s1s2s3b比值比值50100000bi/aij2x1501010-150s2000-21150 x210001001250zj501005005027500j=cj-zj00-500-50再對(duì)基變量x1的目標(biāo)函數(shù)系數(shù) c1進(jìn)行靈敏度分析1c1c0j0150c0150c1c1c1c 1單純形表的靈敏度分析單純形表的靈敏度分析2、從30，得 c1 0，即 c101、用c1代替原來的c1=50迭代迭代次數(shù)次數(shù)基變量基變量cBx1x2s1s2s3b比值比值100000bi/aij2x11010-150s2000-21150 x21

7、0001001250zj100027500j=cj-zj000-c1c1c1c1c1-c1+100c1-10050505050-5050-503、從50，得 c1 1000c1100,若c1超出取值范圍，必存在檢驗(yàn)數(shù)0，可通過迭代來得到新的最優(yōu)解。 1單純形表的靈敏度分析單純形表的靈敏度分析 當(dāng)ckk，即ckzk時(shí)，xk 變?yōu)槿牖兞俊Ｓ?c3 50 ，最優(yōu)解不變。kkkxkccc 為非基變量 剩余單位臺(tái)時(shí)數(shù)設(shè)備：從不獲利到獲利50元時(shí)從而設(shè)備臺(tái)時(shí)數(shù)的對(duì)偶價(jià)格為z3=50元。同樣可知原料A的對(duì)偶價(jià)格為z4=0元，原料B的對(duì)偶價(jià)格為 z5=50 元。 c3 ： 0 50 若有人出50元買1個(gè)設(shè)備

8、臺(tái)時(shí)，廠家則不必為生產(chǎn)、產(chǎn)品而使用完所有的設(shè)備臺(tái)時(shí)。 1單純形表的靈敏度分析單純形表的靈敏度分析由最終單純形表對(duì)于不同約束類型的對(duì)偶價(jià)格的取值如下表： 從對(duì)偶價(jià)格的定義可知，當(dāng)對(duì)偶價(jià)格為正，將改進(jìn)目標(biāo)函數(shù)值，從對(duì)偶價(jià)格的定義可知，當(dāng)對(duì)偶價(jià)格為正，將改進(jìn)目標(biāo)函數(shù)值，當(dāng)對(duì)偶價(jià)格為負(fù)，將當(dāng)對(duì)偶價(jià)格為負(fù)，將“惡化惡化”目標(biāo)函數(shù)值。目標(biāo)函數(shù)值。約束類型約束類型對(duì)偶價(jià)格的取值對(duì)偶價(jià)格的取值等于該約束條件對(duì)應(yīng)的松弛變量的zj值等于該約束條件對(duì)應(yīng)的剩余變量zj的相反數(shù)-zj=等于該約束條件對(duì)應(yīng)的人工變量的zj值 1單純形表的靈敏度分析單純形表的靈敏度分析 在求目標(biāo)函數(shù)最大值最大值的線性規(guī)劃中，對(duì)偶價(jià)格等于等于

9、影子價(jià)格；求目標(biāo)函數(shù)最小值時(shí)最小值時(shí)，影子價(jià)格為對(duì)偶價(jià)格的相反數(shù)相反數(shù)。約束類型約束類型影子價(jià)格的取值影子價(jià)格的取值求目標(biāo)函數(shù)最大值求目標(biāo)函數(shù)最大值求目標(biāo)函數(shù)最小值求目標(biāo)函數(shù)最小值等于該約束條件對(duì)應(yīng)的松弛變量的zj值等于該約束條件對(duì)應(yīng)的松弛變量zj的相反數(shù)-zj等于該約束條件對(duì)應(yīng)的剩余變量zj的相反數(shù)-zj等于該約束條件對(duì)應(yīng)的剩余變量的zj值=等于該約束條件對(duì)應(yīng)的人工變量的zj值等于該約束條件對(duì)應(yīng)的人工變量zj的相反數(shù)-zj 1單純形表的靈敏度分析單純形表的靈敏度分析 求使所得新的解仍可行（0）的bj的變化范圍，即使其新的最優(yōu)解的基變量（最優(yōu)基）都不變，且其對(duì)偶價(jià)格不變的。 二、約束方程中常數(shù)

10、項(xiàng)的靈敏度分析二、約束方程中常數(shù)項(xiàng)的靈敏度分析kkkbbb由于進(jìn)行行初等變換，最終單純形表系數(shù)矩陣不變基變量系數(shù)cB不變zj 都不變jBjzcpj都不變，基變量都不變 1單純形表的靈敏度分析單純形表的靈敏度分析原始的約束方程組：Axb迭代，對(duì)原系數(shù)矩陣進(jìn)行初等行變換，變成以B為基的最終單純形表，即對(duì)原來約束方程組左乘B-1:11B AxB b原始的最終單純形表中系數(shù)矩陣：1B A原始的最終單純形表中基變量xB的解為：1B b 1單純形表的靈敏度分析單純形表的靈敏度分析 kkkbbb 1200 00kkmbbbbbbbbb 原始的最終單純形表中基變量xB變?yōu)閤B：11() = BkBkBkkxB

11、bbxBbxDb 其中Dk為B-1的第k列，12 =kkkmkddDd 1單純形表的靈敏度分析單純形表的靈敏度分析11112222 =0BkBkBkBkkBBmmkBmmkxdxb dxdxb dbxxdxb d 使得對(duì)應(yīng)約束條件 的對(duì)偶價(jià)格不變?yōu)槭剐碌幕窘鈞B的各分量均非負(fù)即： max0min0BiBiikkikikikxxdbddd 1單純形表的靈敏度分析單純形表的靈敏度分析以第二章例1在最終單純形表上對(duì)進(jìn)行b1靈敏度分析：迭代迭代次數(shù)次數(shù)基變基變量量cBx1x2s1s2s3b比值比值50100000bi/aij2x1501010-150s2000-21150 x210001001250

12、zj501005005027500j=cj-zj00-500-50在第一個(gè)約束方程中含有松弛變量s1,其對(duì)應(yīng)的列為(1,-2,0)T,xB為(50,50,250)T,由 ，得到 時(shí)第1個(gè)約束條件的對(duì)偶價(jià)格不變。 max0min0BiBiikkikikikxxdbddd 15025, b 11250325bb 實(shí)際意義：當(dāng)設(shè)備臺(tái)時(shí)數(shù)在250與325之間變化時(shí)，該約束條件即設(shè)備臺(tái)時(shí)數(shù)的對(duì)偶價(jià)格不變，都為每設(shè)備臺(tái)時(shí)50元。 1單純形表的靈敏度分析單純形表的靈敏度分析三、三、約束方程系數(shù)矩陣約束方程系數(shù)矩陣 A 靈敏度分析靈敏度分析1最終單純形表上xk是非基變量非基變量 xk的初始單純形表的系數(shù)列 k

13、kpp 迭代 xk的系數(shù)列、zk以及k變化，其他均不變最終單純形表中新的系數(shù)列 : zk : k : -1kpB-1BkcpB-1kBkccpB若k0，則原最優(yōu)解仍然為最優(yōu)解。若k0，則繼續(xù)進(jìn)行迭代以求出最優(yōu)。 1單純形表的靈敏度分析單純形表的靈敏度分析 例 1以第二章例1為基礎(chǔ)，該廠除生產(chǎn)，種產(chǎn)品外，現(xiàn)試制新產(chǎn)品，已知生產(chǎn)產(chǎn)品，每件需要設(shè)備2臺(tái)時(shí)，A原料0.5公斤,B原料1.5公斤，獲利 150元，問該廠是否該生產(chǎn)該產(chǎn)品、生產(chǎn)多少？ 分析：這是一個(gè)增加新變量的問題，可以認(rèn)為是改變x3 在初始表上的系數(shù)列的問題。 1單純形表的靈敏度分析單純形表的靈敏度分析迭代迭代次數(shù)次數(shù)基變基變量量cBx1x

14、2s1s2s3501000002x1501010-1s2000-211x210001001zj5010050050j=cj-zj00-500-50b比值比值bi/aij505025027500 x315020.51.5175-251、首先，在最終單純形表中直接插入新的列2、在最終單純形表中找到B-1，求出B-1p6,替換該列系數(shù)1500.5-21.53、求出該列zj,j新變量的6 0不為0 且由互補(bǔ)松弛定理有x1 = x3 =0從而原問題的兩個(gè)約束不等式應(yīng)該取“=”1234123412341234 max 22. . 23420 4 3220 ,0zxxxxstxxxxxxxxx x x x1

15、234123412341234 max 22. . 23420 4 3220 ,0zxxxxstxxxxxxxxx x x x將 x1 = x3 =0 帶入此時(shí)原問題的約束條件 3對(duì)偶規(guī)劃的基本性質(zhì)x1 = x3 =01234123412341234 max 22. . 23420 4 3220 ,0zxxxxstxxxxxxxxx x x x242424203 20 xxxx解得，2, 642xx可知可知 滿足原問題約束條件，從而滿足原問題約束條件，從而其為原問題的最優(yōu)解，對(duì)應(yīng)的目標(biāo)函數(shù)最大值為其為原問題的最優(yōu)解，對(duì)應(yīng)的目標(biāo)函數(shù)最大值為14142, 0, 6, 04321xxxx對(duì)偶規(guī)劃的基

16、本性質(zhì)對(duì)偶單純形法本章內(nèi)容本章內(nèi)容1234單純形表的靈敏度分析線性規(guī)劃的對(duì)偶問題 4對(duì)偶單純形法 對(duì)偶單純形法也是解決線性規(guī)劃問題的一種方法。 對(duì)偶單純形法是在保持保持原問題所有所有i 0的情況下，通過迭代，使所有約束條件常數(shù)所有約束條件常數(shù)bj 0，最后求得最優(yōu)解。 簡(jiǎn)化計(jì)算簡(jiǎn)化計(jì)算是對(duì)偶單純形法的優(yōu)點(diǎn)，但其使用上有局限性，主要是大多線性規(guī)劃問題很難找到初始解使其所有檢驗(yàn)數(shù)均i 0。 4對(duì)偶單純形法 在靈敏度分析中，有時(shí)需要對(duì)偶單純形法，可簡(jiǎn)化計(jì)算。解：求出在第2次迭代表上的常數(shù)列，帶入第2次迭代表， 以第二節(jié)例1為例。已知當(dāng)250b1325時(shí)第1個(gè)約束條件的對(duì)偶價(jià)格不變，現(xiàn)在b1=300變

17、成b1=350，問此時(shí)第1個(gè)約束方程的對(duì)偶價(jià)格為多少？11115050100502 502502500=bbbbXXBbb 4對(duì)偶單純形法迭代迭代次數(shù)次數(shù)基變基變量量cBx1x2s1s2s3b比值比值50100000bi/aij2x1501010-1100s2000-211-50 x210001001250zj501005005027500j=cj-zj00-500-50 1、確定出基變量確定出基變量：在常數(shù)列中找一個(gè)最小的負(fù)常量，把該常量所在行的基變量為出基變量。2、確定入基變量確定入基變量：檢查出基變量xk所在行的各系數(shù)akj(j=1,2,.,n)，若所有akj均0，則無可行解；若有akj0，