拍卖算法

拍卖算法第七章 拍卖算法 本章讨论最小费用流的第三类主要算法。1.3.3节介绍过分配问题的拍卖算法，4.2节指出过最小费用流问题可以转换为分配问题，因此本章描述的算法源于分配问题的拍卖算法，数学上也等

拍卖算法 第七章拍卖算法 本章讨论最小费用流的第三类主要算法。1.3.3节介绍过分配问题的拍卖算 法，4.2节指出过最小费用流问题可以转换为分配问题，因此本章描述的算法源于 分配问题的拍卖算法，数学上也等价于分配问题的拍卖算法，在7.3.3节还将更详 细地讨论这个问题。 本章的算法不依赖于改善费用逻辑，这一点与上一章的算法正相反;在迭代的 任何一步，初始费用和对偶费用都有可能同时变坏。另一方面，与7.1节讨论的分 配问题和7.4节讨论的广义最小费用流问题类似，也可以将最小费用流拍卖算法视 为近似同步上升方法。 因为借助分配问题可以获得所有关于拍卖算法的主要理解，所以我们特别关注 分配问题，7.1节详细研究了相应的收敛性和计算复杂度理论。7.2节开发了一类 特殊分配问题的拍卖算法。7.3节分析了最大流问题中流前冲击算法的某些细节并 导出该算法实施过程中的某些计算复杂度;这节还指出，从数学角度看，最小费用 流拍卖算法相当于拍卖一类特定分配问题。最后分别在7.4节和7.5节分析了两种 最小费用流拍卖算法的某些细节，这两种算法是松弛方法和拍卖,续贯最短路算 法。, 一般来说，拍卖算法的实用性较好，特别是用于某些简单的最小费用流问题， 比如分配问题和最大流问题。而且它们的计算复杂度明显低。它们的运行时间很有 竞争力，通常比它们之前的算法和改善对偶费用算法优越，我们将在本章和第九章 涉及凸可分网络流问题的地方指出这一点。 7.1.分配问题的拍卖算法 本节考虑分配问题，也就是个投标人和个物品的一对一问题。首先假定第个投