第二章 對(duì)偶問題.ppt

1、2020/8/3,-第2章 對(duì)偶問題-,-1-,第 二 章 線性規(guī)劃的對(duì)偶理論,Duality 對(duì)偶 Dual Problem 對(duì)偶問題 Dual Linear Programming 對(duì)偶線性規(guī)劃 Dual Theory 對(duì)偶理論,2020/8/3,2,，各生產(chǎn)多少, 可獲最大利潤?,乙方租借設(shè)備： 甲方以何種價(jià)格將設(shè)備A、B、 C租借給乙方比較合理？ 請(qǐng)為 其定價(jià)。,2.1 問題的提出,-第2章 對(duì)偶問題-,2020/8/3,3,而就乙方而言，希望甲方的租金收入在滿足約束的條件下越小越好， 這樣雙方才可能達(dá)成協(xié)議。 于是得到下述 的線性規(guī)劃模型：,解：假設(shè)A、B、C的單位租金分別為 ，所以

2、生產(chǎn)產(chǎn)品的資源用于出租時(shí)，租金收入應(yīng)滿足：,類似的，生產(chǎn)產(chǎn)品的資源用于出租時(shí)，租金收入應(yīng)滿足：,總的租金收入：,-第2章 對(duì)偶問題-,思路： 就甲方而言， 租金收入應(yīng)不低于將設(shè)備用于自己生產(chǎn)時(shí)的利潤。,原問題的對(duì)偶問題,2020/8/3,-第2章 對(duì)偶問題-,-4-,例：某企業(yè)計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，該兩種產(chǎn)品均需經(jīng) A、B、C、D 四種不同設(shè)備加工，按工藝資料規(guī)定，在各種不同設(shè)備上的加工時(shí)間及設(shè)備加工能力、單位產(chǎn)品利潤如表中所示。問：如何安排產(chǎn)品的生產(chǎn)計(jì)劃，才能使企業(yè)獲利最大?,2020/8/3,-第2章 對(duì)偶問題-,-5-,1.最大生產(chǎn)利潤模型,設(shè) 企業(yè)生產(chǎn)甲產(chǎn)品為X1件， 乙產(chǎn)品為X2件

3、，則 max z= 2 X1 +3 X2 s.t 2 X1 +2 X2 12 X1 +2 X2 8 4 X1 16 4 X2 12 X1 0 , X2 0,2.資源最低售價(jià)模型,(原問題) ( 對(duì)偶問題),設(shè)第i種資源價(jià)格為yi,（ i=1, 2, 3, 4,） 則有,min w= 12y1 + 8y2 + 16y3 +12 y4,s.t 2y1 + y2 + 4y3 +0 y4 2,2y1 +2y2 + 0y3 +4 y4 3,yi 0, (i=1, 2, 3, 4 ),y1,y2,y3,y4,2020/8/3,-第2章 對(duì)偶問題-,-6-,2.2 原問題與對(duì)偶問題的關(guān)系,一般表示式： 原問

4、題： max z = c1 X1 + c2 X2 + + cn Xn s.t a11 X1 + a12 X2 + + a1n Xn b1 a21 X1 + a22 X2 + + a2n Xn b2 am1 X1 + am2 X2 + + amn Xn bm xj 0，j=1,2,n 對(duì)偶問題： min w = b1 y1 + b2 y2 + + bm ym s.t a11 y1 + a21 y2 + + am1 ym c1 a12 y1 + a22 y2 + + am2 ym c2 a1n y1 + a2n y2 + + amn ym cn yi 0，(i=1,2,m ),2020/8/3,-

5、第2章 對(duì)偶問題-,-7-,典式模型對(duì)應(yīng)對(duì)偶結(jié)構(gòu)矩陣表示,（1）max z = C X s.t AX b X 0,min w = Y b s.t YA C Y 0,對(duì)偶問題,原問題,這是規(guī)范形式 的原問題，由此寫出其對(duì)偶問題如右方所示，那么，當(dāng)原問題 不是規(guī)范形式時(shí)，應(yīng)如何寫出其對(duì)偶問題？可以先將原問題化成規(guī)范的 原問題，再寫出對(duì)偶問題。,2020/8/3,-第2章 對(duì)偶問題-,-8-,對(duì)偶模型其他結(jié)構(gòu)關(guān)系,（2）若模型為 max z = C X s.t AX b X 0,max z = C X s.t - AX -b X 0,變形,min w = Y b s.t YA C Y 0,Min w

6、=Y (-b) st. Y (-A) CY 0,令 Y= -Y ,對(duì)偶問題,對(duì)偶變量Y,2020/8/3,-第2章 對(duì)偶問題-,-9-,（3）max z = C X s.t AX b X 0,變形,設(shè)X= -X,max = -CX st. -AX b X 0,min w = Y b s.t YA C Y 0,則有,min w = Y b s.t -YA - C Y 0,2020/8/3,-第2章 對(duì)偶問題-,-10-,對(duì)偶問題典式：,用矩陣形式表示： （1） max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 0 （2） max z = C X mi

7、n w = Y b s.t AX b s.t YA C X 0 Y 0 （3）max z = C X min w = Y b s.t AX b s.t YA C X 0 Y 0,11,等式、無約束情況的對(duì)偶：,原問題,對(duì)偶問題,12,推導(dǎo):,原問題化為：,即：,13,根據(jù)對(duì)稱形式的對(duì)偶模型,可直接寫出上述問題的對(duì)偶問題:,14,令 ，得對(duì)偶問題為：,2020/8/3,-第2章 對(duì)偶問題-,-15-,原問題與對(duì)偶問題關(guān)系表,原問題(對(duì)偶問題) 對(duì)偶問題(原問題) 目標(biāo)函數(shù)系數(shù) 約束右端項(xiàng) 約束右端項(xiàng) 目標(biāo)函數(shù)系數(shù) 約束條件系數(shù)列向量 A約束條件系數(shù)行向量 AT 變量個(gè)數(shù)約束條件個(gè)數(shù) max mi

8、n 變量 x j : 約束方程 i : x j 0 x j 無約束 = x j 0 約束方程: 變量 y i : y i 0 = y i 無約束 y i 0,2020/8/3,-第2章 對(duì)偶問題-,-16-,2.3 對(duì)偶問題的基本性質(zhì),Max z = CXMin w = Y b s t . AX b s t . YA C X 0Y 0,(1) 弱對(duì)偶性： 若 X0原問題可行解，Y0對(duì)偶問題可行解 則 CX0 Y0 b 證明： Y0 0， AX0 b， Y0 AX0 Y0 b， 而 Y0 A C ， CX0 Y0AX0 ， CX0 Y0 AX0 Y0 b,推論1: 原問題任一可行解的目標(biāo)函數(shù)值是

9、其對(duì)偶問題目標(biāo)函數(shù)值的下屆；反之，對(duì)偶問題任意可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。,推論2: 在一對(duì)對(duì)偶問題（P）和（D）中，若其中一個(gè)問題可行但目標(biāo)函數(shù)無界，則另一個(gè)問題無可行解；反之不成立。這也是對(duì)偶問題的無界性。,2020/8/3,-第2章 對(duì)偶問題-,-17-,（2）最優(yōu)性：,若 X0原問題可行解，Y0對(duì)偶問題可行解，且 CX0 = Y0 b 則 X0原問題最優(yōu)解， Y0對(duì)偶問題最優(yōu)解 證明：設(shè) X* 原問題最優(yōu)解， Y* 對(duì)偶問題最優(yōu)解 則 CX0 CX* Y* b Y0 b 但 CX0 = Y0 b， CX0 = CX* = Y* b = Y0 b X0 = X* ， Y

10、0 = Y* 即 X0原問題最優(yōu)解， Y0對(duì)偶問題最優(yōu)解 證畢。,若原問題及其對(duì)偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。,2020/8/3,-第2章 對(duì)偶問題-,-18-,（3）無界性,若原問題最優(yōu)解無界，則對(duì)偶問題無可行解 證：有性質(zhì)1，C X0 Y0 b，當(dāng) CX0 時(shí)，則不可能存在Y0，使得 C X0 Y0 b 。 注：逆定理不成立，即 如果原問題（對(duì)偶問題）無可行解，那么 對(duì)偶問題（或原問題）“解無界”不成立。,2020/8/3,-第2章 對(duì)偶問題-,-19-,（4）強(qiáng)對(duì)偶性（對(duì)偶定理）,若原問題有最優(yōu)解，則對(duì)偶問題一定有最優(yōu)解， 且有 z max = w

11、 min 證： 由 = C- CB B-1 A 0 令 CBB-1 = Y * ，得 Y * A C -Y * = -CBB-1 0， Y * 0 因此， Y *是對(duì)偶問題的可行解， 又 CX * = CB (B-1 b) = CB B-1b = Y * b Y *是對(duì)偶問題的最優(yōu)解。,還可推出另一結(jié)論：若（LP）與（DP）都有可行解，則兩者都有最優(yōu)解，若一個(gè)問題無最優(yōu)解，則另一問題也無最優(yōu)解。,2020/8/3,-第2章 對(duì)偶問題-,-20-,Max z=CX st. AX b X 0,Max z=CX st. AX +Xs = b X 0,標(biāo)準(zhǔn)形,Max z=CBXB+CNXN+0XS s

12、t.BXB+NXN+IXS=b ，XB,XN,XS 0,改寫,B-1存在,Max z=CBXB+CNXN+0XS st. B-1BXB+ B-1NXN+ B-1I XS= B-1 bXB,XN,XS 0,左乘B-1,LP模型矩陣變換：,|B|0，,（XB+ B-1NXN+ B-1 XS= B-1 b）,2020/8/3,-第2章 對(duì)偶問題-,-21-,單純形法的矩陣描述：,XB,XN,XS,B,N,I,I,N,B-1,b,b,XS,XB,CB,CN,0,CB,CN,0,= C- CB B-1 A0,0,N,S,xj,cj,pj,0,pj,j,cj,XB= b = B-1 b,N = B-1 N

13、,N = CN -CBB-1 N 0,CB,S = -CB B-1 0,初始表,最終表,A=B N I,2020/8/3,-第2章 對(duì)偶問題-,-22-,（5）互補(bǔ)松弛性,n 若 y i * 0, 則 aij xj* = bi j=1 n 若 a ij xj* bi , 則 y i* = 0 j=1,n n m m 證： cj x j* = ( a ij y i* ) xj* = bi y i* j=1 j=1 i =1 i =1,n m m ( a ij y i* ) xj* - bi y i* =0 j=1 i =1 i =1,m n ( a ij xj* - bi ）y i* =0 i

14、=1 j=1, 當(dāng) y i*0, a ij xj* - bi =0, 即 a ij xj* = bi,當(dāng) a ij xj* - bi 0, y i*=0,j=1,j=1,j=1,n,n,n,2020/8/3,-第2章 對(duì)偶問題-,-23-,設(shè)X0和Y0分別是P問題 和 D問題 的可行解，則它們分別是最優(yōu)解的充要條件是：,其中：Xs、Ys為松弛變量,證明：（LP）和（LD）標(biāo)準(zhǔn)化為：,則有:,2020/8/3,-第2章 對(duì)偶問題-,-24-,必要性：,則,于是,所以,充分性：若,若 為最優(yōu)解,所以 為最優(yōu)解,則,2020/8/3,-第2章 對(duì)偶問題-,25,該性質(zhì)給出了已知一個(gè)問題最優(yōu)解求另一個(gè)

15、問題最優(yōu)解的方法，即已知Y*求X *或已知X *求Y *,互補(bǔ)松弛條件,由于變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系： 若Y * 0，則Xs必為0；若X * 0，則Ys必為0 利用上述關(guān)系，建立對(duì)偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。,例 已知線性規(guī)劃,其對(duì)偶問題的最優(yōu)解為Y * =(0,-2)，求原問題的最優(yōu)解。,解: 對(duì)偶問題是,標(biāo)準(zhǔn)化,設(shè)原問題最優(yōu)解為X * (x1，x2 ，x3)T ,由互補(bǔ)松弛性定理可知，X *和 Y *滿足：,將Y *帶入由方程可知，y3y50，y41。,y2=-20 x50 又y4=10 x20,將x2，x5分別帶入原問

16、題約束方程中，得：,解方程組得：x1=-5,x3=-1, 所以原問題的最優(yōu)解為,X * =(-5,0,-1)，最優(yōu)值z(mì)=-12,例2:,2020/8/3,-第2章 對(duì)偶問題-,-28-,解：對(duì)偶問題為,將y1，y2代入，知(2), (3), (4)為嚴(yán)格不等式, x2 = x3 = x4 = 0,由y1，y20知原約束為等式:, x = (1, 0, 0, 0, 1)T , min W=5,2020/8/3,-第2章 對(duì)偶問題-,-29-,（6）單純形表中的對(duì)應(yīng)關(guān)系,原問題與其對(duì)偶問題的變量與解的對(duì)應(yīng)關(guān)系： 在單純形表中，原問題的松弛變量對(duì)應(yīng)對(duì)偶問題的變量，對(duì)偶問題的剩余變量對(duì)應(yīng)原問題的變量。

17、,max z= 2 x1 +3 x2 min w= 12y1 + 8y2 + 16y3 +12 y4 s.t 2 x1 +2 x2 12 s.t 2y1 + y2 + 4y3 +0 y4 2 x1 +2 x2 8 2y1 +2y2 + 0y3 +4 y4 3 4 x1 16 yi 0, i=1, 2, 3, 4 4 x2 12 x1 0 , x2 0,-y5 -y6 -y1 - y2 - y3 - y4,2020/8/3,-第2章 對(duì)偶問題-,-30-,原問題最優(yōu)表,對(duì)偶問題最優(yōu)表,原問題與對(duì)偶問題解的對(duì)應(yīng)關(guān)系小結(jié),32,原問題的檢驗(yàn)數(shù)行對(duì)應(yīng)對(duì)偶問題的一個(gè)基解。,證明： （LP）和（LD）標(biāo)準(zhǔn)

18、化為：,設(shè)B是原問題的一個(gè)可行基，于是A(B,N)，所以原問題可以改寫為：,33,當(dāng)求得原問題的一個(gè)解,其相應(yīng)檢驗(yàn)數(shù)為：,相應(yīng)地對(duì)偶問題可表示為：,令 ，并將它代入上式得：,思考題,判斷下列結(jié)論是否正確，如果不正確，應(yīng)該怎樣改正？,1）任何線性規(guī)劃都存在一個(gè)對(duì)應(yīng)的對(duì)偶線性規(guī)劃. 2）原問題第i個(gè)約束是“”約束，則對(duì)偶變量yi0. 3）互為對(duì)偶問題，或者同時(shí)都有最優(yōu)解，或者同時(shí)都無最優(yōu)解. 4）對(duì)偶問題有可行解，則原問題也有可行解. 5）原問題有多重解，對(duì)偶問題也有多重解. 6）對(duì)偶問題有可行解，原問題無可行解，則對(duì)偶問題具有無界解. 7）原問題無最優(yōu)解，則對(duì)偶問題無可行解. 8）對(duì)偶問題不可行

19、，原問題可能無界解. 9）原問題與對(duì)偶問題都可行，則都有最優(yōu)解. 10）原問題具有無界解，則對(duì)偶問題不可行. 11）對(duì)偶問題具有無界解，則原問題無最優(yōu)解. 12）若X*、Y*是原問題與對(duì)偶問題的最優(yōu)解，則X*=Y*.,2020/8/3,-第2章 對(duì)偶問題-,-35-,2.4 影子價(jià)格(Shadow price),1、 對(duì)偶變量yi可理解為對(duì)一個(gè)單位第 i種資源的估價(jià)，稱為影子價(jià)格，但并非市場(chǎng)價(jià)格。,假設(shè)有原問題和對(duì)偶問題如下：,2、 對(duì)偶變量yi 的值（即影子價(jià)格）表示第i種資源數(shù)量變化一個(gè)單位時(shí)，目標(biāo)函數(shù)的增量，是一種邊際價(jià)格。,對(duì)bi求偏導(dǎo),說明yi的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下

20、，bi每增加一個(gè)單位時(shí)目標(biāo)函數(shù)Z的增量。,2020/8/3,36,資源增加一個(gè)單位時(shí)，最優(yōu)解及目標(biāo)函數(shù)值的變化,2020/8/3,-第2章 對(duì)偶問題-,-37-,生產(chǎn)過程中如果某種資源 未得到充分利用時(shí)，該種資源的影子價(jià)格為零；經(jīng)濟(jì)解釋：資源未用完，再增加對(duì)目標(biāo)函數(shù)也無貢獻(xiàn)。 當(dāng)資源的影子價(jià)格不為零時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完畢。經(jīng)濟(jì)解釋：該種資源用盡，再購進(jìn)用于擴(kuò)大生產(chǎn)可增加總利潤。,在對(duì)偶問題的互補(bǔ)松弛性質(zhì)中有,影子價(jià)格是一種機(jī)會(huì)成本 影子價(jià)格是在資源最優(yōu)利用條件下對(duì)單位資源的估價(jià)，這種估價(jià)不是資源實(shí)際的市場(chǎng)價(jià)格。因此，從另一個(gè)角度說，它是一種機(jī)會(huì)成本，可用于指導(dǎo)資源的購入與賣出。,若

21、第i 種資源的單位市場(chǎng)價(jià)格為mi ，則有當(dāng)yi* mi 時(shí)，企業(yè)愿意購進(jìn)這種資源，單位純利為yi*mi ，則有利可圖；如果yi* mi ，則企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利miyi* ，否則，企業(yè)無利可圖，甚至虧損。,結(jié)論：若yi* mi 則購進(jìn)資源i，可獲單位純利yi*mi 若yi* mi則轉(zhuǎn)讓資源i ，可獲單位純利miyi,單純形表檢驗(yàn)數(shù),單純形表中的檢驗(yàn)數(shù)與影子價(jià)格,其中cj表示第j種產(chǎn)品的價(jià)格; 表示生產(chǎn)該種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和,即產(chǎn)品的隱含成本。,當(dāng)產(chǎn)值大于隱含成本時(shí)，即 ，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可在計(jì)劃中安排；否則 ，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該

22、產(chǎn)品。,2020/8/3,40,2.5 對(duì)偶單純形法,在單純形表中， 列對(duì)應(yīng)原問題的基可行解， 行 對(duì)應(yīng)對(duì)偶問題的一個(gè)基解（不一定可行），當(dāng) 時(shí)， 在檢驗(yàn)數(shù)行就得到對(duì)偶問題的基可行解，此時(shí)兩個(gè)問題的目 標(biāo)函數(shù)值相等 ，由最優(yōu)性條件知，兩個(gè) 問題都達(dá)到了最優(yōu)解。,單純形法：找一個(gè)初始基可行解，保持b列為正，通過迭代 找到下一個(gè)基可行解，使目標(biāo)函數(shù)值不斷增大，當(dāng)檢驗(yàn)數(shù)行 全部小于等于零時(shí)，達(dá)到最優(yōu)解。,41,原問題基可行解 最優(yōu)解判斷,對(duì)偶問題的可行解,對(duì)偶問題 最優(yōu)解判斷,對(duì)偶單純形法 基本思路,單純形法的基本思路：,對(duì)偶單純形法是求解線性規(guī)劃的另一個(gè)基本方法。它是根據(jù)對(duì)偶原理和單純形法原理而設(shè)

23、計(jì)出來的，因此稱為對(duì)偶單純形法。不要簡單理解為是求解對(duì)偶問題的單純形法。,找出一個(gè)DP的可行基,LP是否可行 （XB 0）,保持DP為可行解情況下轉(zhuǎn)移到LP的另一個(gè)基本解,最優(yōu)解,是,否,循 環(huán),結(jié)束,根據(jù)對(duì)偶問題的對(duì)稱性，保持對(duì)偶問題的解是可行解，即檢驗(yàn)數(shù)行非負(fù)，而原問題從非可行解開始，逐步迭代到基本可行解，也使原問題和對(duì)偶問題達(dá)到最優(yōu)解。,2020/8/3,-第2章 對(duì)偶問題-,-43-,2.5 對(duì)偶單純形法,由于單純表中同時(shí)反映原問題與對(duì)偶問題的最優(yōu)解，故可以從求對(duì)偶問題最優(yōu)解角度求解LP模型。,例：,min z=2x1+3x2 max z=-2x1-3x2+0 x3 +0 x4 s.t

24、 x1+x23 標(biāo)準(zhǔn)化 s.t x1+x2-x3=3 x1+2x2 4 x1+2x2-x4=4 x10, x20 xj 0, (j=1,2,3,4),max z=-2x1-3x2+0 x3 +0 x4 s.t - x1-x2+x3=-3 - x1-2x2+x4=-4 xj 0, (j=1,2,3,4),2020/8/3,-第2章 對(duì)偶問題-,-44-,Cj ,x1,x2,x3,x4,XB,b,CB,-1 -1 1 0 -1 -2 0 1,-2 -3 0 0,-3 -4,x3 x4,00,cj - zj,-2,-3,0,0,-1/2 0 1 -1/2 1/2 1 0 -1/2,x3 x2,-1

25、2,cj - zj,-1/2 0 0 -3/2,0 -3,1 0 -2 1 0 1 1 -1,x1 x2,21,cj - zj,0 0 -1 -1,-2 -3,列單純表計(jì)算：,2020/8/3,-第2章 對(duì)偶問題-,-45-,對(duì)偶單純形法步驟：,1.列初始單純形表，使得所有檢驗(yàn)數(shù)j 0 ； 2.出基變量：取min bi0 = bl x(l) 3.入基變量：min |alk0= xk 4.主元素： alk 5.迭代：同單純形法，新單純表中pk化為單位向量,cj-zj,alj,說明： 10 使用對(duì)偶單純形法時(shí)，初始表中檢驗(yàn)數(shù)必須全部為j 0，即使得其對(duì)偶問題為可行解， 20 為便于說明，這里采取從

26、原問題角度敘述迭代步驟。,2020/8/3,46,1、 為何只考慮 行中 的元素對(duì)應(yīng)的變量進(jìn)基？為使迭代后的基變量取正值。,2、為何采用最小比值規(guī)則選擇進(jìn)基變量？為了使得迭代后的多偶問題解仍為可行解（檢驗(yàn)數(shù)行仍為非正）,3、 原問題無可行解的判別準(zhǔn)則：當(dāng)對(duì)偶問題存在可行解時(shí)， 若有某個(gè) ，而所有 ，則原問題無可行解，對(duì)偶 問題目標(biāo)值無界。 因?yàn)榈趓行的約束方程即為： 其中 ， ，因此不可能存在 使上式成 立。也即原問題無可行解。,2020/8/3,-第2章 對(duì)偶問題-,-47-,對(duì)偶單純形法的優(yōu)點(diǎn)： 不需要人工變量； 對(duì)變量較少，而約束條件很多的LP ,可以先將其變成LD，再運(yùn)用對(duì)偶單純形法計(jì)

27、算； 在靈敏度分析中，有時(shí)需要用對(duì)偶單純形法處理簡化。,用對(duì)偶單純形法求解LD,LP,LD,最優(yōu)解=？ 最優(yōu)值=？,練習(xí)（對(duì)偶單純形法求解）,2020/8/3,-第2章 對(duì)偶問題-,-52-,2.6 靈敏度分析,1靈敏度分析的概念： 當(dāng)某一個(gè)參數(shù)發(fā)生變化后，引起最優(yōu)解如何改變的分析。 可以改變的參數(shù)有： bi約束右端項(xiàng)的變化，通常稱資源的改變； cj 目標(biāo)函數(shù)系數(shù)的變化，通常稱市場(chǎng)條件的變化； pj 約束條件系數(shù)的變化，通常稱工藝系數(shù)的變化； 其他的變化有：增加一種新產(chǎn)品、增加一道新的工序等。,2020/8/3,-第2章 對(duì)偶問題-,-53-,2. 靈敏度分析的一般步驟： (1) 將參數(shù)的改變

28、經(jīng)計(jì)算后反映到最終單純形表中； (2) 檢查原問題和對(duì)偶問題是否仍為可行解； (3) 按照下表對(duì)應(yīng)情況，決定下一步驟。,2020/8/3,-第2章 對(duì)偶問題-,-54-,3分析原理： 借助最終單純形表，將變化后的結(jié)果按下述基本原則反映到最終表中去。,（1）bi變化： （b+b）=B-1 （b+b） = B-1 b+ B-1 b = b+B-1 b （2）pj變化：（pj+ pj ）= B-1 （pj+ pj ） = B-1 pj+ B-1 pj = pj + B-1 pj （3）cj變化：直接反映到最終表中，計(jì)算檢驗(yàn)數(shù)。 （4）增加一個(gè)約束方程：直接反映到最終表中。 （5）增加新產(chǎn)品：仿照pj

29、變化。,2020/8/3,55,一、C 的變化分析 C的變化只影響檢驗(yàn)數(shù)。,例、設(shè)有如下的線性規(guī)劃模型 試分析 分別在什么范圍變化時(shí)，最優(yōu)解不變？,2020/8/3,56,解：問題的最終單純形表如下：,2020/8/3,57,1、當(dāng) 變化時(shí)，假設(shè) ，則要使得問題的最優(yōu)解 保持不變，則檢驗(yàn)數(shù)行 即可，即要求,2、當(dāng) 變化時(shí)，假設(shè) ，則要使得問題的最優(yōu)解 保持不變，則檢驗(yàn)數(shù)行 即可，即要求,2020/8/3,58,二、b 的變化分析 b的變化將只影響原問題的基可行解，即最終表中的b列數(shù)值。,例、設(shè)有如下的線性規(guī)劃模型 試分析 分別在什么范圍變化時(shí)，最優(yōu)基不變？,2020/8/3,59,解：將 重新

30、計(jì)算后填入問題的最終單純形表：,1、當(dāng) 變化時(shí)，假設(shè) ，則問題的解變?yōu)?填入下表，得,2020/8/3,60,要使得最優(yōu)基保持不變，則b列數(shù)值 即可，即要求,同理可得 的變化范圍是： 的變化范圍是：,2020/8/3,61,三、增加一個(gè)變量的變化分析 增加一個(gè)變量，在方程組（矩陣A）中就要增加一個(gè)系數(shù)列，在原來的最終表中也要添加一列 ，檢驗(yàn)數(shù)也要計(jì)算，其余部分不受影響。如果檢驗(yàn)數(shù)行仍 ，則最優(yōu)解不變，否則繼續(xù)迭代尋找最優(yōu)。 一般分析步驟： 1、計(jì)算增加的新變量系數(shù)列 在原最終表中的結(jié)果 ； 2、計(jì)算新變量對(duì)應(yīng)的檢驗(yàn)數(shù) ； 3、根據(jù) 的符號(hào)判斷是否仍是最優(yōu)解，若是，最優(yōu)解不變；若不是，繼續(xù)求解。

31、,2020/8/3,62,例、設(shè)有如下的線性規(guī)劃模型 現(xiàn)增加變量 ，其對(duì)應(yīng)系 數(shù)列為 ，價(jià)值 系數(shù) ，請(qǐng)問最優(yōu)解是否改變？,解：最終表,2020/8/3,63,新變量的檢驗(yàn)數(shù)及系數(shù)列分別為：,填入表中，易知未達(dá)最優(yōu)，繼續(xù)迭代求解。,2020/8/3,64,已達(dá)最優(yōu)。最優(yōu)解為 最優(yōu)目標(biāo)值,2020/8/3,65,四、增加一個(gè)約束條件的變化分析 增加一個(gè)約束條件，相當(dāng)于增加一道工序。 分析方法: 1）先將原最優(yōu)解帶入此新約束，若滿足條件，說明此約束未起作用，原最優(yōu)解不變； 2）否則，將新約束加入到最終表中，繼續(xù)分析。,例、在上例中添加新約束 ，分析最優(yōu)解的變化情況。 解：因?yàn)閷⒃顑?yōu)解 帶入此約束

32、， 不滿足約束，原解已不是最優(yōu)，繼續(xù)分析。,2020/8/3,66,6,x,2020/8/3,67,已達(dá)最優(yōu)。最優(yōu)解為 最優(yōu)目標(biāo)值,2020/8/3,-第2章 對(duì)偶問題-,-68-,3計(jì)算示例：,max z= 2 x1 +3 x2 s.t 2 x1 +2 x2 12 x1 +2 x2 8 4 x1 16 4 x2 12 x1 0 , x2 0,例：已知某線性規(guī)劃模型及最終的單純表如下：,問：（1）若b2增加8個(gè)單位，最優(yōu)解如何變化？ （2）若c2還可增加2個(gè)單位，最優(yōu)解如何改變？ （3）若引進(jìn)一個(gè)新變量（產(chǎn)品）y，其目標(biāo)函 數(shù)系數(shù)為 cy=5，系數(shù)列向量為py=3 2 6 3T，問最優(yōu)解是否會(huì)

33、改變？,cj 2 3 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x6,0 x3 0 2 x1 4 0 x6 4 3 x2 2,0 0 1 -1 -0.25 0 1 0 0 0 0.25 0 0 0 0 -2 0.5 1 0 1 0 0.5 -0.125 0,cjzj,0 0 0 -1.5 -0.125 0,2020/8/3,-第2章 對(duì)偶問題-,-69-,解：（1）,（b+b）=B-1 b+ B-1 b = b+B-1 b =0 4 4 2T + -8 0 -16 4 T = -8 4 -12 6 T,B-1 b =,1 -1 -0.25 0 0 0 0.25 0 0 -2

34、 0.5 1 0 0.5 -0.125 0,0 8 0 0,=,-8 0 -16 4, 利用對(duì)偶單純形法繼續(xù) 求最優(yōu)解。,（2）當(dāng)cj變化時(shí)，=CCB B-1 A，列出單純形表，重新求出檢驗(yàn)數(shù)，如表中所示：,（3）增加y時(shí)， y= cy- CB B-1 py=5- (0 1.5 0.125 0) 3 2 6 3T =1.250 選擇y作入基變量， py= B-1 py= =-0.5 1.5 2 0.25T,繼續(xù)迭代：,2020/8/3,-第2章 對(duì)偶問題-,-70-,cj 2 3 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x6,0 x3 -8 2 x1 4 0 x6 -12

35、 3 x2 6,0 0 1 -1 -0.25 0 1 0 0 0 0.25 0 0 0 0 -2 0.5 1 0 1 0 0.5 -0.125 0,cjzj,0 0 0 -1.5 -0.125 0,0 x3 -2 2 x1 4 0 x4 6 3 x2 3,0 0 1 0 -0.5 -0.5 1 0 0 0 0.25 0 0 0 0 1 -0.25 -0.5 0 1 0 0 0 0.25,cjzj,0 0 0 0 -0.5 -0.75,0 x5 4 2 x1 3 0 x6 7 3 x2 3,0 0 -2 0 1 1 1 0 0.5 0 0 -0.25 0 0 -0.5 1 0 -0.25 0 1

36、 0 0 0 0.25,cjzj,0 0 -1 0 0 -0.25,返回,右端項(xiàng)變化分析單純形表：,2020/8/3,-第2章 對(duì)偶問題-,-71-,cj 2 5 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x6,0 x3 0 2 x1 4 0 x6 4 5 x2 2,0 0 1 -1 -0.25 0 1 0 0 0 0.25 0 0 0 0 -2 0.5 1 0 1 0 0.5 -0.125 0,cjzj,0 0 0 -2.5 0.125 0,0 x3 2 2 x1 2 0 x5 8 5 x2 3,0 0 1 -2 0 0.5 1 0 0 1 0 -0.5 0 0 0 -4

37、 1 2 0 1 0 0 0 0.25,cjzj,0 0 0 -2 0 -0.25,返回,Cj 變化分析單純形表：,2020/8/3,-第2章 對(duì)偶問題-,-72-,cj 2 3 0 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x6 y,0 x3 0 2 x1 4 0 x6 4 3 x2 2,0 0 1 -1 -0.25 0 -0.5 1 0 0 0 0.25 0 1.5 0 0 0 -2 0.5 1 2 0 1 0 0.5 -0.125 0 0.25,cjzj,0 0 0 -1.5 -0.125 0 1.25,0 x3 1 2 x1 1 5 y 2 3 x2 1.5,0 0

38、 1 -1.5 -0.125 0.25 0 1 0 0 1.5 -0.125 -0.75 0 0 0 0 -1 0.25 0.5 1 0 1 0 0.75 -0.1875 -0.125 0,cjzj,0 0 0 -0.25 -0.4375 -0.625 0,增加新產(chǎn)品（變量y）變化分析單純形表：,2020/8/3,-第2章 對(duì)偶問題-,-73-,2.7 參數(shù)線性規(guī)劃,1. 概念：研究目標(biāo)函數(shù)值隨某一參數(shù)變化的規(guī)律及最優(yōu)解相應(yīng)的變化。 算法：先令變化量=0，當(dāng)多個(gè)參數(shù)同時(shí)變化時(shí)，可以引入一個(gè)參數(shù)來表示這種變化。如：b列多個(gè)值發(fā)生變化時(shí)，可表示成 再考察隨著的增加引起解的變化情況。 3. 最后，畫

39、出目標(biāo)值隨的變化所形成的曲線。,2020/8/3,74,例：求解下述參數(shù)線性規(guī)劃問題:,解：求得 時(shí)最終單純形表并將參數(shù)的變化填入表中 ：,2020/8/3,75,2、 是臨界點(diǎn)，當(dāng) 時(shí)， 所以選擇 作為進(jìn)基變量，迭代一步得到：,1、由表可知，當(dāng) 時(shí)，即 最優(yōu)解不變 。目標(biāo)函數(shù)值 是：,2020/8/3,76,3、由上表可知，當(dāng) 時(shí)，即 最優(yōu)解不變 。目標(biāo)函數(shù)值 是,4、 是臨界點(diǎn)，當(dāng) 時(shí)， 所以選擇 作為進(jìn)基變量，迭代一步得到：,2020/8/3,77,5、由上表可知，當(dāng) 時(shí)，最優(yōu)解不再變化。 目標(biāo)函數(shù)值是,6、 是臨界點(diǎn)，當(dāng) 時(shí)， 所以選擇 作為進(jìn)基變量，迭代一步得到：,此時(shí)無論 如何增加

40、，檢驗(yàn)數(shù)始終為負(fù)，最優(yōu)解不再變化。 目標(biāo)函數(shù)值是,2020/8/3,78,15,24,34,2020/8/3,79,例：某文教用品廠利用原材料白坯紙生產(chǎn)原稿紙、日記本、練習(xí)本三種產(chǎn)品，該廠現(xiàn)有工人100人，每天白坯紙供應(yīng)量限制是3萬kg，如果單獨(dú)生產(chǎn)各種產(chǎn)品時(shí)，每人每天生產(chǎn)原稿紙30捆、日記本30打、練習(xí)本30箱。已知原材料消耗為每捆原 稿紙用白坯紙 公斤，每打日記本用白坯紙 公斤， 每箱練習(xí)本用白坯紙 公斤。又知每捆原稿紙可盈利2 元，每打筆記本盈利3元，每箱練習(xí)本盈利1元。試決定 （1）在現(xiàn)有生產(chǎn)條件下，工廠盈利最大的生產(chǎn)方案； （2）如果白坯紙的供應(yīng)數(shù)量不變，當(dāng)工人人數(shù)不足時(shí)可招收臨時(shí)工，其工資支出為每人每天40元，問該廠要不要招收臨時(shí)工，最多招多少？,2020/8/3,80,例：設(shè)該廠每天生產(chǎn)原稿紙、日記本、練習(xí)本的數(shù)量分別是 ， 表示招收臨時(shí)工的數(shù)量。則有下列模 型：,時(shí)，得現(xiàn)有條件下的最優(yōu)生產(chǎn)計(jì)劃，如下表。,2020