《曹钦翔+线性规划与网络流》由会员分享，可在线阅读，更多相关《曹钦翔+线性规划与网络流（51页珍藏版）》请在金锄头文库上搜索。
1、线性规划与网络流,北京大学 曹钦翔,一. 网络流模型,1. 最大流模型 可以沿边的方向运送货物 每条边上的货物流量有上限 求源点到汇点的最大流量,一. 网络流模型,2. 最大流算法 Ford-Fulkerson算法 Dinic算法 Gap优化的SAP算法 最高标号法预流推进,一. 网络流模型,3. 流量下界 问题1：是否有可行流？ 问题2：求最大流（求值、求方案） 问题3：求最小流（求值、求方案）,一. 网络流模型,4. 费用 问题1：求最小费用最大流 问题2：求最小费用可行流 算法：消负圈+最小费用增广路算法5. 点容量 算法：拆点,二. 线性规划,1. 例子 约束条件： 1 +2 2 3
2、2 1 + 2 3 变量：x 1 , x 2 0 目标函数： 最大化 = 1 + 2,二. 线性规划,2. 一般形式 约束条件： 1 1 + 2 2 + 或 1 1 + 2 2 + = 或 1 1 + 2 2 + ,二. 线性规划,2. 一般形式 变量：x 0或x 0或x 无限制 目标函数： 最大化 = 1 1 + 2 2 + 或 最小化 = 1 1 + 2 2 + ,二. 线性规划,3. 各形式相互转化 (1) 变量 若原变量类型为： x 无限制 则令 x = ，则 , 0 (2) 约束条件 若原约束条件为 1 1 + 2 2 + 现添加辅助变量 ，则 1 1 + 2 2 + + =, 0,
3、二. 线性规划,4. 线性规划的解 (1) 可行解：满足所有约束条件的解 (2) 最优解：可行解中使目标函数取到最优值的解,二. 线性规划,4. 线性规划的解 (1) 可行解：满足所有约束条件的解 (2) 最优解：可行解中使目标函数取到最优值的解注：根据线性规划问题是否有可行解、是否有最优解，线性规划问题可以分为 无可行解 有无界解 有最优解 一般而言，我们最为关注有最优解的问题,三. 网络流的线性规划模型,1. 最大流问题的线性规划模型 流量平衡条件（限制条件） =0 (,) 无限制 无限制 流量上限（限制条件） 流量非负（变量） 0 求最大流（目标函数） max = ,三. 网络流的线性规
4、划模型,2. 流量下界 流量限制 变量代换 令 = ,三. 网络流的线性规划模型,2. 流量下界 流量平衡条件（限制条件） = (,) 流量上限（限制条件） 变量类型 0 求最大流（目标函数） max = ( + ) ( + ),三. 网络流的线性规划模型,2. 流量下界 流量平衡条件（限制条件） = (,) 流量上限（限制条件） 流量非负（变量） 0 求最大流（目标函数） max = ,三. 网络流的线性规划模型,3. 最小费用可行流 限制条件与变量性质 同最大流 求最小费用（目标函数） min = , ,三. 网络流的线性规划模型,4. 点容量 点流量平衡与限制条件 = (,) 方案一 =
5、 (,) (,),三. 网络流的线性规划模型,4. 点容量 点流量平衡与限制条件 = (,) 方案二 = (,) = (,) (,),三. 网络流的线性规划模型,5. 二分图最大匹配 限制条件 1 () 1 () 目标函数 max ,三. 网络流的线性规划模型,6. 二分图最大权值匹配 限制条件 1 () 1 () 目标函数 max ,三. 网络流的线性规划模型,7. 小结 通过线性规划模型刻画网络流问题，其核心在于流量平衡条件。 流量平衡条件的特征是每个变量出现两次，一次系数为+1，另一次系数为-1。 具体的模型构建，取决于线性规划问题中的其他参数与特征。,四. 对偶原理与最小割,1. 最小
6、割问题 每条边有一个非负的权值。 表述一：删去若干条边使得源点到汇点不连通，求删边的权值和的最小可能值。,四. 对偶原理与最小割,1. 最小割问题 每条边有一个非负的权值。 表述二：将点集分为(S,T)，记所有从S中出发到T中的边的权值和为c(S,T)，求c(S,T)的最小值。,四. 对偶原理与最小割,2. 线性规划对偶问题 a. 原问题的变量对应对偶问题的约束条件 b. 原问题的约束条件对应对偶问题的变量 c. 原问题与对偶问题的目标函数方向相反 d. 对偶问题的对偶问题是原问题,四. 对偶原理与最小割,原问题,max 1 1 + 2 2 + 约束条件 1 1 + 2 2 + 1 1 + 2
7、 2 + = 1 1 + 2 2 + 1 1 + 2 2 + 无限制 变量 0 0 无限制 =0,对偶问题,min 1 1 + 2 2 + 变量 0 无限制 0 =0 约束条件 1 1 + 2 2 + 1 1 + 2 2 + 1 1 + 2 2 + = 1 1 + 2 2 + 无限制,四. 对偶原理与最小割,3. 对偶最优性 若原问题有最优解，则 (1) 对偶问题也有最优解 (2) 且两个问题的最优解的目标函数值相等。,四. 对偶原理与最小割,4. 最小割的线性规划模型 最小割似乎难以建立线性规划模型最小割模型中的变量点的划分是一个01离散变量最小割模型的目标函数似乎不是线性函数，即 的权值只
8、有在并且的情况下，才会计入目标函数。,四. 对偶原理与最小割,4. 最小割的线性规划模型 最小割似乎难以建立线性规划模型最小割模型中的变量点的划分是一个01离散变量最小割模型的目标函数似乎不是线性函数，即 的权值只有在并且的情况下，才会计入目标函数。 从最大流与最小割的关系入手分析 一个是最大，一个是最小 权值又相等 我们似乎看出一些端倪！,四. 对偶原理与最小割,5. 最大流问题的对偶问题 (1)最大流问题原问题 =0 (,) 无限制 无限制 0 max = ,四. 对偶原理与最小割,5. 最大流问题的对偶问题 (2) 对偶问题 无限制 (,) = =0 0 + min 其中， =1， =1
9、，其余 =0。,四. 对偶原理与最小割,5. 最大流问题的对偶问题 (3) 对偶问题的分析 a. 在最优解中的 取值始终等于max(0, + ) b. 根据 的特征，可以令 = ， = +1(),四. 对偶原理与最小割,5. 最大流问题的对偶问题 (4) 简化的对偶问题 无限制 =1, =0 min (0, ),四. 对偶原理与最小割,5. 最大流问题的对偶问题 (4) 简化的对偶问题 无限制 =1, =0 min (0, ) 这就是最小割问题！ 启发： 可以利用，0这两个条件表示“当且仅当=1且=0时=1这一逻辑关系” 这一关系往往对应最小割模型，或类似对偶模型,四. 对偶原理与最小割,6. 最大匹配问题的对偶问题 (1) 原问题 1 () 1 () max ,四. 对偶原理与最小割,6. 最大匹配问题的对偶问题 (2) 对偶问题 + (当且仅当之间有边时 =1) min + 这就是最小点覆盖问题,
