5

由于公司的变化，我们不得不重新安排我们的坐姿：一间有10张桌子的房间。由于多种原因，有些办公桌比其他办公桌更受欢迎。一种解决方案是从帽子上画一个桌号。我们认为有更好的方法来做到这一点。

我们有 10 张桌子和 10 个人。让我们给这场比赛的每个人 50 个假想的代币，让他们在桌子上竞标。你在一张桌子上的出价没有限制，你可以把所有 50 个都放，这就是说“我只想坐在这里，期间”。你也可以通过给每张桌子 5 个代币说“我不在乎”。

重要提示：没有人知道其他人在做什么。每个人都必须仅根据他/她的最大利益做出决定（听起来很熟悉？）

现在假设我们得到了这些假设的结果：

#  | Desk# >| 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 |
1  | Alise  | 30 | 2  | 2  | 1  | 0  | 0  | 0  | 15 | 0  | 0  | = 50
2  | Bob    | 20 | 15 | 0  | 10 | 1  | 1  | 1  | 1  | 1  | 0  | = 50
   ...
10 | Zed    | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | = 50

现在，我们需要找到一种（或多种）配置，让我们获得最大的满足感（即人们得到他们想要的办公桌，同时考虑到所有的出价并最大化团队的总数。当然，假设是他/她越想要桌子上的人越多）。

由于只有 10 个人，我认为我们可以强制它查看所有可能的配置，但我想知道是否有更好的算法来解决此类问题？

4

2 回答 2

3

您似乎正在查看可以使用匈牙利算法解决的分配问题。这是一个经过充分研究的问题，您可能会在网络上找到可以使用的代码。

在您的情况下，您可以使用 cost = 50 - bid 并使用上述（分配问题的任何解决方案）。

于 2010-06-11T13:15:32.203 回答
0

更快的是，如果你有 Excel，你也应该有一个可用的 SOLVER 版本。只需设置您的出价矩阵（10x10 出价），分配矩阵（10x10 与 0/1 分配），使用 sumproduct(bids,assignments) 计算分配的价值，使其成为您的目标函数，并添加约束，因此仅将人员分配给办公桌和办公桌分配给人员。确保您已选中选项>“线性模型”框并“假设非负”并解决！我刚刚设置了一个示例 10x10 问题 - 似乎工作正常。

于 2010-06-11T21:01:04.903 回答