algorithm - 资源配置-匹配

Question

我遇到了一个问题，我不确定它是否可以通过线性规划来解决。基本上有两组人列出了他们对彼此的偏好，随后将进行匹配。我正在为此编写一个算法。 A 组最多可从 B 组中选择 4 个，反之亦然。

在制定解决方案时，我目前正在为每对组合分配一个成本。例如，如果 A 组的第 1 个人将 B 组的第 3 个人列为他/她的第一选择，反之亦然，则成本最小(第 1-3 对成本:0.01)。同样，我会为其他对分配一个成本，设计一个目标函数，寻求使总成本最小化的配对。

但是，我认为这不可行，因为我不知道如何定义我的约束和总体目标函数。在线阅读和从教科书中阅读，我发现资源分配问题与我正在尝试做的不同。

我可以就如何进行寻求您的建议吗？

Answer 1

您的问题可以表述为 "Assignment Problem 。" 作为典型案例，分配问题是将“工作”分配给“机器”。它们可以很容易地用于匹配两个集合。

公式如下: 两组人A和B

决策变量 Xij

设Xij为1，如果第i个人(集合A中的第i个人)与集合B中的第j个人相匹配； 0否则

参数: 设 Cij 是将人 i 与人 j

配对的成本

目标函数:最小化(对 i 求和)(对 j 求和)Cij * Xij

约束:

Every Person i 恰好配对一次

对 j Xij = 1 求和(对于每个 i)

每个人 j 恰好配对一次

对 i Xij = 1 求和(对于每个 j)

Xij 是二进制变量

Xij = (0,1)

分配问题的巧妙之处在于，可以使用相当容易理解的 'Hungarian Method.' 找到最佳配对。您还可以使用您可以随意使用的 LP/IP 求解器。

希望对您有所帮助。