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

2、的資源全部這時，如果有另一家公司想購買美佳公司的資源全部資源，那么它至少應出多少的價格，才會使美佳公司資源，那么它至少應出多少的價格，才會使美佳公司愿意出讓？愿意出讓？解：設其購買三種資源的價格分別為解：設其購買三種資源的價格分別為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）約束條件當目標函數求極大時均取）約束條件當目標函數求極大時均取“ ”（3）約束條件當目標函數求極大時均取）約束條件當目標函數求極大時均取“ ”.2.1.2 對偶問題的對稱形式對偶問題的對稱形式例例2：寫出下面問題的對偶規劃：寫出下面問題的對偶規劃maxZ= 5X1 +6X2

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

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

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

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

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

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

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

12、性質4. 強對偶性（對偶定理）強對偶性（對偶定理） (1)由性質由性質4可知，對偶問題最優解的表可知，對偶問題最優解的表達式達式Y* = ?(2)求求Y*是否要重新求解是否要重新求解(D) CBB-1 不需要，可以從原問題不需要，可以從原問題(P)的單純形終的單純形終表獲得表獲得.2.2 對偶問題的基本性質對偶問題的基本性質例如，在前面美佳公司的生產計劃中，其單純形終表為：例如，在前面美佳公司的生產計劃中，其單純形終表為： 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 對偶問題的基本性質對偶問題的基本性質由上表可直接得到問題由上表可直接得到問題(P)的最優解和最優值：的最優解和最優值： X* = (7/2, 3/2, 15/2, 0, 0)T Z* = 8.5根據強對偶性可得：根據強對偶性可得： Y* = (0, 1/4, 1/2) Y* = 8.5.2.2 對偶問題的基本性質對偶問題的基本性質5. 互補松弛性（松緊定理）互補松弛性（松緊定理）設設 ， 分別為分別為(P)和和(D)的可行解，則：的可行解，則： , 是最優解是最優解 其中，其中， ， 為最優解中松弛變量部分。為

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

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

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

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

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

19、請根據美佳公司生產計劃安排的單純形終表請根據美佳公司生產計劃安排的單純形終表指出：指出：資源設備資源設備A、B和調試工序的影子價格，并解釋和調試工序的影子價格，并解釋其經濟意義其經濟意義.2.3.1 影子價格影子價格例例5 美佳公司生產計劃安排的單純形終表如下：美佳公司生產計劃安排的單純形終表如下： 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設備

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

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

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

23、產安排生產機會成本等于利潤的產品；機會成本大于利潤的產品不安排生產品不安排生產.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 用對偶單純形法求下述線性規劃問題用對偶單純形法求下述線性規劃問題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 對偶單純形法對偶單純形法從上述對偶單純形法的求解中，可以看出其優點：從上述對偶單純形法的求解中，可以看出其優點：(1) 初始解可以是非可行解，當檢驗數均為非

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

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

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

30、續迭代求解用對偶單純形法繼續迭代求解非可行解非可行解非可行解非可行解引入人工變量，重新計算求解引入人工變量，重新計算求解.2.5.1 分析分析cj的變化的變化例例7在第在第1章例章例1的美佳公司例子中的美佳公司例子中：（1）若家電）若家電1的利潤將至的利潤將至1.5元元/件，美佳公司最優生件，美佳公司最優生產計劃有何變化產計劃有何變化（2）若家電）若家電1的利潤不變，則家電的利潤不變，則家電2的利潤在什么范的利潤在什么范圍內變化時，該公司的最優生產計劃將不發生改變？圍內變化時，該公司的最優生產計劃將不發生改變？.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因為，檢驗數全非正，該解為最優解，即：因為，檢驗數全非正，該解為最優解，即：*(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為保持最優解不變，應有：為保持最優解不變，應有：113.2.5.2 分析分析bi的變化的變化例例8在第在第1章例章例1的美佳公司例子中的美佳公司例子中：（1）若設備）若設備A和調試工序的每天能力不變，而設備和調試工序的每天能力不變，而設備B每天的能力增

33、加到每天的能力增加到32h，分析公司最優計劃的變化；，分析公司最優計劃的變化；（2）若設備）若設備A和設備和設備B每天可用能力不變，則調試工每天可用能力不變，則調試工序能力在什么范圍內變化時，問題的最優基不變？序能力在什么范圍內變化時，問題的最優基不變？.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因為，檢驗數全非正，該解為最優解，即：此時，美因為，檢驗數全非正，該解為最優解，即：此時，美佳公司只生產佳公司只生產5件家電件家電1.2.5.2 分析分析bi的變化的變化解：解：（2）設調試工序每天可用能力為）設調試工序每天可用能力為 h(5)115214/515/ 20101/ 41/ 20201/ 43/ 232bBb .2.5.2 分析分析bi的變化的變

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

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

38、個變量增加一個變量xj的分析的分析解：解：設該公司生產家電設該公司生產家電3的數量為的數量為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此時，美佳公司的最優生產計劃為每天生產此時，美佳公司的最優生產計劃為每天生產7/2件家電件家電1, 3/4件家電件家電2。.2.5.4 分析參數分析參數aij的變化的變化若變量若變量xj在最終單純形表中為非基變量，其約束條件在最終單純形表中為非基變量，其約束條件中系數中系數aij的變化分析可參照增加一個變量的變化分析可參照增加一個變量xj的分析的分析若變量若變量xj在最終單純形表中為基變量，則在最終單純形表中為基變量，則aij的變化將的變化將使相應的使相應的B和和B-1發生變化，從而有可能出現原問題和發生變化，從而有可能出現原問題和對偶問題均為非可行解的情況，此時，需引入人

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

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 分析參數分析參數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 分析參數分析參數aij的變化的變化該表中原問題與對偶問題均為非可行解，故先設法使該表中原問題與對偶問題均為非可行解，故先設法使原問題變為可行解原問題變為可行解 ，該表中第，該表中第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 分析參數分析參數aij的變化的變化此時，美佳公司的最優生產計劃為每天生產此時，美佳公司的最優生產計劃為每天生產11/4件家件家電電I, 8/15件家電件家電II .2.5.5 增加一個約束條件的分析增加一個約束條件的