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

《曹钦翔+线性规划与网络流》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划与网络流北京大学曹钦翔一.网络流模型1.最大流模型可以沿边的方向运送货物每条边上的货物流量有上限求源点到汇点的最大流量一.网络流模型2.最大流算法Ford-Fulkerson算法Dinic算法Gap优化的SAP算法最高标号法预流推进一.网络流模型3.流量下界问题1：是否有可行流？问题2：求最大流（求值、求方案）问题3：求最小流（求值、求方案）一.网络流模型4.费用问题1：求最小费用最大流问题2：求最小费用可行流算法：消负圈+最小费用增广路算法5.点容量算法：拆点二.线性规划1.例子约束条件：变量：目标函数：最大化二.线性规划2.一般形式约束条件：或或二.线

2、性规划2.一般形式变量：或或无限制目标函数：最大化或最小化二.线性规划3.各形式相互转化(1)变量若原变量类型为：无限制则令，则(2)约束条件若原约束条件为现添加辅助变量，则二.线性规划4.线性规划的解(1)可行解：满足所有约束条件的解(2)最优解：可行解中使目标函数取到最优值的解二.线性规划4.线性规划的解(1)可行解：满足所有约束条件的解(2)最优解：可行解中使目标函数取到最优值的解注：根据线性规划问题是否有可行解、是否有最优解，线性规划问题可以分为无可行解有无界解有最优解一般而言，我们最为关注有最优解的问题三.网络流的线性规划模型1.最大流问题的线性规划模型

3、流量平衡条件（限制条件）()无限制无限制流量上限（限制条件）流量非负（变量）求最大流（目标函数）max三.网络流的线性规划模型2.流量下界流量限制变量代换令三.网络流的线性规划模型2.流量下界流量平衡条件（限制条件）()流量上限（限制条件）变量类型求最大流（目标函数）max三.网络流的线性规划模型2.流量下界流量平衡条件（限制条件）()流量上限（限制条件）流量非负（变量）求最大流（目标函数）max三.网络流的线性规划模型3.最小费用可行流限制条件与变量性质同最大流求最小费用（目标函数）min三.网络流的线性规划模型4.点容量点流量平衡与限制条件()方案一()()三

4、.网络流的线性规划模型4.点容量点流量平衡与限制条件()方案二()()()三.网络流的线性规划模型5.二分图最大匹配限制条件()()目标函数max三.网络流的线性规划模型6.二分图最大权值匹配限制条件()()目标函数max三.网络流的线性规划模型7.小结通过线性规划模型刻画网络流问题，其核心在于流量平衡条件。流量平衡条件的特征是每个变量出现两次，一次系数为+1，另一次系数为-1。具体的模型构建，取决于线性规划问题中的其他参数与特征。四.对偶原理与最小割1.最小割问题每条边有一个非负的权值。表述一：删去若干条边使得源点到汇点不连通，求删边的权值和的最小可能值。四.对

5、偶原理与最小割1.最小割问题每条边有一个非负的权值。表述二：将点集分为(S,T)，记所有从S中出发到T中的边的权值和为c(S,T)，求c(S,T)的最小值。四.对偶原理与最小割2.线性规划对偶问题a.原问题的变量对应对偶问题的约束条件b.原问题的约束条件对应对偶问题的变量c.原问题与对偶问题的目标函数方向相反d.对偶问题的对偶问题是原问题四.对偶原理与最小割原问题max约束条件无限制变量无限制对偶问题min变量无限制约束条件无限制四.对偶原理与最小割3.对偶最优性若原问题有最优解，则(1)对偶问题也有最优解(2)且两个问题的最优解的目标函数值相等。四.对偶原理与最

6、小割4.最小割的线性规划模型最小割似乎难以建立线性规划模型最小割模型中的变量——点的划分——是一个01离散变量最小割模型的目标函数似乎不是线性函数，即的权值只有在并且的情况下，才会计入目标函数。四.对偶原理与最小割4.最小割的线性规划模型最小割似乎难以建立线性规划模型最小割模型中的变量——点的划分——是一个01离散变量最小割模型的目标函数似乎不是线性函数，即的权值只有在并且的情况下，才会计入目标函数。从最大流与最小割的关系入手分析一个是最大，一个是最小权值又相等我们似乎看出一些端倪！四.对偶原理与最小割5.最大流问题的对偶问题(1)最大流问题原问题()无限制无限制

7、max四.对偶原理与最小割5.最大流问题的对偶问题(2)对偶问题无限制()min其中，，，其余。四.对偶原理与最小割5.最大流问题的对偶问题(3)对偶问题的分析a.在最优解中的取值始终等于b.根据的特征，可以令，()四.对偶原理与最小割5.最大流问题的对偶问题(4)简化的对偶问题无限制min四.对偶原理与最小割5.最大流问题的对偶问题(4)简化的对偶问题无限制min这就是最小割问题！启发：可以利用，这两个条件表示“当且仅当且时这一逻辑关系”这一关系往往对应最小割模型，或类似对偶模型四.对偶原理与最小割6.最大匹配问题的对偶问题(1)原问题()()max四.对偶原理

8、与最小割6