最小費用流问题.pptVIP

最小费用流问题;例、 最小费用流问题;最小费用流问题的一般提法;;定义 ：从 发出的所有边的终节点指标集合 : 进入 的所有边的始节点的指标集合;再用 表示 的净发出流量，即;网络 的最小费用流问题;最小费用流问题的对偶目标函数;最小费用流问题的松弛条件;最小费用流问题的松弛定理：;利用松弛定理解决最小费用流问题的途径;如何增加流量？;如果沿该增广链 增加流量 ，由容量约束知;流量调整前后原目标函数的改变为;根据前面的讨论可形成下面的最小费用流算法：;对前面的最小费用流算法要解决的问题;;;总结前面讨论，可以把容量网络的每条边按以下规 则等价转换成长度网络（求最短路的网络）中的边;;对长度网络的改进;;用 代替 计算最小费用的可增广链的好处;对第二个问题的回答;对用 生成的长度网络的每个 ，用 表示从 到 的最短路，如果从 到 没有道路，令 ， 用 表示最小费用增广链及其前向和后向边， 由最小费用增广链的定义可知;首先可以看出（反证）;首先考虑 的情况，又要分别考虑两种情形;2）;利用对偶变量的最小费用流求解算法;例 求总流量为10的 最小费用流;;利用可增广链调整流量;第一次迭代后的信息均在下图中，其中顶点后的数 是对偶变量值，容量和费用对下面的数据对是流量 简化成本;利用上图构造长度网络图;求得增广链（红线）和所有的 ;;;利用上图构造长度网络;求得增广链（红线）和所有的 ;利用可增广链调整流量;第三次迭代后的信息;运输问题;运输表描述;运输问题的图描述;产销平衡运输问题的数学规划模型（线性规划问题）;有可行解;最后一个约束多余，等式约束可写成;注意： ;例;图表示;产生基本可行解;;;上述第一种情况的运输表;上述第二种情况的运输表;结论：运输问题一组变量的系数线性无关的充要条件是;用最小元素法产生基本可行解;产地;产地;产地;产地;产地;产生基本可行解等价于在运输图中生成一个支撑树;计算检验数;回忆检验数计算公式;产地;产地;产地;产地;改进基本可行解;产地;由于基本可行解形成一个支撑树，加入任何非基变量一 定和某些基变量形成回路;产地;产地;算法总结;总产量大于总销量（产销不平衡）的运输问题;优化模型;指派问题;例 开办五家新商店，要五家建筑公司分别承建，各公 司营造费用报价如下，如何指派使总造价最小;标准指派问题的一般提法;定义;产地;当且仅当一组变量不含回路时，其对应的系数矩阵 的列向量线性无关;产地;推论 下述运输问题的基本可行解满足0-1约束！;结论;尽管可以用求解运输问题的算法求解标准指派 问题，由于存在大量的退化解，经常出现换基 不能改进目标函数的情况，这种做法效率不高;标准指派问题的第一个有用的性质;标准指派问题的第二个有用的性质;算法设想（匈牙利算法）;例;1 ） 用红圈标出一些某行或某列仅有的零元素，再 通过行列交换把这些零换到左上角（后者非必须）;2 ） 在没有红圈的右下角如果有 零，一定是新的独立零元素;4 ） 在直线未覆盖处找零，如果没有零停止，否则 会出现以下两种情况，其中黑实圈圈住的是新零;;;这种情况也一定能够增加独立零元素;实用性考虑：第一、把所有红圈交换到左上角没有 必要；第二、同一副图上不好删除直线，可用对列 打勾表示该列有直线覆盖，用对行打勾表示该行没 有直线覆盖。由此形成下面的算法;关于前面描述的迭代算法有以下事实：;找出未覆盖处最小的数，在 没被行直线覆盖的行减去最 小数，然后在有负数的列加 上这个最小数;继续找最大的独立零元素组;最终获得的独立零元素组;非标准形式指派问题如何转换成标准问题;2）人数和事情不等的问题