教案6-對偶理論改

1、 設B為A中的一個mm可行基，則可將A分為（B，N），同樣，將X分為（XB，XN）T，C亦分為（CB，CN），原模型Max Z= CBXB+CNXN+0XS (2.1) BXB+NXN+IXS=b (2.2) XB,XN,XS0 (2.3)XB=B-1 b B-1 NXN B-1 XS 代入（2.1）式，有 Z=CB（ B-1 b B-1 NXN B-1 XS）+CNXN+0XS = CB B-1 b+ （CNCB B-1 N）XN CB B-1 XS1Z=CB（ B-1 b B-1 NXN B-1 XS）+CNXN+0XS = CB B-1 b+ （CNCB B-1 N）XN CB B-1

2、XS即方程組為：-Z+(CCBB-1A)XCBB-1XS=CBB-1b B-1AX+B-1XS=B-1 b -Z X B XN XS 右端此方程組的系數增廣矩陣為：2單純形表的矩陣形式3如例1 的初始表和第三張表42 改進單純形法單純形法中，除換入變量外，非基變量系數列的迭代運算是多余的。為了減少計算量和存儲量，產生了改進單純形法。當mn時這種改進的效果明顯。5實際問題： 某養(yǎng)雞所用的混合飼料由A、B、C三種配料組成，下表給出了1單位各種配料所含的營養(yǎng)成分、單位成本以及1份飼料必須含有的各種成份。問如何配制混合飼料使成本最小？設:Xj=混合飼料中第j種配料的含量，j=A、B、CMin Z=6X

3、A+3XB+2XCXA+XB+XC 201/2XA+1/2XB+1/4XC 62XA+XB+XC 10Xj 06 有一個飼料廠，制造含有這3種營養(yǎng)成份各1單位的營養(yǎng)丸，知道養(yǎng)雞場對混合飼料的要求，因此，在制定營養(yǎng)丸的價格時，使每丸D、E、F營養(yǎng)丸的價格分別為q1、q2、q3。養(yǎng)雞場采購1單位配料A,相當于對3種營養(yǎng)丸分別采購1、1/2、2丸等，采購1單位的B,1單位的C, 因此飼料廠定營養(yǎng)丸售價時，必須有：q1+1/2q2+2q3 6q1+1/2q2+q3 3q1+1/4q2+q3 2Max Z=20q1+6q2+10q37設出租單位設備臺時的租金y1 ，轉讓原材料A、B的收費為y2， y3。

4、第一章例1 生產組織問題 Max Z =2x1+3x2 x1+2x28 4x1 16 4x2 12 x1，x20若工廠決策者準備將所 有資源出租或轉讓，問應如何定價？ 設備原材Ay1y2原材By38對偶問題的定義標準型為：9互為轉置列向量行向量n個變量n個約束10211證：AX=b AXbAXbAXb-AX-byy12解：設對偶變量為y1,y2,y3,對偶問題模型為：Max w=5y1+4y2+6y3 y1 +2y2 y1 + y3 -3y1 +2y2 +y3 y1 - y2 +y323-5=1y10, y20, y3無約束134.2 對偶問題的基本性質14注意：(D)無可行解，(P)不一定為

5、無界解。 此性質還說明：(P)有可行解，(D)不一定有可行解。4、可行解是最優(yōu)解時的性質 設 是(P)的可行解， 是(D)的可行解，當 時， 是最優(yōu)解。3、無界性 若（P）問題可行，但目標函數無界，則（D）問題不可行。（D）不可行（P）無界 （P）不可行利用弱對偶定理 5、對偶定理 若（P）有最優(yōu)解，則（D）也有最優(yōu)解，且目標函數最優(yōu)值相等。15例1 已知線性規(guī)劃問題 試用對偶理論證明上述問題無最優(yōu)解。無界性定理。（P）可行，但無界 則（D）不可行。（D）不可行（P）無界（P）不可行對偶問題X（0）=（0，0，0）T是原問題的一個可行解對偶問題不可行166、互補松弛定理 設X*和Y*分別(P）

6、問題(D）問題的可行解，則它們分別是最優(yōu)解的充要條件是Y*（b-AX*)=0 (Y*A-C)X*=0如何應用該定理？AX* bAX*+XS*= bb-AX*=XS*Y*（b-AX*)=0Y*XS*=017對偶變量不為0，原問題相應約束式是等式原問題約束為不等式，相應對偶變量為0最優(yōu)解點18檢驗數行19cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0-14 0 0 -1.5 -1/8 0 x1x5x2203205 對偶問題的經濟解釋 影子價格 (P)的最終單純形表中松弛變量的檢驗數對應(D)的

7、最優(yōu)解。 當某約束條件的右端常數增加一個單位時（假設原問題的最優(yōu)基不變），原問題的目標函數最優(yōu)值增加的數量。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種資源的影子價格是第i個約束條件的右端常數增加一個單位時，目標函數增加的數量21 X(3)=(4，2，0，0, 4)T， z3 =14經濟意義：在其它條件不變的情況下，單位資源變化所引起的目標函數的最優(yōu)值的變化。影子價格22X*=(30,35,0,50,0)T, Z*=135y1*=3/4y

8、2*=0,y3*=1/4影子價格經濟意義：在其它條件不變的情況下，單位資源變化所引起的目標函數的最優(yōu)值的變化。23影子價格的意義(1)影子價格客觀地反映資源在系統內的稀缺程度。如果某一資源在系統內供大于求（即有剩余），其影子價格就為零。如果某一資源是稀缺的（即相應約束條件的剩余變量為零）,則其影子價格必然大零。影子價格越高，資源在系統中越稀缺。(2)影子價格是對系統資源的一種優(yōu)化估價，只有當系統達到最優(yōu)時才能賦予該資源這種價值，因此也稱最優(yōu)價格。(3)影子價格的取值與系統狀態(tài)有關。系統內部資源數量、技術系數和價格的任何變化，都會引起影子價格的變化，它是一種動態(tài)價格。(4)如果考慮擴大生產能力，

9、應該從影子價格高的設備入手。246 對偶單純形法保持對偶可行性，逐步改進主可行性，求解主問題。 當b有負分量，A中有一明顯初始對偶可行基(檢驗數均非正)，因而易得一初始解時，可用對偶單純形法求解。 設B為一個基基本解X（0）為基本可行解的條件？B-1b0X（0）為最優(yōu)解的條件？原原始可行性條件原始最優(yōu)性條件令Y=CBB-1，代入原始最優(yōu)性條件，YAC對偶可行性條件25例 用對偶單純形法求解單純形法大M 法剩余變量、人工變量 用（-1）乘不等式兩邊，再引入松弛變量。26先選出基變量后選進基變量原問題，符合原始最優(yōu)性條件，但不可行27最優(yōu)解X*=（7，0，4，0）TZ*=-728例6 用對偶單純形法求解（P）291 - 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