對偶性與對偶算法(參考版)
2024-10-15 19:00本頁面
【正文】 對偶性與對偶算法 線性規(guī)劃對偶性質(zhì) 1 1 2 21 1 2 2m a x .0 , 1nnnnjc x c x c xP x P x P x bx j n? ? ?? ? ? ?? ? ? ?? ?)()2()1( , mjjj PPPB ??01 ?? bB ?求解標(biāo)準(zhǔn)線性規(guī)劃問題 最終要找到一個(gè)基陣 滿足 1TBC B b?1 0 , 1Tj j B jc C B P j n? ?? ? ? ? ? ?而最優(yōu)目標(biāo)值等于 記 ，原問題有最優(yōu)解時(shí)， 滿足以下約束 可否在滿足以上約束的解中找到 ，進(jìn)而找到 ？ BY,1T jjY P c j n? ? ? ?1TTBBY C B ??BBY設(shè) 是原問題的任意一個(gè)可行解，即滿足 對任何滿足不等式約束 的 ，成立 下述線性規(guī)劃問題的最優(yōu)目標(biāo)值不會 小于原問題任何可行解的目標(biāo)函數(shù)值 ? ?1? ? ?, TnX x x?1 1 2 2? ? ? ?, 0 , 1n n jP x P x P x b x j n? ? ? ? ? ? ? ?Y,1TjjY P c j n? ? ? ?1 1 1? ? ?n n nT T Tj j j j j jj j jY b Y P x Y P x c x? ? ?? ? ?? ? ?m ins. t. , 1TTjjYbY P c j n? ? ? ???? ?m i n s . t . , 1T T TB j jY b Y b Y P c j n? ? ? ? ?當(dāng) 是原問題最優(yōu)基陣時(shí)， 滿足 B 1TTBBY C B ??11, 1 ,T T T T TB j B j j B B BY P C B P c j n Y b C B b C X??? ? ? ? ? ? ?其中 是 決定的最優(yōu)的基本可行解 BBX, , 1T T T TB B j jY b C X Y b Y P c j n? ? ? ? ? ??求解上面的線性規(guī)劃問題能找到原問題的最優(yōu)基矩陣 11m a x . 0 , 1njjjnjjjjcxP x bx j n???? ? ? ???定義：標(biāo)準(zhǔn)線性規(guī)劃問題的對偶問題 原問題 ?對偶問題 m in. , 1TTjjbYP Y c j n? ? ? ?矩陣形式（ ） m a x . 0TCXA X bX???m ins . t. TTbYA Y C?? ?12, , , nA P P P?原問題和對偶問題之間的關(guān)系 強(qiáng)對偶性：若原問題有最優(yōu)解 ，則對偶問題一定也 有最優(yōu)解 ，并且最優(yōu)目標(biāo)值相等，即 則 ? ? ?,0 TA X b X A Y C? ? ?弱對偶性：若 和 分別是原、對偶問題可行解，即 ?X ?YX?Y?TTb Y C X???? ?TTb Y C X?規(guī)范形式線性規(guī)劃問題的對偶問題 ? ?? ?m a x. 0TTbYA Y CY?????原問題 ?標(biāo)準(zhǔn)線性規(guī)劃問題 ? ?? ?m a x , 0 . ,0 , 0TTmXCXXA I bXXX???? ??????????????標(biāo)準(zhǔn)線性規(guī)劃對偶問題 m i n . 0TTmbYCAYI?? ? ?????? ??? ????原問題對偶問題 m i n . 0TCXA X bX??m a xs. t. 0TTbYA Y CY??等價(jià)問題 標(biāo)準(zhǔn)線性規(guī)劃問題對偶問題的對偶問題 原問題 ?對偶問題 ?m ins . t. TTbYA Y C?? ?? ?121212m in ,. ,0 , 0TTTTYbbYYA A CYYY??? ??????????????m a x . 0TCXAbXA bX????? ?????????? ???m a x . 0TCXA X bX??對偶問題的對偶問題是原問題 結(jié)論： 任何原問題和對偶問題之間都存在下述相互關(guān)系 弱對偶性 ：原對偶問題任何可行解的目標(biāo)值都是另一問 題最優(yōu)目標(biāo)值的界（推論：原對偶問題目標(biāo) 值相等的一對可行解是各自的最優(yōu)解） 強(qiáng)對偶性 ：原對偶問題只要有一個(gè)有最優(yōu)解，另一個(gè)就 有最優(yōu)解，并且最優(yōu)目標(biāo)值相等 原 對偶 有最優(yōu)解 有最優(yōu)解 問題無界 問題無界 無可行解 無可行解 不會 不會 不會 不會 不會 不會出現(xiàn)的情況： 原問題 對偶問題 0 s .t .m a x??XbAXXC T?0 s .t .m in??YCYAYbTT?含義：如果原（對偶）問題某不等式是松的（不等于 0） 則其相應(yīng)的對偶（原）變量必須是緊的（等于 0） ? ? ? ? 0??,0?? ???? CYAXXAbY TTT ?互補(bǔ)松弛性定理 若 、 分別是原（對偶）問題可行解，則它們分別 是各自問題最優(yōu)解的充要條件是滿足互補(bǔ)松弛性等式 X? Y?? ? ? ? jcYPxiXaby jTjjiii ??????
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1