1、唯一最優解唯一最優解 N NN YYY添加松弛變量添加松弛變量、人工變人工變量量, 列出初始單純形表列出初始單純形表計算非基變量計算非基變量對應的檢驗數對應的檢驗數 j所有所有 j 0基 變 量基 變 量中中有 非 零有 非 零的的人 工 變人 工 變量量某非基變某非基變量檢驗數量檢驗數為零為零無可行解無可行解無窮多最優解無窮多最優解對某對某 j 0有有aij0無界解無界解令令 k=max j對所有對所有ai k0計算計算 i=bi/aik令令 s=min ixs為換出變量為換出變量ask為主元素為主元素 迭代運算迭代運算. 用非基變量用非基變量xk替換基變量替換基變量xs; . 對主元素行對

2、主元素行(第第s行行)，令，令 bs/askbs;asj/askasj. 對主元素列對主元素列(第第k列列)，令，令1ask；0其它元素其它元素 表中其它行列元素表中其它行列元素 令令 aij-asj/askaikaij bi-bs/askaikbiYN復習上次內容：人工變量法基變量非基變量等式右端XB XN1XS系數矩陣IB-1N1B-1B-1b檢驗數0CN1-CBB-1N1-CBB-1-CBB-1b11111()()min()0()()iskiikkisB bB bBPBPBP單純形表的矩陣表達形式 1:N系數矩陣中對應于非基變量中決策變量的子矩陣3 線性規劃的對偶問題的提出 矩陣形式 0

3、.maxXbAXt.sCXz實際問題提出： 某廠生產甲、乙兩種產品，產量、利潤、設備臺時如下模型所示0,124 16 482 . .32max21212121xxxxxxtsxxz甲產品：獲利2元乙產品：獲利3元 從另一個角度討論這個問題：工廠決定轉讓設備并出讓原材料收取租金，如何確定租價？ 設y1為出租單位出租單位設備臺時的租價，設備臺時的租價， y2，y3分別出讓單位原材料、的出讓單位原材料、的附加額附加額。0,34 22 4 . .12168 min3213121321yyyyyyytsyyyII生產每件產品 的設備臺時和原材料出讓的所有收入生產每件產品 的利潤！ 為什么目標取最小？租金

4、定的越高就不會有人來租，問題就沒有實際意義，工廠和接受者都愿意的條件為上述規劃問題的解。 其中Y=（y1，y2，y3） 每個線性規劃都有另一個線性規劃每個線性規劃都有另一個線性規劃(對偶問題對偶問題)與它密切相與它密切相關，對偶理論揭示了原問題與對偶問題的內在聯系。關，對偶理論揭示了原問題與對偶問題的內在聯系。0,124 16 482 . .32max21212121xxxxxxtsxxz0,34 22 4 . .12168 min3213121321yyyyyyytsyyy 理論上11BCNBCCBBN與檢驗數為優解線性規劃問題有獲得最時并且當0011BCNBCCBBN，稱為單純形乘子令1B

5、CYB0,.0.maxmaxXbIXAXtsXbAXtsCXZCXZsXs因為Yb的上界為無限大,所以b只能有最小值。zbBCYbBCYCYAABCCYBCBBBB ) 3( 0 )2(0 0 ) 1 (11110. .minYCYAtsYb4 線性規劃的對偶理論原問題與對偶問題的數學模型原問題與對偶問題的數學模型原問題標準形式：對偶問題標準形式： 標準對偶問題標準對偶問題nmijTnaAxxxXXbAXtsCXz)(,),(0. . max21),(0.min21myyyYYCYAtsYb標準形式下原問題與對偶問題的對應關系根據下表寫出原問題與對偶問題的表達式 xjyjx1x2by1y2y3

6230. .max XybAXybAXtsCXZ0. .min yyCAAyytsbbyy0,)(. .)(min yyCAyytsbyy由自 . .minYCYAtsYb 如果原問題約束條件是等式約束0. .maxXbAXtsCXZ原問題中的價值向量與對偶問題中的資源向量對換（上下對換）原問題: X在C和A的右邊; 對偶問題:Y在b和A的左邊（左右對換）對偶問題的基本性質和基本定理1. 對稱性定理：對偶問題的對偶是原問題證明：2. 弱對偶性定理 若X（0）和Y（0）分別是原問題和對偶問題的可行解，則有CX（0）Y（0）b3. 若原問題（對偶問題）為無界解，則其對偶問題

7、（原問題）無可行解。 (逆命題未必成立) 由弱對偶定理可證得 證明: 因為X（0）是原問題的可行解，故有 AX（0）b。 又因為Y(0)是對偶問題的可行解，則有 Y（0）AX（0）Y（0）b, 及Y（0）AC故 C X（0）Y（0）A X（0）Y（0）b亦即 C X（0）Y（0）b 證畢4.最優性定理若X（0）和Y（0）分別是原問題和對偶問題的可行解，且有 C X（0）=Y（0）b , 則X（0）和Y（0）分別是原問題和對偶問題的最優解。 證明： 設 X 是原問題任一可行解，Y（0）是對偶問題的可行解，根據弱對偶性定理，有C XY（0）b 因為C X（0）=Y（0）b，故CXC X（0），即X

8、（0）是原問題的最優解。 設Y為對偶問題的任一可行解，同理有Yb Y（0）b 即Y（0）是對偶問題的最優解。5.對偶定理 有一對對偶的線性規劃問題，若其中有一個有最優解，則另一個也有最優解，且相應的目標函數值相等。 證明：設X（0）是原問題的最優解，對應的基矩陣為B, 非基變量的檢驗數為CN- CBB-1N0 全體檢驗數 C- CBB-1A0，即CCBB-1A 令Y（0）= CBB-1 0，則有Y（0）AC 即Y（0）是對偶問題的可行解。 由于z=C X（0）= CBXB（0）= CBB-1b= Y（0）b（目標值相等）由最優性定理可知Y（0）為對偶問題的最優解。綜上，一對對偶問題的解必然下列

9、情況之一：綜上，一對對偶問題的解必然下列情況之一：1、原問題和對偶問題都有解，且目標函數值相等，原問題的 最優解是其對偶問題的最優解。2、一個問題具有無界解，另一個問題無可行解3、一個問題無可行解,另一個問題或具有無界解或無可行解 6 .互補松弛定理 若X（0）和Y（0）分別是原問題和對偶問題的可行解，則X（0）和Y（0）都是最優解的充要條件是 Y（0）Xs=Ys X（0）=0。其中Xs=(xs1,xs2,xsm)T，xs1,xs2,xsm 是原問題的松弛變量，松弛變量， Ys=(ys1,ys2,ysn)T ，ys1,ys2,ysn是對偶問題的剩余變量剩余變量。 如果有某個原始最優解X(0)

10、Ys X（0）=0：對某個下標j滿足X(0)j0，那么與之對應的對偶約束在最優的情況下為等式，即ysj=0(不需要松弛變量)； Y（0）Xs=0：如果原始約束在最優情況下對某個下標i滿足x(0)si0(原問題約束是嚴格不等式，需要松弛變量才能化為等式)，那么對偶問題最優解中與之對應的y(0)i=0。證明: 原問題 對偶問題 max z =CX min =Yb AX+ Xs =b YA-Ys=C X, Xs 0 Y, Ys0 z =(YA-Ys)X=YAX-YsX =Y(AX+Xs)=YAX+YXs 若Y(0)Xs=0和YsX(0) =0, 則Y(0)b=Y(0)AX(0)=CX(0)，根據性質

11、4知: X(0),Y(0)為最優解。 反之, X(0),Y(0)為最優解,則根據性質4: CX(0)=Y(0)b。兩組最優解分別代入目標函數: CX(0)=Y(0)AX(0)-YsX(0) Y(0)AX(0) Y(0) b=Y(0)AX(0)+Y(0)Ys Y(0)AX(0) 可知必有Y(0)Xs=YsX(0) =0。 證畢7. 原問題的檢驗數對應對偶問題的一個基本解設B是原問題的一個可行基,有A=(B,N)max z=CBXB+CNXN min =YbBXB+NXN+XS=b YB-Ys1=CBXB, XN，Xs0 YN-Ys2=CN Y, Ys1，Ys20 YS=（YS1，YS2）證明:

12、原問題 對偶問題 max z =CX min =Yb AX+ Xs =b YA-Ys=C X, Xs 0 Y, Ys0Ys1對應原問題當中基變量XB的剩余變量，Ys2對應原問題當中非基變量XN的剩余變量 當原問題有解XB=B-1b，XN=0時,檢驗數為：CN-CBB-1N，-CBB-1 令Y=CBB-1，代入對偶問題的約束條件得： Ys1=0， -Ys2= CN-CBB-1N 則（Y，Ys1，Ys2）為對偶問題的基本解 證畢檢驗數性質：原問題檢驗數行對應其對偶問題的一個 基解, 關系如下: XB XN Xs 0 CN-CBB-1N -CBB-1 Ys1 - Ys2 -Y例4 已知線性規劃問題

13、max z = x1 + x2 -x1 + x2 + x3 2 -2x1 + x2 - x3 1 x1 , x2 , x30試用對偶理論證明上述線性規劃問題無最優解。 證: 首先看到該問題存在可行解，例如X = (0,0,0) 而上述問題的對偶問題為 min = 2y1 + y2 -y1 - 2y2 1 y1 + y2 1 y1 - y2 0 y1 ,y2 0 由第一約束條件可知對偶問題無可行解，因而無最優解。由此原問題也無最優解。例5 已知線性規劃問題 min = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 x1 + x2 + 2x3 + x4 + 3x5 4 2x1 - x2

14、+ 3x3 + x4 + x5 3 xj 0,j = 1,2,3,4,5 已知其對偶問題的最優解為y1* = 4/5, y2* = 3/5；z = 5。試用對偶理論找出原問題的最優解.解: 先寫出它的對偶問題 max z = 4y1 + 3y2 y1 + 2y2 2 y1 - y2 3 (2) 2y1 + 3y2 5 (3) y1 + y2 2(4) 3y1 + y2 3 y1 ,y2 0將y1*, y2*的值代入上述約束條件，得(2),(3),(4)為嚴格不等式；由互補松弛性得x2* = x3* = x4* = 0 因y1 ,y2 = 0，原問題的兩個約束條件應取等式，故有 x1* + 3x

15、5* = 4 2x1* + x5* = 3 求解后得x1* = 1，x5* = 1故原問題的最優解為 X* = (1,0,0,0,1)T最優值為 * = 55 對偶問題的經濟解釋（影子價格）由對偶定理知，當達到最優解時有： z=CX（0）=Y（0）b=y1（0）b1+ y2（0）b2+ ym（0）bm在最優解處，常數項bi 的微小改變對目標函數值的影響（在不改變最優基情況下）有mmbzybzybzy)0(2)0(21)0(1,這說明若原問題的bi增加一個單位，則由此引起的最優目標函數值增加量等于該約束條件對應的對偶變量yi的最優值。因此，最優對偶變量yi的值，就相當于對單位變化的第i種資源在實

16、現最大利潤時的一種價格估計，這種估計被稱之為影子價格影子價格。原問題：可以理解為資源的合理利用使總利潤最大對偶問題：估計資源的價值問題（但并不是第種資源的實際成本，而是根據企業制造產品的收益估計資源的單位價值，既資源在最優產品組合時具有的潛在價值）影子價格：不同于市場價格，是企業內部估計或核算價格例：某廠生產、種產品要消耗鋼、煤、機械加工時間，現有資源數和利潤表如下，試制定一個最優生產計劃。單位消耗現有資源數鋼煤機時100180240利潤1212121212max3. .2100221806240,0 xxstxxxxxxx x解得：(30,35)135xz123123123123m10018

17、0240. .212263,0inyyystyyyyyyy yy對偶問題:由互補松弛條件：(3/4,0,1/4)y解得：0362010*3*1*3*1*2yyyyy所以： 鋼增加一噸，收入增加3/4萬 煤增加一噸，收入增加0 機時增加一個，收入增加1/4萬 煤本身沒有用完，再增加量，收入也不會增加，而另兩種資源已經用完，再增加資源才會增加收益。影子價格在經濟管理中的作用影子價格在經濟管理中的作用:(1) 指示企業內部挖潛的方向： yi高,對目標增益貢獻大,應重 視此資源的組織、采購； (2)指導企業的購銷決策： yi*是新增資源的價值，在最優產 品不變的情況下，購入資源價格 大于yi*時，企業

18、虧損，若企業有 市價高于影子價格的資源，應設 法將其轉讓；(3)用影子價格分析工藝改變后對資源節約的收益:(4)指導企業間的分工協作: 企業接受外協加工時，制定收費標準可依據影子價格，以使雙方都有利潤，可以促進協作；當外協單位支付的報酬不低于影子價格時，企業可以接受，合作可以促進產品更新換代，以發揮各自優勢。例：A、B、C三廠生產車床、刨床，若只生產一種產品，效率表如右圖。車、刨床需求比例為1：2，試制定最優分工協作計劃，使總的套數最多。解：A、B、C三廠編號為1，2，3 車、刨床的編號為1，2效率車床 刨床ABC1 45 22 3ijx為第i廠生產第j種產品的時間比例則：11213152xxx122232423xxx車床總數：刨床總數：1121311222325214232xxxxxx11213112223221044230 xxxxxx展開得：)2 , 1, 3 , 2 , 1(0111323122211211jixxxxxxxij112131122232212221223132112131122232max5242311.1210442300(1,2,3,1,2)i