在R中对数值表应用优化函数：带约束行选值最大化问题求解

问题背景 #

给定数值矩阵：

values <- matrix(c(0.174,0.349,1.075,3.1424,
                   0.173,0.346,1.038,3.114,
                   0.171,0.343,1.03,3.09,
                   0.17,0.34,1.02,3.06), 
                 ncol=4)

需求：从矩阵每行选一个元素，最大化所选元素的总和，需满足：

• 每行必须且只能选取一列的元素；
• 列1使用成本4，列2成本3，列3成本2，列4成本1，总成本≤11。

尝试用lpSolve包建模但得到解为0，需修正建模逻辑。

解决方案 #

1. 安装并加载lpSolve包 #

if (!require(lpSolve)) {
  install.packages("lpSolve")
  library(lpSolve)
}

2. 定义核心参数 #

# 行数和列数
n_rows <- nrow(values)
n_cols <- ncol(values)

# 列成本向量
col_costs <- c(4, 3, 2, 1)

# 目标函数系数：将矩阵按列展开成一维向量（对应每个x_ij变量）
obj_coeff <- as.vector(values)

3. 构建约束条件 #

约束1：每行必须选且仅选一列

对每一行，对应4个变量（该行的4列）的和必须等于1。约束矩阵的这部分是一个n_rows × (n_rows*n_cols)的矩阵，每行只有对应该行的4个位置为1，其余为0。

约束2：总成本不超过11

计算所有选中列的成本总和：每个列j的成本乘以选中该列的行数（即该列所有x_ij的和），总和≤11。约束矩阵的这一行，对应列j的所有x_ij位置（共n_rows个）的值为col_costs[j]，其余为0。

# 构建约束矩阵
constraint_matrix <- rbind(
  # 每行选一个的约束
  do.call(rbind, lapply(1:n_rows, function(i) {
    row <- rep(0, n_rows*n_cols)
    row[(i-1)*n_cols + 1:n_cols] <- 1
    row
  })),
  # 总成本约束
  col_costs[rep(1:n_cols, each = n_rows)]
)

# 约束方向：前n_rows个约束为等于（"="），最后一个为小于等于（"<="）
constraint_dir <- c(rep("=", n_rows), "<=")

# 约束右侧值：前n_rows个为1，最后一个为11
constraint_rhs <- c(rep(1, n_rows), 11)

4. 求解整数规划模型 #

因为变量是0-1整数，设置all.bin=TRUE：

# 求解最大化问题
result <- lp(direction = "max",
             objective.in = obj_coeff,
             const.mat = constraint_matrix,
             const.dir = constraint_dir,
             const.rhs = constraint_rhs,
             all.bin = TRUE)

5. 解析结果 #

# 查看最优值
cat("最优总和：", result$objval, "\n")

# 查看选中的位置（将一维解向量还原为矩阵）
solution_matrix <- matrix(result$solution, nrow = n_rows, byrow = TRUE)
cat("选中位置矩阵（1表示选中）：\n")
print(solution_matrix)

# 计算总成本
selected_cols <- apply(solution_matrix, 1, which.max)
total_cost <- sum(col_costs[selected_cols])
cat("总成本：", total_cost, "\n")

适配大型数据集 #

上述代码完全基于矩阵的行列数动态生成约束，无需手动调整参数。只需替换values矩阵和col_costs向量，即可直接应用于大型数据集。

常见错误说明 #

之前得到解为0，大概率是以下原因：

• 目标函数方向错误（比如误设为最小化）；
• 约束矩阵构建错误，导致每行选值的约束未生效；
• 未设置all.bin=TRUE，变量被当作连续值求解，出现不符合逻辑的解。

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