そうだR を使ってやろう

20人いる科

毎日2人当直が必要

祝日休日は昼勤務も人員必要

1勤務中\(N\)日以上中日必要

一ヶ月に\(M\)日超えてはならない

休日勤務数も調整したい

リーダー同士や新人同士は同時に当直させられない

\(f(x)=x_1+9x_2+x_3\) を以下の条件で最大化する.

\(\begin{matrix}x_1+2x_2+3x_3\leq 9 \\ 3x_1+2x_2+2x_3 \leq 15 \\x_1, x_2, x_3 \in \mathbb{Z}\end{matrix}\)

整数解に制限した線形計画法

lpSolve::lp または lpSolve::lp.assign

# Set up problem: maximize
#   x1 + 9 x2 +   x3 subject to
#   x1 + 2 x2 + 3 x3 <= 9
# 3 x1 + 2 x2 + 2 x3 <= 15
f.obj <- c(1, 9, 1)
f.con <- matrix (c(1, 2, 3, 3, 2, 2), nrow=2, byrow=TRUE)
f.dir <- c("<=", "<=")
f.rhs <- c(9, 15)
lpSolve::lp("max", f.obj, f.con, f.dir, f.rhs, int.vec=1:3)$solution

[1] 1 4 0

シフト行列\(X\)に\(\{0,1\}\)を割り振る.

3人を5日に割り振る.

シフト行列\(X\)をベクトル\(x\)にして\(\{0,1\}\)を割り振る.

\(X=\begin{bmatrix}\\ x_{*,1} \\\\\end{bmatrix}\begin{bmatrix}\\\cdots\\\\\end{bmatrix}\begin{bmatrix}\\ x_{*,j}\\\\\end{bmatrix}\begin{bmatrix}\\\cdots\\\\\end{bmatrix}\begin{bmatrix}\\ x_{*,5}\\\\\end{bmatrix}\)

\(\begin{align} x &=\{x_{*,1}^\mathsf{T}, \dots, x_{*,j}^\mathsf{T}, \dots, x_{*,5}^\mathsf{T}\}\\ &=\{x_{1,1}, x_{2,1}, x_{3,1}, x_{1,2}, \dots, x_{i,j}, \dots, x_{1,5}, x_{2,5}, x_{3,5}\}\end{align}\)

シフト行列\(X\)をベクトル\(x\)にして\(\{0,1\}\)を割り振る.

\(\begin{matrix}&&&x_{1,1}&x_{2,1}&x_{3,1}&x_{1,2}&x_{2,2}&x_{3,2}&\dots&x_{3,5}&\\c_k&=&\{&0&0&0&1&1&1&\dots&0&\}\end{matrix}\)

\(c_k x^\mathsf{T} = 2\)

シフト行列\(X\)をベクトル\(x\)にして\(\{0,1\}\)を割り振る.

\(\begin{matrix}&&&x_{1,1}&\dots&x_{1,2}&\dots&x_{1,3}&\dots&x_{1,4}&\dots&x_{1,5}&\dots&\\c_k&=&\{&1&0&1&0&1&0&1&0&1&0&\}\end{matrix}\)

\(c_k x^\mathsf{T} \leq 3\)

シフト行列\(X\)をベクトル\(x\)にして\(\{0,1\}\)を割り振る.

\(\begin{matrix}&&&\dots&x_{1,2}&\dots&x_{3,4}&\dots&\\c_k&=&\{&\dots&-p&\dots&0&\dots&\}\\&&\{&\dots&0&\dots&-p&\dots&\}\end{matrix}\)

最終的にすべての制約条件行列\(C\) を使って

\(\underset{x}{\textrm{max}} f(x)=C x^\mathsf{T}\)