第3章 對偶理論及靈敏度分析

1、第 3 3 章線性規(guī)劃的對偶理論及靈敏度分析 BY 蔡連僑蔡連僑北京外國語大學(xué)國際商學(xué)院北京外國語大學(xué)國際商學(xué)院北京外國語大學(xué)國際商學(xué)院蔡連僑3-2如果企業(yè)考慮把設(shè)備等資源出租，應(yīng)該如何定租金，才能保證出租是合算的增加資金投入，應(yīng)該如何進行合理分配在目前的生產(chǎn)計劃情況下，如果產(chǎn)品價格發(fā)生變化，對生產(chǎn)計劃是否有影響，采用新工藝對生產(chǎn)計劃又有什么影響為了增加產(chǎn)量，需要再購買原材料，多高的價格是可以接受的（即采購后可增加產(chǎn)量，也能增加利潤）采購原材料后對生產(chǎn)計劃有什么影響北京外國語大學(xué)國際商學(xué)院蔡連僑3-3線性規(guī)劃的對偶問題(Dual Problem)線性規(guī)劃的對偶單純形法(Dual Simplex

2、 Method)線性規(guī)劃的靈敏度分析(Sensitivity Analysis)參數(shù)線性規(guī)劃(Parametric Linear Programming)北京外國語大學(xué)國際商學(xué)院蔡連僑3-4對偶問題的提出對偶問題的形式對偶問題的基本性質(zhì)影子價格北京外國語大學(xué)國際商學(xué)院蔡連僑3-5 例1（同第2章例1）：某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示： 問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤？產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤（元/件）15002500

3、北京外國語大學(xué)國際商學(xué)院蔡連僑3-6 可以建立如下的線性規(guī)劃模型： 目標(biāo)函數(shù) Max z =1500 x1+2500 x2 約束條件 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1, x2 0 化為標(biāo)準(zhǔn)型，利用單純形法進行求解，得到最優(yōu)解X=(5, 25, 0, 5, 0)T，最優(yōu)值（利潤）為70000。北京外國語大學(xué)國際商學(xué)院蔡連僑3-7最優(yōu)解 x1 = 5 x2 = 25 x4 = 5（松弛標(biāo)量，表示B設(shè)備有5個機時的剩余）， 最優(yōu)值 z* = 70000 北京外國語大學(xué)國際商學(xué)院蔡連僑3-8 現(xiàn)在從另一個角度來討論該問題：如果工廠考慮不安排生產(chǎn)，而準(zhǔn)備把所

4、有設(shè)備出租（或用于外協(xié)加工），工廠收取租金（或加工費）。試問：設(shè)備 A、B、C 每工時各如何收費（租金或加工費）才最有競爭力？ 工廠為了獲得最大利潤，在為設(shè)備定價時，應(yīng)保證生產(chǎn)某產(chǎn)品的設(shè)備工時所收取的費用不低于生產(chǎn)該產(chǎn)品的利潤；同時，為了提高競爭力，應(yīng)該使定價盡可能低北京外國語大學(xué)國際商學(xué)院蔡連僑3-9 設(shè) y1 ，y2 ，y3 分別為每工時設(shè)備 A、B、C 的收費?？梢越⒁韵戮€性規(guī)劃模型： Min f = 65 y1 + 40 y2 + 75 y3 s.t. 3 y1 + 2 y2 1500 （不少于甲產(chǎn)品的利潤） 2 y1 + y2 + 3 y3 2500 （不少于乙產(chǎn)品的利潤） y1,

5、 y2 , y3 0化為標(biāo)準(zhǔn)型，利用單純形法進行求解，得到最優(yōu)解Y=(500, 0, 500, 0, 0)T，最優(yōu)值（收費）為70000。北京外國語大學(xué)國際商學(xué)院蔡連僑3-10最優(yōu)解 y1 = 500 y3 = 500， 最優(yōu)值 f* = 70000 北京外國語大學(xué)國際商學(xué)院蔡連僑3-11 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 65 2 x1 + x2 40 原問題原問題 3 x2 75 x1 , x2 0 Min f = 65 y1 + 40 y2 + 75 y3 s.t. 3 y1 + 2 y2 1500 2 y1 + y2 + 3 y3 2

6、500 對偶問題對偶問題 y1, y2 , y3 0北京外國語大學(xué)國際商學(xué)院蔡連僑3-12可以看到，這兩個問題關(guān)系密切，用同樣的原始數(shù)據(jù)目標(biāo)函數(shù)MaxMin約束條件系數(shù)矩陣AAT資源常數(shù)bc目標(biāo)系數(shù)cb 2個變量2個約束 3個約束3個變量 解檢驗數(shù) 檢驗數(shù)解北京外國語大學(xué)國際商學(xué)院蔡連僑3-13線性規(guī)劃有一個有趣的特性，就是對于任何一個求極大的線性規(guī)劃問題都存在一個與其匹配的求極小的線性規(guī)劃問題，并且這一對線性規(guī)劃問題的解之間還存在著密切的關(guān)系。線性規(guī)劃的這個特性稱為對偶性對這兩個線性規(guī)劃問題，一般稱前者為原問題，后者是前者的對偶問題北京外國語大學(xué)國際商學(xué)院蔡連僑3-14對偶問題的提出對偶問題

7、的形式對偶問題的基本性質(zhì)影子價格北京外國語大學(xué)國際商學(xué)院蔡連僑3-15如果線性規(guī)劃問題的變量均具有非負(fù)約束，其約束條件當(dāng)目標(biāo)函數(shù)求極大時均取“”，當(dāng)目標(biāo)函數(shù)求極小時均取“”，則稱具有對稱形式對稱形式下原問題和對偶問題的形式 (LP) Max z = CX (DP) Min f = YTb s.t. AX b s.t. ATY CT X 0 Y 0 “Max - ” “Min- ”北京外國語大學(xué)國際商學(xué)院蔡連僑3-16一對對稱形式的對偶規(guī)劃之間具有下面的對應(yīng)關(guān)系若一個模型為目標(biāo)求“極大”，約束為“小于等于”的不等式，則它的對偶模型為目標(biāo)求“極小”，約束是“大于等于”的不等式。即“max，”和“m

8、in，”相對應(yīng)從約束系數(shù)矩陣看：一個模型中為，則另一個模型中為AT。一個模型是m個約束，n個變量，則它的對偶模型為n個約束，m個變量從數(shù)據(jù)b、C的位置看：在兩個規(guī)劃模型中，b和C的位置對換兩個規(guī)劃模型中的變量皆非負(fù)北京外國語大學(xué)國際商學(xué)院蔡連僑3-17把對稱形式的對偶規(guī)劃之間的對應(yīng)關(guān)系表示在表中Max zMin fx1x2xnxi 0y1a11a12a1nb1y2a21a22a2nb2ymam1am2amnbmyi 0c1c2cn北京外國語大學(xué)國際商學(xué)院蔡連僑3-18對偶問題的對偶即是原問題(DP) Min f = YTb s.t. ATY CT Y 0 (LP) Max f = -YTb s

9、.t. - ATY - CT Y 0 (DP) Min z = - CX s.t. - AX - b X 0 (LP) Max z = CX s.t. AX b X 0 北京外國語大學(xué)國際商學(xué)院蔡連僑3-19一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃對于非對稱形式的規(guī)劃，可以按照下面的對應(yīng)關(guān)系進行處理并給出其對偶規(guī)劃將模型統(tǒng)一為“max，”或“min，” 的形式，對于其中的等式約束按下面的方法處理若原規(guī)劃的某個約束條件為等式約束，則在對偶規(guī)劃中與此約束對應(yīng)的那個變量取值沒有非負(fù)限制若原規(guī)劃的某個變量的值沒有非負(fù)限制，則在對偶問題中與此變量對應(yīng)的那個約束為等式也可以直接給出其對偶規(guī)

10、劃北京外國語大學(xué)國際商學(xué)院蔡連僑3-20例2：寫出下面線性規(guī)劃的對偶規(guī)劃模型 Max z = x1 + 4 x2 + 3 x3 s.t. 2 x1 + 3 x2 5 x3 2 3 x1 x2 + 6 x3 1 x1 + x2 + x3 = 4 x1 0，x2 0，x3 沒有非負(fù)限制北京外國語大學(xué)國際商學(xué)院蔡連僑3-21解：先化為對稱形式（Max）“”的約束兩端同乘以“1”“=”的約束等價轉(zhuǎn)換為“”和“”的兩個約束，再變換變量0，用變量替換，如 x2 = x2 變量無非負(fù)限制，用變量替換，如 x3 = x3 x3” Max z = x1 4 x2 + 3 x3 3 x3” s.t. 2 x1 3

11、 x2 5 x3 + 5 x3” 2 3 x1 x2 6 x3 + 6 x3” 1 x1 x2 + x3 x3” 4 x1 + x2 x3 + x3” 4 x1，x2，x3 ，x3” 0北京外國語大學(xué)國際商學(xué)院蔡連僑3-22寫出對偶問題 Min f = 2 y1 y2 + 4 y3 4 y3” s.t. 2 y1 3 y2 + y3 y3” 1 3 y1 y2 y3 + y3” 4 5 y1 6 y2 + y3 y3” 3 5 y1 + 6 y2 y3 + y3” 3 y1，y2，y3 ，y3” 0北京外國語大學(xué)國際商學(xué)院蔡連僑3-23變量替換，令y2 = y2 ，y3 = y3 y3” Mi

12、n f = 2 y1 + y2 + 4 y3 s.t. 2 y1 + 3 y2 + y3 1 3 y1 y2 + y3 4 5 y1 + 6 y2 + y3 = 3 y1 0 ，y2 0，y3 無非負(fù)限制北京外國語大學(xué)國際商學(xué)院蔡連僑3-24把對偶問題和原問題進行比較 Max z = x1 + 4 x2 + 3 x3 s.t. 2 x1 + 3 x2 5 x3 2原問題 3 x1 x2 + 6 x3 1 x1 + x2 + x3 = 4 x1 0，x2 0，x3 沒有非負(fù)限制 Min f = 2 y1 + y2 + 4 y3 s.t. 2 y1 + 3 y2 + y3 1對偶問題 3 y1 y

13、2 + y3 4 5 y1 + 6 y2 + y3 = 3 y1 0 ，y2 0，y3無非負(fù)限制北京外國語大學(xué)國際商學(xué)院蔡連僑3-25 由此得到非對稱形式的線性規(guī)劃原問題和對偶問題的對應(yīng)關(guān)系（對稱形式也適用）原問題對偶問題A約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置b約束條件右端項目標(biāo)函數(shù)中的系數(shù)C目標(biāo)函數(shù)中的系數(shù)約束條件右端項目標(biāo)函數(shù)Max z = cj xjMin f = bi yi變量n個 xj 0(0，無限制)約束條件n個aij yj(，=)cj約束條件m個aij xj(，=)bi變量m個 yi0(0，無限制)北京外國語大學(xué)國際商學(xué)院蔡連僑3-26例3：寫出下面線性規(guī)劃的對偶問題 Max z =

14、x1 x2 + 5 x3 7 x4 s.t. x1 + 3 x2 2 x3 + x4 = 25原問題 2 x1 7 x3 + 2 x4 60 2 x1 + 2 x2 4 x3 30 5 x4 10 ，x1，x2 0 ，x3 沒有非負(fù)限制 Min f = 25 y1 60 y2 + 30 y3 5 y4 + 10 y5 s.t. y1 + 2 y2 + 2 y3 1對偶問題 3 y1 + 2 y3 1 2 y1 7 y2 4 y3 = 5 y1 + 2 y2 + y4 + y5 = 7 y1無非負(fù)限制， y2， y4 0 ， y3， y5 0 北京外國語大學(xué)國際商學(xué)院蔡連僑3-27例：寫出下面運

15、輸問題的對偶問題njmixnjdxmisxtsxcwMinijjmiijinjijminjijij, 2 , 1;, 2 , 10, 2 , 1, 2 , 1. .1111北京外國語大學(xué)國際商學(xué)院蔡連僑3-28對偶問題的提出對偶問題的形式對偶問題的基本性質(zhì)影子價格北京外國語大學(xué)國際商學(xué)院蔡連僑3-29對偶問題的基本性質(zhì)對對稱形式和非對稱形式都是同樣適用的，但為了方便，在說明或證明時以對稱形式為例（非對稱形式可以化為對稱形式）對稱形式下原(Primal)問題和對偶(Dual)問題如下 (P) Max z = CX (D) Min f = YTb s.t. AX b s.t. ATY CT X 0

16、 Y 0 “Max - ” “Min- ”北京外國語大學(xué)國際商學(xué)院蔡連僑3-30（弱對偶定理）若X，Y分別為（P) 和（D）的可行解，那么CX YTb。證明：由變量的非負(fù)性限制，可以得到miiinjjjybxc11 minjijijnjjmiiijnjjjyxaxyaxc11111)( minjijijmiinjjijmiiiyxayxayb11111)(北京外國語大學(xué)國際商學(xué)院蔡連僑3-31弱對偶定理的推論（P）任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下界；（D）任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界若（P）可行，那么（P）無有限最優(yōu)解的充分必要條件是（D）無可行解若（D）可

17、行，那么（D）無有限最優(yōu)解的充分必要條件是（P）無可行解若（P）、 （D）可行，那么（P）、 （D）都有最優(yōu)解（P）有最優(yōu)解的充分必要條件是（D）有最優(yōu)解北京外國語大學(xué)國際商學(xué)院蔡連僑3-32（最優(yōu)性準(zhǔn)則定理）若X，Y分別為(P)，(D)的可行解，且CTX=YTb，則X，Y分別為(P)和(D)的最優(yōu)解證明：設(shè) X 為(P)的可行解，由弱對偶定理可得 CTX YTb = CTX 因此 X 為(P) 的最優(yōu)解設(shè) Y 為(D)的可行解，由弱對偶定理可得 YTb CTX = YTb 因此 Y 為(D) 的最優(yōu)解北京外國語大學(xué)國際商學(xué)院蔡連僑3-33（主對偶定理）若(P)和(D)均可行，那么(P)和(D

18、)均有最優(yōu)解，且最優(yōu)值相等。證明：若(P)和(D)均可行，則由弱對偶定理的推論知 (P)和(D)均有最優(yōu)解 設(shè)(P)的最優(yōu)基為B，令YT= CBB-1，由=C - CBB-1A 0，對于松弛變量部分，目標(biāo)函數(shù)系數(shù)為0，系數(shù)矩陣為單位陣，檢驗數(shù)為= - CBB-10，故Y0，且YTAC，ATY CT，因此 Y 為(D)的可行解 目標(biāo)YTb = CBB-1b = CX（原問題最優(yōu)值），由最優(yōu)性準(zhǔn)則定理知 Y 為 (D) 的最優(yōu)解注：(P) 松弛變量的檢驗數(shù)的絕對值是(D)的基可行解北京外國語大學(xué)國際商學(xué)院蔡連僑3-34對稱形式下原問題和對偶問題的標(biāo)準(zhǔn)形式如下 （互補松弛定理）若X 和Y 分別是 (

19、P)和(D)的最優(yōu)解（對稱形式的標(biāo)準(zhǔn)型下），則有 即約束取等式或?qū)?yīng)的變量為0), 2 , 1(0), 1(11mnjxmibxxaxczMaxjiinnjjijnjjj), 2 , 1( 0), 1(11mniynjcyyaybfMinijjmmiiijmiii), 1;, 1( 0, 0njmixyyxinijmj北京外國語大學(xué)國際商學(xué)院蔡連僑3-35證明：由弱對偶定理（CXYTb）得 由主對偶定理可知最優(yōu)值相等，上述不等式取“=”， miiiminjijijnjjjybyxaxc1111 miiinmiinjjijiminjijijmiiiyxyxabyxayb111111)(00, 0

20、,yxyxiinij得由 njjjmnjjjmiiijnjjjminjijijxyxcyaxcyxa111111)(00, 0,yxyxjmjij得由北京外國語大學(xué)國際商學(xué)院蔡連僑3-36對偶問題基本性質(zhì)的應(yīng)用利用單純形法，求得對偶問題最優(yōu)解 X=(1, 0, 0, 2, 0)T，最優(yōu)值 z* = 9。由互補松弛定理，得 x1 y3 = 0， x2 y4 = 0，x3 y5 = 0，x4 y1 = 0， x5 y2 =0，因此有 y1 = 0，y3 = 0，代入第1個約束得到y(tǒng)2 = 9，代入其余約束得 y4 = 4， y5 = 64對于變量數(shù)量少、約束多的問題，可以利用基本性質(zhì)簡化求解例4：

21、 Min f = 5 y1 + y2 s.t. 3 y1 + y2 9 y1 + y2 5 y1 + 8 y2 8 y1，y2 0 Max z = 9 x1 + 5 x2 + 8 x3 s.t. 3 x1 + x2 + x3 5 x1 + x2 + 8 x3 1 x1， x2， x3 0 北京外國語大學(xué)國際商學(xué)院蔡連僑3-37對偶問題的提出對偶問題的形式對偶問題的基本性質(zhì)影子價格北京外國語大學(xué)國際商學(xué)院蔡連僑3-38影子價格 (Shadow Price) 的概念若X*，Y* 分別為（P）和（D）的最優(yōu)解，則 z = CX* = Y*Tb = f根據(jù) z = b1y1*+b2y2*+bmym*

22、可知 z / bi = yi* 其中bi表示第 i 種資源的擁有量， yi*表示 bi 變化1個單位對目標(biāo) z 產(chǎn)生的影響，也是在資源最優(yōu)利用條件下對該資源的估價，稱為該資源的影子價格例如，在例1中 yi* 是對設(shè)備租金的估價注意：注意：若 B 是最優(yōu)基， y*T = CBB-1北京外國語大學(xué)國際商學(xué)院蔡連僑3-39影子價格的經(jīng)濟含義及應(yīng)用資源的市場價格是已知的，且相對比較穩(wěn)定，而影子價格有賴于資源的利用情況，是未知數(shù)，隨著企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況的變化而發(fā)生變化影子價格是一種邊際價格，說明在資源得到最優(yōu)利用的條件下，增加單位資源量可以增加的收益影子價格是對現(xiàn)有資源實現(xiàn)最大效益時的一種估價

23、，實際上是一種機會成本。企業(yè)可以根據(jù)現(xiàn)有資源的影子價格，考慮經(jīng)營策略：如果影子價格高于市場價格，可考慮買進設(shè)備，以擴大生產(chǎn)能力，否則不宜買進；若某設(shè)備的租費高于影子價格，可考慮出租該設(shè)備，否則不宜出租北京外國語大學(xué)國際商學(xué)院蔡連僑3-40由互補松弛定理，可知如果某種資源未得到充分利用時（松弛變量不為0），則其影子價格為0（對應(yīng)變量為0）；當(dāng)資源的影子價格不為0，表明該資源在生產(chǎn)中已耗費完畢從影子價格的含義上來考察檢驗數(shù)j = cj - aij yi，其中 cj 表示產(chǎn)品的價值，aij yi是生產(chǎn)該產(chǎn)品所消耗的各項資源的影子價格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)品的價值大于隱含成本時，表明生產(chǎn)該產(chǎn)品

24、有利；否則就不安排生產(chǎn)。這就是檢驗數(shù)的經(jīng)濟含義影子價格反映了不同的局部或個體的增量可以獲得不同的整體經(jīng)濟效益。如果為了擴大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從影子價格高的設(shè)備入手，以較少的局部努力，獲得較大的整體效益北京外國語大學(xué)國際商學(xué)院蔡連僑3-41一般來說，對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當(dāng)估價。這種估價涉及到資源的最有效利用，如在一個大公司內(nèi)部，可借助資源的影子價格確定內(nèi)部結(jié)算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞需要指出的是，影子價格不是固定不變的，當(dāng)約束條件、產(chǎn)品利潤等發(fā)生變化時，有可能使影子價格發(fā)生變化。另外，影子價格

25、說明增加單位資源量可以增加的收益，是指資源在一定范圍內(nèi)增加時的情況，當(dāng)某種資源的增加超過了一定的范圍，總利潤的增加量就不是按照影子價格給出的數(shù)值線性地增加。這將在靈敏度分析中討論北京外國語大學(xué)國際商學(xué)院蔡連僑3-42 影子價格的應(yīng)用舉例例5：某外貿(mào)公司準(zhǔn)備購進兩種產(chǎn)品A1，A2。購進產(chǎn)品A1每件需要10元，占用5平方米的空間，賣出1件可獲純利潤3元；購進產(chǎn)品A2每件需要15元，占用3平方米的空間，賣出1件可獲純利潤4元。公司現(xiàn)有資金1400元，有430平方米的倉庫空間存放產(chǎn)品。根據(jù)這些條件可以建立求最大利潤的線性規(guī)劃模型： Max z = 3 x1 + 4 x2 s.t. 10 x1 + 15

26、 x2 1400 5 x1 + 3 x2 430 x1, x2 0 北京外國語大學(xué)國際商學(xué)院蔡連僑3-43求解后得到最優(yōu)單純形表如下所示 ：因此，最優(yōu)方案是分別購進兩種產(chǎn)品50件和60件，公司的最大利潤為390元。同時，從表中也可以看到，資金的影子價格為11/45，即增加1元用于購買產(chǎn)品，可以多獲利潤11/45元；倉庫的影子價格為1/9，即增加1平方米的倉庫空間，可以多獲利潤1/9元CBXBbx1x2x3x44x260011/9-2/93x15010-1/151/3-z-39000-11/45-1/9北京外國語大學(xué)國際商學(xué)院蔡連僑3-44假設(shè)公司現(xiàn)在另有一筆資金585元，準(zhǔn)備用于投資。當(dāng)然，這

27、筆資金用于購買產(chǎn)品或者增加倉庫空間都可以使公司獲得更多的利潤。問題是應(yīng)該如何合理安排投資，使公司能夠獲得更多的利潤。已知增加1平方米的倉庫空間需要0.8元，因此如果資金用于增加倉庫空間，每投資0.8元可以多獲利1/9元，即每增加1元投資可多獲利5/36=0.14元；而每增加1元用于購買產(chǎn)品，可以多獲利11/45=0.24元。因此應(yīng)該把資金用于購買產(chǎn)品，這樣可以獲得更多的利潤將這585元也用于購買產(chǎn)品，可以增加利潤 585y1=58511/45=143元北京外國語大學(xué)國際商學(xué)院蔡連僑3-45這可通過對改變條件的新模型的求解結(jié)果得到驗證。新模型為 Max z = 3 x1 + 4 x2 s.t.

28、10 x1 + 15 x2 1985 5 x1 + 3 x2 430 x1, x2 0 得到最優(yōu)解X =(11, 125)T，總利潤為533元，增加533-390=143元如果采用其他方案，利潤增加量肯定小于143元。如585元中510元用于購買產(chǎn)品，75元用于增加倉庫空間(75/0.8=93.75)。則有 Max z = 3 x1 + 4 x2 s.t. 10 x1 + 15 x2 1910 5 x1 + 3 x2 523.75 x1, x2 0 得最優(yōu)解X =(47.25, 95.83)T，總利潤為525.08元，只增135.08元北京外國語大學(xué)國際商學(xué)院蔡連僑3-46線性規(guī)劃的對偶問題線

29、性規(guī)劃的對偶單純形法線性規(guī)劃的靈敏度分析參數(shù)線性規(guī)劃北京外國語大學(xué)國際商學(xué)院蔡連僑3-47單純形法的思路對原問題的一個基本可行解，判別是否所有檢驗數(shù)滿足最優(yōu)條件。若是，即找到了問題最優(yōu)解；否則，再找出相鄰的目標(biāo)函數(shù)值更大的基本可行解，并繼續(xù)判別，直到找到最優(yōu)解或判別出無最優(yōu)解為止也就是說，單純形法在求解過程中保持原問題的可行性，尋找對偶問題的可行解根據(jù)對偶問題的基本性質(zhì)，當(dāng)對于某個基而言，原問題的基本解是可行的，對偶問題的解也是可行的，則由兩者的目標(biāo)函數(shù)值相等，因此此解為最優(yōu)解。是否可以保持對偶問題的可行性，然后尋找原問題的可行解，這就是對偶單純形法的思路北京外國語大學(xué)國際商學(xué)院蔡連僑3-48

30、對偶單純形法的基本思想從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行，但它對應(yīng)著一個對偶可行解（檢驗數(shù)非正），所以也可以說是從一個對偶可行解出發(fā)；然后檢驗原規(guī)劃的基本解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應(yīng)著另一個對偶可行解（檢驗數(shù)非正）。如果得到的基本解的分量皆非負(fù)則該基本解為最優(yōu)解也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，?dāng)同時得到對偶規(guī)劃與原規(guī)劃的可行解時，便得到原規(guī)劃的最優(yōu)解北京外國語大學(xué)國際商學(xué)院蔡連僑3-49對偶單純形法求解線性規(guī)劃問題過程：建立初始對偶單純形表，對

31、應(yīng)一個基本解，所有檢驗數(shù)均非正，轉(zhuǎn)下一步若b0，則得到最優(yōu)解，停止；否則，若有bk0則選k行的基變量為出基變量，轉(zhuǎn)下一步若所有akj0( j = 1,2,n)，則原問題無可行解，停止；否則，若有akj0 則選 =minj / akj | akj0=r/akr，那么 xr為進基變量，轉(zhuǎn)下一步以akr為轉(zhuǎn)軸元，作矩陣行變換使其變?yōu)?，該列其他元變?yōu)?，轉(zhuǎn)回第二步北京外國語大學(xué)國際商學(xué)院蔡連僑3-50例6：求解線性規(guī)劃問題：求解線性規(guī)劃問題：標(biāo)準(zhǔn)化：標(biāo)準(zhǔn)化： Max z = - 2 x1 3 x2 - 4 x3 s.t. - x1 - 2 x2 - x3 + x4 = -3 -2 x1 + x2 -

32、 3 x3 + x5 = -4 x1, x2, x3, x4, x5 0Min f = 2 x1 + 3 x2 + 4 x3 S.t. x1 + 2 x2 + x3 3 2 x1 - x2 + x3 4 x1 , x2 , x3 0北京外國語大學(xué)國際商學(xué)院蔡連僑3-51北京外國語大學(xué)國際商學(xué)院蔡連僑3-52ekeikikiabaab0minekkejejiaaa0min是是是是否否否否所有所有得到最優(yōu)解計算計算原規(guī)劃的基本解是可行的原規(guī)劃的基本解的檢驗數(shù)為非正所有所有計算計算以aek為中心元素進行迭代以aek為中心元素進行迭代停沒有有限最優(yōu)解沒有可行解單純形法對偶單純形法0j0ib0maxjj

33、k0miniiebbb0ika0eja北京外國語大學(xué)國際商學(xué)院蔡連僑3-53對偶單純形法的應(yīng)用前提：有一個基，其對應(yīng)的基滿足：單純形表的檢驗數(shù)行全部非正（對偶可行）變量取值可有負(fù)數(shù)（非可行解）對偶單純形法適合于解如下形式的線性規(guī)劃問題njxmibxacxcfjnjijijnjjjj,2, 1,0,2, 10min11北京外國語大學(xué)國際商學(xué)院蔡連僑3-54在引入松弛變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對偶單純形表進行求解，非常方便對于有些線性規(guī)劃模型，如果在開始求解時不能很快使所有檢驗數(shù)非正，最好還是采用單純形法求解。因為，這樣可以

34、免去為使檢驗數(shù)全部非正而作的許多工作。從這個意義上看，可以說，對偶單純形法是單純形法的一個補充。除此之外，在對線性規(guī)劃進行靈敏度分析中有時也要用到對偶單純形方法，可以簡化計算北京外國語大學(xué)國際商學(xué)院蔡連僑3-55上表中6個常數(shù) a1 , a2 , a3 , b , 1 , 2 取值在什么范圍可使1、現(xiàn)可行解最優(yōu)，且唯一？何時不唯一？2、現(xiàn)基本解不可行；3、問題無可行解；4、無有限最優(yōu)解；5、現(xiàn)基本解可行，由 x1 取代 x6 目標(biāo)函數(shù)可改善。 北京外國語大學(xué)國際商學(xué)院蔡連僑3-561、b0,10,20, 1=0或2=0時不唯一（不考慮退化的復(fù)雜情況，需要再分情況討論）2、b 0 時現(xiàn)基本解不可

35、行3、b 0, a1 0, b0,無有限最優(yōu)解5、10, b0, a3 0, 3/a3 0csMinj /asjasj0csMinj /asjasj0brMin-bi/irir0北京外國語大學(xué)國際商學(xué)院蔡連僑3-72例10：例9的最優(yōu)單純形表如下 0 1/4 0 這里 B-1 = -2 1/2 1 1/2 -1/8 0 各列分別對應(yīng) b1、b2、b3 的單一變化，因此，設(shè) b1 增加 4，則 x1, x5, x2分別變?yōu)椋?+04 = 4，4+(-2)4 = -40，2+1/24=4北京外國語大學(xué)國際商學(xué)院蔡連僑3-73 用對偶單純形法進一步求解，可得： x* = ( 4, 3, 2, 0,

36、0 )T, z * = 17北京外國語大學(xué)國際商學(xué)院蔡連僑3-74是否投產(chǎn)新產(chǎn)品增加一個變量 假設(shè)可以生產(chǎn)一種新產(chǎn)品，增加變量 xn+1，則有相應(yīng)的pn+1，cn+1 計算出B-1pn+1 , n+1=cn+1-ci ai ,n+1，填入最優(yōu)單純形表，不影響解的可行性以及其余檢驗數(shù) 若 n+1 0 則 最優(yōu)解不變；否則，進一步用單純形法求解北京外國語大學(xué)國際商學(xué)院蔡連僑3-75例11：例9增加x6 ， p6=( 2, 6, 3 )T，c6 = 5 計算得到用單純形法進一步求解，可得：x* = ( 1,3/2,0,0,0,2 )T z* = 33/2，應(yīng)該生產(chǎn)新產(chǎn)品北京外國語大學(xué)國際商學(xué)院蔡連僑

37、3-76增加資源約束或加工工序增加一個約束有些資源由于緊缺，不能像以前一樣隨便使用，如電力供應(yīng)有限制等，這就增加了約束；或者增加一道工序，也需要增加一個約束增加約束一個之后，應(yīng)把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入一個新的非負(fù)變量（原約束若是小于等于形式可引入非負(fù)松弛變量，否則引入非負(fù)人工變量），并通過矩陣行變換把對應(yīng)基變量的元素變?yōu)?，進一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼獗本┩鈬Z大學(xué)國際商學(xué)院蔡連僑3-77例12：例9增加3x1+ 2x215，原最優(yōu)解不滿足這個約束。引入松弛變量，得到 3 x1+ 2 x2 + x6 = 15經(jīng)過行變換，可以得到北京

38、外國語大學(xué)國際商學(xué)院蔡連僑3-78經(jīng)對偶單純形法一步，可得最優(yōu)解為（7/2, 9/4, 0, 2, 3, 0 )T，最優(yōu)值為 55/4北京外國語大學(xué)國際商學(xué)院蔡連僑3-79生產(chǎn)工藝發(fā)生變化A中元素發(fā)生變化如果發(fā)生變化的元素不在基中，則與增加變量 xn+1 的情況類似，假設(shè) pj 變化，那么，重新計算出B-1pj ，j = cj - ci ai j ，填入最優(yōu)單純形表，若 j 0 則最優(yōu)解不變；否則，進一步用單純形法求解如果發(fā)生變化的元素在基中，則B和B-1都發(fā)生變化，也可能原問題和對偶問題的解均不可行，這時需引入人工變量將原問題的解轉(zhuǎn)化為可行解，再用單純形法求解北京外國語大學(xué)國際商學(xué)院蔡連僑3

39、-80例13：例9中若原計劃生產(chǎn)產(chǎn)品I的工藝有了改進，相關(guān)技術(shù)系數(shù)向量由P1=(1,4,0)T變?yōu)镻1=(2,5,2)T，每件利潤為4元，試分析對原最優(yōu)計劃有什么影響? 解：把改進工藝結(jié)構(gòu)的產(chǎn)品I看作產(chǎn)品I，設(shè)x1為其產(chǎn)量。于是在原計算的最終表中以于是在原計算的最終表中以x1代替代替x1，計算對，計算對應(yīng)應(yīng)x1的列向量及檢驗數(shù)。的列向量及檢驗數(shù)。8383214530248321452520812112120410111111TBPBCcPB北京外國語大學(xué)國際商學(xué)院蔡連僑3-81以x1為換入變量，x1為換出變量，經(jīng)過迭代得到最優(yōu)解為（16/5, 4/5, 0, 0, 12/5)T，最優(yōu)值為 76

40、/5。北京外國語大學(xué)國際商學(xué)院蔡連僑3-82例14：例9中若原計劃生產(chǎn)產(chǎn)品I的工藝有了改進，相關(guān)技術(shù)系數(shù)向量由P1=(1,4,0)T變?yōu)镻1=(4,5,2)T，每件利潤為4元，試分析對原最優(yōu)計劃有什么影響? 解：把改進工藝結(jié)構(gòu)的產(chǎn)品I看作產(chǎn)品I，設(shè)x1為其產(chǎn)量。在原計算的最終表中以在原計算的最終表中以x1代替代替x1，計算對應(yīng)，計算對應(yīng)x1的列向量及檢驗數(shù)。的列向量及檢驗數(shù)。8218112745302481127452540812112120410111111TBPBCcPB北京外國語大學(xué)國際商學(xué)院蔡連僑3-83注意：若碰到原問題和對偶問題均為非可行解時，就注意：若碰到原問題和對偶問題均為非可

41、行解時，就需要引進人工變量后重新求解。需要引進人工變量后重新求解。北京外國語大學(xué)國際商學(xué)院蔡連僑3-84原問題和對偶問題都是非可行解，引入人工變量x6。在上表中x2所在行，用方程表示為0 x1 + x2 + 1/2 x3 2/5 x4 + 0 x5 = - 12/5引入人工變量x6后，化為 0 x1 x2 1/2 x3 + 2/5 x4 + 0 x5 + x6 = 12/5將x6作為基變量代替x2，填入表中，得到下表。北京外國語大學(xué)國際商學(xué)院蔡連僑3-85得到最優(yōu)解為（2/3, 8/3, 0, 38/3, 0, 0)T，最優(yōu)值為 32/3。北京外國語大學(xué)國際商學(xué)院蔡連僑3-8686多個參數(shù)同時

42、發(fā)生變化，適用100%準(zhǔn)則。多個目標(biāo)函數(shù)系數(shù)發(fā)生變化，定義變化的程度比例：為允許的最大減量）（若為允許的最大增量）（若jjjjjjjjjjDDcrcIIcrc, 0, 0然是最優(yōu)的。，那么原來的最優(yōu)解仍如果1jr北京外國語大學(xué)國際商學(xué)院蔡連僑3-8787多個右端項同時發(fā)生變化，定義變化的程度比例：為允許的最大減量）（若為允許的最大增量）（若jjjjjjjjjjDDbrbIIbrb, 0, 0，那么最優(yōu)基不變。如果1jr北京外國語大學(xué)國際商學(xué)院蔡連僑3-88利用軟件進行求解QSBLINDOEXCEL（舉例說明使用方法）北京外國語大學(xué)國際商學(xué)院蔡連僑3-89線性規(guī)劃的對偶問題線性規(guī)劃的對偶單純形法

43、線性規(guī)劃的靈敏度分析參數(shù)線性規(guī)劃北京外國語大學(xué)國際商學(xué)院蔡連僑3-90參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃靈敏度分析時，主要討論在最優(yōu)基不變情況下，確定系數(shù)aij，bi，cj的變化范圍。而參數(shù)線性規(guī)劃是研究這些參數(shù)中某一參數(shù)連續(xù)變化時，使最優(yōu)解發(fā)生變化的各臨界點的值。即把某一參數(shù)作為參變量，而目標(biāo)函數(shù)在某區(qū)間內(nèi)是這個參變量的線性函數(shù)，含這個參變量的約束條件是線性等式或不等式。因此仍可用單純形法和對偶單純形法分析參數(shù)線性規(guī)劃問題。北京外國語大學(xué)國際商學(xué)院蔡連僑3-91參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃其步驟是：對含有某參變量t的參數(shù)線性規(guī)劃問題。先令t=0，用單純形法求出最優(yōu)解用靈敏度分析法，將參變量t直接反映到最終

44、表中當(dāng)參變量t連續(xù)變大或變小時，觀察b列和檢驗數(shù)行各數(shù)字的變化。若在b列首先出現(xiàn)某負(fù)值時，則以它對應(yīng)的變量為換出變量；于是用對偶單純形法迭代一步。若在檢驗數(shù)行首先出現(xiàn)某正值時，則將它對應(yīng)的變量為換入變量；用單純形法迭代一步在經(jīng)迭代一步后得到的新表上，令參變量t繼續(xù)變大或變小，重復(fù)上一個步驟，直到b列不能再出現(xiàn)負(fù)值，檢驗數(shù)行不能再出現(xiàn)正值為止北京外國語大學(xué)國際商學(xué)院蔡連僑3-92參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃參數(shù)C的變化例15：試分析以下參數(shù)線性規(guī)劃問題。當(dāng)參數(shù)t0時的最優(yōu)解變化。0,18231224)5()23()(max21212121xxxxxxxtxttz北京外國語大學(xué)國際商學(xué)院蔡連僑3-93參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃解 將此模型化為標(biāo)準(zhǔn)型令t=0，用單純形法求解：0,18231224)(0)5()23()(max543