求解具有特定约束的指派问题

Question

想象一下下面的数据（复制所有输出的代码在最后）：

df

           cars horsepower year safety
1        Toyota        140 2008      4
2      Chrysler        120 2009      4
3          Ford        140 2010      5
4           BMW        150 2008      3
5 Mercedes-Benz        150 2008      3
6       Hyundai        120 2009      4
7        Jaguar        150 2007      3
8         Tesla        120 2010      5

我想把车换成这样：

^{pr2}$

这是一个典型的分配问题，在上面的情况下是随机解决的，也就是说，在所有情况下，成本矩阵都设置为0。在

我感兴趣的是结果。在上述情况下，解决方案产生以下统计信息：

^{3}$

也就是说，四分之一的掉期具有相同的马力等

我的问题是：如何通过直接设置结果统计数据的约束来解决这些任务，而不需要设置成本的试错法？在

例如，如果我想要一个解决方案，其中safety的匹配大于0.20，并且{}至少为0.10，如下所示？在

desiredOutput

   cars_initial    cars_match
1        Toyota      Chrysler
2         Tesla Mercedes-Benz
3 Mercedes-Benz           BMW
4        Jaguar        Toyota
5       Hyundai         Tesla
6          Ford       Hyundai
7      Chrysler        Jaguar
8           BMW          Ford

statsDesired

  horsepower year safety
1       0.25 0.12   0.25

当然，我可以将成本矩阵设置为一个较低的数字，在所有的情况下，safety的汽车是相等的。在

但是，有没有一种方法可以通过直接设置结果统计的约束来影响结果呢？在

也许有一种方法可以优化成本以达到预期的结果？在

代码：

library(lpSolve)
library(dplyr)
library(tidyr)

set.seed(1)

df <- data.frame(
  cars = c("Toyota", "Chrysler", "Ford", "BMW", "Mercedes-Benz", "Hyundai", "Jaguar", "Tesla"),
  horsepower = c(140, 120, 140, 150, 150, 120, 150, 120),
  year = c(2008, 2009, 2010, 2008, 2008, 2009, 2007, 2010),
  safety = c(4, 4, 5, 3, 3, 4, 3, 5)
)

mat <- df %>% select(cars) %>%
  crossing(df %>% select(cars)) %>%
  mutate(val = 0) %>% 
  spread(cars, val)

solved <- lp.assign(mat %>% select(-cars1) %>% as.matrix())$solution

matches <- as.data.frame(solved) %>%
  setNames(., names(mat %>% select(-cars1))) %>%
  bind_cols(mat %>% select(cars1)) %>%
  gather(key, val, -cars1) %>%
  filter(val == 1) %>% select(-val, cars_initial = cars1, cars_match = key)

nms <- c("cars", paste0(names(df %>% select(-cars)), "Match"))

matches <- matches %>%
  left_join(df, by = c("cars_initial" = "cars")) %>%
  left_join(df %>% setNames(., nms), by = c("cars_match" = "cars"))

stats <- matches %>%
  summarise(
    horsepower = round(sum(horsepower == horsepowerMatch) / n(), 2),
    year = round(sum(year == yearMatch) / n(), 2),
    safety = round(sum(safety == safetyMatch) / n(), 2)
  )

desiredOutput <- data.frame(cars_initial = matches$cars_initial, cars_match = c("Chrysler", "Mercedes-Benz", "BMW", "Toyota", "Tesla", "Hyundai", "Jaguar", "Ford"))

statsDesired <- desiredOutput %>%
  left_join(df, by = c("cars_initial" = "cars")) %>%
  left_join(df %>% setNames(., nms), by = c("cars_match" = "cars")) %>%
  summarise(
    horsepower = round(sum(horsepower == horsepowerMatch) / n(), 2),
    year = round(sum(year == yearMatch) / n(), 2),
    safety = round(sum(safety == safetyMatch) / n(), 2)
  )

如果我需要更多的例子，请让我知道以上的问题。在

代码在R中，但我还添加了标记Python，因为我不太在意可能的解决方案的语言。在

Answer 1

这是一个整数规划（IP）问题的部分形式。在

让I是汽车类型的集合。对于i和I中的j，让：

• h[i,j]=1如果汽车i和j具有相同的马力
• y[i,j]=1如果汽车i和j有相同的年份
• 类似地，s[i,j]（安全性）

这些是参数，表示对模型的输入。（您需要编写代码来根据数据表计算这些二进制量。）

现在介绍以下决策变量，即您的IP模型将选择其值的变量：

• x[i,j]=1，如果我们将汽车类型j指定为类型i的匹配

现在，IP通常有一个我们想要最小化或最大化的目标函数。在这种情况下，没有目标函数，您只想找到一组满足您的约束的匹配。所以你的目标函数可以是：

minimize 0

这是第一个约束。它说：至少a的火柴必须具有相同的马力。（a是一个分数。）左边是具有相同马力的匹配项的数目：对于每一对汽车类型i和{}，如果j被指定为i的匹配和它们具有相同的马力，则计数为1；否则，计数为0。右边是您想要的匹配数，即整组的a分数。在

^{pr2}$

现在为其他类别制定类似的约束条件。在

接下来，您需要一个约束，该约束要求每个汽车类型i必须恰好分配给一个汽车类型j：

subject to sum {j in I} x[i,j] == 1 for all i in I

最后，您需要约束，说明决策变量是二进制的：

subject to x[i,j] in {0,1} for all i, j in I

现在，为了解决这个问题，您需要使用一种数学建模语言，比如AMPL或GAMS，或者使用一个包，比如Python的PuLP。在

我希望这有帮助。我可能吃得比你在这里吃得多。在