1、5 對偶問題的經濟解釋 影子價格 (P)的最終單純形表中松弛變量的檢驗數對應(D)的最優解。 當某約束條件的右端常數增加一個單位時（假設原問題的最優基不變），原問題的目標函數最優值增加的數量。Z*=CX*=Y*b =(y1*,y2*, ,ym*)b1b2bm=y1*b1+y2*b2+ym*bm當某個右端常數bi bi+1時bi+1yi*+yi*(bi+1)=Y*b+yi*=Z*+yi*第I種資源的影子價格是第i1 甲 乙可用量機械設備 1 28原材料A 4 016原材料B 0 412 X(3)=(4，2，0，0, 4)T， z3 =14cj23000CBXBbx1x2 x3x4x5203x1x

2、5x2442100001-2-3/2-1/81/8010-1400-3/2-1/80經濟意義：在其它條件不變的情況下，單位資源變化所引起的目標函數的最優值的變化。影子價格2 產品資源 現有資源數鋼材1 2100（噸）煤2 2180（噸）機時1 6240（小時）利潤（萬元）1 3x1x2x3x4x5 -zXB-13500-3/40-1/4x130103/20-1/2x45000-5/211/2x23501-1/401/4X*=(30,35,0,50,0)T, Z*=135y1*=3/4y2*=0,y3*=1/4影子價格經濟意義：在其它條件不變的情況下，單位資源變化所引起的目標函數的最優值的變化。

3、3影子價格的意義(1)影子價格客觀地反映資源在系統內的稀缺程度。如果某一資源在系統內供大于求（即有剩余），其影子價格就為零。如果某一資源是稀缺的（即相應約束條件的剩余變量為零）,則其影子價格必然大零。影子價格越高，資源在系統中越稀缺。(2)影子價格是對系統資源的一種優化估價，只有當系統達到最優時才能賦予該資源這種價值，因此也稱最優價格。(3)影子價格的取值與系統狀態有關。系統內部資源數量、技術系數和價格的任何變化，都會引起影子價格的變化，它是一種動態價格。(4)如果考慮擴大生產能力，應該從影子價格高的設備入手。46 對偶單純形法保持對偶可行性，逐步改進主可行性，求解主問題。 當b有負分量，A中

4、有一明顯初始對偶可行基(檢驗數均非正)，因而易得一初始解時，可用對偶單純形法求解。 設B為一個基基本解X（0）為基本可行解的條件？B-1b0X（0）為最優解的條件？原原始可行性條件原始最優性條件令Y=CBB-1，代入原始最優性條件，YAC對偶可行性條件56例 用對偶單純形法求解單純形法大M 法剩余變量、人工變量 用（-1）乘不等式兩邊，再引入松弛變量。7cj -1 -4 0 -3 0 0CBXBb x1 x2 x3 x4 x5 x600 x5x6-3-2 -1 -2 1 - 1 1 0 2 1 -4 -1 0 10 -1 -4 0 -3 0 0先選出基變量后選進基變量原問題，符合原始最優性條件

5、，但不可行cj -1 -4 0 -3 0 0CBXBb x1 x2 x3 x4 x5 x6-10 x1x63-8 1 2 - 1 1 -1 0 0 -3 -2 -3 2 13 0 -2 -1 -2 -1 08cj -1 -4 0 -3 0 0CBXBb x1 x2 x3 x4 x5 x6-10 x1x63-8 1 2 - 1 1 -1 0 0 -3 -2 -3 2 13 0 -2 -1 -2 -1 0-10 x1x374 1 7/2 0 5/2 -2 -1/2 0 3/2 1 3/2 -1 -1/2 7 0 -1/2 0 -1/2 -2 -1/2最優解X*=（7，0，4，0）TZ*=-79例6

6、 用對偶單純形法求解（P）101 - 4/3 - -1 0 -5/2 1/2 1 -1/2 2 1 -1/2 3/2 0 -1/2 0 -4 -1 0 -1- 8/5 - - 22/5 0 1 -1/5 -2/5 1/5 11/5 1 0 7/5 -1/5 -2/5 0 0 -3/5 -8/5 -1/5 11對偶單純形法的一個應用： 增加一個約束條件的分析 。 檢查原最優解是否滿足新的約束條件 滿足，則原最優解仍為最優解，否則，2。2 將約束方程帶到最優單純形表中。max z =x+45x+24x 40123s.t. 例新增加一個條件 127 靈敏度分析 系數bi、cj 、aij 變化，最優解

7、的最優性、可行性是否變化？ 系數在什么范圍內變化，最優解或最優性不變？ 如何求新的最優解？本節重點137.1 靈敏度分析的原理是最優解，則可行性條件最優性條件正則性 bi非基變量cj基變量cB增加新變量一個非基變量 系數aij的變化，要視aij對應的變量是基變量或非基變量而定。14XB=B-1(b+b)，其中b=(0, br ,0,0)T只要XB0，最終表中檢驗數不變（b變化，不影響檢驗數），則最優性不變，但最優解的值發生變化, XB成為新的最優解.B-1(b+b)= B-1b+ B-1b0新的最優解允許范圍是:當某一個資源系數br 發生變化，亦即br= br +br ，其他系數不變，這樣最終

8、的單純形表中原問題的解相應地變化為1、資源系數br的靈敏度變化分析15B-1的第r列進一步得，最終表中b列元素bbairir-D B-1b,0babririD+i=1，2，mi=1，2，miririrabba;/0-Diririrabba/0-D16x1, x5, x2是基變量，從而可得基B例：求第一章例題中當第二個約束條件b2變化范圍b2。得到公式: 17cj23000CBXBbx1x2 x3x4x5203x1x5x2442100001-0-21/21/41/2-1/8010-1400-3/2-1/8018可得b2-4/0.25=-16, b2-4/0.5=-8, b22/0.125=16由

9、公式知b2變化范圍-8,16, 顯然b2變化范圍8,32 例題: 將上面例題進行實際應用。每臺設備臺時的影子價格為1.5元。若該廠又從別處抽出4臺時用于生產兩種產品，求這時該廠生產兩種產品的最優方案。B=（x1 x5 x2)19將這個結果放到最終表中得解：先計算B-1b 2 3 0 0 0 cj203x1x2x54+04-82+2CBXBbx1 x2 x3 x4 x5 1 0 0 0.25 00 0 -2 0.5 10 1 0.5 -0.125 0cj-zj 0 0 -1.5 -0.125 020 表中b列中有負數，即解答列有負數，故可用對偶單純形法求最優解。 最優解見下表 最優生產方案應改為

10、第一種產品4件，第二種產品3件，獲利z=17元。 2 3 0 0 0 cj203x1x2x3423CBXBbx1 x2 x3 x4 x5 1 0 0 0.25 00 0 1 -0.25 -050 1 0 0 0.25cj-zj 0 0 0 -0.5 -0.7521（1）當cj是非基底變量xj的系數，檢驗數為或當cj變化cj后，檢驗數應要小于或等于零，即2、目標函數中價值系數C的變化22（2）當cr是基底變量xr的系數，即crCB，cr變化cr后，有aaaCAC B BABCABCrnrrrrBLLL),()0,0(21111D+=D+-最優解不變njacA)jcrjrjjL,2,1,=D-=s

11、(CBB1-23cr的變化范圍 例8： 仍以第一章例1的最終表為例。設基變量x2的系數c2變化c2，在原最優解不變的條件下，確定c2的變化范圍。 解：這時最終計算表為24cj2 3 000CBXBbx1x2x3x4x5203x1x5x24421000010-20.50.250.5-0.125010cj-zj00-1.5-0.1250 可見c2-1.5/0.5; c2-0.125/(-0.125) 故c2的變化范圍: -3c21即x2的價值系數c2可在0,4之間變化，不影響原最優解。25cj50 30 00CBXBbx1x2x3x43050 x2x1201501101-1/2-23/2cj-zj

12、00-5-15已知線性規劃問題最優單純形表練習1263 aij的變化分析(1). aij 為非基變量的系數只影響xj的檢驗數，從而影響最優性。 例: 第一章例1，增加一種新產品，它的技術系數是(2，6，3)T，利潤系數是5。問該廠是否應生產該產品和生產多少？ 解：設新產品的產量為x3 (對于原最優解來說是非基變量)。因 故應生產產品。 x3進基27在最終表中的系數是： 原最終表成為： 28用單純形法求解得： 29(2). aij為基變量系數基變化，影響最優性、可行性。 例: 第一章例1，若生產產品的工藝結構有改進，其技術系數變為（2， 5 ，2)T，利潤系數為4，試分析對生產計劃有什么影響？

13、解： 設產品產量為x1(產品產量在原最優解中是基變量)。計算 30將和所求系數填入原最終表的x1列位置，得 將x1的系數列向量變換為單位向量 31 上表中假如對偶可行，主不可行，則用對偶單純形法求新解；假如主對偶均不可行，要加入人工變量，用單純形法繼續解。注意：例11 假設例10的產品的技術系數向量為 p1=（4，5，2），而每件獲利仍為4元。試該廠應如何安排最優生產方案？323334練習2 在練習1中，如果新增加產品，其目標系數為100，消耗系數為（9，3.5） 是否應該生產該產品cj50 30 00CBXBbx1x2x3x43050 x2x1201501101-1/2-23/2cj-zj0

14、0-5-15最優單純形表35(1)求線性規劃問題的最優解；(2)求對偶問題的最優解； (3)當b3= -150時最優基是否發生變化？為什么？ (4)求C2的靈敏度范圍; (5)如果x3的系數由1，3，5變為1，3，2最優基是否改變？若改變求新的最優解 ;(6)假定新增決策變量x8，且p8=(2，5，3)，C8=4，原最優解是否改變？為什么？ 36線性規劃綜合例題 某工廠使用5種生產方式，生產A、B、C三種產品，有關每種方法的批產量數據如表1、資源消耗如表2。有一合同要求至少生產A110單位。 表1 每種方法的批產量 方法產品12345單價ABC3622164254110481054 方法產品12345單價工時機時成本/元01484119623011442178050-表2 資源消耗 1.若第2種生產方法的成本提高到21元，問是否改變最有解？ 2.現每工時的工資為3元，若加班，另附加費用1.5元