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