國家集訓隊2007論文集6.李宇騫《淺談信息學

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

2、劃：在滿足一些線性等式或者不等式的條件下，最優(yōu)化一個線性函數。x1+x2+x3+x4-2x1+8x2+0x3+10x4 >= 50x1 >=0x2<=4x1+5=x2,多物網絡流,,,,,,,,,,,,,,,,,,,,源點1,源點2,匯點1,匯點2,要求流量,多物網絡流,k個物品，那么對每個邊，設k個變量，分別代表該物品在此邊上的流量。最優(yōu)化的目標函數：無——只求可行解約束：所有物品流量和不超過邊容

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

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

5、n個數的坐標,n個n元一次方程組的解,n個不等式取等號,,,,,單純形法,松弛形式（Slack form)將n+m個不等式和n+m個變量一一對應,x1>=0,xn>=0,…,x1>=0,xn>=0,xn+j>=0,…,第i個不等式取等號時就是xi=0,單純形法,松弛形式（Slack form）,n維空間中的一個頂點,n個不等式取等號,n個變量取0,N,單純形法,松弛形式（Slack form）,N,N,點

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

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