「ナース・スケジューリング: 問題把握とモデリング」　を文系初心者にも分かるように図やイラストを追加する_3

# この記事は
:::note warn
この記事は
「ナース・スケジューリング: 問題把握とモデリング」　を文系初心者にも分かるように図やイラストを追加する_2 の続きとなる記事です。
:::

https://qiita.com/ookamikujira/items/507501c8ee8927f7f781

# 3章 組み合わせ最適化問題としての定式化
## 3-3　各ナースの各日程の勤務内容を組み合わせる定式化(p.44)
>b)同一シフトが連続しない場合の間隔日数
>$ナースi\in M$の$シフトk\in W$の間隔日数の下限$u_k$を守るために
＜中略＞
以下のように表す。
>```math
>x_{i,j-t,k}-\sum_{h=1}^{t-1}x_{i,j-h,k}+x_{ijk}\leqq1\\
>t\in \{2,3,...,u_k\}
>```

本書の例に倣って$u_k=4$（間隔下限が4日。下の図では休みの間隔下限として図解。）
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/823518/7dc1da5f-f855-d217-bf9d-5b45c52d6adf.png)


休みの間隔を判定する条件式は複数の式を組み合わせて定式化します。
パターンが多いですが休みの間隔が最低4日の例を考えてみます。
4日間の間隔があいているか否かを調べるには5日間を見ればOKです。

**OK…休みの間隔が4日以上またはその可能性**
**NG…休みの間隔が4日未満(休みと休みの間に出勤が3日以下)**
0,1の5つの並びなので全部で32パターンです。
||1日目|2日目|3日目|4日目|5日目|判定|
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|パターン1|0|0|0|0|0|<font color="Green">OK</font>|
|パターン2|0|0|0|0|1|<font color="Green">OK</font>|
|パターン3|0|0|0|1|0|<font color="Green">OK</font>|
|パターン4|0|0|0|1|1|<font color="Green">OK</font>|
|パターン5|0|0|1|0|0|<font color="Green">OK</font>|
|パターン6|0|0|1|0|1|<font color="Red">NG</font>|
|パターン7|0|0|1|1|0|<font color="Green">OK</font>|
|パターン8|0|0|1|1|1|<font color="Green">OK</font>|
|パターン9|0|1|0|0|0|<font color="Green">OK</font>|
|パターン10|0|1|0|0|1|<font color="Red">NG</font>|
|パターン11|0|1|0|1|0|<font color="Red">NG</font>|
|パターン12|0|1|0|1|1|<font color="Red">NG</font>|
|パターン13|0|1|1|0|0|<font color="Green">OK</font>|
|パターン14|0|1|1|0|1|<font color="Red">NG</font>|
|パターン15|0|1|1|1|0|<font color="Green">OK</font>|
|パターン16|0|1|1|1|1|<font color="Green">OK</font>|
|パターン17|1|0|0|0|0|<font color="Green">OK</font>|
|パターン18|1|0|0|0|1|<font color="Red">NG</font>|
|パターン19|1|0|0|1|0|<font color="Red">NG</font>|
|パターン20|1|0|0|1|1|<font color="Red">NG</font>|
|パターン21|1|0|1|0|0|<font color="Red">NG</font>|
|パターン22|1|0|1|0|1|<font color="Red">NG</font>|
|パターン23|1|0|1|1|0|<font color="Red">NG</font>|
|パターン24|1|0|1|1|1|<font color="Red">NG</font>|
|パターン25|1|1|0|0|0|<font color="Green">OK</font>|
|パターン26|1|1|0|0|1|<font color="Red">NG</font>|
|パターン27|1|1|0|1|0|<font color="Red">NG</font>|
|パターン28|1|1|0|1|1|<font color="Red">NG</font>|
|パターン29|1|1|1|0|0|<font color="Green">OK</font>|
|パターン30|1|1|1|0|1|<font color="Red">NG</font>|
|パターン31|1|1|1|1|0|<font color="green">OK</font>|
|パターン32|1|1|1|1|1|<font color="Green">OK</font>|

先ほどの制約式の振り返りです。
```math
x_{i,j-t,k}-\sum_{h=1}^{t-1}x_{i,j-h,k}+x_{ijk}\leqq1\\
t\in \{2,3,...,u_k\}
```
上記の32パターンの意思決定変数をこの制約式の左辺に代入し、1以下と制約すれば取りうるパターンはOKパターンのみになります。
実際に見てみます。

```math
t\in \{2,3,...,u_k\}\\
```

なので

```math
t\in\{2,3,4\}
```
となり3つの制約式ができます。 

```math
u_k=4 , j=5 , t = 4 \\
x_{i,5-4,k}-(x_{i,5-1,k}+x_{i,5-2,k}+x_{i,5-3,k})+x_{i,5,k}\leqq1\\
x_{i,1,k}-x_{i,4,k}-x_{i,3,k}-x_{i,2,k}+x_{i,5,k}\leqq1…①\\
```
 

```math
u_k=4 , j=5 , t = 3 \\
x_{i,5-3,k}-(x_{i,5-1,k}+x_{i,5-2,k})+x_{i,5,k}\leqq1\\
x_{i,2,k}-x_{i,4,k}-x_{i,3,k}+x_{i,5,k}\leqq1…②
```
 

```math
u_k=4 , j=5 , t = 2 \\
x_{i,5-2,k}-(x_{i,5-1,k})+x_{i,5,k}\leqq1\\
x_{i,3,k}-x_{i,4,k}+x_{i,5,k}\leqq1…③
```

①②③の式を簡単に表現すると
```math
(4日前)-(3日前)-(2日前)-(1日前)+(基準日)\leqq1…①\\
(3日前)-(2日前)-(1日前)+(基準日)\leqq1…②\\
(2日前)-(1日前)+(基準日)\leqq1…③\\
```

試しにパターン6を見てみます。ここでいう基準日とは$j$の値ですので$5日目$になります。
||1日目|2日目|3日目|4日目|5日目|判定|
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|パターン6|0|0|1|0|1|<font color="Red">NG</font>|

それぞれの式に代入すると
```math
0-0-1-0+1\leqq1…①\\
0-1-0+1\leqq1…②\\
1-0+1\leqq1…③\\
```

③の式が成り立ちません。ゆえにこの条件下でパターン6の意思決定変数の並びを作ることはできません。

ただこれだけでは足りません。
これら3つの式が見ている部分（守備範囲）は以下の図のようになるからです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/823518/1d7a2da2-4d66-8e1b-712c-4708234a5a89.png)



パターン19を見てみると
||1日目|2日目|3日目|4日目|5日目|判定|
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|パターン19|1|0|0|1|0|<font color="Red">NG</font>|

①②③すべての式が成り立ってしまいます。
```math
\begin{align}
0\leqq1…①\\
-1\leqq1…②\\
-1\leqq1…③
\end{align}
```
そのため5日間の内、前半部分でも同じように制約を付与します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/823518/a9937818-8768-4b83-2c28-4be433af25cd.png)



>また、説明のため$j=4,t=2,3$と$j=3,t=2$に対する式も以下に示しておく
>```math
>j=4,t=3\\
>x_{i1k}-x_{i2k}-x_{i3k}+x_{i4k}\leqq1…④\\
>\\
>j=4,t=2\\
>x_{i2k}-x_{i3k}+x_{i4k}\leqq1…⑤\\
>\\
>j=3,t=2\\
>x_{i1k}-x_{i2k}+x_{i3k}\leqq1…⑥\\
>```

日付軸に五つ並んだ意思決定変数がこれらの制約をすべて満たす限り、
5日間のどこにも「101」、「1001」、「10001」といった4日未満の間隔を作ることができません。
すなわち、休みの間隔を4日以上開けることができます。
　
　


先ほどは間隔日数の下限でした。
次は上限です。
休みと休みの間が離れずぎるのも避けたいという考えです。

>次に、$ナース_i\in{M}$の$シフト_k\in{W}$の間隔日数の上限$v_k$を守るために$日_i\in{N}$までの$v_k+1$日分の変数を利用して、
>以下のように表す。
>```math
>\sum_{h=0}^{v_k}x_{i,j-h,k}\geqq1
>```
><中略>
>例えば、$v_k=6,j=7$で、この制約式を表してみると、
>```math
>x_{i1k}+x_{i2k}+x_{i3k}+x_{i4k}+x_{i5k}+x_{i6k}+x_{i7k}\geqq1
>```
分かりやすくすると
```math
(6日前)+(5日前)+(4日前)+(3日前)+(2日前)+(1日前)+(基準日)\geqq1
```
これは非常にシンプルです。
7日間の内、最低でもどこか1日は休みのシフトを割り当てるということです。
$v_k=6$であれば休みが離れていいのは最大6日という意味です。
それを超えた連続勤務（休み以外のシフトを勤務とした場合）は「7日間休みなし(=制約式左辺が0)」になるためそれを制限します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/823518/6f0c46b6-954c-08f4-ed40-e89a733c4dd7.png)


>c)異種勤務を含む禁止シフト並びを禁止する
>$ナース_i\in{M}$の$日_j\in{N}$までの日が、禁止シフト並び$(k_0,k_1,...,k_t)\in{Q}$にならないよう、対応する変数がすべて一緒に1になることを禁ずる。
>```math
>\sum_{h=0}^{t}x_{i,j-t+h,k_h}\leqq t
>```
>例えば$(深夜勤,休み,日勤)$が禁止されているならば(集合$Q$の要素ならば)、$j=3$でこの制約式を表してみると、
>```math
>x_{i1深夜勤}\hspace{5pt}+x_{i2休み}\hspace{5pt}+x_{i3日勤}\hspace{5pt}\leqq2
>```

これも非常にシンプルです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/823518/32c2dd06-7efa-1fc7-f12b-857d23034521.png)![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/823518/5d76aafa-5c05-1b0f-ad77-9c9c24aa5d87.png)


禁止並びの長さによって右辺の$t$の値が変わります。
3日間の並びであれば$t$の値は$並びの長さ-1$であるため$t=2$となります。

# 続き
書いています。