从Excel到R的优化
我正努力在R中求解以下优化问题。用excel求解器很容易,但是我不能在R中做同样的问题。我在R中没有太多的优化经验问题是当某个特定活动应该是在一段时间内完成的。 A1,A2,…,A12是在一个字段中完成的12个活动。 0代表未分配,1代表分配。
约束是 –
- A2应该在A1完成之后发生,A3应该在A2完成之后发生,以此类推
- A3,A5,A6 – 这些活动中只有两个可以在某一天发生
- 每个活动应该发生在一个字段(在Excel解算器中,这个约束是通过取行等于1来定义的
这将是一个很大的帮助,如果有人可以帮助解决这个问题。 为了更好地理解这个问题,我附上了图片。 另外,请让我知道是否有任何网站或书籍,丰富的例子“如何解决R中的优化问题”。 感谢你在期待。
您可以使用lpSolve
软件包解决您的问题。
您将需要一个成本向量和约束信息。 在以下结构中将约束信息input到函数中:
-
lhs
:系数的“左侧”matrix,每个决策variables一个 -
dir
:“方向”,即<
,<=
,==
,>=
,>
-
rhs
:数字值为“右侧”
为了build立你的约束列表,我觉得有必要考虑一下你可能把每一个决定作为一个X(成为lhs
表中的一列)和每个约束你想定义为一个单独的方程(成为lhs
表,分别在dir
和rhs
有对应的值)
让我们从所有可能的决定开始:
library(tidyverse) library(stringr) # What are the decision variables? ---- # Which action to take actions <- str_c('A',seq(1:12) %>% formatC(width = 2, flag = '0')) actions #[1] "A01" "A02" "A03" "A04" "A05" "A06" "A07" "A08" "A09" "A10" "A11" "A12" # When to take it timings <- str_c('T',seq(1:12) %>% formatC(width = 2, flag = '0')) timings #[1] "T01" "T02" "T03" "T04" "T05" "T06" "T07" "T08" "T09" "T10" "T11" "T12" # List of all possible decisions is this: decisions <- expand.grid(actions, timings) # Convert it to a vector decision_variables <- str_c(decisions[,1], '_', decisions[,2]) # You also need a cost vector. # We'll use a value increasing as a function of timings, # as this will penalize "late" actions? cost <- rep(seq(1:length(timings)), length(actions)) %>% sort
decision_variables
每个元素是一个可能的动作(即在给定的时间采取行动,现在我们可以通过引入约束来缩小求解器的选项范围。
第一种约束:每个选项只应该采取一次! (这实际上是你的第三个,但我从这个开始,因为它是最简单的)我们可以这样形成:
# Create a matrix with one column per possible decision # and one row per action (for now) lhs <- matrix(0, nrow = length(actions), ncol = length(decision_variables), dimnames = list( actions, decision_variables)) # Each action should only be taken once! for (i in 1:length(actions)) { # Which fields does an action occur in? this_action <- str_detect(colnames(lhs), actions[i]) # Set their coefficients to 1 lhs[i,this_action] <- 1 } # create corresponding dir and rhs values dir <- rep('==', length(actions)) rhs <- rep(1, length(actions))
你可以看到,我们把所有包含有问题的X
(决定)的系数设置为1
。 在我们的最终解决scheme中,每个X
将取0
或1
的值。 如果X
是零,那么系数将是不相关的。 如果X
是1
,系数将被加到lhs
的总和上,并用dir
与rhs
值进行比较。
在这里,我们的约束是,我们刚刚介绍的每个约束的coefficient * X == 1
的总和。 对于包含给定动作的所有可能的决定,系数是1。 因此,一个解决scheme只有在任何给定的行动只被采取一次有效。
第二个约束: c('A03', 'A05', 'A06')
只有两个应该在某一天同时出现。
再次,我们为每个约束生成一行。 在这种情况下,我认为我们每天需要一个约束。 我们将生成的值附加到已经存在的lhs
, dir
和rhs
variables中:
# only one of A3, A5, A6 at any given time. # One constraint for each timestep for (j in timings) { lhs <- rbind(lhs, ifelse(str_detect(decision_variables, paste0('A0[356]{1}_',j)), 1, 0)) dir <- c(dir, '<=') rhs <- c(rhs, 2) }
第三个约束的占位符
Presto,我们制定了我们的问题。 现在让lpSolve
紧缩数字! 你可以把我们的问题提供给像这样的algorithm:
library(lpSolve) # Run lpSolve to find best solution solution <- lp( # maximise or minimise the objective function? direction = 'min', # coefficients of each variable objective.in = cost, const.mat = lhs, const.dir = dir, const.rhs = rhs) # Extract the values of X for the best solution: print(solution$solution) # Convert it into ta matrix of the format you are familiar with matrix(solution$solution, nrow = length(timings), ncol = length(actions), dimnames = list(actions, timings))
这是否做你所需要的?
任何问题?