曹钦翔+线性规划与网络流课件

线性规划与网络流线性规划与网络流北京大学 曹钦翔一一.网络流模型网络流模型n1.最大流模型n可以沿边的方向运送货物n每条边上的货物流量有上限n求源点到汇点的最大流量一一.网络流模型网络流模型n2.最大流算法nFord-Fulkerson算法nDinic算法nGap优化的SAP算法n最高标号法预流推进一一.网络流模型网络流模型n3.流量下界n问题1：是否有可行流？n问题2：求最大流（求值、求方案）n问题3：求最小流（求值、求方案）一一.网络流模型网络流模型n4.费用n问题1：求最小费用最大流n问题2：求最小费用可行流n算法：消负圈+最小费用增广路算法n5.点容量n算法：拆点二二.线性规划线性规划二二.线性规划线性规划二二.线性规划线性规划二二.线性规划线性规划二二.线性规划线性规划n4.线性规划的解n(1)可行解：满足所有约束条件的解n(2)最优解：可行解中使目标函数取到最优值的解二二.线性规划线性规划n4.线性规划的解n(1)可行解：满足所有约束条件的解n(2)最优解：可行解中使目标函数取到最优值的解n注：根据线性规划问题是否有可行解、是否有最优解，线性规划问题可以分为n无可行解n有无界解n有最优解n一般而言，我们最为关注有最优解的问题三三.网络流的线性规划模型网络流的线性规划模型三三.网络流的线性规划模型网络流的线性规划模型三三.网络流的线性规划模型网络流的线性规划模型三三.网络流的线性规划模型网络流的线性规划模型三三.网络流的线性规划模型网络流的线性规划模型三三.网络流的线性规划模型网络流的线性规划模型三三.网络流的线性规划模型网络流的线性规划模型三三.网络流的线性规划模型网络流的线性规划模型三三.网络流的线性规划模型网络流的线性规划模型三三.网络流的线性规划模型网络流的线性规划模型n7.小结n通过线性规划模型刻画网络流问题，其核心在于流量平衡条件。n流量平衡条件的特征是每个变量出现两次，一次系数为+1，另一次系数为-1。n具体的模型构建，取决于线性规划问题中的其他参数与特征。四四.对偶原理与最小割对偶原理与最小割n1.最小割问题n每条边有一个非负的权值。n表述一：删去若干条边使得源点到汇点不连通，求删边的权值和的最小可能值。四四.对偶原理与最小割对偶原理与最小割n1.最小割问题n每条边有一个非负的权值。n表述二：将点集分为(S,T)，记所有从S中出发到T中的边的权值和为c(S,T)，求c(S,T)的最小值。四四.对偶原理与最小割对偶原理与最小割n2.线性规划对偶问题na.原问题的变量对应对偶问题的约束条件nb.原问题的约束条件对应对偶问题的变量nc.原问题与对偶问题的目标函数方向相反nd.对偶问题的对偶问题是原问题四四.对偶原理与最小割对偶原理与最小割原原问题对偶偶问题四四.对偶原理与最小割对偶原理与最小割n3.对偶最优性n若原问题有最优解，则n(1)对偶问题也有最优解n(2)且两个问题的最优解的目标函数值相等。四四.对偶原理对偶原理与最小割与最小割四四.对偶原理与最小割对偶原理与最小割四四.对偶原理与最小割对偶原理与最小割四四.对偶原理与最小割对偶原理与最小割四四.对偶原理与最小割对偶原理与最小割四四.对偶原理与最小割对偶原理与最小割四四.对偶原理与最小割对偶原理与最小割四四.对偶原理与最小割对偶原理与最小割四四.对偶原理与最小割对偶原理与最小割四四.对偶原理与最小割对偶原理与最小割四四.对偶原理与最小割对偶原理与最小割四四.对偶原理与最小割对偶原理与最小割n8.小结n最大流的对偶问题是最小割n最大匹配的对偶问题是最小点覆盖n最优匹配的对偶问题是最小顶标和五五.线性规划与经典模型线性规划与经典模型n导言n在备考过程中，熟练掌握各种现有的网络流问题经典模型，可以保证我们在赛场上解决绝大部分的网络流问题。n但是，当出现新的网络流模型时，利用问题中刻画的线性规划问题辅助思考，是解决一些难题的捷径。五五.线性规划与经典模型线性规划与经典模型五五.线性规划与经典模型线性规划与经典模型五五.线性规划与经典模型线性规划与经典模型六六.经典例题选讲经典例题选讲n导言n由于网络流这一图论问题，与线性规划这一代数问题之间紧密的联系。n通常而言，任何一道网络流考题，都可以直接图论建模或者利用线性规划问题建模。六六.经典例题选讲经典例题选讲六六.经典例题选讲经典例题选讲六六.经典例题选讲经典例题选讲六六.经典例题选讲经典例题选讲六六.经典例题选讲经典例题选讲六六.经典例题选讲经典例题选讲六六.经典例题选讲经典例题选讲六六.经典例题选讲经典例题选讲