5

部屋のリスト、部屋の最大平方フィート、プログラム、プログラムの最大平方フィート、および部屋が意図したプログラムの使用にどれだけ一致するか (一致数) の値があります。助けを借りて、部屋ごとに 1 つのプログラムのマッチ数と平方フィートの使用を最大化することができました。ただし、この分析をさらに一歩進めて、同じ部屋で複数のプログラムを許可したいと思います。一致数が最も高い場合は、倍数が平方フィートの要件内に収まる限り、同じプログラムの倍数を許可します。さらに、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 の密閉型オフィスを配置しようとします。これは、合計 12 の一致に対して、1 つの共同スペース (8 一致) および 1 つのストレージ/アーカイブ (4 一致) よりもはるかに高い最適一致 # を獲得します。

これは、ソリューション マトリックス内の特定のプログラムの総数を制限するという次の質問につながります。私はそれが何らかの種類を含むと仮定します 

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

しかし、それを制限する方法もわかりません。これらの数値は、すべてのプログラムで異なります。

ご協力いただきありがとうございます。不明な点がございましたら、お気軽にお問い合わせください。

更新: 制約

  • 各部屋の一致数 (obj.vals) を最大化します。
  • プログラムを最大化します。各部屋のサイズは平方​​フィートです。サイズは平方​​フィートです。これを行うには、同じプログラムを複数回使用するか (5 x 密閉型オフィス)、またはプログラムを組み合わせます (1 つのコラボレーティブ スペースと 1 つのパフォーマンス)。
  • ソリューションで返されるプログラムの数を制限または強制します。プログラムは、すべての部屋でそのプログラムに提供する最大数を超えない限り、部屋間で分割できます。(全 28 列で選択できるのは、5 つの閉鎖されたオフィス、8 つのスタジオ/教室、1 つのファブリケーションなどのみです。
4

1 に答える 1

5

R パッケージlpSolveAPI(lpSolve のラッパー) を使用すると、少し簡単になります。まず、数式 (整数プログラム) を見てから、問題を解決するためのコードを示します。

処方

を正X_r_pの整数値をとる決定変数とします。

X_r_pp=ルームに割り当てられたタイプのプログラムの数r (全体として、問題には 28*12=336 の決定変数があります)

目的関数

一致スコアを最大化する

Max sum(r) sum(p) C_r_p * X_r_p# ここで C_r_p は部屋 r に p を割り当てたスコアです

対象

部屋面積制限の制約

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

(このような制約は 28 個あります)

プログラムの数を制限する 制約

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

(このような制約は 12 個あります)

 X_r_p >= 0, Integer

それがすべての定式化です。336 列 40 行。

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:コードを変更して、すべての部屋に少なくとも 1 つのプログラムがあることを確認します。

次の制約セットを追加します。

X_r_p >= 1 for all r

注: これは最大化問題であるため、最適解はデフォルトでこの制約を尊重する必要があります。つまり、割り当てのスコアが正であると仮定して、可能な場合は常にプログラムを任意の部屋に割り当てます。

フォローアップの質問 2:もう 1 つの質問は、合計で 28 以上のプログラムを持つように依頼できるかどうかです。たとえば、28 の密閉型オフィスが必要な場合、ほぼすべてが 2938 平方フィートの 1 つの部屋に収まります。最大値が28に設定されている場合、Rに他のプログラムを検索するように依頼するにはどうすればよいですか?

この目標を達成するために、少し異なる方法で行うことができます。すべてのプログラムの合計 <= 28 という制約はまったくありません。（上記の解決策に注意してください。私の制約は少し異なります。）

制約:

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

プログラムの種類ごとの最大値のみを制限します。合計に制限はありません。また、プログラムの種類ごとにそのような制約を 1 つ記述する必要はありません。この制約は、発生を制限したい場合にのみ記述してください。

これを一般化するために、各タイプのプログラムの合計の下限と上限を設定できます。これにより、割り当てを非常に細かく制御できます。

min_allowable(p) <= sum(over r) X_r_p <= max_allowable(p) for any program type p
于 2015-08-05T00:04:02.097 に答える