R 函数可找到数据框中对象的最佳排名？

Question

我正在尝试找到 n 种产品列表的最佳顺序，以最大化收入。

示例：

产品位置1 位置2 位置3

   X 0.38 美元 0.17 美元 0.11 美元

   是 $1.08 $0.71 $0.52

   Z $0.82 $0.41 $0.26

一个产品（X,Y,Z）只能列出一次，每个位置（1,2,3）也只能列出一次。对于此示例，有 6 种可能的解决方案 (n=3, r=3, 3!/(3!-3!)=6) 但这应该能够适用于排名在 r 点的 n 产品

X1 + Y2 + Z3 = $1.35
X1 + Z2 + Y3 = $1.31
Y1 + X2 + Z3 = $1.51
Y1 + Z2 + X3 = $1.60
Z1 + X2 + Y3 = $1.51
Z1 + Y2 + X3 = $1.64

将选择最终组合（Z1 + Y2 + X3），因为 1.64 美元提供最大收入。除了找到最佳收入数字之外，我还需要知道所选择的有序组合，以便我知道哪些产品属于哪个位置。

我尝试过combn和expand.grid等函数，但这些函数似乎将所有元素组合在一个向量中，而我只能在一个位置存在一个产品。

R 是解决这个问题的可行工具吗？我需要以不同的格式构建数据吗？

Answer 1

从“但是这个解决方案应该能够应用于排名在N个位置的N个产品”我们知道

number of products = number of spots = N

。这本质上是一个分配问题。

数学模型通常表述为：

 min sum((i,j), c[i,j]*x[i,j])
 subject to
     sum(i, x[i,j]) = 1   for all locations j
     sum(j, x[i,j]) = 1   for all products i
     x[i,j] in {0,1}

这可以使用 LP 求解器或专用求解器来求解。请参阅link了解一些（有限的）性能数据。我认为开发自己的算法来找到最佳解决方案并快速完成此任务并不容易。

PS 这句话“但是这个解决方案应该能够适用于排名在N个位置的N个产品”已经被发帖者删除了，这有点不幸。所以问题发生了一些变化。随着问题的变化，模型可能需要更新。我们现在面临的不是平衡分配问题，而是不平衡分配问题。根据产品数量 (N) 小于还是大于位置数量 (M)，我们需要稍微更改模型。它仍然可以被表述为 LP/MIP，或者可以通过添加虚拟源或目标节点来转化为分配问题。

Answer 2

您可以使用匈牙利算法求解器来解决此问题。

db <- read.table(header=TRUE, text="Product Position.1  Position.2  Position.3
X 0.38  0.17  0.11
Y 1.08  0.71  0.52
Z 0.82  0.41  0.26")

我们加载库并使用负成本作为成本矩阵来最小化。

library(RcppHungarian)
HungarianSolver(-as.matrix(db[-1]))

$cost
[1] -1.64

$pairs
     [,1] [,2]
[1,]    1    3
[2,]    2    2
[3,]    3    1

第二栏给出了答案。产品 X 分配到位置 3，产品 Y 分配到位置 2，产品 Z 分配到位置 1。