时间戳

首页 > 解决方案 > 解决具有特定约束的分配问题

python - 解决具有特定约束的分配问题

问题描述

想象一下以下数据（重现所有输出的代码在最后）：

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，因为我并不介意可能的解决方案的语言。

标签： pythonrgraph-theorymathematical-optimizationlpsolve

解决方案

这是这个问题作为整数规划 (IP) 问题的部分表述。

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

  • 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，如果j分配为i​​' 匹配并且它们具有相同的马力，则计数为 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 这样的数学建模语言，或者像PuLPPython 这样的包。

我希望这有帮助。我可能咬掉的东西比你在这里咀嚼的还多。

推荐阅读