李宇騫《淺談信息學(xué)競賽中的線性規(guī)劃——簡潔高效的單純形法實(shí)現(xiàn)與應(yīng)用》

1、淺談信息學(xué)競賽中的線性規(guī)劃淺談信息學(xué)競賽中的線性規(guī)劃簡潔高效的單純形法實(shí)現(xiàn)與應(yīng)用簡潔高效的單純形法實(shí)現(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)用 單純形法簡介 實(shí)現(xiàn)構(gòu)造模型解線性規(guī)劃定義 線性規(guī)劃：在滿足一些線性等式或者不線性等式或者不等式等式的條件下，最優(yōu)化一個(gè)線性函數(shù)線性函數(shù)。 x1+x2+x3+x4 -2x1+8x2+0

2、 x3+10 x4 = 50 x1 =0 x2=4 x1+5=x2多物網(wǎng)絡(luò)流源點(diǎn)1源點(diǎn)2匯點(diǎn)1匯點(diǎn)2要求流量要求流量多物網(wǎng)絡(luò)流 k個(gè)物品，那么對(duì)每個(gè)邊，設(shè)k個(gè)變量，分別代表該物品在此邊上的流量。 最優(yōu)化的目標(biāo)函數(shù)：無只求可行解 約束： 所有物品流量和不超過邊容量限制 每個(gè)物品的流都滿足流量平衡條件流量平衡條件 每個(gè)物品總流量達(dá)到它的要求流量單純形法 標(biāo)準(zhǔn)形式統(tǒng)一問題的描述 主程序主程序調(diào)整法調(diào)整法 松弛形式方便程序中點(diǎn)的表示 轉(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個(gè)約束，除了n個(gè)變量的非負(fù)限制外，還滿足m個(gè)約束，第j個(gè)約束為1niiic xj1= b (1 = j =0 xn=0 x1=0 xn=0j1=0n+jj1= bnijiixa x第第i個(gè)不等式取等號(hào)時(shí)就是個(gè)不等式取等號(hào)時(shí)就是xi=0單純形法 松弛形式（Slack form）n維空間中的一個(gè)頂點(diǎn)n個(gè)不等式取等號(hào)n個(gè)變量取0單純形法 松弛形式（Slack

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