含“或”约束的线性优化器构建及额外约束添加求助

我会帮你把两个新约束整合到现有的lpSolve代码中，下面是分步实现方法和完整代码：

1. 约束逻辑转化思路 #

因为线性规划只能处理线性约束，我们需要把你的逻辑需求转化为可量化的线性表达式：

• 约束1（至少一种type1出现≥2次）：通过引入辅助0-1变量实现"或"逻辑，确保至少有一个type1类别的选中数量达标。
• 约束2（Y物品的type1唯一）：通过线性化处理，避免非线性乘积项，确保选中的Y物品的type1不会出现在X物品中。

2. 完整修改后的可运行代码 #

library(lpSolve)
library(dplyr)

# 初始化物品数据
id <- 1:50
type1 <- sample(c('A', 'B', 'C', 'D', 'E'), length(id), replace = T)
type2 <- sample(c('X', 'X', 'X', 'Y'), length(id), replace = T)
value <- round(runif(length(id), 0, 20),0)
cost <- round(runif(length(id), 750, 1250),0)
df <- data.frame(id, type1, type2, value, cost) %>% mutate(total = 1)

# 添加属性哑变量
type1Dummy <- as.data.frame.matrix(table(df$id, df$type1))
type2Dummy <- as.data.frame.matrix(table(df$id, df$type2))
df <- cbind(df, type1Dummy, type2Dummy)

# ---------------------- 新增约束相关处理 ----------------------
# 1. 为约束1创建辅助0-1变量（对应A-E五个type1类别）
num_z_vars <- 5
z_names <- paste0("z_", colnames(type1Dummy))

# 扩展目标函数：辅助变量不影响价值最大化，系数设为0
obj <- c(df$value, rep(0, num_z_vars))

# 2. 构建完整约束矩阵
# 保留原有约束（总数量、总成本、X数量、Y数量），并扩展辅助变量列
existing_mat <- t(data.frame(df$total, df$cost, df$X, df$Y))
existing_mat <- cbind(existing_mat, matrix(0, nrow = nrow(existing_mat), ncol = num_z_vars))

# --- 约束1：至少一个type1出现≥2次 ---
# 子约束：每个type1类别满足「选中数 +5*辅助变量 ≥2」
constraint_type1_freq <- list()
for (k in colnames(type1Dummy)) {
  row <- c(df[[k]], rep(0, num_z_vars))
  row[which(z_names == paste0("z_", k))] <- 5
  constraint_type1_freq[[k]] <- row
}
constraint_type1_freq <- do.call(rbind, constraint_type1_freq)

# 总约束：辅助变量之和≥1（确保至少有一个类别触发选中数≥2的要求）
constraint_z_sum <- c(rep(0, nrow(df)), rep(1, num_z_vars))

# --- 约束2：Y物品的type1不在X物品中出现 ---
# 对每个type1类别，约束「X中该类选中数 +5*Y中该类选中数 ≤5」
# 逻辑：若Y物品是该类，则第二项为5，强制X中选中数为0；否则约束自动满足
constraint_y_type1_unique <- list()
for (k in colnames(type1Dummy)) {
  row <- c(df$X * df[[k]] + 5 * df$Y * df[[k]], rep(0, num_z_vars))
  constraint_y_type1_unique[[k]] <- row
}
constraint_y_type1_unique <- do.call(rbind, constraint_y_type1_unique)

# 合并所有约束矩阵
mat <- rbind(existing_mat, constraint_type1_freq, constraint_z_sum, constraint_y_type1_unique)

# 3. 构建约束方向和右侧值
# 原有约束参数
rhs <- c(5, 5000, 4, 1)
dir <- c("==", "<=", "==", "==")

# 约束1的参数
rhs <- c(rhs, rep(2, num_z_vars), 1)
dir <- c(dir, rep(">=", num_z_vars), ">=")

# 约束2的参数
rhs <- c(rhs, rep(5, num_z_vars))
dir <- c(dir, rep("<=", num_z_vars))

# ---------------------- 求解并验证结果 ----------------------
sol <- lpSolve::lp("max", 
                   objective.in = obj, 
                   const.mat = mat, 
                   const.dir = dir, 
                   const.rhs = rhs, 
                   all.bin = T )

# 提取选中物品
df$selected <- sol$solution[1:nrow(df)]
dfSolved <- df[df$selected == 1,]

# 输出结果
cat("选中的物品：\n")
print(dfSolved %>% select(id, type1, type2, value, cost))

# 验证约束是否满足
cat("\n=== 约束验证 ===\n")
# 验证约束1
type1_counts <- table(dfSolved$type1)
cat("约束1：是否有type1出现≥2次？\n")
print(type1_counts)
cat(paste("结果：", any(type1_counts >=2), "\n"))

# 验证约束2
y_item <- dfSolved %>% filter(type2 == "Y")
y_type1 <- y_item$type1
x_has_y_type1 <- y_type1 %in% dfSolved$type1[dfSolved$type2 == "X"]
cat("\n约束2：Y物品的type1是否不在X物品中？\n")
cat(paste("Y物品的type1：", y_type1, "\n"))
cat(paste("X物品中是否存在该type1：", x_has_y_type1, "\n"))
cat(paste("结果：", !x_has_y_type1, "\n"))

代码关键说明 #

• 辅助变量z_k仅用于实现"或"逻辑，不影响价值最大化目标；
• 约束2通过线性化处理，巧妙规避了非线性的乘积项，符合线性规划要求；
• 代码末尾添加了验证步骤，可直观检查两个约束是否被满足。

内容的提问来源于stack exchange，提问作者CoolGuyHasChillDay