こんにちは！しゅんです！
割当問題を簡単に説明すると、例えば10人の従業員を10個の仕事に割り当てるときにどのように割り当てたら効率的になるかを考える問題です。
今回の記事では割当問題の中でも
「1日でやる仕事数に上限がある場合の割当問題」
を整数計画問題として定式化してみたいと思います。それではやっていきましょう！
「従業員に余りが出る場合の割当問題」
「従業員が複数の仕事を担当できる場合の割当問題」
「時間帯によって異なる仕事を行う場合の割当問題」
「1日でやる仕事数に上限がある場合の割当問題」
「最も負担がかかる従業員の負担を最小にする割当問題」
普段は統計検定2級の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
具体例を使って考える
今回は3人の従業員に6個の仕事を割り当てることを考えます。6個の仕事は朝、昼、夕の3つの時間帯で分けられていて、朝に仕事1,2、昼に仕事3,4、夕に仕事5,6を行います。
各時間帯において各従業員は最大1つの仕事が割り当てられ、各仕事は必ず1人の従業員に割り当てられます。各辺には重みがあります。ごちゃごちゃするので図では省略しています。
上図の例で言うと、朝は「従業員1が仕事2、従業員2が仕事1」を担当し、昼は「従業員2が仕事3、従業員3が仕事4」を担当し、夕は「従業員1が仕事2、従業員3が仕事6」を担当します。
これに加えて今回は「各従業員が1日でできる仕事数は最大2つまで」という制約を考えます。
例えば上のような割当を見てみると、従業員1が仕事を3回やっていますね。これは「各従業員が1日でできる仕事数は最大2つまで」と言う制約に反しているので、ダメな割当とします。
今回はこのような割当の中で、重みの合計が最小となるような割当を求める問題を整数計画問題として定式化してみたいと思います。
整数計画問題として定式化する
「変数・パラメータ」、「目的関数」、「制約条件」の順番で説明したいと思います。
変数・パラメータの設定
パラメータとして時間帯の集合\(T\)、従業員の集合\(E\)、仕事の集合\(J_1,J_2,J_3\)、辺\((i,j)\)の重み\(w_{ij}\)を設定します。（朝を1、昼を2、夕を3とします。）
オーソドックスな割当問題と違って今回は時間帯という概念を追加するので、仕事の集合も朝、昼、夕の3つに分けます。
また0-1変数として\(x_{ijt}\)を設定します。この変数\(x_{ijt}\)は時間帯\(t\)に従業員\(i\)が仕事\(j\)を担当するなら1、そうでなければ0を取ります。
・パラメータ
\(T = \{1,2,3\}\)：時間帯の集合
\(E = \{1,2,3\}\) : 従業員の集合
\(J_1 = \{1,2\}\) : 朝の仕事の集合
\(J_2 = \{3,4\}\) : 昼の仕事の集合
\(J_3 = \{5,6\}\) : 夕の仕事の集合
\(w_{ij}\) : 辺\((i,j)\)の重み
・変数
\(x_{ijt} \in \{0,1\} \;\; (\forall t \in T, \forall i \in E, \forall j \in J_t)\)
目的関数の設定
目的関数は以下のように設定できます。
\(\sum\limits_{t \in T}\sum\limits_{i \in E}\sum\limits_{j \in J_t} w_{ij}x_{ijt}\)
例えば上図の左側の例だと、朝\((t=1)\)は\(x_{121},x_{211}\)が1、昼\((t=2)\)は\(x_{232},x_{342}\)が1、夕\((t=3)\)は\(x_{153},x_{363}\)が1でそれ以外が0となります。
したがって\(\sum\limits_{t \in T}\sum\limits_{i \in E}\sum\limits_{j \in J_t} w_{ij}x_{ijt}\)の値は
\(\sum\limits_{t \in T}\sum\limits_{i \in E}\sum\limits_{j \in J_t} w_{ij}x_{ijt}\)
\( = w_{11}x_{111} + w_{12}x_{121}\)
\( + w_{21}x_{211} + w_{22}x_{221}\)
\( + w_{31}x_{311} + w_{32}x_{321}\)
\( + w_{13}x_{132} + w_{14}x_{142}\)
\( + w_{23}x_{232} + w_{24}x_{242}\)
\( + w_{33}x_{332} + w_{34}x_{342}\)
\( + w_{15}x_{153} + w_{16}x_{163}\)
\( + w_{25}x_{253} + w_{26}x_{263}\)
\( + w_{35}x_{353} + w_{36}x_{363}\)
\(= (3 \times 0) + (4 \times 1)\)
\(+ (2 \times 1) + (5 \times 0)\)
\(+ (4 \times 0) + (6 \times 0)\)
\(+ (8 \times 0) + (4 \times 0)\)
\(+ (1 \times 1) + (3 \times 0)\)
\(+ (5 \times 0) + (2 \times 1)\)
\(+ (2 \times 1) + (4 \times 0)\)
\(+ (5 \times 0) + (6 \times 0)\)
\(+ (1 \times 0) + (6 \times 1)\)
\(= 4 + 2 + 1 + 2 + 2 + 6 = 17\)
となります。
制約条件の設定
最後に制約条件について設定したいと思います。従業員側の制約条件と仕事側の制約条件分けて説明したいと思います。
従業員側の制約条件
従業員側の制約条件は以下のように設定できます。
\( \sum\limits_{j \in J_t} x_{ijt} \leq 1 \;\;\; (\forall t \in T, \forall i \in E)\)
\( \sum\limits_{t \in T}\sum\limits_{j \in J_t} x_{ijt} \leq 2 \;\;\; (\forall i \in E)\)
1行目の制約式は各時間帯で最大1つの仕事を担当するというのを表しています。この式は過去の記事でも解説しているので、今回は説明を省略します。
過去の記事はこちらから！
2行目の式は1日通して最大2回までしか仕事ができないという制約式です。例えば従業員1について考えてみましょう。従業員1に関する2行目の制約式は以下のようになります。
\(\sum\limits_{t \in T}\sum\limits_{j \in J_t} x_{1jt} \leq 2\)
\(\sum\)を使わずに書いてみます。
\(x_{111}+x_{121}+x_{132}+x_{142}+x_{153}+x_{163} \leq 2\)
これは上の式で使われている6つの変数の中で、最大でも2つしか1になれないことを表しています。例えば\(x_{111},x_{132}\)が1になったら他の変数は0になります。つまり時間帯3に仕事をすることができないという制約になっています。
同じように考えると、ある2つの時間帯で仕事をする場合残り1つの時間帯では仕事ができないという制約になっていることが分かります。これを全ての従業員に対して作れば、今回考えている
「各従業員が1日でできる仕事数は最大2つまで」
という制約を表現することができます。
1行目の制約式で\(x_{111},x_{121}\)が両方1になる状態を禁止できています。
仕事側の制約条件
仕事側の制約条件は以下のように設定できます。
\( \sum\limits_{i \in E} x_{ijt} = 1 \;\;\; (\forall t \in T, \forall j \in J_t)\)
例えば朝\((t=1)\)の仕事1について考えてみましょう。仕事1は従業員1～3のうちだれか1人に割り当てられます。
これを制約条件で言い換えると
\(x_{111} = 1\)のパターン
\(x_{211} = 1\)のパターン
\(x_{311} = 1\)のパターン
の3つだったらOKっていう制約条件を作ります。これは
\(x_{111} + x_{211} + x_{311} = 1\)
という制約式で表現することができます。\(\sum\)を使ってこの式表すと
\(\sum\limits_{i \in E} x_{i11} = 1 \)
となります。この制約式を\(j = 2,3,…,6\)に対しても作れば全ての仕事に対して制約条件を作ることができます。
\(t=1\)とすれば\(J_t = \{1,2\}\)となり、仕事1,2を指定できます。
\(t=2\)とすれば\(J_t = \{3,4\}\)となり、仕事3,4を指定できます。
\(t=3\)とすれば\(J_t = \{5,6\}\)となり、仕事5,6を指定できます。
このように時間帯\(t\)を動かすと仕事の集合\(J_t\)が自動的に決まり、その結果仕事1,2,…,6を指定することができます。
整数計画問題としてまとめる
最後にこれらをまとめて整数計画問題として定式化しましょう。
定式化：
\(\min \;\;\; \sum\limits_{t \in T}\sum\limits_{i \in E}\sum\limits_{j \in J_t} w_{ij}x_{ijt}\)
\(\;\text{s.t.}\;\;\;\sum\limits_{j \in J_t} x_{ijt} \leq 1 \;\;\;\; (\forall t \in T, \forall i \in E)\)
\(\;\;\;\;\;\;\;\;\;\;\sum\limits_{i \in E} x_{ijt}=1 \;\;\;\; (\forall t \in T, \forall j \in J_t)\)
\(\;\;\;\;\;\;\;\;\;\;\sum\limits_{t \in T}\sum\limits_{j \in J_t} x_{ijt} \leq 2 \;\;\;\; (\forall i \in E)\)
\(\;\;\;\;\;\;\;\;\; x_{ijt} \in \{0,1\} \;\;(\forall t \in T, \forall i \in E, \forall j \in J_t)\)
次回の記事では今回定式化した整数計画問題をpythonで表現して実際に問題を解いてみたいと思います！
次回の記事はこちらから！
おわりに
いかがでしたか。
今回の記事では割当問題について解説していきました。
今後もこのような数理最適化に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
