文档介绍：精品文档，仅供学****与交流，如有侵权请联系网站删除
【精品文档】第 1 页
拍卖算法
本章讨论最小费用流的第三类主要算法。，，因此本章描述的算法源于分配问题的拍卖算法，数学上也等价于分配问题的拍卖算法，。
本章的算法不依赖于改善费用逻辑，这一点与上一章的算法正相反；在迭代的任何一步，初始费用和对偶费用都有可能同时变坏。另一方面，，也可以将最小费用流拍卖算法视为近似同步上升方法。
因为借助分配问题可以获得所有关于拍卖算法的主要理解，所以我们特别关注分配问题，。。；这节还指出，从数学角度看，最小费用流拍卖算法相当于拍卖一类特定分配问题。，这两种算法是松弛方法和拍卖／续贯最短路算法。
一般来说，拍卖算法的实用性较好，特别是用于某些简单的最小费用流问题，比如分配问题和最大流问题。而且它们的计算复杂度明显低。它们的运行时间很有竞争力，通常比它们之前的算法和改善对偶费用算法优越，我们将在本章和第九章涉及凸可分网络流问题的地方指出这一点。
分配问题的拍卖算法
本节考虑分配问题，也就是个投标人和个物品的一对一问题。首先假定第个投标人与第个物品匹配的‘值’或者‘好处’是。我们希望以总‘好处’最大为目标，把人和物品匹配起来。可以分配给第个投标人的物品集合是个非空集合，记为。所有可以分配给第个投标人的物品与第个投标人配对的二元组集合为，
注意：是基分配图的弧集，中的元素个数记为。
分配是人与物品的二元对集合（可能是空集），它满足：对任意都有；对每个投标人，至多存在一对，对每个物品，至多存在一对。给定分配，若存在一对，则称第个投标人被分配，否则称第个投标人未被分配；用类似的术语形容物品。若分配包含个二元对，使每个投标人和每个物品都被分配，则就称该分配为可行分配或者完全分配，否则称该分配为偏分配。
前面描述的分配问题是对称分配问题，它与非对称分配问题不同。在非对称分配问题中，人数少于物品数。。
主拍卖算法
，当初的动机比较简单、幼稚，难免有缺陷。算法可以正确运行的关键概念是补松弛（缩写为），它与偏分配和价值向量联系在一起。若
则称第个物品在范围内是第个投标人的最佳物品。若对任意都有
，（）
精品文档，仅供学****与交流，如有侵权请联系网站删除
【精品文档】第 3 页
则称和满足补松弛条件。
拍卖算法不断跌代，直至获得完全分配才终止跌代。跌代从满足补松弛条件的偏分配和价值向量开始；初始价值向量只要与空分配满足平凡补松弛条件就可以。后面将会指出：跌代能够保持补松弛条件一直得到满足。整个跌代过程由两个阶段组成：投标阶段和分配阶段。下面描述这两个阶段。
拍卖跌代的投标阶段
设分配中未被分配的人构成的集合为；对任意：
寻找最佳物品，使
和对应值
，（）
并寻找物品以外其它物品提供的最佳值
。（）
（如果是中的唯一物品，那么定义，或者为了便于计算，用一个比小得多的数定义。）
用下式计算第个投标人的‘标值’，
。（）
（这里的用词不是很准确，应该说第个投标人对第个物品投的标，并且第个物品收到第个投标人的标。）
拍卖跌代的分配阶段
每个物品有可能收到若干个投标人在投标阶段的投标，记这些人的集合为。如果非空，记最高投标为，即
；（）
从分配中去掉对（如果在中，第个物品被分配给第个投标人），加上对，其中是中取得上述最大值的那个投标人。
注意，允许选择参与投标人的集合。一种选择是只包括一个未被分配物品的人。因为这种选择类似于求解非线性方程组的Gauss-Seidel方法，所以称这种选择为Gauss-Seidel版，这种选择通常在串行计算环境下效果好。另一种选择是只包括所有未被分配物品的人。这种选择适于并行计算环境，因为它类似于求解非线性方程组的Jacobi方法，所以称这种选择为Jacobi版。
在跌代过程中，价格改变的物品就是收到投标的物品。每次价格变化至少增加。具体来看，如果第
精品文档，仅供学****与交流，如有侵权请联系网站删除
【精品文档】第 3 页
个投标人根据方程（）至（）投标第个物品，相