我有一个房间列表，房间的最大平方英尺，程序，程序的最大平方英尺，以及房间与预期程序使用的匹配程度（匹配＃）的值 . 在帮助下，我已经能够最大化匹配＃和平方英尺使用每个房间一个程序 . 但是，我想进一步采用这种分析，只要多次匹配仍然符合平方英尺要求，允许同一房间内的多个程序或同一程序的多个程序，如果它具有最高匹配＃ . 此外，我想告诉lpSolve整体而言，我只想在整个建筑物中使用“x”数量的办公室，“y”数量的工作室等 . 到目前为止，这是我的数据和代码：

program.size <- c(120,320,300,800,500,1000,500,1000,1500,400,1500,2000)
room.size <- c(1414,682,1484,2938,1985,1493,427,1958,708,581,1485,652,727,2556,1634,187,2174,205,1070,2165,1680,1449,1441,2289,986,298,590,2925)
(obj.vals <- matrix(c(3,4,2,8,3,7,4,8,6,4,7,7,
                  3,4,2,8,3,7,4,8,6,4,7,7,
                  4,5,3,7,4,6,5,7,5,3,6,6,
                  2,3,1,7,2,6,3,7,7,5,6,6,
                  4,5,3,7,4,6,5,7,5,3,6,6,
                  3,6,4,8,5,7,4,8,7,7,7,7,
                  3,4,2,8,3,7,4,8,6,4,7,7,
                  4,5,3,7,4,6,5,7,5,3,6,6,
                  6,7,5,7,6,6,7,7,5,3,6,6,
                  6,7,5,7,6,6,7,7,5,3,6,6,
                  5,6,6,6,5,7,8,6,4,2,5,5,
                  6,7,5,7,6,6,7,7,5,3,6,6,
                  6,7,5,7,6,6,7,7,5,3,6,6,
                  3,4,4,8,3,9,6,8,6,4,7,7,
                  3,4,2,6,3,5,4,6,6,4,5,5,
                  4,5,3,5,4,4,5,5,5,3,4,4,
                  5,6,4,8,5,7,6,8,6,4,7,7,
                  5,6,4,8,5,7,6,8,6,4,7,7,
                  4,5,5,7,4,8,7,7,5,3,6,6,
                  5,6,4,8,5,7,6,8,6,4,7,7,
                  3,4,2,6,3,5,4,6,6,4,5,5,
                  5,6,4,8,5,7,6,8,6,4,7,7,
                  5,6,4,8,5,7,6,8,6,4,7,7,
                  5,4,4,6,5,5,6,6,6,6,7,5,
                  6,5,5,5,6,4,5,5,5,7,6,4,
                  4,5,3,7,4,6,5,7,7,5,6,6,
                  6,5,5,5,6,4,5,5,5,7,6,4,
                  3,4,4,6,3,7,6,6,6,4,5,5), nrow=12))
rownames(obj.vals) <- c("Enclosed Offices", "Open Office", "Reception / Greeter", "Studio / Classroom",
                    "Conference / Meeting Room", "Gallery", "Public / Lobby / Waiting", 
                    "Collaborative Space", "Mechanical / Support", "Storage / Archives", 
                    "Fabrication", "Performance")
(obj.adj <- obj.vals * outer(program.size, room.size, "<="))


nr <- nrow(obj.adj)
nc <- ncol(obj.adj)

library(lpSolve)
obj <- as.vector(obj.adj)
con <- t(1*sapply(1:nc, function(x) rep(1:nc == x, each=nr)))
dir <- rep("<=", nc)
rhs <- rep(1, nc)
mod <- lp("max", obj, con, dir, rhs, all.bin=TRUE)

final <- matrix(mod$solution, nrow=nr)

所以现在我的问题是如何让解算器最大化平方英尺使用并匹配每个房间（列）中的＃并允许多个相同的程序或程序组合来实现这一目标？我知道我必须解除“mod”中的“<= 1”限制，但我无法弄清楚如何让它找到最适合每个房间，然后最终，整体而言 .

应该来的解决方案[，1]是：

$optimum
33

并且它将尝试在房间内安装11个附属办公室，其中比1个协作空间（8个匹配）和1个存储/存档（4个匹配）获得更高的最佳匹配，总共12个匹配 .

因此，这导致我的下一个问题是限制我的解决方案矩阵中某些程序的总数 . 我认为它会包括某种形式

as.numeric(data$EnclosedOffices "<=" 5)

但我也无法弄清楚如何限制它 . 所有节目的这些数字都不同 .

感谢您提供任何帮助，并随时要求澄清 .

Update: 约束

最大化每个房间的匹配＃（obj.vals） .
最大化每个房间内的program.size平方英尺 . 尺寸 . 通过多次使用相同的程序（5 x封闭式办公室）或组合程序（1个协作空间和1个性能）来完成此操作 .
限制和/或强制解决方案中返回的程序数 . 这些程序可以在房间之间分开，只要它不超过我在所有房间中为该程序提供的最大数量 . （所有28个栏目中只能选择5个附属办公室，8个工作室/教室，1个制作等） .

1 回答

如果您使用R包 lpSolveAPI （lpSolve的包装器），那么它会变得容易一些 . 首先，看看数学公式（整数程序），然后我向您展示解决问题的代码 .

配方

设 X_r_p 是采用正整数值的决策变量 .

X_r_p =分配给房间 r 的 p 类型的程序数量（在所有问题中将有28 * 12 = 336个决策变量）

Objective Function

最大化匹配分数

Max sum(r) sum(p) C_r_p * X_r_p ＃这里C_r_p是将p分配给房间r的分数

受制于

Room Area Limitation Constraint

Sum(p) Max_area_p * X_r_p <= Room Size (r) for each room r

（我们将有28个这样的限制）

Restrict the Number of programs Constraint

Sum(r) X_r_p <= Max_allowable(p) for each program p

（我们将有12个这样的限制）

X_r_p >= 0, Integer

这就是所有的表述 . 336列和40行 .

Implementatin in R

这是R中的一个实现，使用 lpSolveAPI . 注意：由于OP没有在建筑物中提供max_allowable程序，我为 max_programs. 生成了我自己的数据

program.size <- c(120,320,300,800,500,1000,500,1000,1500,400,1500,2000)
    room.size <- c(1414,682,1484,2938,1985,1493,427,1958,708,581,1485,652,727,2556,1634,187,2174,205,1070,2165,1680,1449,1441,2289,986,298,590,2925)
    (obj.vals <- matrix(c(3,4,2,8,3,7,4,8,6,4,7,7,3,4,2,8,3,7,4,8,6,4,7,7,
4,5,3,7,4,6,5,7,5,3,6,6,2,3,1,7,2,6,3,7,7,5,6,6, 4,5,3,7,4,6,5,7,5,3,6,6,
3,6,4,8,5,7,4,8,7,7,7,7,3,4,2,8,3,7,4,8,6,4,7,7, 4,5,3,7,4,6,5,7,5,3,6,6,
6,7,5,7,6,6,7,7,5,3,6,6,6,7,5,7,6,6,7,7,5,3,6,6, 5,6,6,6,5,7,8,6,4,2,5,5,
6,7,5,7,6,6,7,7,5,3,6,6, 6,7,5,7,6,6,7,7,5,3,6,6, 3,4,4,8,3,9,6,8,6,4,7,7,
3,4,2,6,3,5,4,6,6,4,5,5, 4,5,3,5,4,4,5,5,5,3,4,4, 5,6,4,8,5,7,6,8,6,4,7,7,
5,6,4,8,5,7,6,8,6,4,7,7, 4,5,5,7,4,8,7,7,5,3,6,6, 5,6,4,8,5,7,6,8,6,4,7,7,
3,4,2,6,3,5,4,6,6,4,5,5, 5,6,4,8,5,7,6,8,6,4,7,7, 5,6,4,8,5,7,6,8,6,4,7,7,
5,4,4,6,5,5,6,6,6,6,7,5, 6,5,5,5,6,4,5,5,5,7,6,4, 4,5,3,7,4,6,5,7,7,5,6,6,
6,5,5,5,6,4,5,5,5,7,6,4, 3,4,4,6,3,7,6,6,6,4,5,5), nrow=12))
rownames(obj.vals) <- c("Enclosed Offices", "Open Office", "Reception / Greeter", "Studio / Classroom",
                        "Conference / Meeting Room", "Gallery", "Public / Lobby / Waiting", 
                        "Collaborative Space", "Mechanical / Support", "Storage / Archives", 
                        "Fabrication", "Performance")

对于12个程序中的每个程序，让我们设置可以分配给所有房间的最大重复次数 . 请注意，这是我添加的内容，因为OP未提供此数据 . （限制他们被分配到太多房间 . ）

max_programs <- c(1,2,3,1,5,2,3,4,1,3,1,2)

library(lpSolveAPI)

nrooms <- 28
nprgs <- 12
ncol = nrooms*nprgs

lp_matching <- make.lp(ncol=ncol)
#we want integer assignments
set.type(lp_matching, columns=1:ncol, type = c("integer"))

# sum r,p Crp * Xrp
set.objfn(lp_matching, obj.vals) #28 rooms * 12 programs
lp.control(lp_matching,sense='max')

#' Set Max Programs constraints
#' No more than max number of programs over all the rooms
#' X1p + x2p + x3p ... + x28p <= max(p) for each p
Add_Max_program_constraint <- function (prog_index) {
  prog_cols <- (0:(nrooms-1))*nprgs + prog_index
  add.constraint(lp_matching, rep(1,nrooms), indices=prog_cols, rhs=max_programs[prog_index])
}
#Add a max_number constraint for each program
lapply(1:nprgs, Add_Max_program_constraint)

#' Sum of all the programs assigned to each room, over all programs 
#' area_1 * Xr1+ area 2* Xr2+ ... + area12* Xr12 <= room.size[r] for each room
Add_room_size_constraint <- function (room_index) {
  room_cols <- (room_index-1)*nprgs + (1:nprgs) #relevant columns for a given room
  add.constraint(lp_matching, xt=program.size, indices=room_cols, rhs=room.size[room_index])
}
#Add a max_number constraint for each program
lapply(1:nrooms, Add_room_size_constraint)

解决这个问题：

> solve(lp_matching)
> get.objective(lp_matching)
 [1] 195
get.variables(lp_matching) # to see which programs went to which rooms

> print(lp_matching)
Model name: 
  a linear program with 336 decision variables and 40 constraints

您还可以将IP模型写入文件以进行检查：

#Give identifiable column and row names
rp<- t(outer(1:nrooms, 1:nprgs, paste, sep="_"))
rp_vec <- paste(abc, sep="")
colnames<- paste("x_",rp_vec, sep="")
# RowNames
rownames1 <- paste("MaxProg", 1:nprgs, sep="_")
rownames2 <- paste("Room", 1:nrooms, "AreaLimit", sep="_")
dimnames(lp_matching) <- list(c(rownames1, rownames2), colnames)

write.lp(lp_matching,filename="room_matching.lp")

希望有所帮助 .

根据后续问题进行更新

后续问题1：更改代码以确保每个房间至少有一个程序 .

添加以下约束集：

X_r_p >= 1 for all r

注意：由于这是最大化问题，因此默认情况下，最佳解决方案应遵循此约束 . 换句话说，如果可以，它将始终将程序分配给任何房间，假设分配正分数 .

跟进问题2：另一个问题是，我是否可以要求它总共有超过28个程序？例如，如果我想要28个封闭式办公室，他们几乎都可以放在2938平方英尺的一个房间里 . 如果最大值设置为28，我怎么能要求R仍然找到其他程序？

为了实现这一目标，您可以采用不同的方式 . 根本没有所有程序<= 28约束的总和 . （如果你在上面的解决方案中注意到，我的约束略有不同 . ）

约束：

Sum(r) X_r_p <= Max_allowable(p) for each program p

仅限制每种类型程序的最大值 . 总数没有限制 . 此外，您不必为每种类型的程序编写一个这样的约束 . 仅在要限制其出现时才写入此约束 .

为了概括这一点，您可以设置每种类型程序总数的下限和上限 . 这会给你非常精细地控制作业 .

min_allowable(p) <= sum(over r) X_r_p <= max_allowable(p) for any program type p

回复于 2024-04-27T15:47:08+08:00

lpSolve in R with Character和Column Sum Contraints

1 回答

配方

根据后续问题进行更新

相关问题