最小费用流问题课件

最小费用流问题最小费用流问题例、例、最小费用流问题最小费用流问题目标：从发点到收点的总的流量费用最小目标：从发点到收点的总的流量费用最小约束：约束：1）容量约束，各边流量不大于容量）容量约束，各边流量不大于容量 2）流量平衡约束，各点进出流量总和相等）流量平衡约束，各点进出流量总和相等 3）从发点到收点的总流量为）从发点到收点的总流量为括号内第一个数字是容量，第二个是单位流量费用括号内第一个数字是容量，第二个是单位流量费用最小费用流问题的一般提法最小费用流问题的一般提法容量网络容量网络 的每边另外赋值非负的单位的每边另外赋值非负的单位流量费用流量费用 ，记为，记为 ，给，给定从定从 到到 的总流量的总流量 ，要求一个总流量等于，要求一个总流量等于 的可行流的可行流 使得总费用使得总费用达到最小，特别是，如果给定总流量等于最大流，达到最小，特别是，如果给定总流量等于最大流，所求问题称为最小费用最大流问题所求问题称为最小费用最大流问题下例中可行流下例中可行流 要满足的流量平衡约束要满足的流量平衡约束中间节点：中间节点：发点：发点：收点：收点：定义定义 ：从：从 发出的所有边的终节点指标集合发出的所有边的终节点指标集合 :进入进入 的所有边的始节点的指标集合的所有边的始节点的指标集合如下图：如下图：再用再用 表示表示 的净发出流量，即的净发出流量，即流量平衡约束可统一写成流量平衡约束可统一写成网络网络 的最小费用流问题的最小费用流问题是一种特殊的线性规划问题是一种特殊的线性规划问题最小费用流问题的对偶目标函数最小费用流问题的对偶目标函数对偶目标函数对偶目标函数其中其中 是是 的分量，的分量，表示容量约束表示容量约束最小费用流问题的最小费用流问题的松弛条件松弛条件和和 满足松弛条件满足松弛条件满足容量约束满足容量约束最小费用流问题的松弛定理最小费用流问题的松弛定理：则则 是原问题最优解，是原问题最优解，是对偶问题最优解是对偶问题最优解如果可行流如果可行流 和对偶变量和对偶变量 满足松弛条件满足松弛条件由弱对偶定理可知结论成立由弱对偶定理可知结论成立证明：证明：满足松弛条件满足松弛条件可行流可行流利用松弛定理解决最小费用流问题的途径利用松弛定理解决最小费用流问题的途径1）产生一对满足松弛条件和所有中间节点的流）产生一对满足松弛条件和所有中间节点的流 量平衡条件的量平衡条件的 ，的总流量不大于的总流量不大于 ，例如，例如，2）如果）如果 也满足收点和发点的流量平衡条也满足收点和发点的流量平衡条 件（总流量为件（总流量为 ），），已是原问题的最优解已是原问题的最优解3）如果）如果 不满足发点和收点的平衡条件，不满足发点和收点的平衡条件，那么在满足那么在满足 1）的条件的前提下改进）的条件的前提下改进 ，使，使 其流量增加其流量增加如何完成如何完成 3）的任务？）的任务？如何增加流量？如何增加流量？已知条件：已知条件：（满足所有中间节点的流量平衡条件和容量约束）（满足所有中间节点的流量平衡条件和容量约束）是最大流的充要条件（增广链定理）：是最大流的充要条件（增广链定理）：不存在关于不存在关于 的可增广链的可增广链可以采用的方法：可以采用的方法：是最大流问题的一个可行流是最大流问题的一个可行流寻找关于寻找关于 的可增广链，如果找不到，的可增广链，如果找不到，已已经是最大流，原问题不可行，否则增加流量经是最大流，原问题不可行，否则增加流量如果沿该增广链如果沿该增广链 增加流量增加流量 ，由容量约束知，由容量约束知由于增加后的总流量为由于增加后的总流量为 ，应满足，应满足 所以最终选用的流量增加值应该为所以最终选用的流量增加值应该为假设假设 是从是从 到到 关于关于 的可增广链，用的可增广链，用表示其前向边的集合，表示其前向边的集合，表示后向边的集合，用表示后向边的集合，用 表示当前的总流量表示当前的总流量流量调整前后原目标函数的改变为流量调整前后原目标函数的改变为 是沿是沿 增加单位流量的费用，称为增加单位流量的费用，称为 的费用，显然的费用，显然应该选择费用最小的可增广链增加总流量应该选择费用最小的可增广链增加总流量记记沿沿 对对 进行调整获得新的流量进行调整获得新的流量 ，则，则根据前面的讨论可形成下面的最小费用流算法：根据前面的讨论可形成下面的最小费用流算法：1）令）令 2）如果）如果 ，停止，否则求出费用，停止，否则求出费用 最小最小 的可增广链的可增广链 （如果没有可增广链，停止）（如果没有可增广链，停止）3）令）令 4）用）用 替换替换 ，替换替换 ，回到，回到 2）对前面的最小费用流算法要解决的问题对前面的最小费用流算法要解决的问题1）实现问题）实现问题 如何方便地求出费用如何方便地求出费用 最小的可增广链最小的可增广链？2）理论问题）理论问题 算法停止于算法停止于 时所产生的时所产生的 是否是最是否是最 小费用流问题的解？小费用流问题的解？对第一个问题的解决方法对第一个问题的解决方法情况情况1）如果）如果 出现在某个可增广链出现在某个可增广链 中，中，一定属于该链的前向边，此时如果把一定属于该链的前向边，此时如果把 转换转换 成从成从 到到 的下述道路的下述道路 任取任取 ，其，其 只会是以下三种情况之一只会是以下三种情况之一1），2），3）那么那么 构成路长的一部分，就象构成路长的一部分，就象 构成构成 的一部分一样的一部分一样情况情况2）如果）如果 出现在某个可增广链出现在某个可增广链 中，中，一定属于该链的后向边，此时如果把一定属于该链的后向边，此时如果把 转换转换 成从成从 到到 的下述道路的下述道路 那么那么 构成路长的一部分，就象构成路长的一部分，就象 构成构成 的一部分一样的一部分一样情况情况3）此时既可能属于前向边，也可能属于后向）此时既可能属于前向边，也可能属于后向 边，所以上述两种可能的等价转化方式都应边，所以上述两种可能的等价转化方式都应 该保留该保留总结前面讨论，可以把容量网络的每条边按以下规总结前面讨论，可以把容量网络的每条边按以下规则等价转换成长度网络（求最短路的网络）中的边则等价转换成长度网络（求最短路的网络）中的边如果如果如果如果如果如果然后求长度网络的最短路确定最小费用可增广链然后求长度网络的最短路确定最小费用可增广链例例长度网络长度网络由于有小于零的权值，要用值迭代法求最短路由于有小于零的权值，要用值迭代法求最短路对长度网络的改进对长度网络的改进简化成本简化成本定义定义从从 到到 关于关于 的可增广链的可增广链 的长度的长度增广链上任意中间节点增广链上任意中间节点 的三种可能情况的三种可能情况可以用可以用 代替代替 生成计算最小费用的可增广链生成计算最小费用的可增广链用用 代替代替 计算最小费用的可增广链的计算最小费用的可增广链的好处好处 和和 满足松弛条件满足松弛条件最短路网络无负数，可用最短路网络无负数，可用Dijkstra算法算法对第二个问题的回答对第二个问题的回答那么存在对偶变量那么存在对偶变量 和和 一起满足松弛条件一起满足松弛条件定理定理 如果下述条件满足：如果下述条件满足：1）满足所有中间节点的流量平衡条件满足所有中间节点的流量平衡条件2）存在对偶变量）存在对偶变量 和和 一起满足松弛条件一起满足松弛条件3）是从是从 到到 关于关于 的最小费用可增广链的最小费用可增广链4）沿）沿 对对 按前面的算法调整获得按前面的算法调整获得一旦证明了上述定理，马上可以说明前面的最小费用流一旦证明了上述定理，马上可以说明前面的最小费用流算法或者能够证明没有可行解，或者能够给出最优解算法或者能够证明没有可行解，或者能够给出最优解对用对用 生成的长度网络的每个生成的长度网络的每个 ，用，用 表示从表示从 到到 的最短路，如果从的最短路，如果从 到到 没有道路，令没有道路，令 ，用用 表示最小费用增广链及其前向和后向边，表示最小费用增广链及其前向和后向边，由最小费用增广链的定义可知由最小费用增广链的定义可知定义定义 如下如下下面说明，这样定义的下面说明，这样定义的 和和 一起满足松弛条件，一起满足松弛条件，从而完成对前面定理的证明从而完成对前面定理的证明首先可以看出（反证）首先可以看出（反证）所以，如果能够证明上面条件成立，就可完成证明所以，如果能够证明上面条件成立，就可完成证明首先考虑首先考虑 的情况，又要分别考虑两种情形的情况，又要分别考虑两种情形1）2）（不一定在增广链上）（不一定在增广链上）对对 的情况可类似证明的情况可类似证明利用对偶变量的最小费用流求解算法利用对偶变量的最小费用流求解算法1）令）令2）如果）如果 ，停止，停止3）令）令 ，构造长度网络，构造长度网络4）求出从）求出从 到每个到每个 的最短路长的最短路长 ，如果到，如果到 某个某个 没有最短路，令没有最短路，令5）如果）如果 ，停止（没有可增广链），停止（没有可增广链）6）利用从）利用从 到到 的最短路和所有的的最短路和所有的 修改原修改原 变量和对偶变量，并用修改后的数值替换原变量和对偶变量，并用修改后的数值替换原 来的数值，同时修改总流量，然后回到来的数值，同时修改总流量，然后回到 2）例例 求总流量为求总流量为10的的 最小费用流最小费用流令令 ，长度网络为，长度网络为求得增广链（红线）和所有的求得增广链（红线）和所有的 （括号内的数）（括号内的数）求出求出 （）利用可增广链调整流量利用可增广链调整流量第一次迭代后的信息均在下图中，其中顶点后的数第一次迭代后的信息均在下图中，其中顶点后的数是对偶变量值，容量和费用对下面的数据对是流量是对偶变量值，容量和费用对下面的数据对是流量简化成本简化成本可验证松弛条件可验证松弛条件利用上图构造长度网络图利用上图构造长度网络图求得增广链（红线）和所有的求得增广链（红线）和所有的 利用利用求出求出利用可增广链调整流量利用可增广链调整流量第二次迭代后的信息第二次迭代后的信息可验证松弛条件可验证松弛条件利用上图构造长度网络利用上图构造长度网络求得增广链（红线）和所有的求得增广链（红线）和所有的 利用利用求出求出利用可增广链调整流量利用可增广链调整流量第三次迭代后的信息第三次迭代后的信息可验证松弛条件可验证松弛条件由于总流量等于由于总流量等于10已经满足约束，所以是最优解已经满足约束，所以是最优解运输问题运输问题运输表描述运输表描述产地产地销地销地产量产量销量销量运输问题的图描述运输问题的图描述产地产地销地销地产量产量销量销量在流量平衡和非负约束下极小化总的运输费用在流量平衡和非负约束下极小化总的运输费用产销平衡运输问题的数学规划模型（线性规划问题）产销平衡运输问题的数学规划模型（线性规划问题）产销平衡假定：产销平衡假定：有可行解有可行解最后一个约束多余，等式约束可写成最后一个约束多余，等式约束可写成共有共有 个等式约束个等式约束注意：注意：其中其中列向量表示模型列向量表示模型例例产地产地销地销地产量产量销量销量图表示图表示产生基本可行解产生基本可行解如果一组变量（红线表示）形成回路如果一组变量（红线表示）形成回路在在 中令其他变量等于中令其他变量等于0如果一组变量（红线表示）不含回路如果一组变量（红线表示）不含回路在在 中令其他变量等于中令其他变量等于0上述第一种情况的运输表上述第一种情况的运输表产地产地销地销地产量产量销量销量上述第二种情况的运输表上述第二种情况的运输表产地产地销地销地产量产量销量销量结论：运输问题一组变量的系数线性无关的充要条件是结论：运输问题一组变量的系数线性无关的充要条件是在图或表中不含有回路在图或表中不含有回路基本可行解的个数基本可行解的个数用用最小元素法最小元素法产生基本可行解产生基本可行解基本思想：优先安排单位运输成本最小的运输方式基本思想：优先安排单位运输成本最小的运输方式产地产地销地销地产量产量销量销量产地产地销地销地产量产量销量销量产地产地销地销地产量产量销量销量产地产地销地销地产量产量销量销量产地产地销地销地产量产量销量销量产地产地销地销地产量产量销量销量最后删除两个约束最后删除两个约束不会形成回路不会形成回路每次删除一个约束（节点）每次删除一个约束（节点）变量变量产生基本可行解等价于在运输图中生成一个支撑树产生基本可行解等价于在运输图中生成一个支撑树由流量平衡方程依次可得对应的可行流由流量平衡方程依次可得对应的可行流计算检验数计算检验数回忆检验数计算公式回忆检验数计算公式令令 （对偶变量）（对偶变量）产地产地销地销地产量产量位势行位势行位势列位势列销量销量利用运输表解对偶变量（利用运输表解对偶变量（位势法位势法）产地产地销地销地产量产量位势行位势行位势列位势列销量销量产地产地销地销地产量产量位势行位势行位势列位势列销量销量产地产地销地销地产量产量位势行位势行位势列位势列销量销量利用对偶变量计算检验数利用对偶变量计算检验数（视（视 ）改进基本可行解改进基本可行解产地产地销地销地产量产量销量销量已知以下基本可行解和负的检验数已知以下基本可行解和负的检验数让让 进基（取值大于零）可改进基本可行解进基（取值大于零）可改进基本可行解由于基本可行解形成一个支撑树，加入任何非基变量一由于基本可行解形成一个支撑树，加入任何非基变量一定和某些基变量形成回路定和某些基变量形成回路加入加入 形成回路形成回路产地产地销地销地产量产量销量销量在在 和基变量形成的回路中，让基变量依次减少和基变量形成的回路中，让基变量依次减少或增加或增加 的增加值，可保持等式约束满足的增加值，可保持等式约束满足产地产地销地销地产量产量销量销量取取 ，可得下面新的基本可行解，可得下面新的基本可行解 出基，目标函数等于原目标值加上出基，目标函数等于原目标值加上算法总结算法总结1）用最小元素法确定一个基本可行解）用最小元素法确定一个基本可行解2）用位势法计算所有非基变量的检验数）用位势法计算所有非基变量的检验数3）如果所有检验数不小于零，已得最优解，）如果所有检验数不小于零，已得最优解，否则找出最小检验数对应的非基变量以及否则找出最小检验数对应的非基变量以及 与其形成回路的基变量，据此确定相应非与其形成回路的基变量，据此确定相应非 基变量的增加值以及回路基变量的新值，基变量的增加值以及回路基变量的新值，然后回到上一步继续迭代然后回到上一步继续迭代总产量大于总销量（产销不平衡）的运输问题总产量大于总销量（产销不平衡）的运输问题优化模型优化模型处理办法处理办法引入假想销地引入假想销地优化模型优化模型往假想销地的运量没有成本往假想销地的运量没有成本定义假想销地定义假想销地 的销量的销量指派问题指派问题例例 开办五家新商店，要五家建筑公司分别承建，各公开办五家新商店，要五家建筑公司分别承建，各公 司营造费用报价如下，如何指派使总造价最小司营造费用报价如下，如何指派使总造价最小商店商店费用报价费用报价公司公司标准指派问题的一般提法标准指派问题的一般提法有有 件事要件事要 个人完成个人完成，每人做一件事，每人做一件事，已知第已知第 个人做第个人做第 件事的成本是件事的成本是 ，要确定人和事之间一对一的指派方案，使要确定人和事之间一对一的指派方案，使完成这完成这 件事的总费用最小件事的总费用最小称称 为指派问题的系数矩阵为指派问题的系数矩阵定义定义整数规划模型整数规划模型产地产地销地销地产量产量销量销量标准指派问题是一个特殊的产销平衡运输问题标准指派问题是一个特殊的产销平衡运输问题当且仅当一组变量不含回路时，其对应的系数矩阵当且仅当一组变量不含回路时，其对应的系数矩阵的列向量线性无关的列向量线性无关推论推论一组线性无关的系数向量对应的变量中，至少有一一组线性无关的系数向量对应的变量中，至少有一个变量所在行或列没有其它基变量个变量所在行或列没有其它基变量在运输问题的讨论中已得出下面的结论在运输问题的讨论中已得出下面的结论推论推论运输问题的基变量取值一定等于产量或销量或它们运输问题的基变量取值一定等于产量或销量或它们的差或它们的差的差的差或它们的差的差产地产地销地销地产量产量销量销量例例推论推论 产量和销量都是非负整数的运输问题的基本可行产量和销量都是非负整数的运输问题的基本可行 解的每个分量一定是非负整数解的每个分量一定是非负整数推论推论 下述运输问题的基本可行解满足下述运输问题的基本可行解满足0-1约束！约束！产地产地销地销地产量产量销量销量结论结论不用考虑不用考虑0-1变量约束！变量约束！求解下述运输问题可得标准指派问题的解求解下述运输问题可得标准指派问题的解尽管可以用求解运输问题的算法求解标准指派尽管可以用求解运输问题的算法求解标准指派问题，由于存在大量的退化解，经常出现换基问题，由于存在大量的退化解，经常出现换基不能改进目标函数的情况，这种做法效率不高不能改进目标函数的情况，这种做法效率不高进一步挖掘标准指派问题的特点可以获得更加进一步挖掘标准指派问题的特点可以获得更加有效的算法，这就是所谓的有效的算法，这就是所谓的匈牙利算法匈牙利算法标准指派问题的第一个有用的性质标准指派问题的第一个有用的性质任取任取 和任意实数和任意实数 ，用，用 和和 分别分别表示将表示将 的第的第 行或第行或第 列减去列减去 以后得到以后得到的系数矩阵，则以的系数矩阵，则以 ，或或 为系数矩阵的指为系数矩阵的指派问题的最优方案相同派问题的最优方案相同理由：理由：目标函数差一个常数，约束相同，最优解也相同目标函数差一个常数，约束相同，最优解也相同标准指派问题的第二个有用的性质标准指派问题的第二个有用的性质如果如果 的所有元素中没有负数，且存在的所有元素中没有负数，且存在 个行列号都互不相同的零元素（简称为独立零元个行列号都互不相同的零元素（简称为独立零元素），那么对应的标准指派问题的最优目标值等素），那么对应的标准指派问题的最优目标值等于零，最优方案可以由独立零元素的位置确定于零，最优方案可以由独立零元素的位置确定例如例如最优解最优解算法设想（匈牙利算法）算法设想（匈牙利算法）一、利用第一个性质产生独立零元素一、利用第一个性质产生独立零元素二、对给定矩阵找到最大的独立零元素组二、对给定矩阵找到最大的独立零元素组三、当最大的独立零元素组的零元素数目不够三、当最大的独立零元素组的零元素数目不够 时增加独立零元素的数目时增加独立零元素的数目通过以上步骤的迭代找到足够的独立零元素通过以上步骤的迭代找到足够的独立零元素例例一、顺序对每行每列减去最小值产生零元素一、顺序对每行每列减去最小值产生零元素1）用红圈标出一些某行或某列仅有的零元素，再用红圈标出一些某行或某列仅有的零元素，再通过行列交换把这些零换到左上角（后者非必须）通过行列交换把这些零换到左上角（后者非必须）行行交交换换二、对给定矩阵找到最大数目的独立零元素组二、对给定矩阵找到最大数目的独立零元素组列列交交换换2）在没有红圈的右下角如果有在没有红圈的右下角如果有零，一定是新的独立零元素零，一定是新的独立零元素3）用直线覆盖红圈所在行用直线覆盖红圈所在行4）在直线未覆盖处找零，如果没有零停止，否则在直线未覆盖处找零，如果没有零停止，否则会出现以下两种情况，其中黑实圈圈住的是新零会出现以下两种情况，其中黑实圈圈住的是新零情况二情况二情况一情况一两两种种情情况况的的处处理理方方法法前面第一种情况后可能发生的另外一种情况前面第一种情况后可能发生的另外一种情况例例未覆盖的黑圈所在列的红圈所在未覆盖的黑圈所在列的红圈所在行存在没有列直线覆盖的零，和行存在没有列直线覆盖的零，和前面的第二种情况一样，但是该前面的第二种情况一样，但是该黑圈所在行有红圈，不能将该零黑圈所在行有红圈，不能将该零选为独立零元素选为独立零元素此时要覆盖剩下的零必须加直线此时要覆盖剩下的零必须加直线这种情况也一定能够增加独立零元素这种情况也一定能够增加独立零元素理由：新选零未被行直线覆盖，而该行有红圈，红理由：新选零未被行直线覆盖，而该行有红圈，红圈一定被列直线覆盖，其所在列一定有黑圈（记为圈一定被列直线覆盖，其所在列一定有黑圈（记为A），如果），如果 A 所在行没有红圈，即可按上面图型显所在行没有红圈，即可按上面图型显示的方法增加一个独立零元素，如果示的方法增加一个独立零元素，如果 A 所在行有红所在行有红圈（记为圈（记为 B），），B 一定被列直线覆盖，其所在列一一定被列直线覆盖，其所在列一定有黑圈（记为定有黑圈（记为 C），如果），如果C 所在行没有红圈，可所在行没有红圈，可按上述方法增加独立零元素，否则可继续追踪，一按上述方法增加独立零元素，否则可继续追踪，一定可找到所在行没有红圈的黑圈，增加独立零元素定可找到所在行没有红圈的黑圈，增加独立零元素实用性考虑：第一、把所有红圈交换到左上角没有实用性考虑：第一、把所有红圈交换到左上角没有必要；第二、同一副图上不好删除直线，可用对列必要；第二、同一副图上不好删除直线，可用对列打勾表示该列有直线覆盖，用对行打勾表示该行没打勾表示该列有直线覆盖，用对行打勾表示该行没有直线覆盖。由此形成下面的算法有直线覆盖。由此形成下面的算法关于前面描述的迭代算法有以下事实：关于前面描述的迭代算法有以下事实：1）每次迭代至少增加一个被圈住的零）每次迭代至少增加一个被圈住的零2）所有红圈圈住的一定是独立零元素组）所有红圈圈住的一定是独立零元素组3）直线的数目和红圈的个数相同）直线的数目和红圈的个数相同上述第一个事实说明迭代算法有限步停止，第二个事实上述第一个事实说明迭代算法有限步停止，第二个事实说明算法能产生最大的独立零元素组，第三个事实说明说明算法能产生最大的独立零元素组，第三个事实说明算法产生的是能够覆盖所有零元素的数目最少的直线组算法产生的是能够覆盖所有零元素的数目最少的直线组找出未覆盖处最小的数，在找出未覆盖处最小的数，在没被行直线覆盖的行减去最没被行直线覆盖的行减去最小数，然后在有负数的列加小数，然后在有负数的列加上这个最小数上这个最小数三、利用第一个性质在直线未覆盖处产生零元素三、利用第一个性质在直线未覆盖处产生零元素继续找最大的独立零元素组继续找最大的独立零元素组出现前面讨论过的第三种情况，出现前面讨论过的第三种情况，因此一定可以增加独立零元素因此一定可以增加独立零元素最终获得的独立零元素组最终获得的独立零元素组独立零元素数等于任务数，已得最优解独立零元素数等于任务数，已得最优解非标准形式指派问题如何转换成标准问题非标准形式指派问题如何转换成标准问题1）目标函数求最大）目标函数求最大取取 ，令，令 ，得标准问题，得标准问题2）人数和事情不等的问题）人数和事情不等的问题补充虚拟的人或事，费用系数取补充虚拟的人或事，费用系数取03）一人可做几件事的问题）一人可做几件事的问题将该人转换成相同的几个人接受指派，这些人将该人转换成相同的几个人接受指派，这些人的费用系数完全相同的费用系数完全相同4）某事一定不能由某人做的问题）某事一定不能由某人做的问题将相应费用取为充分大的正数将相应费用取为充分大的正数