第2章線性規(guī)劃的對偶理論與靈敏度分析

1、.第第2章章 線性規(guī)劃的對偶理論與靈敏度分析線性規(guī)劃的對偶理論與靈敏度分析2.1 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)2.3 影子價格影子價格2.4 對偶單純形法對偶單純形法2.5 靈敏度分析靈敏度分析.2.1.1 對偶問題的提出對偶問題的提出例例1 第一章例第一章例1中美佳公司利用公司資源生產(chǎn)兩種家中美佳公司利用公司資源生產(chǎn)兩種家電產(chǎn)品時，其線性規(guī)劃問題為：電產(chǎn)品時，其線性規(guī)劃問題為：12max2zxxs.t.2515x 126224xx125xx12,0 x x (P).2.1.1 對偶問題的提出對偶問題的提出這時，如果有另一家公司想購買美佳公司

2、的資源全部這時，如果有另一家公司想購買美佳公司的資源全部資源，那么它至少應(yīng)出多少的價格，才會使美佳公司資源，那么它至少應(yīng)出多少的價格，才會使美佳公司愿意出讓？愿意出讓？解：設(shè)其購買三種資源的價格分別為解：設(shè)其購買三種資源的價格分別為y1, y2, y3, 總花費總花費為為w，則：，則：123min15245wyyy2312362521 yyyyys.t.y1, y2, y30 (D).2.1.1 對偶問題的提出對偶問題的提出123min15245wyyy2312362521 yyyyys.t.y1, y2, y3012max2zxxs.t.2515x 126224xx125xx12,0 x x

3、 (P) (D).2.1.1 對偶問題的提出對偶問題的提出1 122max.nnzc xc xc x11 1122111.jjnna xa xa xa xb21 1222222.jjnna xa xa xa xb1 122.mmmjjmnnma xaxa xa xb.s.t.0(1,., )jxjn1y2ymy.1122.jjmjmja ya ya yc.2.1.1 對偶問題的提出對偶問題的提出1 122min.mmwb xb yb ys.t.111212111.iimma ya ya ya yc121222222.iimma ya ya yayc0(1,2,.,)jyim.1122.nnin

4、imnmna ya ya yayc1x2xmx.1 122.iiinnia xa xa xb.2.1.2 對偶問題的對稱形式對偶問題的對稱形式max. .0zCXAXbstX(P)min. .0wYbYAcstY(D)123(,)Yy yy對稱式對偶模型：對稱式對偶模型：（1）其變量均具有非負約束）其變量均具有非負約束（2）約束條件當目標函數(shù)求極大時均取）約束條件當目標函數(shù)求極大時均取“ ”（3）約束條件當目標函數(shù)求極大時均?。┘s束條件當目標函數(shù)求極大時均取“ ”.2.1.2 對偶問題的對稱形式對偶問題的對稱形式例例2：寫出下面問題的對偶規(guī)劃：寫出下面問題的對偶規(guī)劃maxZ= 5X1 +6X2

5、 3X1 -2X2 74X1 +X2 9X1 , X2 0minW=7y1 +9y23y1+4y2 5 -2y1 +y2 6y1, y2 0.2.1.2 對偶問題的對偶問題的“非對稱非對稱”形式形式原問題（或?qū)ε紗栴}）原問題（或?qū)ε紗栴}）對偶問題（或原問題）對偶問題（或原問題）目標函數(shù)目標函數(shù) max zn個個00無約束無約束變量變量m個個 =約束條件約束條件約束條件右端項約束條件右端項目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)目標函數(shù)目標函數(shù) min wn個個=約束條件約束條件變量變量m個個00無約束無約束約束條件右端項約束條件右端項目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù).2.1.2 對偶問題的對稱

6、形式對偶問題的對稱形式例例3：寫出下面問題的對偶規(guī)劃：寫出下面問題的對偶規(guī)劃1234min235zxxxx1234235xxxx2134224xxxx2413236xxxx12340;,0,xx xx無約束無約束.2.1.2 對偶問題的對稱形式對偶問題的對稱形式解：解：123max546wyyy1232322yyx213223xyy1233325yyy 1230;0,yyy1231323yyy無約束無約束.2.1.2 對偶問題的一般形式對偶問題的一般形式練習(xí)：練習(xí)： 寫出下面線性規(guī)劃的對偶規(guī)劃模型寫出下面線性規(guī)劃的對偶規(guī)劃模型12max23zxxs.t.1223xx1225xx 1231xx1

7、20,xx無約束無約束123min224zxxxs.t.1232342xxx123,0,x xx無約束無約束1232333xxx1232432xxx.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)1. 對稱性對稱性 對偶問題的對偶問題是原問題對偶問題的對偶問題是原問題 （P）與（）與（D）互為對偶，沒有要求原問題一定）互為對偶，沒有要求原問題一定要是要是max型，對偶問題一定要是型，對偶問題一定要是min型型2. 弱對偶性弱對偶性 設(shè)設(shè)X, Y分別為分別為(P), (D)的任一可行解，則的任一可行解，則CX Yb證：因為證：因為X, Y分別為分別為(P), (D)的可行解，那么有：的可行解，那么

8、有：AX b YAXYb YA C YAX CX CX Yb.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)2. 弱對偶性弱對偶性 由上述弱對偶性可推出：由上述弱對偶性可推出：若若(P)為無界解，則為無界解，則(D)無可行解無可行解若若(D)為無界解，則為無界解，則(P)無可行解無可行解CXYb？課本中關(guān)于弱對偶性的推論如何理解？課本中關(guān)于弱對偶性的推論如何理解.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)推論推論1 原問題任一可行解的目標函數(shù)值是其對偶問題原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界，反之，對偶問題任一可行解的目目標函數(shù)值的下界，反之，對偶問題任一可行解的目標函數(shù)值

9、是其原問題目標函數(shù)值的上界。標函數(shù)值是其原問題目標函數(shù)值的上界。推論推論2 若原問題有可行解且目標函數(shù)值無界，則其對若原問題有可行解且目標函數(shù)值無界，則其對偶問題無可行解；反之，對偶問題有無界解，原問題偶問題無可行解；反之，對偶問題有無界解，原問題無可行解。（但逆向不成立）無可行解。（但逆向不成立）推論推論3 若原問題有可行解，對偶問題無可行解，則原若原問題有可行解，對偶問題無可行解，則原問題目標函數(shù)值無界；反之，對偶問題有可行解，而問題目標函數(shù)值無界；反之，對偶問題有可行解，而原問題無可行解，則對偶問題的目標函數(shù)值無界。原問題無可行解，則對偶問題的目標函數(shù)值無界。.2.2 對偶問題的基本性質(zhì)

10、對偶問題的基本性質(zhì)3. 最優(yōu)性最優(yōu)性 設(shè)設(shè) ， 分別為分別為(P)與與(D)的可行解，且的可行解，且 ，則則 ，證：對任一可行解證：對任一可行解X, 由弱對偶性由弱對偶性 ，故故 ，同理，同理XYCXYb*XX*YYCXYbCX*XX*YY.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)4. 強對偶性（對偶定理）強對偶性（對偶定理） 若若(P)有最優(yōu)解，則有最優(yōu)解，則(D)也有最優(yōu)解，且二者最優(yōu)值也有最優(yōu)解，且二者最優(yōu)值相等相等證：對證：對(P)增加松弛變量增加松弛變量Xs, 化為：化為：max0szCXXs.t.,0sX X sAXIXb.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)4. 強對

11、偶性（對偶定理）強對偶性（對偶定理） 證證：（續(xù)）：（續(xù)）設(shè)其最優(yōu)基為設(shè)其最優(yōu)基為B, 終表為：終表為：cj C 0CB XB B-1b B-1A B-1I 檢驗數(shù)檢驗數(shù)C - CBB-1A 0 CBB-1IC - CBB-1A 00 CBB-1I 0取取1BYC B.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)4. 強對偶性（對偶定理）強對偶性（對偶定理） 證證：（續(xù)）：（續(xù)）則則 滿足：滿足：1BYC B0CYA00YYAC0Y 是是(D)的可行解，且的可行解，且 ，由最有性定理，可得：由最有性定理，可得： 1*BYbC B bzY1*BYYC B.2.2 對偶問題的基本性質(zhì)對偶問題的基本

12、性質(zhì)4. 強對偶性（對偶定理）強對偶性（對偶定理） (1)由性質(zhì)由性質(zhì)4可知，對偶問題最優(yōu)解的表可知，對偶問題最優(yōu)解的表達式達式Y(jié)* = ?(2)求求Y*是否要重新求解是否要重新求解(D) CBB-1 不需要，可以從原問題不需要，可以從原問題(P)的單純形終的單純形終表獲得表獲得.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)例如，在前面美佳公司的生產(chǎn)計劃中，其單純形終表為：例如，在前面美佳公司的生產(chǎn)計劃中，其單純形終表為： 2 1 0 0 0 x1 x2 x3 x4 x5 0 x3 15/22 x1 7/21 x2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0

13、 -1/4 3/2 0 0 0 -1/4 -1/2jjcBXBC1B bi.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)由上表可直接得到問題由上表可直接得到問題(P)的最優(yōu)解和最優(yōu)值：的最優(yōu)解和最優(yōu)值： X* = (7/2, 3/2, 15/2, 0, 0)T Z* = 8.5根據(jù)強對偶性可得：根據(jù)強對偶性可得： Y* = (0, 1/4, 1/2) Y* = 8.5.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)5. 互補松弛性（松緊定理）互補松弛性（松緊定理）設(shè)設(shè) ， 分別為分別為(P)和和(D)的可行解，則：的可行解，則： , 是最優(yōu)解是最優(yōu)解 其中，其中， ， 為最優(yōu)解中松弛變量部分。為

14、最優(yōu)解中松弛變量部分。XYXY0ssYXY XsXsY.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)證：證：將將(P)、(D)的約束條件化為等式：的約束條件化為等式：sAXIXbsYA Y IC因為因為 ， 是最優(yōu)解，所以是最優(yōu)解，所以 ，即：，即：XYCXYb()()ssYA Y I XY AXIXssYAXY XYAXYX而而0,0ssY XYX故只有：故只有：0ssY XYX.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)原始問題變量原始問題變量原始問題的松弛變量原始問題的松弛變量1xjxnx1nxn ixn mx1mymjym ny1yiymy對偶問題變量對偶問題變量對偶問題的松弛變量對

15、偶問題的松弛變量0jmjx y0in iy x在如上的一對變量中，其中一個大于在如上的一對變量中，其中一個大于0，另一個一定等于，另一個一定等于0.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)在線性規(guī)劃問題中在線性規(guī)劃問題中（1）如果對應(yīng)于某一約束條件的對偶變量值為）如果對應(yīng)于某一約束條件的對偶變量值為非非0，則該約束條件取嚴格等式，則該約束條件取嚴格等式（2）如果約束條件取嚴格不等式，則其對應(yīng)的）如果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為對偶變量一定為0.2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)例例4 已知如下線性規(guī)劃問題已知如下線性規(guī)劃問題12345min23523wxxxxx

16、s.t.12345234xxxxx12345233xxxxx已知其對偶問題最優(yōu)解已知其對偶問題最優(yōu)解 , , 試利用對偶理論，找出原問題的最優(yōu)解。試利用對偶理論，找出原問題的最優(yōu)解。 *145y *235y *5z .2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)解：先寫出其對偶問題解：先寫出其對偶問題12max43zyys.t.1222yy123yy12235yy122yy1233yy12,0y y (1)(2)(3)(4)(6)將將 ， 的值代入的值代入左邊左邊5個約束條件中，個約束條件中，得約束（得約束（2），（），（3），），（4）為嚴格等式，）為嚴格等式，由互補松弛性定理得：由互補松弛

17、性定理得：*1y*2y234xxx又又 , ，所以，所以對應(yīng)于原問題的約束對應(yīng)于原問題的約束條件取等式條件取等式*1y*20y .2.2 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì)所以：所以：12345234xxxxx12345233xxxxx1534xx1523xx*(1,0,0,0,1)TX .2.3 對偶問題的經(jīng)濟解釋對偶問題的經(jīng)濟解釋2.3.3 對偶松弛變量的經(jīng)濟解釋對偶松弛變量的經(jīng)濟解釋 產(chǎn)品的差額成本產(chǎn)品的差額成本2.3.1 對偶問題最優(yōu)解的經(jīng)濟解釋對偶問題最優(yōu)解的經(jīng)濟解釋 資源的影子價格資源的影子價格2.3.2 對偶約束的經(jīng)濟解釋對偶約束的經(jīng)濟解釋 產(chǎn)品的機會成本產(chǎn)品的機會成本2.3.

18、4 互補松弛關(guān)系的經(jīng)濟解釋互補松弛關(guān)系的經(jīng)濟解釋.2.3.1 影子價格影子價格根據(jù)前述對偶定理可知，對偶問題最優(yōu)解的表根據(jù)前述對偶定理可知，對偶問題最優(yōu)解的表達式達式Y(jié)* = CBB-1CBB-1 對偶問題的最優(yōu)解對偶問題的最優(yōu)解 買主的最低出價買主的最低出價CBB-1 原問題資源的影子價格原問題資源的影子價格 當該資源增加當該資源增加1單位時引起的總收入的增量單位時引起的總收入的增量 賣主的內(nèi)控價格賣主的內(nèi)控價格設(shè)設(shè)D的最優(yōu)解為的最優(yōu)解為Z*（注：與（注：與P最優(yōu)值相同）最優(yōu)值相同）, 則：則：*1 12 2.m mZY by by by b*iiZyb.2.3.1 影子價格影子價格例例5

19、請根據(jù)美佳公司生產(chǎn)計劃安排的單純形終表請根據(jù)美佳公司生產(chǎn)計劃安排的單純形終表指出：指出：資源設(shè)備資源設(shè)備A、B和調(diào)試工序的影子價格，并解釋和調(diào)試工序的影子價格，并解釋其經(jīng)濟意義其經(jīng)濟意義.2.3.1 影子價格影子價格例例5 美佳公司生產(chǎn)計劃安排的單純形終表如下：美佳公司生產(chǎn)計劃安排的單純形終表如下： 2 1 0 0 0 x1 x2 x3 x4 x5 0 x3 15/22 x1 7/21 x2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2jjcBXBC1B bi.2.3.1 影子價格影子價格解：解：1*0Ay設(shè)備

20、 臺時的影子價格 21*4y設(shè) 備 B臺 時 的 影 子 價 格 31*2y調(diào)試工序臺時的影子價格 即再增加設(shè)備即再增加設(shè)備A臺時，利潤不會增加臺時，利潤不會增加即再增加即再增加1個設(shè)備個設(shè)備B臺時，利潤增加臺時，利潤增加1/4元元即再增加即再增加1個調(diào)試臺時，利潤增加個調(diào)試臺時，利潤增加1/2元元.2.3.1 影子價格影子價格2515x 126224xx125xx3155152273622422 73522x30, y1=0 x4=0, y20 x5=0, y30.2.3.1 影子價格影子價格因為，影子價格只是表示某種資源在企業(yè)內(nèi)部的因為，影子價格只是表示某種資源在企業(yè)內(nèi)部的虛擬價格，而不等

21、于資源的市場價格虛擬價格，而不等于資源的市場價格.2.3.1 影子價格影子價格影子價格在管理決策中的應(yīng)用影子價格在管理決策中的應(yīng)用這種資源對目標增益的影響越大這種資源對目標增益的影響越大這種資源對該企業(yè)越稀缺、貴重這種資源對該企業(yè)越稀缺、貴重管理措施：管理措施：通過挖掘革新、降低消耗或及時補充該種資源通過挖掘革新、降低消耗或及時補充該種資源重視對該資源的管理；重視對該資源的管理；.2.3.1 影子價格影子價格某種資源的影子價格為某種資源的影子價格為0，表明：，表明：這種資源對該企業(yè)而言，是相對富余的這種資源對該企業(yè)而言，是相對富余的管理措施：管理措施：通過對企業(yè)內(nèi)部的改造、挖掘和增加對影子價格

22、通過對企業(yè)內(nèi)部的改造、挖掘和增加對影子價格大于零的資源的投入，使原有剩余資源得到充分大于零的資源的投入，使原有剩余資源得到充分利用利用以市場價出售以市場價出售.2.3.1 影子價格影子價格影子價格影子價格 市場價格，則買進該資源市場價格，則買進該資源影子價格影子價格 0 xn+i = 0 yi0 xn+i = 0 0in iy xxj0 ym+j = 0 xj=0 ym+j 0 在利潤最大化的生產(chǎn)計劃中在利潤最大化的生產(chǎn)計劃中(1) 影子價格大于影子價格大于0的資源沒有剩余；的資源沒有剩余； 有剩余的資源影子價格為有剩余的資源影子價格為0(2)安排生產(chǎn)機會成本等于利潤的產(chǎn)品；機會成本大于利潤的

23、產(chǎn)安排生產(chǎn)機會成本等于利潤的產(chǎn)品；機會成本大于利潤的產(chǎn)品不安排生產(chǎn)品不安排生產(chǎn).2.4 對偶單純形法對偶單純形法二、對偶單純形法基本步驟二、對偶單純形法基本步驟 max型型(1) 作初始表，要求全部作初始表，要求全部j 0 ( 0)(2) 判定：判定： B-1 b全全 0，停停。否則，取否則，取max B-1 b =(B-1 b)l B-1 b0令第令第 l 行的行的Xj l為換出變量為換出變量.(3)確定換入變量確定換入變量 若若Xi l行的行的alj 全全 0 ，停，原問題無可行解。，停，原問題無可行解。 若若Xi l行的行的alj 有有alj 0 ,則求則求j k =min =aljal

24、kalj 0 Xk為換入變量為換入變量2.4 對偶單純形法對偶單純形法(4) 以以alk 為主元，換基迭代為主元，換基迭代.2.4 對偶單純形法對偶單純形法例例6 用對偶單純形法求下述線性規(guī)劃問題用對偶單純形法求下述線性規(guī)劃問題123min15245wyyy2312362521 yyyyys.t.y1, y2, y30.2.4 對偶單純形法對偶單純形法解：先將問題改寫為：解：先將問題改寫為：,123max15245wyyy 234123562521yyyyyyys.t.yi0(i = 1, , 5).2.4 對偶單純形法對偶單純形法在上述兩個約束條件兩端乘在上述兩個約束條件兩端乘“-1”,12

25、3min15245wyyy 234123562521yyyyyyy s.t.yi0(i = 1, , 5).2.4 對偶單純形法對偶單純形法列出單純形表，用對偶單純形法進行計算：列出單純形表，用對偶單純形法進行計算：-15 -24 -5 0 0 y1 y2 y3 y4 y50 y3 -20 y4 -1 0 -6 -1 1 0-5 -2 -1 0 1 -15 -24 -5 0 0jcBXBC1B bji* .2.4 對偶單純形法對偶單純形法列出單純形表，用對偶單純形法進行計算：列出單純形表，用對偶單純形法進行計算：-15 -24 -5 0 0 y1 y2 y3 y4 y50 y3 -20 y4

26、-1 0 -6 -1 1 0-5 -2 -1 0 1 -15 -24 -5 0 0jcBXBC1B bji* .2.4 對偶單純形法對偶單純形法-15 -24 -5 0 0 y1 y2 y3 y4 y5-24 y2 1/4-5 y3 1/2-5/4 1 0 -1/4 1/415/2 0 1 1/2 -3/2 -15/2 0 0 -7/2 -3/2jcBXBC1B bjiY*=(0,1/4,1/2,0,0), w = 8.5(元元).2.4 對偶單純形法對偶單純形法從上述對偶單純形法的求解中，可以看出其優(yōu)點：從上述對偶單純形法的求解中，可以看出其優(yōu)點：(1) 初始解可以是非可行解，當檢驗數(shù)均為非

27、正數(shù)時，初始解可以是非可行解，當檢驗數(shù)均為非正數(shù)時，就可以進行基變換，此時無需加入人工變量，因此可就可以進行基變換，此時無需加入人工變量，因此可以簡化計算以簡化計算(2) 當變量多余約束條件時，用對偶單純形法計算可以當變量多余約束條件時，用對偶單純形法計算可以減少計算工作量減少計算工作量(3) 在靈敏度析及整數(shù)規(guī)劃的割平面法中，有時需要用在靈敏度析及整數(shù)規(guī)劃的割平面法中，有時需要用對偶單純形法以簡化問題的處理對偶單純形法以簡化問題的處理.2.4 對偶單純形法對偶單純形法但對偶單純形法也有其局限性：但對偶單純形法也有其局限性：對于多數(shù)線性規(guī)劃問題，在初始單純形表中其對偶問對于多數(shù)線性規(guī)劃問題，在

28、初始單純形表中其對偶問題應(yīng)是基可行解這一點很難實現(xiàn)，所以對偶單純形法題應(yīng)是基可行解這一點很難實現(xiàn)，所以對偶單純形法一般不單獨使用一般不單獨使用.2.4 對偶單純形法對偶單純形法練習(xí)練習(xí)1：用對偶單純形法求解：用對偶單純形法求解123min234wxxx12312323234xxxxxxs.t.xj0(j = 1, , 3).2.4 對偶單純形法對偶單純形法練習(xí)練習(xí)2：用對偶單純形法求解：用對偶單純形法求解124max43zxxx 1234123423242xxxxxxxxs.t.xj0(j = 1, , 4).2.5 靈敏度分析靈敏度分析靈敏度靈敏度指系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度

29、指系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度1jjBjcC B P10B b最優(yōu)性最優(yōu)性可行性可行性.2.5 靈敏度分析靈敏度分析靈敏度分析步驟靈敏度分析步驟1. 將參數(shù)的改變通過計算反映到最終單純形表上來將參數(shù)的改變通過計算反映到最終單純形表上來2. 檢查員問題是否仍為可行解檢查員問題是否仍為可行解3. 檢查對偶問題是否仍為可行解檢查對偶問題是否仍為可行解原問題原問題對偶問題對偶問題結(jié)論或繼續(xù)計算的步驟結(jié)論或繼續(xù)計算的步驟可行解可行解可行解可行解問題的最優(yōu)解不變問題的最優(yōu)解不變可行解可行解非可行解非可行解用單純形法繼續(xù)迭代求解用單純形法繼續(xù)迭代求解非可行解非可行解可行解可行解用對偶單純形法繼

30、續(xù)迭代求解用對偶單純形法繼續(xù)迭代求解非可行解非可行解非可行解非可行解引入人工變量，重新計算求解引入人工變量，重新計算求解.2.5.1 分析分析cj的變化的變化例例7在第在第1章例章例1的美佳公司例子中的美佳公司例子中：（1）若家電）若家電1的利潤將至的利潤將至1.5元元/件，美佳公司最優(yōu)生件，美佳公司最優(yōu)生產(chǎn)計劃有何變化產(chǎn)計劃有何變化（2）若家電）若家電1的利潤不變，則家電的利潤不變，則家電2的利潤在什么范的利潤在什么范圍內(nèi)變化時，該公司的最優(yōu)生產(chǎn)計劃將不發(fā)生改變？圍內(nèi)變化時，該公司的最優(yōu)生產(chǎn)計劃將不發(fā)生改變？.jcBXBC1B bji2.5.1 分析分析cj的變化的變化 2 1 0 0 0

31、x1 x2 x3 x4 x50 x3 15/22 x1 7/21 x2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/21.5 21.52 1/8-9/4.1.5 2 0 0 0 x1 x2 x3 x4 x50 x4 61.5 x1 22 x2 3 0 0 5/4 1 -6 1 0 -1/5 0 1 0 1 1/5 0 0 0 0 -1/10 0 -3/2jjcBXBC1B bi因為，檢驗數(shù)全非正，該解為最優(yōu)解，即：因為，檢驗數(shù)全非正，該解為最優(yōu)解，即：*(2,3,6,0,0)TX *19()BZC B b元2.5

32、.1 分析分析cj的變化的變化.2.5.1 分析分析cj的變化的變化 2 0 0 0 x1 x2 x3 x4 x50 x3 15/22 x1 7/2 x2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0jjcBXBC1B bi1111-1/4-1/2114413221104413022為保持最優(yōu)解不變，應(yīng)有：為保持最優(yōu)解不變，應(yīng)有：113.2.5.2 分析分析bi的變化的變化例例8在第在第1章例章例1的美佳公司例子中的美佳公司例子中：（1）若設(shè)備）若設(shè)備A和調(diào)試工序的每天能力不變，而設(shè)備和調(diào)試工序的每天能力不變，而設(shè)備B每天的能力增

33、加到每天的能力增加到32h，分析公司最優(yōu)計劃的變化；，分析公司最優(yōu)計劃的變化；（2）若設(shè)備）若設(shè)備A和設(shè)備和設(shè)備B每天可用能力不變，則調(diào)試工每天可用能力不變，則調(diào)試工序能力在什么范圍內(nèi)變化時，問題的最優(yōu)基不變？序能力在什么范圍內(nèi)變化時，問題的最優(yōu)基不變？.2.5.2 分析分析bi的變化的變化 2 0 0 0 x1 x2 x3 x4 x50 x3 15/22 x1 7/2 x2 3/2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0jjcBXBC1B bi11-1/4-1/2.2.5.2 分析分析bi的變化的變化解：解：（1）由已知得，）由已

34、知得， 則：則：080b 114/515/ 201001/ 41/ 28201/ 43/ 202bBb .2.5.2 分析分析bi的變化的變化解：解：114/515/ 201001/ 41/ 28201/ 43/ 202bBb 115/ 21035/ 27/ 2211/ 23/ 221/ 2bB bb.2.5.2 分析分析bi的變化的變化 2 0 0 0 x1 x2 x3 x4 x50 x3 2 x1 x2 0 0 1 5/4 15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0jjcBXBC1B bi11-1/4-1/215/27/23/235/211/2-1/2

35、.2.5.2 分析分析bi的變化的變化 2 0 0 0 x1 x2 x3 x4 x50 x3 2 x1 x4 0 5 1 0 0 1 1 0 0 1 0 -4 0 1 -6 0 -1 0 0 -2jjcBXBC1B bi11 15 5 2因為，檢驗數(shù)全非正，該解為最優(yōu)解，即：此時，美因為，檢驗數(shù)全非正，該解為最優(yōu)解，即：此時，美佳公司只生產(chǎn)佳公司只生產(chǎn)5件家電件家電1.2.5.2 分析分析bi的變化的變化解：解：（2）設(shè)調(diào)試工序每天可用能力為）設(shè)調(diào)試工序每天可用能力為 h(5)115214/515/ 20101/ 41/ 20201/ 43/ 232bBb .2.5.2 分析分析bi的變化的變

36、化解：解：115151522215/ 21717/ 22223/ 2333222bB bb +當當 時，問題的最優(yōu)基不變，可解得時，問題的最優(yōu)基不變，可解得 0b 11 由此，調(diào)試工序的能力在由此，調(diào)試工序的能力在4h6h之間之間 .2.5.3 增加一個變量增加一個變量xj的分析的分析增加一個變量在實際問題中反映為增加一個新的品種，增加一個變量在實際問題中反映為增加一個新的品種，其分析步驟如下：其分析步驟如下：1. 計算計算2. 計算計算3. 若若 ，原最優(yōu)解不變，只需將計算得到的，原最優(yōu)解不變，只需將計算得到的 直接寫入最終單純形表中；若直接寫入最終單純形表中；若 ，則按單純，則按單純形法繼

37、續(xù)迭代計算找出最優(yōu)解。形法繼續(xù)迭代計算找出最優(yōu)解。*1mjjijiica y1jjpB P0jjPj0j.2.5.3 增加一個變量增加一個變量xj的分析的分析例例9在第在第1章例章例1的美佳公司例子中的美佳公司例子中，設(shè)該公司又計劃推出，設(shè)該公司又計劃推出新型號的家電新型號的家電3，生產(chǎn)一件所需設(shè)備，生產(chǎn)一件所需設(shè)備A、B及調(diào)試工序及調(diào)試工序的時間分別為的時間分別為3h, 4h, 2h, 該產(chǎn)品的預(yù)期盈利為該產(chǎn)品的預(yù)期盈利為3元元/件，件，試分析該種產(chǎn)品是否值得投產(chǎn)；如投產(chǎn)，對該公司的試分析該種產(chǎn)品是否值得投產(chǎn)；如投產(chǎn)，對該公司的最優(yōu)生產(chǎn)計劃有何影響？最優(yōu)生產(chǎn)計劃有何影響？.2.5.3 增加一

38、個變量增加一個變量xj的分析的分析解：解：設(shè)該公司生產(chǎn)家電設(shè)該公司生產(chǎn)家電3的數(shù)量為的數(shù)量為x6, 由已知可得：由已知可得：c6 = 3, P6 = (3, 4, 2)T3*66133(0,1/ 4,1/ 2) 412ijiica y 由原最終單純形表可得，由原最終單純形表可得，Y* = (0, 1/4, 1/2)1615/ 415/ 23701/ 41/ 24001/ 43/ 222jPB P .2.5.3 增加一個變量增加一個變量xj的分析的分析解：解：將其反映到最終單純形表中：將其反映到最終單純形表中： 2 1 0 0 0 3 x1 x2 x3 x4 x5 x6 0 x3 15/2 2

39、x1 7/2 1 x2 3/2 0 0 1 5/4 15/2 -7 1 0 0 1/4 -1/2 0 0 1 0 -1/4 3/2 2 - - 3/4 0 0 0 -1/4 -1/2 1jjcBXBC1B bi* .2.5.3 增加一個變量增加一個變量xj的分析的分析解：解：將其反映到最終單純形表中：將其反映到最終單純形表中： 2 1 0 0 0 3 x1 x2 x3 x4 x5 x6 0 x3 51/4 2 x1 7/2 3 x6 3/4 0 7/2 1 3/8 -9/4 0 1 0 0 1/4 -1/2 0 0 1/2 0 -1/8 3/4 1 0 -1/2 0 -1/8 -5/4 0jj

40、cBXBC1B bi此時，美佳公司的最優(yōu)生產(chǎn)計劃為每天生產(chǎn)此時，美佳公司的最優(yōu)生產(chǎn)計劃為每天生產(chǎn)7/2件家電件家電1, 3/4件家電件家電2。.2.5.4 分析參數(shù)分析參數(shù)aij的變化的變化若變量若變量xj在最終單純形表中為非基變量，其約束條件在最終單純形表中為非基變量，其約束條件中系數(shù)中系數(shù)aij的變化分析可參照增加一個變量的變化分析可參照增加一個變量xj的分析的分析若變量若變量xj在最終單純形表中為基變量，則在最終單純形表中為基變量，則aij的變化將的變化將使相應(yīng)的使相應(yīng)的B和和B-1發(fā)生變化，從而有可能出現(xiàn)原問題和發(fā)生變化，從而有可能出現(xiàn)原問題和對偶問題均為非可行解的情況，此時，需引入人

41、工變對偶問題均為非可行解的情況，此時，需引入人工變量先將原問題的解轉(zhuǎn)化為可行解，再用單純形法求解。量先將原問題的解轉(zhuǎn)化為可行解，再用單純形法求解。.2.5.4 分析參數(shù)分析參數(shù)aij的變化的變化例例10在第在第1章例章例1的美佳公司例子中的美佳公司例子中，若家電，若家電2每件需設(shè)備每件需設(shè)備A, B和調(diào)試工序工時變?yōu)楹驼{(diào)試工序工時變?yōu)?h, 4h, 1h, 該產(chǎn)品的利潤變該產(chǎn)品的利潤變?yōu)闉?元元/件，試重新確定該公司最優(yōu)生產(chǎn)計劃。件，試重新確定該公司最優(yōu)生產(chǎn)計劃。解：解：先將生產(chǎn)工時變化后的新家電先將生產(chǎn)工時變化后的新家電2看作是一種新產(chǎn)品，看作是一種新產(chǎn)品，生產(chǎn)量為生產(chǎn)量為 ，計算，計算 、

42、 ，并反映到最終單純，并反映到最終單純形表中：形表中：22p2x. 2 1 3 0 0 0 x1 x2 x3 x4 x5 0 x3 15/2 2 x1 7/2 1 x2 3/2 0 0 11/2 1 5/4 -15/2 1 0 1/2 0 1/4 -1/2 0 1 1/2 0 -1/4 3/2 0 0 3/2 0 -1/4 1/2jjcBXBC1B bi2.5.4 分析參數(shù)分析參數(shù)aij的變化的變化2x* 因因 已變換為已變換為 ，故用單純形法將，故用單純形法將 替換出原基替換出原基變量中的變量中的 ，并在下一表中不再保留，并在下一表中不再保留 2x2x2x2x2x. 2 3 0 0 0 x1

43、 x3 x4 x5 0 x3 -9 2 x1 2 3 3 0 0 1 4 -24 1 0 0 1/2 -2 0 1 0 -1/2 3 0 0 0 1/2 -5 2.5.4 分析參數(shù)分析參數(shù)aij的變化的變化該表中原問題與對偶問題均為非可行解，故先設(shè)法使該表中原問題與對偶問題均為非可行解，故先設(shè)法使原問題變?yōu)榭尚薪庠瓎栴}變?yōu)榭尚薪?，該表中第，該表中第1行的約束可寫為：行的約束可寫為： jjcBXBC1B b2x2x3454249xxx 34564249xxxx. 2 3 0 0 0 -M x1 x3 x4 x5 x6 0 x6 3/8 2 x1 11/4 3 15/8 0 0 -1/24 -1/6 1 1/24 1 0 -1/12 1/6 0 1/12 0 1 1/8 0 0 -1/8 0 0 -5/24 -1/3 0 -M+5/24 jjcBXBC1B b2x2x2.5.4 分析參數(shù)分析參數(shù)aij的變化的變化此時，美佳公司的最優(yōu)生產(chǎn)計劃為每天生產(chǎn)此時，美佳公司的最優(yōu)生產(chǎn)計劃為每天生產(chǎn)11/4件家件家電電I, 8/15件家電件家電II .2.5.5 增加一個約束條件的分析增加一個約束條件的