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