英语原文共 5 页
基于匈牙利算法的竞争分配问题算法
KONG Chao ，REN Yongtai ，GE Huiling，and DENG Hualing
Department ofStudent Afairs，Heilongjiang Institute ofTechnology，Harbin 150050，China
College of Science，Northeast Agricultural University，Harbin 150030，China
摘要：传统匈牙利方法只能解决标准分配问题，而不能解决竞争分配问题。本文着重讨论了标准分配问题和竞争分配之间的差异，基于匈牙利方法的竞争分配问题算法及其解决方案
研究。
关键词：最优分配问题 竞争分配问题 匈牙利方法
中图分类号：O224 文件代码：A 文章ID: 1006-8104(2007)-O1-0067-0
标准形式的最优分配问题
最优分配（分配）问题是经济计划工作中经常遇到的问题。当n人被任命完成n个任务时，应满足以下三个假设：（1）人数等于任务;（2）每个人必须当且仅当完成一个任务（3）每个任务必须当且仅当由一个人完成。
以价值系数被熟知的是当第i个人称完成第j项任务时消耗的资源（当找到目标函数的最小值时）或获得的利益（当找到目标函数的最大值时）。数学模型如下。
min(max)z=
s.t.
关于该模型的描述如下：
做任务与否是一个人的两个选择。换句话说，在每个人和每个任务之间只有两个状态，做或不做。因此，我们将变量插入如下
在这里我们叫为0—1变量，因为每个人只能完成一项任务。因此我们有：
另外，每项任务都应该只被一个人完成，因此我们有：
匈牙利算法和一些启发式算法（例如，模拟退火算法，蚁群算法，粒子群算法和遗传算法
引入算法）来解决分配问题。启发式算法通常用于解决问题高复杂分配问题。 但是，因为它随机开始搜索，无法保证到达优化结果。匈牙利算法是一种分析算法。 因为它的简单性和查找能力最佳解决方案，无需验证，匈牙利语算法广泛用于解决分配问题。对于上述关于最优赋值的线性规划问题，显然我们可以用单纯形法解决它。然而，由于赋值问题的特殊性，这种方法比匈牙利方法更复杂.匈牙利方法不仅有效，而且比较简单。 在解决当前的最优分配问题。
HA用于无线通信系统中的子载波分配问题.HA提供最大值将N个子载波分配给K个用户，计算复杂度为O（N4）。 这种巨大的计算复杂性HA成为无线通信系统的瓶颈。 因此，基于GPU的并行处理可以在基站使用以减少这些算法的执行时间，特别是对于大多数计算
密集的系统部分。 这促使使用HA的并行实现来解决子载波下行链路场景中的分配问题。 子载波分配在系统中的BS处执行; 因此，平行过减少执行时间，HA的实施可以提供显着的优势。
标准分配问题最优解的性质
假设是指派问题的值系数矩阵。现在从某个行（或某个列）中的每个元素中减去k（k是常数，可以是正数或负数），得到矩阵。然后是最优解。作为价值系数矩阵的新指派问题与主指派问题的最优解相同。但最优解的值比前者小k。应用上述性质，我们可以将原值系数矩阵转化为包含许多零元素的新系数矩阵。其最优解仍然是不可改变的。在矩阵中，我们关心的是不同行和不同列中的零元素。 简单，我们在文章中将它们称为独立的零元素。如果我们可以从系数矩阵得到n个独立的零元素，则假设解析矩阵的变量]，其中对应的n个独立零元素为1，其他变量为0 然后，我们可以获得主要指派问题的最优解。
各种解决子载波分配问题的方法被提出。其中，匈牙利算法（HA）是最着名的算法之一，广泛用于线性分配问题（LAP）.HA最初是由Harold William Kuhn开发的， 然后由James Munkres评论，10提供从O（N4）到O（N3）的最坏情况计算复杂度的减少，其中N是需要分配的源或任务的数量。 通过考虑HA实现中的高计算复杂性，各种研究有助于缩短不同应用领域的执行时间。Pentico还审查了解决LAP的其他算法.Bertsekas开发了拍卖算法，Jonker和Volgenant提出了最短路径算法的有效实现，并表明该算法具有O（N3）的理论复杂度。 Balas等人20代表了分配问题的最短路径算法的并行实现。 Jonker和Volgenant14提出了一种改进的HA，在交替路径搜索过程中有两个简单但有效的改进。 Wright还提出了更快版本的HA，它在成本矩阵中实现了微小的修改，以减少执行时间。在LAP中，对于大型问题实例，串行算法的立方容量可能需要大量的执行时间，这可以通过它们在并行体系结构上的实现来减少。 Bertsekas和Castantilde;on提出了HA的并行异步实现，它通常比同步的快。近年来，对并行体系结构上线性分配算法的实现进行了广泛的研究。这些实现是在特定于应用程序的并行体系结构上实现的，通常实现显着性加速比。
矩阵中零元素的定理
系数矩阵中的最大零个元素数等于可以覆盖所有零个元素的最小右边数。
应用上述属性，我们可以划分匈牙利标准指派问题的方法步骤。
步骤l：变换值系数矩阵，以使零元素出现在每一行和每一列中。
步骤2：尝试指派以找到最佳解决方案。
步骤3：用最小值覆盖所有零元素右线数量。
步骤4：转换所获取的矩阵以增加它的零元素
竞争分配问题
上述标准分配问题应满足三个假设。但在实际应用中，大多数分配问题不满足第一个假设;第二个假设不满足企业，部门和社会提出的要求。虽然提出了经典的匈牙利算法许多年前，已被广泛用于解决任务工程中的问题，它只能解决那些问题总费用是每项工作的总和。 然而，许多分配问题，例如串行并行系统，不满足这种约束 因此，我们提出了一种改进的匈牙利算法解决串行并行中的分配问题系统，而不是所有工作按顺序完成有些工作是并行完成的，因此总数所有工作的时间并不简单。引入竞争机制之后，虽然有些人研究了一些常见的和非标准的形式分配问题，但是在将非标准形式转化为标准形式之后，他们大多用匈牙利方法解决它们。我们仍然举出人事指派的例子。 m人完成n个任务，并且编辑完成kl任务，1le;kile;n(i=1,2,hellip;,m)。对于上述假设3，我们假设， 因此，每个任务可以由某人完成。因此，关于竞争分配问题的数学模型如下。
Minz=
s.t.
假设的含义与标准赋值问题的含义相同，则该模型定义为标准竞争赋值问题。
如果n=m,=1（i=1,2，...，m），则模型退化为标准分配问题。为了找到新的最佳分配，
在形成系统时，应假设所有作业时间向量，包括每个工人的工作时间完成工作。
由于在竞赛分配问题上第i个人完成第个任务，我们可以根据ki的值对竞赛分配问题进行分类。
- 假设=n（i=1,2,hellip;,m），它被称为自由竞争分配问题。
- 当假设1le;le;n（1,2,..,m）并且等号对P（Ole;ple;m）为真时，它被称为半自由竞争分配问题。
- 假设，=1（i=1,2,hellip;,m），它被称为弱竞争分配问题。如果，m=n，然后它退化成标准分配问题。事实上，这个问题根本没有任何竞争性。
为了克服经典匈牙利算法的缺点，它只能解决总成本是每个工作总和的问题，提出了一种改进的匈牙利算法，用于解决串并联系统的分配问题。首先，通过用虚拟作业替换并行作业，所提出的算法将串行并行系统转换为纯串行系统，其中经典匈牙利算法可用于通过优化生成时间分配计划。之后，通过检查虚拟工作是否可以通过本地搜索实现真实工作来验证分配计划。如果分配计划无效，则将通过调整虚拟工作的参数来调整转换后的系统，然后再次进行优化。通过迭代搜索，最终可以得到有效的最优分配方案。
为了评估该算法，将有效的最优分配方案应用于作为典型串并联系统的制造系统的人工分配。在分析经典匈牙利算法的基础上，提出了一种改进的匈牙利算法“零行方法”来解决不完全赋值问题。在Matlab程序中引入匈牙利算法并用于解决典型问题分配问题，如婚姻分配。在一种新方法中，提出了“差异法”来解决非标准分配问题 - “任务多于人数”。与传统算法相比，该方法更简单，因为它不需要使用新的矩阵来代替原始系数一开始的矩阵，但直接解决了原始系数矩阵的问题。
为了研究恶劣环境下的多维护调度问题，提出了一种改进的匈牙利算法。为了提高云计算任务的分配效率，提出了一种基于经典匈牙利算法的快速或减少优化算法。通过消除决定的矩阵元素，可以快速降低矩阵的阶数，提高计算效率。参考文献用匈牙利方法研究了武器目标的动态功率分配将其转化为分配问题。此外，经典匈牙利算法已被用于解决许多领域的工程问题
竞争分配算法问题
步骤l：首先，对于串并联中的每个并行部分系统，创建一个虚拟工作来替换它因此生成了一个纯串行系统。 然后经典的匈牙利算法用于优化生成的串行系统以获得最佳分配计划。 要验证生成的分配计划，它会检查分配计划中是否有所有虚拟工作可以实现与实际工作的平行部分原始系统，在这种情况下，分配计划是串并联系统的最佳方案。 否则，虚拟工作将通过调整其参数进行调整，因此要形成一个新的纯系列系统也以同样的方式进行优化。 整个过程会重复，直到获得有效的最佳分配计划所有虚拟工作都可以通过实际工作实现列表值系数矩阵，如果,我们可以在中添加零列,是相应的任务数。因此变为了标准的竞争分配问题。
步骤2：变换值系数矩阵，使每行和每列出现零元素。此步骤与匈牙利方法的步骤2相同。
步骤3：尝试分配以找到最佳解决方案。
- 进行列测试。我们从第一列逐一开始测试。如果只有一列包含未标记的零元素，则在零元素上标记△并在△所在的列中的其他零元素上标记O ，这可以避免再次分配列的任务。让△所在的行是第i行。如果这行中的△数已经等于，这意味着行委托的人的任务数量已经饱和。因此，在此行中的其他零元素上标记O，这意味着我们不再向此人分配任务。
- 迭代执行列测试直到所有零元素被标记。如果至少有两个零在某些剩余列列中未标记的元素，然后在任意零元素上标记△并标记O其他零元素。
- 当△元素的数量等于矩阵的列数时，找到问题的最优解。否则转到步骤4。
步骤4：覆盖所有实际零元素，并使用最少数量的右行传递一些行和一些列。请注意，如果将第i行划掉，则使用的右行数由ki签名 其他步骤与Hungadan方法基本相同，但应将列转换为行。
a.Mark没有△的列：
b.Mark包含列中包含o的行并且所在列被标记
c.Mark包括标记的行中包含△的列并所在行被标记
d.迭代地执行b.c，直到我们不再标记为止;
e.在已标记的行上绘制水平线，在未标记的列上绘制/和铅垂线。
步骤5：该步骤与匈牙利方法的第4步相同
实例
现在结合实际问题，阐述了基于匈牙利方法的竞争分配问题算法。
- 有4个任务需要3个人（第一个，第二个，第三个）完成。每个人完成每项任务的时间如下（表1）。如果任务数量没有限制 每个人都完成了。现在如何指派三个人完成任务以减少消耗的时间？
表1每个人完成每项任务所需的时间
|
Workers |
Tasks |
|||
|
A |
B |
C |
D |
|
|
第一个 |
3 |
8 |
2 |
3 |
|
第二个 |
8 |
7 |
2 |
7 |
|
第三个 |
6 |
4 |
2 |
5 |
由于每个人完成的任务数量没有限制，因此获取ki（i=1,2,3），它属于自由竞争分配问题。
步骤一：因为
将0列添加到系数矩阵以使其标准化。因此：
=
步骤二：从每列中的每个元素中减去最小元素，有
每行和每列中都有零元素
步骤三：尝试分配并寻找最佳解决方案。 从而
矩阵中的数量等于矩阵的列数，因此我们有以下最优解。第一个完成任务A和任务D，第二个完成任务C，第三个完成任务B 他们完成任务需要至少12小时
- 如果我们改变（1），则问题变为第一个完成一个任务，第三个完成一个任务，第二个完成两个任务。尝试找到最佳分配项目。对于k1 = k3 = l，k2 = 2，这是半分配问题
步骤一： 通过列出系数矩阵
步骤二：从每行中的每个元素中减去最小元素，然后从每列中的每个元素中减去最小元素，得到
每行和每列中都有零元素
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
