LPsolve — установка ограничений для суммы нескольких столбцов
Я хорошо разбираюсь в использовании LPSolve для задач линейной оптимизации, но один аспект оказался в тупике. Я хотел бы создать ограничение для суммы нескольких столбцов. Например, у меня есть ограничение, запрещающее любому из четырех конкретных столбцов быть больше 3. Однако я требую, чтобы любой четырех столбцов было равно 3.
РАБОЧИЙ ПРИМЕР
В этом примере я готовлю еду, чтобы оптимизировать «Ценность», оставаясь при этом менее 5 отдельных продуктов и 40 долларов США в стоимости. У меня также есть четыре разные группы продуктов — мясо, овощи, фрукты, крахмал — и я требую, чтобы в еде было не более четырех продуктов из любой группы, но в любой группе должно быть 3 элемента (вот где я в тупике).
Ниже приведен код, который дает мне желаемый результат, за исключением последнего ограничения:
## Choose 5 food items remaining under $40 and maximizing Value ##
## There can be no more than 3 items from the same group chosen, but **there must be 3 items from at least one group**(??) ##
library(dplyr)
library(lpSolve)
# Constraints
totalItems <- 5
totalCost <- 40
maxAllGroups <- 3
# Setup problem
food <- c('Chicken', 'Beef', 'Lamb', 'Fish', 'Pork', 'Carrot', 'Lettuce', 'Asparagus', 'Beats', 'Broccoli', 'Orange', 'Apple', 'Pear', 'Banana', 'Watermelon', 'Potato', 'Corn', 'Beans', 'Bread', 'Pasta')
group <- c('Meat', 'Meat', 'Meat', 'Meat', 'Meat', 'Veggie', 'Veggie', 'Veggie', 'Veggie', 'Veggie', 'Fruit', 'Fruit', 'Fruit', 'Fruit', 'Fruit', 'Starch', 'Starch', 'Starch', 'Starch', 'Starch')
cost <- round(runif (length(food), 1, 20), 0)
value <- round(runif (length(food), 20, 60), 0)
df <- data.frame(food, group, cost, value, stringsAsFactors = FALSE) %>%
mutate(Total = 1)
# Value to be maximized
Value <- df$value
# Create constraint vectors
ConVec_Cost <- df$cost
ConVec_Items <- df$Total
# Make `Group` dummy variables
groups <- unique(df$group)
ConVec_Groups <- data.frame(row.names = 1:nrow(df))
for(i in 1:length(groups)){
currGroup <- groups[i]
vec <- df %>%
mutate(isGroup = (group == currGroup)*1) %>%
select(isGroup)
colnames(vec) <- currGroup
ConVec_Groups <- cbind(ConVec_Groups, vec)
}
# ConVec_AnyGroupEqual3 <- ???
ConVec_All <- t(cbind(ConVec_Cost, ConVec_Items, ConVec_Groups))
# Create constraint directions
ConDir_Cost <- "< = "
ConDir_Items <- "= = "
ConDir_Groups <- rep("< = ", ncol(ConVec_Groups))
# ConDir_AnyGroupEqual3 <- "= = "
ConDir_All <- c(ConDir_Cost, ConDir_Items, ConDir_Groups)
# Create constraint values
ConVal_Cost <- totalCost
ConVal_Items <- totalItems
ConVal_Groups <- rep(maxAllGroups, ncol(ConVec_Groups))
# ConVal_AnyGroupEqual3 <- 1 #1 group should have 3
ConVal_All <- c(ConVal_Cost, ConVal_Items, ConVal_Groups)
# Solve
sol <- lpSolve::lp("max",
objective.in = Value,
const.mat = ConVec_All,
const.dir = ConDir_All,
const.rhs = ConVal_All,
all.bin = TRUE
)
# Solution
df[sol$solution == 1,]
Если бы мне нужно было, чтобы у конкретной группы продуктов было 3, это было бы легко, но тот факт, что мне нужно, чтобы любая из групп была 3, усложняет задачу. Есть ли способ сделать это, не прибегая к LPSolveAPI (о котором я, правда, мало что знаю)?
Ответы 1
Я понял это, проанализировав чей-то ответ на аналогичный вопрос некоторое время назад. По сути, вам нужно добавить 5 «фиктивных рядов» (по одному для каждой группы продуктов) со значением -3 по диагонали. Затем вам нужно добавить еще один столбец со всеми значениями, равными 0, за исключением последних 5 строк, равных 1 (строки, которые вы только что добавили в матрицу). Вы заставляете новый столбец быть не менее 1, что означает, что будет выбрана одна из этих последних 5 строк должен.
Поскольку будет выбрана одна из этих строк, и эта строка добавляет -3 к любой группе продуктов, в которой она находится, а также у вас есть ограничения, которые заставляют каждую группу продуктов быть по крайней мере 0, тогда выбранная строка -3 заставит эту еду- групповой столбец, чтобы выбрать 3, чтобы сумма была >= 0.
НОВЫЙ КОД
## Choose 5 food items remaining under $40 and maximizing Value ##
## There can be no more than 3 items from the same group chosen, but **there must be 3 items from at least one group**(??) ##
library(dplyr)
library(lpSolve)
# Constraints
totalItems <- 5
totalCost <- 40
minAllGroups <- 0
atLeastNFrom1 <- 3
# Setup problem
food <- c('Chicken', 'Beef', 'Lamb', 'Fish', 'Pork', 'Carrot', 'Lettuce', 'Asparagus', 'Beats', 'Broccoli', 'Orange', 'Apple', 'Pear', 'Banana', 'Watermelon', 'Potato', 'Corn', 'Beans', 'Bread', 'Pasta')
group <- c('Meat', 'Meat', 'Meat', 'Meat', 'Meat', 'Veggie', 'Veggie', 'Veggie', 'Veggie', 'Veggie', 'Fruit', 'Fruit', 'Fruit', 'Fruit', 'Fruit', 'Starch', 'Starch', 'Starch', 'Starch', 'Starch')
cost <- round(runif (length(food), 1, 20), 0)
value <- round(runif (length(food), 20, 60), 0)
df <- data.frame(food, group, cost, value, stringsAsFactors = FALSE) %>%
mutate(Total = 1)
# Create constraint vectors
ConVec_Cost <- df$cost
ConVec_Items <- df$Total
# Make `Group` dummy variables
groups <- unique(df$group)
ConVec_Groups <- data.frame(row.names = 1:nrow(df))
for(i in 1:length(groups)){
currGroup <- groups[i]
vec <- df %>%
mutate(isGroup = (group == currGroup)*1) %>%
select(isGroup)
colnames(vec) <- currGroup
ConVec_Groups <- cbind(ConVec_Groups, vec)
}
# New vector for atleast
ConVec_AtLeastN <- 0
ConVec_All <- cbind(ConVec_Cost, ConVec_Items, ConVec_Groups, ConVec_AtLeastN)
# Add the negative values to the matrix
ConVec_All <- rbind(ConVec_All, c(0,0,-atLeastNFrom1,0,0,0,1))
ConVec_All <- rbind(ConVec_All, c(0,0,0,-atLeastNFrom1,0,0,1))
ConVec_All <- rbind(ConVec_All, c(0,0,0,0,-atLeastNFrom1,0,1))
ConVec_All <- rbind(ConVec_All, c(0,0,0,0,0,-atLeastNFrom1,1))
# Create constraint directions
ConDir_Cost <- "< = "
ConDir_Items <- "= = "
ConDir_Groups <- rep("> = ", ncol(ConVec_Groups))
ConDir_AtLeastN <- "> = "
ConDir_All <- c(ConDir_Cost, ConDir_Items, ConDir_Groups, ConDir_AtLeastN)
# Create constraint values
ConVal_Cost <- totalCost
ConVal_Items <- totalItems
ConVal_Groups <- rep(minAllGroups, ncol(ConVec_Groups))
ConVal_AtLeastN <- 1
ConVal_All <- c(ConVal_Cost, ConVal_Items, ConVal_Groups, ConVal_AtLeastN)
# Value to be maximized
Value <- c(df$value, rep(0, nrow(ConVec_All) - length(df$value)))
# Solve
sol <- lpSolve::lp("max",
objective.in = Value,
const.mat = t(ConVec_All),
const.dir = ConDir_All,
const.rhs = ConVal_All,
all.bin = TRUE
)
# Solution
df[sol$solution[1:nrow(df)] == 1,]
Я запустил этот пример, и похоже, что ограничение максимальной цены не соблюдается.