曹欽翔+線性規(guī)劃與網(wǎng)絡流ppt課件

1、線性規(guī)劃與網(wǎng)絡流線性規(guī)劃與網(wǎng)絡流北京大學 曹欽翔.一一. 網(wǎng)絡流模型網(wǎng)絡流模型n1. 最大流模型n可以沿邊的方向運送貨物n每條邊上的貨物流量有上限n求源點到匯點的最大流量.一一. 網(wǎng)絡流模型網(wǎng)絡流模型n2. 最大流算法nFord-Fulkerson算法nDinic算法nGap優(yōu)化的SAP算法n最高標號法預流推進.一一. 網(wǎng)絡流模型網(wǎng)絡流模型n3. 流量下界n問題1：能否有可行流？n問題2：求最大流求值、求方案n問題3：求最小流求值、求方案.一一. 網(wǎng)絡流模型網(wǎng)絡流模型n4. 費用n問題1：求最小費用最大流n問題2：求最小費用可行流n算法：消負圈+最小費用增廣路算法n5. 點容量n算法：拆點.二

2、二. 線性規(guī)劃線性規(guī)劃n1. 例子n約束條件：n變量：n目的函數(shù)：n最大化.二二. 線性規(guī)劃線性規(guī)劃n2. 普通方式n約束條件：n 或n 或.二二. 線性規(guī)劃線性規(guī)劃n2. 普通方式n變量：n或n或n無限制n目的函數(shù)：n最大化或n最小化.二二. 線性規(guī)劃線性規(guī)劃n3. 各方式相互轉化n(1) 變量n假設原變量類型為：無限制 n那么令，那么n(2) 約束條件n假設原約束條件為n現(xiàn)添加輔助變量，那么.二二. 線性規(guī)劃線性規(guī)劃n4. 線性規(guī)劃的解n(1) 可行解：滿足一切約束條件的解n(2) 最優(yōu)解：可行解中使目的函數(shù)取到最優(yōu)值的解.二二. 線性規(guī)劃線性規(guī)劃n4. 線性規(guī)劃的解n(1) 可行解：滿足

3、一切約束條件的解n(2) 最優(yōu)解：可行解中使目的函數(shù)取到最優(yōu)值的解n注：根據(jù)線性規(guī)劃問題能否有可行解、能否有最優(yōu)解，線性規(guī)劃問題可以分為n無可行解n有無界解n有最優(yōu)解n普通而言，我們最為關注有最優(yōu)解的問題.三三. 網(wǎng)絡流的線性規(guī)劃模型網(wǎng)絡流的線性規(guī)劃模型n1. 最大流問題的線性規(guī)劃模型n流量平衡條件限制條件n ()n 無限制 n 無限制n流量上限限制條件n流量非負變量n求最大流目的函數(shù)nmax .三三. 網(wǎng)絡流的線性規(guī)劃模型網(wǎng)絡流的線性規(guī)劃模型n2. 流量下界n流量限制n變量代換n令.三三. 網(wǎng)絡流的線性規(guī)劃模型網(wǎng)絡流的線性規(guī)劃模型n2. 流量下界n流量平衡條件限制條件n ()n流量上限限制條

4、件n變量類型n求最大流目的函數(shù)nmax .三三. 網(wǎng)絡流的線性規(guī)劃模型網(wǎng)絡流的線性規(guī)劃模型n2. 流量下界n流量平衡條件限制條件n ()n流量上限限制條件n流量非負變量n求最大流目的函數(shù)nmax .三三. 網(wǎng)絡流的線性規(guī)劃模型網(wǎng)絡流的線性規(guī)劃模型n3. 最小費用可行流n限制條件與變量性質n同最大流n求最小費用目的函數(shù)nmin .三三. 網(wǎng)絡流的線性規(guī)劃模型網(wǎng)絡流的線性規(guī)劃模型n4. 點容量n點流量平衡與限制條件n ()n方案一n ()n().三三. 網(wǎng)絡流的線性規(guī)劃模型網(wǎng)絡流的線性規(guī)劃模型n4. 點容量n點流量平衡與限制條件n ()n方案二n ()n()n().三三. 網(wǎng)絡流的線性規(guī)劃模型網(wǎng)絡

5、流的線性規(guī)劃模型n5. 二分圖最大匹配n限制條件n ()n ()n目的函數(shù)nmax .三三. 網(wǎng)絡流的線性規(guī)劃模型網(wǎng)絡流的線性規(guī)劃模型n6. 二分圖最大權值匹配n限制條件n ()n ()n目的函數(shù)nmax .三三. 網(wǎng)絡流的線性規(guī)劃模型網(wǎng)絡流的線性規(guī)劃模型n7. 小結n經(jīng)過線性規(guī)劃模型描寫網(wǎng)絡流問題，其中心在于流量平衡條件。n流量平衡條件的特征是每個變量出現(xiàn)兩次，一次系數(shù)為+1，另一次系數(shù)為-1。n詳細的模型構建，取決于線性規(guī)劃問題中的其他參數(shù)與特征。.四四. 對偶原理與最小割對偶原理與最小割n1. 最小割問題n每條邊有一個非負的權值。n表述一：刪去假設干條邊使得源點到匯點不連通，求刪邊的權值

6、和的最小能夠值。.四四. 對偶原理與最小割對偶原理與最小割n1. 最小割問題n每條邊有一個非負的權值。n表述二：將點集分為(S,T)，記一切從S中出發(fā)到T中的邊的權值和為c(S,T)，求c(S,T)的最小值。.四四. 對偶原理與最小割對偶原理與最小割n2. 線性規(guī)劃對偶問題na. 原問題的變量對應對偶問題的約束條件nb. 原問題的約束條件對應對偶問題的變量nc. 原問題與對偶問題的目的函數(shù)方向相反nd. 對偶問題的對偶問題是原問題.四四. 對偶原理與最小割對偶原理與最小割原問題原問題nmax n約束條件n無限制n變量n無限制對偶問題對偶問題nmin n變量n無限制n約束條件n無限制.四四. 對

7、偶原理與最小割對偶原理與最小割n3. 對偶最優(yōu)性n假設原問題有最優(yōu)解，那么n(1) 對偶問題也有最優(yōu)解n(2) 且兩個問題的最優(yōu)解的目的函數(shù)值相等。.四四. 對偶原理與最小割對偶原理與最小割n4. 最小割的線性規(guī)劃模型n最小割似乎難以建立線性規(guī)劃模型n 最小割模型中的變量點的劃分是一個01離散變量n 最小割模型的目的函數(shù)似乎不是線性函數(shù)，即的權值只需在并且的情況下，才會計入目的函數(shù)。.四四. 對偶原理與最小割對偶原理與最小割n4. 最小割的線性規(guī)劃模型n最小割似乎難以建立線性規(guī)劃模型n 最小割模型中的變量點的劃分是一個01離散變量n 最小割模型的目的函數(shù)似乎不是線性函數(shù)，即的權值只需在并且的情

8、況下，才會計入目的函數(shù)。n從最大流與最小割的關系入手分析n一個是最大，一個是最小n權值又相等n我們似乎看出一些端倪！.四四. 對偶原理與最小割對偶原理與最小割n5. 最大流問題的對偶問題n(1)最大流問題原問題n ()n 無限制 n 無限制nmax .四四. 對偶原理與最小割對偶原理與最小割n5. 最大流問題的對偶問題n(2) 對偶問題n無限制 ()nmin n其中， ， ，其他。.四四. 對偶原理與最小割對偶原理與最小割n5. 最大流問題的對偶問題n(3) 對偶問題的分析na. 在最優(yōu)解中的取值一直等于nb. 根據(jù)的特征，可以令，().四四. 對偶原理與最小割對偶原理與最小割n5. 最大流問

9、題的對偶問題n(4) 簡化的對偶問題n無限制n nmin .四四. 對偶原理與最小割對偶原理與最小割n5. 最大流問題的對偶問題n(4) 簡化的對偶問題n無限制n nmin n這就是最小割問題！n啟發(fā)：n可以利用，這兩個條件表示“當且僅當且時這一邏輯關系n這一關系往往對應最小割模型，或類似對偶模型.四四. 對偶原理與最小割對偶原理與最小割n6. 最大匹配問題的對偶問題n(1) 原問題n ()n ()nmax .四四. 對偶原理與最小割對偶原理與最小割n6. 最大匹配問題的對偶問題n(2) 對偶問題n (當且僅當之間有邊時)nmin n這就是最小點覆蓋問題.四四. 對偶原理與最小割對偶原理與最小

10、割n7. 最優(yōu)匹配問題的對偶問題n(1) 原問題n ()n ()nmax .四四. 對偶原理與最小割對偶原理與最小割n7. 最優(yōu)匹配問題的對偶問題n(2) 對偶問題n (當且僅當之間有邊時)nmin n這就是最小頂標和問題。.四四. 對偶原理與最小割對偶原理與最小割n8. 小結n最大流的對偶問題是最小割n最大匹配的對偶問題是最小點覆蓋n最優(yōu)匹配的對偶問題是最小頂標和.五五. 線性規(guī)劃與經(jīng)典模型線性規(guī)劃與經(jīng)典模型n導言n在備考過程中，熟練掌握各種現(xiàn)有的網(wǎng)絡流問題經(jīng)典模型，可以保證我們在賽場上處理絕大部分的網(wǎng)絡流問題。n但是，當出現(xiàn)新的網(wǎng)絡流模型時，利用問題中描寫的線性規(guī)劃問題輔助思索，是處理一些

11、難題的捷徑。.五五. 線性規(guī)劃與經(jīng)典模型線性規(guī)劃與經(jīng)典模型n1. 經(jīng)典模型一n有個市政建立工程，第個建立工程的受害為(可正可負)。而這些建立工程之間存在著先后建立的依賴關系(保證依賴關系不構成環(huán))。設有組依賴關系，其中第組依賴關系為：n必需先完成第個工程才干開場建立第個工程n問：假設合理的選擇建立的工程，最大的總收益是多少？.五五. 線性規(guī)劃與經(jīng)典模型線性規(guī)劃與經(jīng)典模型n2. 經(jīng)典模型一變形n有個市政建立工程，第個建立工程的受害為(可正可負)。而這些建立工程之間存在著先后建立的依賴關系(保證依賴關系不構成環(huán))。設有組依賴關系，其中第組依賴關系為：n必需先完成第個工程才干開場建立第個工程n假設違

12、反上面規(guī)定，那么需支付的額外建立費用n問：假設合理的選擇建立的工程，最大的總收益是多少？.五五. 線性規(guī)劃與經(jīng)典模型線性規(guī)劃與經(jīng)典模型n3. 經(jīng)典模型二n輸入個帶權開區(qū)間，選出其中一部分，使得數(shù)軸上的恣意一個點都被覆蓋不超越次。問：選出的這些區(qū)間的權值和最大是多少。.六六. 經(jīng)典例題選講經(jīng)典例題選講n導言n由于網(wǎng)絡流這一圖論問題，與線性規(guī)劃這一代數(shù)問題之間嚴密的聯(lián)絡。n通常而言，任何一道網(wǎng)絡流考題，都可以直接圖論建?；蛘呃镁€性規(guī)劃問題建模。.六六. 經(jīng)典例題選講經(jīng)典例題選講n例題1n標題來源：2021年清華集訓營考試n給定一個的稀疏矩陣A，兩個長度分別為的向量，求一個矩陣，使得其滿足：n限制

13、條件：.六六. 經(jīng)典例題選講經(jīng)典例題選講n例題2n標題來源：ACM World Final 2021n一張的芯片上，有些格子曾經(jīng)焊接有零件，有些格子制止焊接零件。問，在滿足下面約束的前提下，至多可以再焊接多少個零件。n每個格子至多焊接一個零件n第i行上的零件總數(shù)與第i列一致n恣意一行的零件數(shù)不得超越總零件數(shù)的A/B.六六. 經(jīng)典例題選講經(jīng)典例題選講n例題3n標題來源：URAL 1833n學校要給名教授分配科研經(jīng)費。由于該學校的教授們通常是兩人協(xié)作共同完成一個科研工程的，所以，教授們要求：n一切協(xié)作進展科研的兩名教授分配到的經(jīng)費之和不小于。n當然，一名教授又能夠參與了多個協(xié)作的科研工程，因此學校

14、想知道，至少需求向一切教授支付多少科研經(jīng)費。.六六. 經(jīng)典例題選講經(jīng)典例題選講n例題4n標題來源：POJ 2699n名選手之間進展單循環(huán)賽。知競賽終了后每一名選手的勝場。問：至多有多少名選手戰(zhàn)勝了一切勝場比他多的選手。.六六. 經(jīng)典例題選講經(jīng)典例題選講n例題5n標題來源：CTSC 2021n2323年，隨著科技的開展以及地球日趨嚴重的人口壓力，人類開場大規(guī)模向火星移民。n令人欣喜的是，移民工程的第一步獲得了宏大的勝利，曾經(jīng)在火星外表建立了個移民站，其中第個移民站的坐標是。n但是在進展后續(xù)的移民任務時，人們遇到了一個嚴峻的問題：如何選擇新建的移民站的地址。.六六. 經(jīng)典例題選講經(jīng)典例題選講n例題5n標題來源：CTSC 2021n經(jīng)過調查確定，需求在火星上再新建個移民站。n知n原有的第個移民站和新建的第個移民站之間信息傳輸?shù)牧髁渴莕新建的第個移民站和第個移民站之間信息傳輸?shù)牧髁渴莕將一