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