國(guó)家集訓(xùn)隊(duì)2007論文集6.李宇騫《淺談信息學(xué)

1、淺談信息學(xué)競(jìng)賽中的線(xiàn)性規(guī)劃——簡(jiǎn)潔高效的單純形法實(shí)現(xiàn)與應(yīng)用,浙江省杭州第二中學(xué)李宇騫,引子,最優(yōu)匹配網(wǎng)絡(luò)流最短路資源優(yōu)化配置問(wèn)題最佳物資供給問(wèn)題多物網(wǎng)絡(luò)流,引子,最優(yōu)匹配網(wǎng)絡(luò)流最短路,資源優(yōu)化配置問(wèn)題最佳物資供給問(wèn)題多物網(wǎng)絡(luò)流,,只有線(xiàn)性規(guī)劃,引子,無(wú)論作為替代解法或者唯一解法,構(gòu)造模型,解線(xiàn)性規(guī)劃,一勞永逸復(fù)雜,因題而異簡(jiǎn)單,,,概覽,定義與簡(jiǎn)單應(yīng)用單純形法簡(jiǎn)介實(shí)現(xiàn),構(gòu)造模型,解線(xiàn)性規(guī)劃,定義,線(xiàn)性規(guī)

2、劃：在滿(mǎn)足一些線(xiàn)性等式或者不等式的條件下，最優(yōu)化一個(gè)線(xiàn)性函數(shù)。x1+x2+x3+x4-2x1+8x2+0x3+10x4 >= 50x1 >=0x2<=4x1+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ù)：無(wú)——只求可行解約束：所有物品流量和不超過(guò)邊容

3、量限制每個(gè)物品的流都滿(mǎn)足流量平衡條件每個(gè)物品總流量達(dá)到它的要求流量,單純形法,標(biāo)準(zhǔn)形式——統(tǒng)一問(wèn)題的描述主程序——調(diào)整法松弛形式——方便程序中點(diǎn)的表示轉(zhuǎn)軸操作——最核心的調(diào)整操作,單純形法,標(biāo)準(zhǔn)形式(Standard form)最大化 x1+x2+x3+x4滿(mǎn)足：x1+2x2+3x3 = 0,目標(biāo)函數(shù)要求最大化,所有的變量都有非負(fù)限制,,,所有的限制條件都是小于等于的,,單純形法,標(biāo)準(zhǔn)形式(Standard

4、 form),單純形法,標(biāo)準(zhǔn)形式(Standard form)最大化共n+m個(gè)約束，除了n個(gè)變量的非負(fù)限制外，還滿(mǎn)足m個(gè)約束，第j個(gè)約束為,單純形法,形象的理解,最優(yōu)值在某一頂點(diǎn)上用調(diào)整法，從一個(gè)頂點(diǎn)出發(fā)，不斷尋找目標(biāo)函數(shù)更大的點(diǎn)，直到到達(dá)一個(gè)最優(yōu)值。,單純形法,主程序,初始化：首先找到一個(gè)頂點(diǎn),最優(yōu)化：不斷調(diào)整，直到最優(yōu),化歸,單純形法,,頂點(diǎn),松弛形式,一個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)松弛形式,數(shù)形結(jié)合,單純形法,n維空間中的一個(gè)頂點(diǎn),,

5、n個(gè)數(shù)的坐標(biāo),n個(gè)n元一次方程組的解,n個(gè)不等式取等號(hào),,,,,單純形法,松弛形式（Slack form)將n+m個(gè)不等式和n+m個(gè)變量一一對(duì)應(yīng),x1>=0,xn>=0,…,x1>=0,xn>=0,xn+j>=0,…,第i個(gè)不等式取等號(hào)時(shí)就是xi=0,單純形法,松弛形式（Slack form）,n維空間中的一個(gè)頂點(diǎn),n個(gè)不等式取等號(hào),n個(gè)變量取0,N,單純形法,松弛形式（Slack form）,N,N,點(diǎn)

6、,點(diǎn),松弛形式,松弛形式,單純形法,轉(zhuǎn)軸操作（Pivot）,,,,,,n-1個(gè)等式確定一條邊,,單純形法,時(shí)間復(fù)雜度最多有 個(gè)松弛形式,頂點(diǎn)的個(gè)數(shù)遠(yuǎn)不到這么多,調(diào)整法“爬”得很快，經(jīng)過(guò)很少的點(diǎn)以后就達(dá)到了最優(yōu),實(shí)現(xiàn),細(xì)節(jié)決定成敗系數(shù)矩陣的表示——以退為進(jìn)初始化中X0的處理——被忽略的關(guān)鍵貪心的優(yōu)化——小改動(dòng)帶來(lái)速度上的大飛躍,編程復(fù)雜度,速度,實(shí)現(xiàn),編程復(fù)雜度200行110行,17個(gè)空行,12行注釋

7、,18個(gè)“{”,14行讀入、輸出,UVA10498，沒(méi)有初始化步驟的單純形法,實(shí)現(xiàn),優(yōu)化貪心：每一次調(diào)整使目標(biāo)函數(shù)變得盡量大！普通的最優(yōu)化過(guò)程——25行加優(yōu)化以后的過(guò)程——35行,速度？,測(cè)試,200個(gè)變量、200個(gè)約束,測(cè)試,300個(gè)變量、200個(gè)約束,測(cè)試,300個(gè)變量、300個(gè)約束,總結(jié),線(xiàn)性約束,,線(xiàn)性函數(shù)的最優(yōu)值,單純形法,非多項(xiàng)式級(jí)別，但是速度很快,簡(jiǎn)單的優(yōu)化，非常好的效果,總結(jié),優(yōu)美的單純形法,松弛形式——數(shù)形結(jié)合