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

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

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

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

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

5、 y2 , y3 0化為標準型，利用單純形法進行求解，得到最優(yōu)解Y=(500, 0, 500, 0, 0)T，最優(yōu)值（收費）為70000。北京外國語大學國際商學院蔡連僑3-10最優(yōu)解 y1 = 500 y3 = 500， 最優(yōu)值 f* = 70000 北京外國語大學國際商學院蔡連僑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北京外國語大學國際商學院蔡連僑3-12可以看到，這兩個問題關系密切，用同樣的原始數據目標函數MaxMin約束條件系數矩陣AAT資源常數bc目標系數cb 2個變量2個約束 3個約束3個變量 解檢驗數 檢驗數解北京外國語大學國際商學院蔡連僑3-13線性規(guī)劃有一個有趣的特性，就是對于任何一個求極大的線性規(guī)劃問題都存在一個與其匹配的求極小的線性規(guī)劃問題，并且這一對線性規(guī)劃問題的解之間還存在著密切的關系。線性規(guī)劃的這個特性稱為對偶性對這兩個線性規(guī)劃問題，一般稱前者為原問題，后者是前者的對偶問題北京外國語大學國際商學院蔡連僑3-14對偶問題的提出對偶問題

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

8、in，”相對應從約束系數矩陣看：一個模型中為，則另一個模型中為AT。一個模型是m個約束，n個變量，則它的對偶模型為n個約束，m個變量從數據b、C的位置看：在兩個規(guī)劃模型中，b和C的位置對換兩個規(guī)劃模型中的變量皆非負北京外國語大學國際商學院蔡連僑3-17把對稱形式的對偶規(guī)劃之間的對應關系表示在表中Max zMin fx1x2xnxi 0y1a11a12a1nb1y2a21a22a2nb2ymam1am2amnbmyi 0c1c2cn北京外國語大學國際商學院蔡連僑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 北京外國語大學國際商學院蔡連僑3-19一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃對于非對稱形式的規(guī)劃，可以按照下面的對應關系進行處理并給出其對偶規(guī)劃將模型統一為“max，”或“min，” 的形式，對于其中的等式約束按下面的方法處理若原規(guī)劃的某個約束條件為等式約束，則在對偶規(guī)劃中與此約束對應的那個變量取值沒有非負限制若原規(guī)劃的某個變量的值沒有非負限制，則在對偶問題中與此變量對應的那個約束為等式也可以直接給出其對偶規(guī)

10、劃北京外國語大學國際商學院蔡連僑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 沒有非負限制北京外國語大學國際商學院蔡連僑3-21解：先化為對稱形式（Max）“”的約束兩端同乘以“1”“=”的約束等價轉換為“”和“”的兩個約束，再變換變量0，用變量替換，如 x2 = x2 變量無非負限制，用變量替換，如 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北京外國語大學國際商學院蔡連僑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北京外國語大學國際商學院蔡連僑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 無非負限制北京外國語大學國際商學院蔡連僑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 沒有非負限制 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無非負限制北京外國語大學國際商學院蔡連僑3-25 由此得到非對稱形式的線性規(guī)劃原問題和對偶問題的對應關系（對稱形式也適用）原問題對偶問題A約束系數矩陣約束系數矩陣的轉置b約束條件右端項目標函數中的系數C目標函數中的系數約束條件右端項目標函數Max z = cj xjMin f = bi yi變量n個 xj 0(0，無限制)約束條件n個aij yj(，=)cj約束條件m個aij xj(，=)bi變量m個 yi0(0，無限制)北京外國語大學國際商學院蔡連僑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 沒有非負限制 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無非負限制， y2， y4 0 ， y3， y5 0 北京外國語大學國際商學院蔡連僑3-27例：寫出下面運

15、輸問題的對偶問題njmixnjdxmisxtsxcwMinijjmiijinjijminjijij, 2 , 1;, 2 , 10, 2 , 1, 2 , 1. .1111北京外國語大學國際商學院蔡連僑3-28對偶問題的提出對偶問題的形式對偶問題的基本性質影子價格北京外國語大學國際商學院蔡連僑3-29對偶問題的基本性質對對稱形式和非對稱形式都是同樣適用的，但為了方便，在說明或證明時以對稱形式為例（非對稱形式可以化為對稱形式）對稱形式下原(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- ”北京外國語大學國際商學院蔡連僑3-30（弱對偶定理）若X，Y分別為（P) 和（D）的可行解，那么CX YTb。證明：由變量的非負性限制，可以得到miiinjjjybxc11 minjijijnjjmiiijnjjjyxaxyaxc11111)( minjijijmiinjjijmiiiyxayxayb11111)(北京外國語大學國際商學院蔡連僑3-31弱對偶定理的推論（P）任一可行解的目標函數值是其對偶問題目標函數值的下界；（D）任一可行解的目標函數值是其原問題目標函數值的上界若（P）可行，那么（P）無有限最優(yōu)解的充分必要條件是（D）無可行解若（D）可

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

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

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

20、,yxyxiinij得由 njjjmnjjjmiiijnjjjminjijijxyxcyaxcyxa111111)(00, 0,yxyxjmjij得由北京外國語大學國際商學院蔡連僑3-36對偶問題基本性質的應用利用單純形法，求得對偶問題最優(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個約束得到y2 = 9，代入其余約束得 y4 = 4， y5 = 64對于變量數量少、約束多的問題，可以利用基本性質簡化求解例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 北京外國語大學國際商學院蔡連僑3-37對偶問題的提出對偶問題的形式對偶問題的基本性質影子價格北京外國語大學國際商學院蔡連僑3-38影子價格 (Shadow Price) 的概念若X*，Y* 分別為（P）和（D）的最優(yōu)解，則 z = CX* = Y*Tb = f根據 z = b1y1*+b2y2*+bmym*

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

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

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

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

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

27、筆資金用于購買產品或者增加倉庫空間都可以使公司獲得更多的利潤。問題是應該如何合理安排投資，使公司能夠獲得更多的利潤。已知增加1平方米的倉庫空間需要0.8元，因此如果資金用于增加倉庫空間，每投資0.8元可以多獲利1/9元，即每增加1元投資可多獲利5/36=0.14元；而每增加1元用于購買產品，可以多獲利11/45=0.24元。因此應該把資金用于購買產品，這樣可以獲得更多的利潤將這585元也用于購買產品，可以增加利潤 585y1=58511/45=143元北京外國語大學國際商學院蔡連僑3-45這可通過對改變條件的新模型的求解結果得到驗證。新模型為 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元用于購買產品，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元北京外國語大學國際商學院蔡連僑3-46線性規(guī)劃的對偶問題線

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

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

31、應一個基本解，所有檢驗數均非正，轉下一步若b0，則得到最優(yōu)解，停止；否則，若有bk0則選k行的基變量為出基變量，轉下一步若所有akj0( j = 1,2,n)，則原問題無可行解，停止；否則，若有akj0 則選 =minj / akj | akj0=r/akr，那么 xr為進基變量，轉下一步以akr為轉軸元，作矩陣行變換使其變?yōu)?，該列其他元變?yōu)?，轉回第二步北京外國語大學國際商學院蔡連僑3-50例6：求解線性規(guī)劃問題：求解線性規(guī)劃問題：標準化：標準化： 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北京外國語大學國際商學院蔡連僑3-51北京外國語大學國際商學院蔡連僑3-52ekeikikiabaab0minekkejejiaaa0min是是是是否否否否所有所有得到最優(yōu)解計算計算原規(guī)劃的基本解是可行的原規(guī)劃的基本解的檢驗數為非正所有所有計算計算以aek為中心元素進行迭代以aek為中心元素進行迭代停沒有有限最優(yōu)解沒有可行解單純形法對偶單純形法0j0ib0maxjj

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

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

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

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

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

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

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

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

41、行解時，就需要引進人工變量后重新求解。需要引進人工變量后重新求解。北京外國語大學國際商學院蔡連僑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，填入表中，得到下表。北京外國語大學國際商學院蔡連僑3-85得到最優(yōu)解為（2/3, 8/3, 0, 38/3, 0, 0)T，最優(yōu)值為 32/3。北京外國語大學國際商學院蔡連僑3-8686多個參數同時

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

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

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