對偶性與對偶算法-預覽頁
【正文】 說 明在 以后產(chǎn)生的基矩陣不可能等于 對應的基矩 陣，因此， 在非退化條件下可以保證算法收斂于最 優(yōu)解 ，在退化情況下，只要采取輔助措施避免在具 有相同 值的幾個基矩陣中循環(huán)就可以保證收斂 z? z?? zz ?? ??z? z?z?()()()?? ? ??jtjkt j kxz z za?? ? ? ? ?1 1 2 21 1 2 2m a x .0 , 1nnnnjzP x P x P x bc x c x c x zx j n? ? ? ?? ? ? ?? ? ? ?為什么叫對偶單純型法 ？ m in . , 1TTjjYbjnY P c ? ? ??原問題 對偶問題 和一次迭代后的 都是對偶問題的 可行解，目標值滿足 ，該算法 的本質(zhì)是 在對偶問題的可行頂點集中沿著目標函數(shù)下 降路徑找到最優(yōu)頂點 ，所以叫對偶單純型法 1TTBBY C B ?? 1TTBBY C B ??? ??11? ?TTBBz C B b C B b z?? ? ??? ? ?1x2x? ?0,4? ?0,0可行集 ? ?5,0? ?3,3? ?0,5例 1 的可行集和目標函數(shù)等值線如下圖所示，其中 黃點是基本可行解，黑點是不可行基矩陣確定的點 對偶單純型法的幾何意義 0?z3?z?z9?z對偶單純型法 是從不可行區(qū) 域逐漸減少目 標函數(shù)值逼近 最優(yōu)解，如右 圖從 到最 優(yōu)解 ? ?,? ?3,3? ?,什么時候用對偶單純型法 ？ 例、 0,0,012526 s .t .52415m in32132132321??????????xxxxxxxxxxx等價問題 ? ?0121012501160 s .t .0,0,5,24,15m a x????????????????????????????XXX上述問題沒有明顯的初始可行基，需引入人工變量，但 有明顯的對偶可行基，用對偶單純型法不需要人工變量 ?原問題 結論： 對偶單純型法適用于 的下述線性規(guī)劃問題 ? ?0,s . t . m in ?? XbAXXC T ?0?C靈敏度分析 假定已求得最優(yōu)可行基 ，并獲得 等有關數(shù)據(jù) 對于標準線性規(guī)劃問題 0 s .t .m a x??XbAXXC T?B若某些參數(shù)發(fā)生變化，如 1?BbbbCCC ??? ?????? ,如何利用已知數(shù)據(jù)確定新的最優(yōu)解？ R H SBV13254321??????zxxxxxxxx51,052426155 s .t .2m a x5214213221??????????????ixxxxxxxxxxxzi例 1 最終單純型表 2121 xxzxxz ?????如果 目標函數(shù)改變 ： 最終單純型表 1 2 3 4 5231B V RH S0 1 0 0. 25 1. 5 1. 50 0 1 1. 25 7. 5 7. 51 0 0 0. 25 0. 5 3. 51. 5 2 0 0 0x x x x xxxxz???繼續(xù)迭代 ??1 2 3 4 5231B V RH S0 1 0 0. 25 1. 5 1. 50 0 1 1. 25 7. 5 7. 51 0 0 0. 25 0. 5 3. 50 0 0 0. 12 5 2. 25 8. 25x x x x xxxxz??????如果 常數(shù)向量改變 ： ? ? ? ? TT bb 5,32,155,24,15 ???? ??最終單純型表 1 2 3 4 5223311B V RH S?0 1 0 0. 25 1. 5?0 0 1 1. 25 7. 5?1 0 0 0. 25 0. 50 0 0 0. 25 0. 5x x x x xxxxxxx??????其中新的常數(shù)向量為 ，如果 ，已經(jīng)得到 最優(yōu)解，否則可用對偶單純型法繼續(xù)迭代 bB ???1 01 ??? bB ?能否從最終單純型表中找出 ？ 1?Bzxxxxxxxx0001251001124010261500150R H SBV54354321初始單純型表 R H SBV13254321??????zxxxxxxxx最終單純型表 ? ????????????????,1132PPP?? ? ?? 1132 , PPP?? ?nPPPA , 21 ??一般情況：若在標準型初始矩陣 中存 在單位陣 ，比如 由于單純型表的各列向量等于 ? ??????????????11, )()2()1( ?? mPPP ???njPBP jj ???? ? 1,? 1所以 只要將最初的單位向量所在列的最終數(shù)據(jù)按單位向量在 單位矩陣中的位置排好就可以得到 ? ?? ? ? ?)()2()1()(1)2(1)1(1)()2()1(11?,?,?,mmmPPPPBPBPBPPPBB????????????????????1?B注意： 中各 所在列數(shù)取決于基變量所在行數(shù) ！ BiP
教學課件相關推薦
鄂ICP備17016276號-1