lpSolve无可行解问题排查：含不可重复选择约束的线性规划

问题根源分析 #

1. 约束矩阵逻辑完全错误 #

约束矩阵mat的构造逻辑颠倒且矛盾：

• 约束矩阵的行代表约束条件，列代表变量（每个待选数值）。你当前的列向量（如第一列c(1,0,0,0,0,0,0,0,1)）表示该数值同时被计入第1个约束（第一行选5）和第9个约束（第九行选1），意味着一个数值属于两行，这和实际业务逻辑矛盾——每个数值应仅属于某一行，不可能同时归属于第一行和第九行。
• 这种错误关联会导致约束冲突：选中该数值会同时占用两行的配额，而第九行仅允许选1个、第一行需要选5个，最终无法找到满足所有约束的组合。

2. 未指定0-1整数变量约束 #

你的问题属于0-1整数规划（变量取1表示选中，0表示不选），但lp()默认求解连续线性规划，变量可取0到1之间的小数，不符合“选择与否”的业务需求。同时你未添加每个数值仅能选一次的约束，进一步导致逻辑漏洞。

3. 约束配额的逻辑冲突 #

你需要选中的总数值数量为5 + 8 = 13个，obj有17个数值，本身可行，但错误的约束矩阵让系统认为约束互相矛盾，无法分配配额。

修正后的代码示例 #

首先需明确每个数值对应的行（以下为模拟示例，你需根据实际行归属调整row_assign）：

library(lpSolve)

# 目标函数系数
obj <- c(
  49.2723892, 31.4629786, 25.3265757, 23.3915431, 19.5677222,
  19.2621303, 18.2912147, 16.7899278, 14.5498144, 12.7440869,
  11.6331623, 11.0012557, 7.9473880, 7.8453557, 3.7182273,
  0.2084929, 0.0100000
)

# 定义每个数值所属行（1=第一行，2=第二行...9=第九行），需替换为实际归属
row_assign <- c(1,1,1,1,1, 2,3,4,5,6,7,8,9,9,9,9,9)

# 构造约束矩阵
# 第一部分：行选择数量约束（9行）
row_constraints <- sapply(1:9, function(r) as.integer(row_assign == r))
# 第二部分：每个数值仅选一次的约束（17行，每行对应一个变量）
unique_constraints <- diag(length(obj))

# 合并约束矩阵
mat <- rbind(row_constraints, unique_constraints)

# 约束方向与右侧值
const.dir <- c(rep("==", 9), rep("<=", length(obj)))
const.rhs <- c(5, rep(1, 8), rep(1, length(obj)))

# 求解0-1整数规划
sol <- lp(direction = "max", obj, mat, const.dir, const.rhs, all.bin = TRUE)

# 输出结果
print(sol)
if(sol$status == 0) {
  cat("选中的数值索引：", which(sol$solution == 1), "\n")
  cat("选中的数值：", obj[sol$solution == 1], "\n")
  cat("目标函数最大值：", sol$objval, "\n")
}

关键修正说明 #

• 明确行归属：row_assign定义每个变量所属行，是正确构造约束的基础。
• 拆分约束：分为行配额约束（控制每行选中数量）和变量唯一性约束（控制每个数值仅选一次）。
• 指定变量类型：通过all.bin=TRUE指定所有变量为0-1整数，匹配业务逻辑。

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