select children 幼儿园组二元线性规划

Question

我有以下选择问题。我有一些孩子，他们每个人都有可能 weekday-combinations 加入幼儿园小组。每个 weekday-combination 都有自己的收入（每周天数越多，收入越多）。每个工作日的最大儿童人数有一些限制。并非每个 child 都必须被选中。目标是使总收入最大化。这是一个示例数据集：

df <- data.frame(kid.nr=c(1,1,2,3,3, 3),
             kid.comb.nr=c(1,2,1,1,2, 3), 
             monday=c(0,0,1,0,1, 0),  
             tuesday=c(1,0,1,0,1, 0), 
             wednesday=c(0,1,0,0,1, 0), 
             thursday=c(0,0,1,1,1, 0), 
             friday=c(0,0,1,0,1, 0), 
             revenue.per.combn =c(100, 100, 400, 100, 500, 0)  )

# kid.nr 3 doesnt necessarily has to bee chosen

max.nr.kids.per.weekday <- c(1,2,3,2,1)

据我所知，lpsolve 可以解决这个二进制线性规划问题吗？怎么做到的？特别是，我如何应对一些孩子有超过 1 个可能 weekday-combination，但每个孩子应该只被考虑一次的事实？

Answer 1

首先要做的是建立一个数学模型。这可能看起来像：

然后你需要将它实现到 R 中。我建议使用 OMPR 包。

基本上问题如下：我们有二进制变量 x(i,j)，其中 i=kids 和 j=daycombinations。现在 x(i,j) 有点 "ragged"：它不存在于所有 i,j。例如。 i=kid 2 只有一个 j。这种事情可以由 OMPR 处理（他们称之为 "filter"）。

select children 幼儿园组二元线性规划

select children for kindergarden group with binary linear programming

r

linear-programming

lpsolve