最小费用流问题.pptVIP

标准指派问题的第二个有用的性质 如果 的所有元素中没有负数，且存在 个行列号都互不相同的零元素（简称为独立零元 素），那么对应的标准指派问题的最优目标值等 于零，最优方案可以由独立零元素的位置确定 例如 最优解 算法设想（匈牙利算法） 一、利用第一个性质产生独立零元素 二、对给定矩阵找到最大的独立零元素组 三、当最大的独立零元素组的零元素数目不够 时增加独立零元素的数目 通过以上步骤的迭代找到足够的独立零元素 例 一、顺序对每行每列减去最小值产生零元素 1 ） 用红圈标出一些某行或某列仅有的零元素，再 通过行列交换把这些零换到左上角（后者非必须） 行交换 二、对给定矩阵找到最大数目的独立零元素组 列交换 2 ） 在没有红圈的右下角如果有 零，一定是新的独立零元素 3 ） 用直线覆盖红圈所在行 4 ） 在直线未覆盖处找零，如果没有零停止，否则 会出现以下两种情况，其中黑实圈圈住的是新零 情况二 情况一 两种情况的处理方法 前面第一种情况后可能发生的另外一种情况 例 未覆盖的黑圈所在列的红圈所在 行存在没有列直线覆盖的零，和 前面的第二种情况一样，但是该 黑圈所在行有红圈，不能将该零 选为独立零元素 此时要覆盖剩下的零必须加直线 这种情况也一定能够增加独立零元素 理由：新选零未被行直线覆盖，而该行有红圈，红 圈一定被列直线覆盖，其所在列一定有黑圈（记为 A），如果 A 所在行没有红圈，即可按上面图型显 示的方法增加一个独立零元素，如果 A 所在行有红 圈（记为 B ），B 一定被列直线覆盖，其所在列一 定有黑圈（记为 C ），如果C 所在行没有红圈，可 按上述方法增加独立零元素，否则可继续追踪，一 定可找到所在行没有红圈的黑圈，增加独立零元素 实用性考虑：第一、把所有红圈交换到左上角没有 必要；第二、同一副图上不好删除直线，可用对列 打勾表示该列有直线覆盖，用对行打勾表示该行没 有直线覆盖。由此形成下面的算法 √ √ √ √ 关于前面描述的迭代算法有以下事实： 1）每次迭代至少增加一个被圈住的零 2）所有红圈圈住的一定是独立零元素组 3）直线的数目和红圈的个数相同 上述第一个事实说明迭代算法有限步停止，第二个事实 说明算法能产生最大的独立零元素组，第三个事实说明 算法产生的是能够覆盖所有零元素的数目最少的直线组 找出未覆盖处最小的数，在 没被行直线覆盖的行减去最 小数，然后在有负数的列加 上这个最小数 三、利用第一个性质在直线未覆盖处产生零元素 继续找最大的独立零元素组 出现前面讨论过的第三种情况， 因此一定可以增加独立零元素 最终获得的独立零元素组 独立零元素数等于任务数，已得最优解 非标准形式指派问题如何转换成标准问题 1）目标函数求最大 取 ，令 ，得标准问题 2）人数和事情不等的问题 补充虚拟的人或事，费用系数取0 3）一人可做几件事的问题 将该人转换成相同的几个人接受指派，这些人 的费用系数完全相同 4）某事一定不能由某人做的问题 将相应费用取为充分大的正数 产地 销地 产量 销量 产地 销地 产量 销量 产地 销地 产量 销量 产地 销地 产量 销量 产地 销地 产量 销量 最后删除两个约束 不会形成回路 每次删除一个约束（节点） 变量 产生基本可行解等价于在运输图中生成一个支撑树 由流量平衡方程依次可得对应的可行流 计算检验数 回忆检验数计算公式 令 （对偶变量） 产地 销地 产量 位势行 位势列 销量 利用运输表解对偶变量（位势法） 产地 销地 产量 位势行 位势列 销量 产地 销地 产量 位势行 位势列 销量 产地 销地 产量 位势行 位势列 销量 利用对偶变量计算检验数 （视 ） 改进基本可行解 产地 销地 产量 销量 已知以下基本可行解和负的检验数 让 进基（取值大于零）可改进基本可行解 由于基本可行解形成一个支撑树，加入任何非基变量一 定和某些基变量形成回路 加入 形成回路 产地 销地 产量 销量 在 和基变量形成的回路中，让基变量依次减少 或增加 的增加值，可保持等式约束满足 产地 销地 产量 销量 取 ，可得下面新的基本可行解 出基，目标函数等于原目标值加上 算法总结 1）用最小元素法确定一个基本可行解 2）用位势法计算所有非基变量的检验数 3）如果所有检验数不小于零，已得最优解， 否则找出最小检验数对应的非基变量以及 与其形成回路的基变量，据