規(guī)劃數(shù)學(xué)對偶理論ppt課件(編輯修改稿)
2025-05-30 06:49 本頁面
【文章內(nèi)容簡介】 CY ?bYYXC ?? XA對偶問題 (min)的任何可行解 Y， 其目標(biāo)函數(shù)值總是 不小于原問題 (max)任何可行解 X的目標(biāo)函數(shù)值 弱 對偶定理推論 原問題的任何可行解目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下限；對偶問題的任何可行解目標(biāo)函數(shù)值是原問題目標(biāo)函數(shù)值的上限 ? 如果原 (對偶 )問題為無界解，則其對偶 (原 )問題無可行解 ? 如果原 (對偶 )問題有可行解，其對偶 (原 )問題無可行解，則原問題為無界解 ? 當(dāng)原問題 (對偶問題 )為無可行解 ,其對偶問題 (原問題 )或具有無界解或無可行解 bYYXC ?? XA (3)強(qiáng)對偶性 證：由弱對偶定理推論 1，結(jié)論是顯然的。 X? Y?bYXC ?? ? X? Y?若 是原問題的可行解，是對偶問題可行解，當(dāng) , , 分別是相應(yīng)問題的最優(yōu)解 XCbY ??bYXC ?? ?若bYbY ??是使目標(biāo)函數(shù)取最小值的解，因此是最優(yōu)解 Y?可行解是最優(yōu)解的性質(zhì) (最優(yōu)性準(zhǔn)則定理 ) (4) 對偶 定理 若原問題和對偶問題兩者皆可行 ,則兩者均有最優(yōu)解 ,且此時(shí)目標(biāo)函數(shù)值相等 . 第 1部分 :證明兩者均有最優(yōu)解 證明分兩部分 由于原問題和對偶問題均可行 ,根據(jù)弱對偶性 ,可知兩者均有界 ,于是均有最優(yōu)解 . bYXC ?第 2部分 :證明有相同的目標(biāo)函數(shù)值 設(shè) 為原問題的最優(yōu)解 X? 它所對應(yīng)的基矩陣是 B， 則其檢驗(yàn)數(shù)滿足 C ? CBB?1A ? 0 bBX 1? ??因此有對偶問題目標(biāo)函數(shù)值 而原問題最優(yōu)解的目標(biāo)函數(shù)值為 0??? 1 ??? ? YCAYBCY B ，則有令顯然 為對偶問題的可行解。 Y?bBCbY B 1? ????bBCXCz B 1? ???證畢 故由最優(yōu)解準(zhǔn)則定理可知 為對偶問題的最優(yōu)解 . Y?對偶定理推論 ? 根據(jù)對偶定理第 2部分的證明 ,可以得出 :若互為對偶的線性規(guī)劃問題中的任一個(gè)有最優(yōu)解 ,則另一個(gè)也有最優(yōu)解 ,且目標(biāo)函數(shù)值相等 . 綜上所述 ,一對對偶問題的解必然是下列三種情況之一 : ? 原問題和對偶問題都有最優(yōu)解 ? 一個(gè)問題具有無界解 ,另一個(gè)問題無可行解 ? 原問題和對偶問題都無可行解 (5)互補(bǔ)松弛 定理 證：由定理所設(shè)，可知有 Y?X? SXSYY?X?設(shè) , 分別是原問題和對偶問題的可行解， 為原問題的松弛變量的值，為對偶問題剩余變量的值。 , 分別是原問題和對偶問題最優(yōu)解的充分必要條件是 0?? ??SS YXXY0,?? ??? SS XXbXXA0,?? ??? SS YYCYAY分別以 左乘 (1)式，以 右乘 (2)式后，兩式相減，得 Y? X?XCbYXYXY SS ???? ???0?? ?? XYXY SS若根據(jù)最優(yōu)解判別定理， 分別是原問題和對偶問題最優(yōu)解。反之亦然。 YX ?,?證畢 。 （ 1） （ 2） 0?? ?? SS YXXY即0?? ?? XCbY XCbY ?? ?max z=CX . AX+XS=b X, XS ≥0 min w=Yb . AYYS=C Y, YS ≥0 XYS=0 YXS=0 m n = Y YS A I C n = A XS I b n m m X 原始問題和對偶問題變量、松弛變量的維數(shù) 原始問題和對偶問題最優(yōu)解之間的互補(bǔ)松弛關(guān)系 maxz=CX . AX+XS=b X, XS≥0 min w=bY . AYYS=C Y, YS≥0 maxz=CX . AX≤b X ≥0 min w=bY . AY≥C Y≥0 對偶 引進(jìn)松弛變量 引進(jìn)松弛變量 XYS=0 YXS=0 互補(bǔ)松弛關(guān)系 X， Xs Y， Ys y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 對偶問題的變量 原始問題的松弛變量 xjym+j=0 yixn+i=0 (i=1,2,…,m。 j=1,2,…,n) 在一對變量中，其中一個(gè)大于 0，另一個(gè)一定等于 0 原始問題的變量 對偶問題的松弛變量 (6)原問題單純形表檢驗(yàn)數(shù)行與對偶問題解的關(guān)系 ? 原問題單純形表檢驗(yàn)數(shù)的相反數(shù)對應(yīng)對偶問題的一個(gè)基解 .顯然 ,原問題最終單純形表檢驗(yàn)數(shù)的相反數(shù)對應(yīng)對偶問題的一個(gè)基可行解 BX NX SX1SYNBCC BN 1?? 1?? BC B0 2SY? Y?證：標(biāo)準(zhǔn)化后的原問題和對偶問題的表達(dá)式為 ： 0,CXm a x :????SSXXbXAXz原問題0,min :????SSYYCYYAYb?對偶問題若 B是 A中的一個(gè)基， A=（ B， N） ?????????0,XCm a x :SNBSNBNNBBXXXbXNXBXXCz原問題改寫為),(0,Ybm in :212121SSSSSNSBSYYYYYYCYYNCYYB?????????????對偶問題為原問題解為 XB=B1b ， BS
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1