對偶理論和靈敏度分析.ppt

《對偶理論和靈敏度分析.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、對偶理論和靈敏度分析1.單純形的矩陣描述用矩陣語言描述單純形法的關(guān)鍵是寫出兩個基本的表達(dá)式,設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型為maxz=CXAX=bX≥0C=(CB,CN)，X=(XB,XN)’，A=(B,N)由約束條件AX=(B,N)(XB,XN)=BXB+NXN=b，可以得到用非基變量表示基變量的表達(dá)式:XB=B-1b-B-1NXN(1)將(1)式代入目標(biāo)函數(shù)的表達(dá)式,可以得到用非基變量表示目標(biāo)函數(shù)的表達(dá)式.Z=CX=(CB,CN)(XB,XN)’=CBXB+CNXN=CB(B-1-B-1NXN)+CNXN=CBB

2、-1b+(CN-CBB-1N)XN=CBB-1b+σNXN另非基變量等于零，則Z=CBB-1b注意XB檢驗數(shù)為零,實質(zhì)上是CB-CBB-1B=0Y=CBB-1為單純形乘子cxbCBCNθXBXNXBB-1bB-1BB-1N-z-CBB-1b0CN-CBB-1N注意:在初始單位矩陣的位置,在各運算表中就是B-1的所在位置BI……IB-12.改進(jìn)單純形法改進(jìn)單純形法又稱為逆矩陣法或修正單純形法,是在原來單純形法基礎(chǔ)上加以改進(jìn)，關(guān)鍵在于求B-1,有了B-1,單純形算法的各個表中的數(shù)字都可以利用線性規(guī)劃中的原始數(shù)

3、據(jù)計算出來。3對偶理論某廠生產(chǎn)甲乙兩種產(chǎn)品，各自的零部件分別在A、B車間生產(chǎn)，最后都需在C車間裝配，相關(guān)數(shù)據(jù)如表所示：問如何安排甲、乙兩產(chǎn)品的產(chǎn)量，使利潤為最大。產(chǎn)品車間工時單耗甲乙生產(chǎn)能力ABC10023481236單位產(chǎn)品獲利35maxZ=3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.若上例中該廠的產(chǎn)品平銷，現(xiàn)有另一企業(yè)想租賃其設(shè)備。廠方為了在談判時心中有數(shù)，需掌握設(shè)備臺時費用的最低價碼，以便衡量對方出價，對出租與否做出抉擇。在這個問題上廠長面臨著兩種選擇：自行

4、生產(chǎn)或出租設(shè)備。首先要弄清兩個問題：①合理安排生產(chǎn)能取得多大利潤?②為保持利潤水平不降低，資源轉(zhuǎn)讓的最低價格是多少？問題①的最優(yōu)解：x1=4，x2=6，Z*=42。假設(shè)出讓A、B、C設(shè)備所得利潤分別為y1、y2、y3原本用于生產(chǎn)甲產(chǎn)品的設(shè)備臺時，如若出讓，不應(yīng)低于自行生產(chǎn)帶來的利潤，否則寧愿自己生產(chǎn)。于是有y1+0y2+3y3≥3同理，對乙產(chǎn)品而言，則有0y1+2y2+4y3≥5設(shè)備臺時出讓的收益（希望出讓的收益最少值）min?=8y1+12y2+36y3顯然還有y1，y2，y3≥0min?=8y1+12

5、y2+36y3y1+0y2+3y3≥30y1+2y2+4y3≥5y1，y2，y3≥0S.t.maxZ=3x1+5x2x1≤82x2≤123x1+4x2≤36x1,x2≥0S.t.例線性規(guī)劃問題maxz=3x1+5x2stx1+3x2?107x1+4x2?20xj?0;j=1,2.對偶問題為：ming=10y1+20y2sty1+7y2?33y1+4y2?5yi?0;i=1,2。3.1對偶變換的規(guī)則3.2對偶問題的基本性質(zhì)為了便于討論，下面不妨總是假設(shè)(1)對稱性：對偶問題的對偶是原問題。(2)弱對偶性

6、：對偶問題(min)的任何可行解Y0，其目標(biāo)函數(shù)值總是不小于原問題(max)任何可行解X0的目標(biāo)函數(shù)值，即CX0≤Yb0。弱對偶定理推論：原問題的任何可行解目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下限；對偶問題的任何可行解目標(biāo)函數(shù)值是原問題目標(biāo)函數(shù)值的上限。(3)無界性若原(對偶)問題為無界解，則其對偶(原)問題無可行解當(dāng)原問題(對偶問題)為無可行解,其對偶問題(原問題)或具有無界解或無可行解。如果原(對偶)問題有可行解，其對偶(原)問題無可行解，則原問題為無界解。(4)強(qiáng)對偶性可行解是最優(yōu)解的性質(zhì)(最優(yōu)性準(zhǔn)則

7、定理)若原問題的某個可行解X0的目標(biāo)函數(shù)值與對偶問題某個可行解Y0的目標(biāo)函數(shù)值相等，則X0,Y0分別是相應(yīng)問題的最優(yōu)解（5）主對偶定理若原問題和對偶問題兩者皆可行,則兩者均有最優(yōu)解,且此時目標(biāo)函數(shù)值相等。綜上所述，一對對偶問題的解必然是下列三種情況之一:原問題和對偶問題都有最優(yōu)解。一個問題具有無界解，另一個問題無可行解。原問題和對偶問題都無可行解。(6)互補(bǔ)松弛性設(shè)X0,Y0分別是原問題和對偶問題的可行解，Xs為原問題的松弛變量的值、Ys為對偶問題剩余變量的值。X0,Y0分別是原問題和對偶問題最優(yōu)解的充分

8、必要條件是：Y0Xs=YsX0=0(7)原問題單純形表檢驗數(shù)行與對偶問題解的關(guān)系原問題單純形表檢驗數(shù)的相反數(shù)對應(yīng)對偶問題的一個基解.顯然,原問題最終單純形表檢驗數(shù)的相反數(shù)對應(yīng)對偶問題的一個基可行解XBXNXS0CN-CBB-1N-CBB-1YS1-YS2-Y例已知線性規(guī)劃問題：試用對偶理論證明此線性規(guī)劃問題無最優(yōu)解。解：對偶問題為：由第一約束條件顯見，對偶問題無可行解因為（0，0，0）為線性規(guī)劃問題的可行解。而對偶問題無可行解