想象以下数据(再现所有输出的代码在结尾):

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


我想交换汽车以获得类似的东西:

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


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

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

stats

  horsepower year safety
1       0.25 0.25      0


也就是说,1/4的掉期具有相等的马力,等等。

我的问题是:如何通过设置直接直接在结果统计上的约束来解决此类任务,而无需通过反复试验的方法来确定成本?

例如,如果我想要一个解决方案,其中safety的匹配项大于0.20,而year的匹配项至少为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,因为我并不介意可能的解决方案的语言。

最佳答案

这是将此问题部分表示为整数编程(IP)问题。

I为汽车类型的集合。对于i中的jI汽车类型,让:


如果h[i,j]i的马力相同,则j = 1
如果y[i,j]i的年份相同,则j = 1
对于s[i,j]同样(安全)


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

现在介绍以下决策变量,即IP模型将选择以下变量的值:


如果我们将汽车类型x[i,j]分配为类型j的匹配项,则i = 1


现在,IP通常具有我们想要最小化或最大化的目标功能。在这种情况下,没有目标函数-您只想找到一组满足约束条件的匹配项。因此,您的目标函数可以是:

minimize 0


这是第一个约束。它说:至少a个比赛必须具有相同的马力。 (a是一个分数。)左侧是具有相同马力的比赛数量:对于每对类型的ij汽车,如果将j分配为i, s比赛,他们具有相同的马力,计为1;否则,计数为0。右侧是您想要的匹配项数,即整个集合中的a分数。

subject to sum {i in I, j in I} h[i,j] * x[i,j] >= a * |I|


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

接下来,您需要一个约束条件,规定每个汽车类型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),或者使用诸如PuLP的软件包用于Python。

我希望这有帮助。我咬的东西可能比您在这里所能嚼的更多。

09-10 02:44
查看更多