整数线性规划（ILP）：组不混合约束的R代码调试求助

问题背景 #

需将3个不同群组（Group A、Group B、Group C）分配至6个不同地点。

目标 #

最小化各地点的未使用空间（等价于最大化已使用空间）。

约束条件 #

• 约束1：每个地点j，所有群组分配至该地点的总人数 ≤ 地点j的容量。
• 约束2：分配至各地点的Group A、Group B、Group C总人数分别不得超过对应群组的可用总人数。
• 约束3：群组不可混合：同一地点不得同时存在不同群组。

现有问题 #

已基于lpSolve库实现满足前两个约束的R脚本，但在构建第三个约束时遇到困难，尝试的代码出现subscript out of bounds（下标越界）错误，需调整代码解决该问题。

实现前两个约束的R代码 #

library(lpSolve)

# 定义数据
n_groups <- 3
n_locations <- 6
n_group_a <- 130
n_group_b <- 40
n_group_c <- 120
l_capacities <- c(60, 50, 40, 30, 20, 10)

# 定义决策变量
vars <- matrix(0, nrow = n_groups * n_locations, ncol = 1)

for (i in 1:n_groups) {
  for (j in 1:n_locations) {
    vars[(i-1)*n_locations+j] <- 1
  } 
}

# 最大化已使用空间
obj <- rep(1, n_locations*n_groups)

# 定义约束条件
rhs <- c(l_capacities, n_group_a, n_group_b, n_group_c)
dir <- c(rep("<=", n_locations + n_groups))

con <- matrix(0, nrow = n_locations + n_groups, ncol = n_groups * n_locations)

# 约束1：每个地点j，所有群组分配至该地点的总人数 ≤ 地点j的容量
for (j in 1:n_locations) {
  for (i in 1:n_groups) {
    con[j, (i-1)*n_locations+j] <- 1
  }
}

# 约束2：各群组分配的总人数不超过可用总人数
for (j in 1:n_groups) {
  con[n_locations+j, seq((j-1)*n_locations+1, j*n_locations)] <- rep(1, n_locations)
}

# 求解问题
result <- lp(direction = "max", objective.in = obj, const.mat = con, const.dir = dir, const.rhs = rhs)

# 输出最优分配结果
assignment <- matrix(result$solution[1:(n_groups*n_locations)], nrow = n_locations)
rownames(assignment) <- paste0("Location ", 1:n_locations)
colnames(assignment) <- c("Group A", "Group B", "Group C")
print(assignment)

尝试的第三个约束代码（报错） #

# 错误的约束3实现：逻辑偏差且下标越界
# for (i in 1:n_groups) {
#   con[n_locations+2*n_groups+i, seq((i-1)*n_locations+1, i*n_locations)] <- rep(1, n_locations)
# }

问题原因与修正方案 #

报错原因 #

1. 下标越界：初始定义的con矩阵仅包含n_locations + n_groups（6+3=9）行，但代码试图访问n_locations+2*n_groups+i（即第13行及以后）的位置，超出矩阵行数范围。
2. 逻辑错误：原代码试图限制每个群组只能分配到一个地点，这与约束3“同一地点不能混合群组”的要求完全不符。

正确的约束3实现逻辑 #

约束3要求每个地点最多只能分配一个群组，即对每个地点j，分配到该地点的不同群组变量之和≤1。具体步骤：

1. 扩展con矩阵行数，新增n_locations行用于存放地点群组不混合约束。
2. 对每个地点j，将该地点对应的3个群组变量位置设为1，约束方向设为<=1，右侧值为1。

修正后的完整代码 #

library(lpSolve)

# 定义数据
n_groups <- 3
n_locations <- 6
n_group_a <- 130
n_group_b <- 40
n_group_c <- 120
l_capacities <- c(60, 50, 40, 30, 20, 10)

# 目标：最大化总使用人数（等价于最小化未使用空间）
obj <- rep(1, n_locations*n_groups)

# 约束矩阵：行数 = 地点容量约束数 + 群组人数约束数 + 地点群组不混合约束数
con <- matrix(0, nrow = n_locations + n_groups + n_locations, ncol = n_groups * n_locations)
dir <- c(rep("<=", n_locations), rep("<=", n_groups), rep("<=", n_locations))
rhs <- c(l_capacities, n_group_a, n_group_b, n_group_c, rep(1, n_locations))

# 约束1：每个地点的总分配人数 ≤ 地点容量
for (j in 1:n_locations) {
  con[j, c(j, j+n_locations, j+2*n_locations)] <- 1
}

# 约束2：每个群组的总分配人数 ≤ 群组可用人数
for (g in 1:n_groups) {
  con[n_locations + g, seq((g-1)*n_locations + 1, g*n_locations)] <- 1
}

# 约束3：每个地点最多只能分配一个群组
for (j in 1:n_locations) {
  con[n_locations + n_groups + j, c(j, j+n_locations, j+2*n_locations)] <- 1
}

# 求解线性规划问题
result <- lp(direction = "max", objective.in = obj, const.mat = con, const.dir = dir, const.rhs = rhs)

# 输出最优分配结果
assignment <- matrix(result$solution, nrow = n_locations, byrow = FALSE)
rownames(assignment) <- paste0("地点 ", 1:n_locations)
colnames(assignment) <- c("Group A", "Group B", "Group C")
print(assignment)
cat("总已使用空间：", result$objval, "\n")
cat("总未使用空间：", sum(l_capacities) - result$objval, "\n")

代码说明 #

• 扩展了约束矩阵的行数，确保能容纳新增的约束3。
• 约束3的逻辑准确匹配“同一地点不能混合群组”的要求，每个地点的三个群组变量之和≤1，保证最多只有一个群组被分配到该地点。
• 优化了约束1的赋值逻辑，代码更简洁清晰。

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