こんにちは！しゅんです！
割当問題を簡単に説明すると、例えば10人の従業員を10個の仕事に割り当てるときにどのように割り当てたら効率的になるかを考える問題です。
今回の記事では割当問題の中でも
「従業員が複数の仕事を担当できる場合の割当問題」
を整数計画問題として定式化してみたいと思います。それではやっていきましょう！
割当問題の制約条件を色々変えてみたシリーズの他の記事はこちらから！
「従業員に余りが出る場合の割当問題」
「従業員が複数の仕事を担当できる場合の割当問題」
「時間帯によって異なる仕事を行う場合の割当問題」
普段は統計検定2級の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
具体例を使って考える
今回は3人の従業員を4つの仕事に割り当てることを考えます。この例では仕事の数の方が多いので、
「各従業員は最大2つまで仕事ができる」
という仮定を置きます。
上図の例で言うと従業員1、3はそれぞれ1つの仕事を担当しますが、従業員2は仕事1,3の2つを担当します。今回はこのような例をOKとしたとき、重みの合計が最小となるような割当を求める問題を整数計画問題として定式化してみたいと思います。
仕事側の制約は「必ず1人の従業員に割り当てられる」にします。
整数計画問題として定式化する
「変数・パラメータ」、「目的関数」、「制約条件」の順番で説明したいと思います。
変数・パラメータの設定
パラメータとして従業員の集合\(E\)、仕事の集合\(J\)、辺\((i,j)\)の重み\(w_{ij}\)を設定します。
また0-1変数として\(x_{ij}\)を設定します。この変数\(x_{ij}\)は従業員\(i\)に仕事\(j\)が割り当てられれば1、そうでなければ0を取ります。
・パラメータ
\(E = \{1,2,3\}\) : 従業員の集合
\(J = \{1,2,3,4\}\) : 仕事の集合
\(w_{ij}\) : 辺\((i,j)\)の重み
・変数
\(x_{ij} \in \{0,1\} \;\; (\forall i \in E, \forall j \in J)\)
目的関数の設定
目的関数は以下のように設定できます。
\(\sum\limits_{i \in E}\sum\limits_{j \in J} w_{ij}x_{ij}\)
例えば上図の左側の例だと、\(x_{14},x_{21},x_{23},x_{32}\)が1でそれ以外が0となります。したがって\(\sum\limits_{i \in E, j \in J} w_{ij}x_{ij}\)の値は
\(\sum\limits_{i \in E}\sum\limits_{j \in J} w_{ij}x_{ij}\)
\(= w_{11}x_{11} + w_{12}x_{12} + w_{13}x_{13}+w_{14}x_{14}\)
\( + w_{21}x_{21} + w_{22}x_{22} + w_{23}x_{23}+w_{24}x_{24}\)
\( + w_{31}x_{31} + w_{32}x_{32} + w_{33}x_{33}+w_{34}x_{34}\)
\(= (2 \times 0) + (3 \times 0) + (4 \times 0) + (6 \times 1)\)
\(+ (8 \times 1) + (3 \times 0) + (2 \times 1) + (4 \times 0)\)
\(+ (5 \times 0) + (1 \times 1) + (7 \times 0) + (4 \times 0)\)
\(= 6 + 8 + 2 + 1 = 17\)
となります。右側の例に関しても同じように計算できます。
制約条件の設定
最後に制約条件について設定したいと思います。従業員側の制約条件と仕事側の制約条件に分けて説明したいと思います。
従業員側の制約条件
従業員側の制約条件は以下のように設定できます。
\( \sum\limits_{j \in J} x_{ij} \leq 2 \;\;\; (\forall i \in E)\)
例えば従業員1について考えてみましょう。従業員1は仕事1～4のどれかを1つ担当する、2つ担当する、どの仕事も担当しないという選択肢があります。
これを制約条件で言い換えると
\(x_{1j} = 1\)となる\(j \in J\)が0つのパターン
\(x_{1j} = 1\)となる\(j \in J\)が1つのパターン
\(x_{1j} = 1\)となる\(j \in J\)が2つのパターン
の3パターンだったらOKっていう制約条件を作ります。これは
\(x_{11} + x_{12} + x_{13} + x_{14} \leq 2\)
という制約式で表現することができます。\(\sum\)を使ってこの式表すと
\(\sum\limits_{j \in J} x_{1j} \leq 2 \)
となります。この制約式を\(i = 2,3\)に対しても作れば全ての従業員に対して制約条件を作ることができます。
今回は「最大2つまで仕事ができる」という制約なので\(\leq 2\)となっています。一般に「最大\(n\)個まで仕事ができる」という制約は\(\leq n\)とすれば良いです。
仕事側の制約条件
仕事側の制約条件は以下のように設定できます。
\( \sum\limits_{i \in E} x_{ij} = 1 \;\;\; (\forall j \in J)\)
例えば仕事1について考えてみましょう。仕事1は従業員1～3のうちだれか1人に割り当てられます。
これを制約条件で言い換えると
\(x_{11} = 1\)のパターン
\(x_{21} = 1\)のパターン
\(x_{31} = 1\)のパターン
の3つだったらOKっていう制約条件を作ります。これは
\(x_{11} + x_{21} + x_{31} = 1\)
という制約式で表現することができます。\(\sum\)を使ってこの式表すと
\(\sum\limits_{i \in E} x_{i1} = 1 \)
となります。この制約式を\(j = 2,3,4\)に対しても作れば全ての仕事に対して制約条件を作ることができます。
整数計画問題としてまとめる
最後にこれらをまとめて整数計画問題として定式化しましょう。
定式化：
\(\min \;\;\; \sum\limits_{i \in E}\sum\limits_{j \in J} w_{ij}x_{ij}\)
\(\;\text{s.t.}\;\;\;\sum\limits_{j \in J} x_{ij} \leq 2 \;\;\;\; (\forall i \in E)\)
\(\;\;\;\;\;\;\;\;\;\sum\limits_{i \in E} x_{ij}=1 \;\;\;\; (\forall j \in J)\)
\(\;\;\;\;\;\;\;\;\; x_{ij} \in \{0,1\} \;\;(\forall i \in E, \forall j \in J)\)
次回の記事では今回定式化した整数計画問題をpythonで表現して実際に問題を解いてみたいと思います！
次回の記事はこちらから！
おわりに
いかがでしたか。
今回の記事では割当問題について解説していきました。
今後もこのような数理最適化に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
