算法合集之《淺談信息學(xué)競賽中的線性規(guī)劃——簡潔高效的單純形法

1、淺談信息學(xué)競賽中的線性規(guī)劃淺談信息學(xué)競賽中的線性規(guī)劃簡潔高效的單純形法實現(xiàn)與應(yīng)用簡潔高效的單純形法實現(xiàn)與應(yīng)用 引子最優(yōu)匹配網(wǎng)絡(luò)流最短路資源優(yōu)化配置問題最佳物資供給問題多物網(wǎng)絡(luò)流引子最優(yōu)匹配網(wǎng)絡(luò)流最短路有更好的特殊解法資源優(yōu)化配置問題資源優(yōu)化配置問題最佳物資供給問題最佳物資供給問題多物網(wǎng)絡(luò)流多物網(wǎng)絡(luò)流只有線性規(guī)劃引子 無論作為替代解法或者唯一解法構(gòu)造模型解線性規(guī)劃一勞永逸復(fù)雜復(fù)雜因題而異簡單簡單概覽 定義與簡單應(yīng)用 單純形法簡介 實現(xiàn)構(gòu)造模型解線性規(guī)劃定義 線性規(guī)劃：在滿足一些線性等式或者不線性等式或者不等式等式的條件下，最優(yōu)化一個線性函數(shù)線性函數(shù)。 x1+x2+x3+x4 -2x1+8x2+0

2、 x3+10 x4 = 50 x1 =0 x2=4 x1+5=x2多物網(wǎng)絡(luò)流源點1源點2匯點1匯點2要求流量要求流量多物網(wǎng)絡(luò)流 k個物品，那么對每個邊，設(shè)k個變量，分別代表該物品在此邊上的流量。 最優(yōu)化的目標(biāo)函數(shù)：無只求可行解 約束： 所有物品流量和不超過邊容量限制 每個物品的流都滿足流量平衡條件流量平衡條件 每個物品總流量達(dá)到它的要求流量單純形法 標(biāo)準(zhǔn)形式統(tǒng)一問題的描述 主程序主程序調(diào)整法調(diào)整法 松弛形式方便程序中點的表示 轉(zhuǎn)軸操作最核心的調(diào)整操作單純形法 標(biāo)準(zhǔn)形式(Standard form) 最大化 x1+x2+x3+x4 滿足： x1+2x2+3x3 = 3 x4 = 0目標(biāo)函數(shù)要求最

3、大化目標(biāo)函數(shù)要求最大化所有的變量都有非負(fù)限制所有的變量都有非負(fù)限制所有的限制條件所有的限制條件都是小于等于的都是小于等于的單純形法 標(biāo)準(zhǔn)形式(Standard form)mnacb單純形法 標(biāo)準(zhǔn)形式(Standard form) 最大化 共n+m個約束，除了n個變量的非負(fù)限制外，還滿足m個約束，第j個約束為1niiic xj1= b (1 = j =0 xn=0 x1=0 xn=0j1=0n+jj1= bnijiixa x第第i個不等式取等號時就是個不等式取等號時就是xi=0單純形法 松弛形式（Slack form）n維空間中的一個頂點n個不等式取等號n個變量取0單純形法 松弛形式（Slack

4、 form）點點松弛形式松弛形式單純形法 轉(zhuǎn)軸操作（Pivot）n-1個等式確定一條邊調(diào)換N中的某一個元素沿著另外n-1個等式所確定的邊到達(dá)另一個點單純形法 時間復(fù)雜度 最多有 個松弛形式nn mC頂點的個數(shù)遠(yuǎn)不到這么多頂點的個數(shù)遠(yuǎn)不到這么多調(diào)整法調(diào)整法“爬爬”得很快，經(jīng)過得很快，經(jīng)過很少的點以后就達(dá)到了最優(yōu)很少的點以后就達(dá)到了最優(yōu)實現(xiàn) 細(xì)節(jié)決定成敗 系數(shù)矩陣的表示以退為進(jìn) 初始化中X0的處理被忽略的關(guān)鍵 貪心的優(yōu)化小改動帶來速度上的大飛躍實現(xiàn) 編程復(fù)雜度 200行行 110行行17個空行12行注釋18個“”14行讀入、輸出UVA10498，沒有初始化，沒有初始化步驟的單純形法步驟的單純形法實現(xiàn) 優(yōu)化貪心：每一次調(diào)整使目標(biāo)函數(shù)變得盡量大！貪心：每一次調(diào)整使目標(biāo)函數(shù)變得盡量大！ 普通的最優(yōu)化過程25行 加優(yōu)化以后的過程35行速度？測試 200個變量、200個約束普通程序優(yōu)化程序LINDO時間（秒）811操作數(shù)（Pivot）5396336558測試 300個變量、200個約束普通程序優(yōu)化程序LINDO時間（秒）1111操作數(shù)（Pivot）5310349578測試 300個變量、300個約束普通程序優(yōu)化程序LINDO時間（秒）10577操