單純型算法的復(fù)雜性及改進(jìn)途經(jīng)(參考版)
2025-07-21 13:53本頁面
【正文】 單純型算法的復(fù)雜性及改進(jìn)途經(jīng) 說明單純型算法計(jì)算復(fù)雜性的例子 例、 111m a x. 11 , 2nj j jxxx x x j n???????? ? ? ? ? ?0 0 .5???2n? ? ?1, 1 ??? ?2,1???? ?2,??21xx??1 1x ?? ?1,?12 1xx? ??1x ??其中 （ KleeMinty， 1971 ） 的可行集 對(duì)原問題進(jìn)行可逆的線性變換，令 211 2 1m a xs. t. 11xxx x x?????? ? ?21 1 2 1 2 2,x y x y y? ? ? ? ?? ? ? ? ?原問題 變換后的等價(jià)問題 1 2 2111 2 212m a xs. t. 1220 , 0yyyyyyy??? ? ?????? ? ???? ?1 1 2 2 1 2,y x y x x? ? ? ?? ? ? ?則 ?1 2 21111 2 2 21 2 1 2m a xs. t. 1220 , 0 , 0 , 0yyysy y sy y s s??? ? ???? ? ?? ? ? ?? ? ? ?? ?0, 02 0y ?1 1y ???1 0y ?11 2 222yy? ? ??? ? ?變換后問題的標(biāo)準(zhǔn)形式 變換后的可行集 對(duì)任何給定算法，可選擇參數(shù)經(jīng)過所有 個(gè)頂點(diǎn) ！ 1y221?如果選最小正檢驗(yàn)數(shù)進(jìn)基，取 ，還是 進(jìn)基 從 出發(fā)用單純型法求解上述問題 2 1? ?1y如果選最大檢驗(yàn)數(shù)進(jìn)基，取 ， 進(jìn)基 2 1? ?11 2 12 3 2111xx x xx x x???????? ? ?? ? ?3n? 的可行集 ? ?? ?1 , 1 , 1? ? ???? ?? ?22, 1 , 1? ? ? ???? ?23,? ? ?? ?21, ,??32xx??321xx???? ?? ?1 , 1 , 1 1? ? ?? ? ?? ?? ?22, 1 , 1 1? ? ? ?? ? ?? ?23, , 1? ? ??? ?21, ,1???對(duì)原問題進(jìn)行可逆的線性變換，令 ? ? ? ?21 1 2 1 2 2 3 1 2 2 3 3,x y x y y x y y y? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ?? ? ? ? 21 1 2 2 1 2 3 3 2 3,y x y x x y x x? ? ? ? ? ? ?? ? ? ? ? ?則 311 2 12 3 2m a x. 111xxx x xx x x???????? ? ?? ? ?原問題 變換后的等價(jià)問題 1 2 2 3 3111 2 221 2 2 3 31 2 3m a x. 1222 2 20 , 0 , 0y y yyyyy y yy y y???? ? ?? ? ? ???????? ? ?? ? ? ?? ? ??? ?? ?1 , 1 , 1? ? ???? ?? ?22, 1 , 1? ? ? ???? ?23,? ? ? ? ?21, ,??? ?? ?1 , 1 , 1 1? ? ?? ? ?? ?? ?22, 1 , 1 1? ? ? ?? ? ?? ?23, , 1? ? ??? ?21, ,1???1 2 2 3 3111 2 221 2 2 3 31 2 3m a x. 1222 2 20 , 0 , 0y y yyyyy y yy y y???? ? ?? ? ? ???????? ? ?? ? ? ?? ? ?經(jīng)過 個(gè)頂點(diǎn) ！ 321?對(duì)已經(jīng)提出的進(jìn)出基規(guī)則，均能設(shè)計(jì)出要經(jīng)歷的 頂點(diǎn)個(gè)數(shù)是變量維數(shù)的指數(shù)函數(shù)的例子 但是，也不能證明無論采用什么進(jìn)出基規(guī)則，均 能設(shè)計(jì)出要經(jīng)歷的頂點(diǎn)個(gè)數(shù)是變量維數(shù)的指數(shù)函 數(shù)的例子 只要 比較大，搜索 個(gè)頂點(diǎn)的計(jì)算量就不 可能完成！能否找到?jīng)]有上述問題的其他算法？ 21n ?n算法的計(jì)算復(fù)雜性 如何描述算法的計(jì)算復(fù)雜性？ 要排除機(jī)器性能和程序性能的影響 ?要排除問題規(guī)模的影響 以具體 實(shí)例 的全部數(shù)據(jù)的大小為變量 ? 以一種最 基本的計(jì)算模型 的 運(yùn)算次數(shù) 描述 ?要排除不同數(shù)據(jù)的影響 考慮 最壞 （為什么不是平均？）情況 計(jì)算復(fù)雜性： ? ? ? ?()?m a xq Q Lf L f q??L ：二進(jìn)制數(shù)的總位數(shù) ()QL ：全部數(shù)據(jù)的總位數(shù)不大于 的具體實(shí)例集 L? ??fq ：實(shí)例 的 基本計(jì)算模型 的 基本運(yùn)算次數(shù) q多項(xiàng)式算法 ： 存在正整數(shù) 和常數(shù) 滿足 通常記為 k C () kf L C L?? ?() kf L O L?現(xiàn)有的單純型算法都不是多項(xiàng)式算法 ！ 說明： 以上數(shù)據(jù)均為轉(zhuǎn)換成整數(shù)后的數(shù)據(jù) 線性規(guī)劃問題是否有多項(xiàng)式算法 ？ q一個(gè)有用的事實(shí)： 如果一個(gè)算法中間過程產(chǎn)生的數(shù)據(jù)位數(shù)均有 的 多項(xiàng)式上界，而算法的所有 代數(shù)運(yùn)算 次 數(shù)存在 的多項(xiàng)式上界，那么 （實(shí)例 的 基本計(jì)算模型 的 基本運(yùn)算 次數(shù)） 也有 的多項(xiàng)式上界 LLL ? ??fq理由：在基本計(jì)算模型里完成所有代數(shù)運(yùn)算的算 法都是多項(xiàng)式算法 用處： 分析計(jì)算復(fù)雜性時(shí)不用知道基本計(jì)算模型 線性規(guī)劃的橢球算法 （ Khachian，哈奇楊， 1979） 規(guī)范形式線性規(guī)劃問題及其對(duì)偶問題 原問題 據(jù)對(duì)偶性原理，當(dāng)且僅當(dāng) 和 滿足以下方程時(shí)，它 們分別是原問題和對(duì)偶問題的最優(yōu)解 m in. 0TCXA X bX??m a xs. t. 0TTbYA Y CY??對(duì)偶問題 X Y, , 0 , , 0T T TC X b Y A X b X A Y C Y? ? ? ? ?求解規(guī)范形式的線性規(guī)劃問題等價(jià)于解決下述問題： 或者找到等式和不等式方程組的解，或者斷定無解 , , 0 , , 0T T TC X b Y A X b X A Y C Y? ? ? ? ?00000000TTTTTCbCbX bAYICAI?? ????? ????? ???? ?????? ? ?????? ? ? ? ??? ?????? ??????????可以寫成下述不等式方程組 等式和不等式方程組 其系數(shù)矩陣是 列滿秩矩陣 求解線性規(guī)劃問題可等價(jià)為求解下述 判定問題 ： X ??? ?nX R A X b? ? ? ?
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1