こんにちは！しゅんです！
割当問題を簡単に説明すると、例えば10人の従業員を10個の仕事に割り当てるときにどのように割り当てたら効率的になるかを考える問題です。
今回の記事では割当問題の中でも
「最も負担がかかる従業員の負担を最小にする割当問題」
を混合整数計画問題として定式化してみたいと思います。それではやっていきましょう！
「従業員に余りが出る場合の割当問題」
「従業員が複数の仕事を担当できる場合の割当問題」
「時間帯によって異なる仕事を行う場合の割当問題」
「1日でやる仕事数に上限がある場合の割当問題」
「最も負担がかかる従業員の負担を最小にする割当問題」
普段は統計検定2級の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
具体例を使って考える
3人の従業員に4個の仕事を割り当てることを考えます。各辺にはコストが設定されていて、このコストが大きい程従業員はその仕事をしたくないと仮定します。
また今回の記事では従業員は何個でも仕事をできると仮定します。そのため以下のような割当もOKとします。
従業員1が4つ全ての仕事を担当しています。非常に不公平感がありますがこれもOKとします。とはいえさすがにこの割当は現実味がないので、今回は目的関数を
「最も負担がかかる従業員の負担を最小にする」
とします。
ここで言う従業員の負担は「その従業員が担当する仕事に対するコストの合計」とします。例えば上の例で言うと各従業員の負担は、従業員1が\(2+3+4+6=15\)で従業員2,3,4が\(0\)です。
このように目的関数を設定することで、不公平感をなるべく無くすことができますね。ということで今回は上記のような問題を混合整数計画問題として定式化してみたいと思います。
仕事は必ず誰かによって担当されるとします。
混合整数計画問題として定式化する
「変数・パラメータ」、「目的関数」、「制約条件」の順番で説明したいと思います。
変数・パラメータの設定
パラメータとして従業員の集合\(E\)、仕事の集合\(J\)、辺\((i,j)\)の重み\(w_{ij}\)を設定します。
また0-1変数として\(x_{ij}\)を設定します。この変数\(x_{ij}\)は従業員\(i\)が仕事\(j\)を担当するなら1、そうでなければ0を取ります。
そして今回はこれらに加えて連続変数\(t\)を用意します。これが何なのかは目的関数の所で説明します。
・パラメータ
\(E = \{1,2,3\}\) : 従業員の集合
\(J_1 = \{1,2,3,4\}\) : 仕事の集合
\(w_{ij}\) : 辺\((i,j)\)の重み
・変数
\(x_{ij} \in \{0,1\} \;\; (\forall i \in E, \forall j \in J)\)
\(t\)
整数変数と連続変数の両方を含む数理計画問題は混合整数計画問題と言います。
目的関数の設定
目的関数を考えるために「その従業員が担当する仕事に対するコストの合計」を数式で表しましょう。従業員\(i\)が担当する仕事に対するコストの合計は以下の式で表せます。
\(\sum\limits_{j \in J} w_{ij}x_{ij}\)
例えば上の例で言うと
\(\sum\limits_{j\in J}w_{1j}x_{1j}=2+6=8\)
\(\sum\limits_{j\in J}w_{2j}x_{2j}=2\)
\(\sum\limits_{j\in J}w_{3j}x_{3j}=1\)
となります。これらの中で値が最も大きいものを取り出したいので
\(\displaystyle\max_{i \in E} \sum\limits_{j \in J} w_{ij}x_{ij}\)
とします。さらにこれを最小にするのが目的なので
\(\min\displaystyle\max_{i \in E} \sum\limits_{j \in J} w_{ij}x_{ij}\)
とします。ということで今回の問題をミニマックス問題として表すことができました。さらにここからもう1ステップ踏み込んでみます。
「変数・パラメータ」の所で設定した連続変数\(t\)を使ってただの最小化問題に変形しましょう。結論以下のように変形できます。
\(\min \;\;t\)
\(\text{s.t} \;\;\;\; \sum\limits_{j \in J}w_{ij}x_{ij} \leq t \;\;\; (\forall i \in E)\)
上の式の意味を説明します。まず制約条件を見てみましょう。この式の左辺は「従業員\(i\)が担当する仕事に対するコストの合計」となっていますね。これが\(t\)以下という式です。
例えば上の例で言うと制約式
\(\sum\limits_{j \in J}w_{ij}x_{ij} \leq t \;\;(\forall i \in E)\)
は以下のようになります。
\(\sum\limits_{j \in J}w_{1j}x_{1j}= 8 \leq t\),
\(\sum\limits_{j \in J}w_{1j}x_{1j} =2 \leq t\),
\(\sum\limits_{j \in J}w_{1j}x_{1j}= 1 \leq t\).
つまり\(t\)は8以上ということを表します。つぎに目的関数を見てみましょう。目的関数は\(t\)で、この\(t\)を最小化することを目的としています。当然\(t=8\)となりますね。
すなわち\(t\)が上の割当において最も負担が大きい従業員の負担を表しています。ということで、この制約の下で最小となる\(t\)を求めることが、最も負担が大きい授業員の負担を最小にする割当を求めることになります。
制約条件の設定
最後に制約条件について設定したいと思います。今回は仕事側の制約条件のみになります。
結論仕事側の制約条件は以下のように設定できます。
\( \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 \;\;\; t\)
\(\;\text{s.t.}\;\;\;\sum\limits_{j \in J} w_{ij}x_{ij} \leq t \;\;\;\; (\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で表現して実際に問題を解いてみたいと思います！
次回の記事はこちらから！
おわりに
いかがでしたか。
今回の記事では割当問題について解説していきました。
今後もこのような数理最適化に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
