- なぜハンガリー法で最適解が得られるの？
- 割当問題の相補性条件ってなに？
こんにちは！しゅんです！
今回の記事ではなぜハンガリー法で割当問題の最適解が得られるのかについて考えていきます！
以前ハンガリー法の手順を紹介しましたが、なんでこれで割当問題の最適解が得られるのかはちょっと分からないですよね。
ということでこの記事では具体例を使ってなぜハンガリー法で割当問題の最適解が得られるのかを考えてみたいと思います。
それではやっていきましょう！
ハンガリー法の手順は知っている前提でこの先進めていきます。またこの記事では厳密な証明をするわけではないので注意してください。
普段は統計検定2級の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
相補性条件ってなに？
ハンガリー法について考えるには、相補性条件というものを理解している必要があります。この章では相補性条件について紹介します。
割当問題を線形計画問題として定式化する
まず最初に割当問題を線形計画問題として定式化します。
\(\min \;\;\; \sum\limits_{i \in E, j \in J} c_{ij}x_{ij}\)
\(\;\text{s.t.}\;\;\;\sum\limits_{j \in J} x_{ij}=1 \;\;\;\; (\forall i \in E)\)
\(\;\;\;\;\;\;\;\;\;\sum\limits_{i \in E} x_{ij}=1 \;\;\;\; (\forall j \in J)\)
\(\;\;\;\;\;\;\;\;\; x_{ij} \geq 0 \;\;(\forall i \in E \; \forall j \in J)\)
整数計画問題として定式化する方が直観的ですが、上のように定式化される割当問題は線形緩和しても整数最適解が得られるという性質があるので上記のように線形計画問題として定式化できます。
これ以降この線形計画問題を主問題と呼びます。
割当問題の双対問題
次に先ほど定式化した割当問題の双対問題を考えます。
\(\max \;\;\; \sum\limits_{i \in E}d(i) + \sum\limits_{j \in J} d(j)\)
\(\;\text{s.t.}\;\;\;d(i) + d(j) \leq c_{ij} \;\;\;\; (\forall i \in E, \; \forall j \in J)\)
相補性条件ってなに？
相補性条件：
\(x_{ij} = 0\) または \(d(i) + d(j) = c_{ij} \; (\forall i \in E, \forall j \in J)\) が成立する。
\(d(i) = 0\) または \(\sum\limits_{j \in J}x_{ij} = 1\; (\forall i \in E)\) が成立する。
\(d(j) = 0\) または \(\sum\limits_{i \in E}x_{ij} = 1\; (\forall j \in J)\) が成立する。
割当問題において、上記の条件を相補性条件と言います。この相補性条件の何がすごいかと言うと、\(x,d\)がそれぞれ主問題と双対問題の実行可能解のとき、\(x,d\)がこの相補性条件を満たせば\(x,d\)は必ず最適解になるんです。
もうすこしちゃんと記述すると、「\(x,d\)がそれぞれ主問題と双対問題の実行可能解のとき、\(x,d\)がともに最適解であるための必要十分条件は\(x,d\)が上の相補性条件を満たすことである」となります。このことを相補性定理と言います。
また相補性定理は一般にある線形計画問題とその双対問題の間で成り立つ定理なので、割当問題に限った話ではないです。
ハンガリー法はこの相補性条件が成立している状態を保てるように \(x,d\) を更新していくという方法になります。
今回は \(x\) が主問題の実行可能解であれば \(\sum\limits_{j \in J}x_{ij} = 1\;\;\; (\forall i \in E)\) と \(\sum\limits_{i \in E}x_{ij} = 1\;\;\; (\forall j \in J)\) は常に成立するので、相補性条件は
\(x_{ij} = 0\) または \(d(i) + d(j) = c_{ij} \; (\forall i \in E, \forall j \in J)\) が成立する。
を考えるだけでOKです。
最適解かどうか調べるために確認すること
以上のことを踏まえると、ある解 \(x,d\) が割当問題の最適解かどうかを調べるために確かめることは以下のようになります。
最適解かどうか調べるために確かめること：
1. \(x\) が主問題の実行可能解である。
2. \(d\) が双対問題の実行可能解である。
3. \(x_{ij} = 0\) または \(d(i) + d(j) = c_{ij} \; (\forall i \in E, \forall j \in J)\) が成立する。
具体例1を使って考える
まず最初に上の具体例1を使って考えていきます。この表は \(E = \{1,2,3,4\},J = \{A,B,C,D\}\) の割当問題を表しています。
\((i,j)\) 成分は \(i \in E\) を \(j \in J\) に割り当てるときのコスト \(c_{ij}\) を表しています。例えば \(c_{1A}=1,c_{2C}=2,c_{3C}=6\) です。
一番左と一番上に \(d(i),d(j)\) を示しておきます。最初は \(d(i) = d(j)=0 \; (\forall i \in E, j \in J)\) とします。
STEP 1
STEP 1でやることは
「各行に対してその行の成分の最小値を引く」
です。例えば1行目の成分の最小値は\(c_{1A}=1\)なので1行目の各成分から1を引き算します。
これを各行に対して実行すると上のような表が得られると思います。この際引き算した値、つまり\(i\)行目の最小値を\(d(i)\)とします。
1行目の最小値は1なので\(d(1)=1\)、2行目の最小値は2なので\(d(2)=2\)、3行目の最小値は3なので\(d(3)=3\)、4行目の最小値は1なので\(d(4)=1\)となります。
STEP 2
STEP 1でやることは
「各列に対してその列の成分の最小値を引く」
です。今回の場合、A,B,C列目の最小値は全て0なので何も引き算しません。D列目の最小値は1なので、D列目の各成分から1を引き算します。
さっきと同じように引いた値、つまり\(j\)列目の最小値を\(d(j)\)とします。今回の例だと\(d(A)=d(B)=d(C)=0, d(D)=1\)とします。
各成分の値がどうやって表されるかを考える
ここで重要なのは各成分がどうやって表されるかということです。
例えば1行A列目の成分について考えてみます。1行A列目の成分は元々\(c_{1A}\)でしたが、そこから\(d(1),d(A)\)を引きました。そのため1行A列目の成分は
\(c_{1A}-d(1)-d(A)\)
と表すことができます。
例えば2行D列目について考えてみましょう。2行D列目の成分は元々\(c_{2D}\)でしたが、そこから\(d(2),d(D)\)を引きました。そのため2行D列目の成分は
\(c_{2D}-d(2)-d(D)\)
と表すことができます。より一般に\((i,j)\)成分は
\(c_{ij}-d(i)-d(j)\)
と表すことができます。さらにこの行列の各成分は必ず0以上なので
\(c_{ij}-d(i)-d(j) \geq 0\)
が成立します。これを変形すると
\(d(i)+d(j) \leq c_{ij}\)
となります。これって双対問題の制約条件と同じ形をしていますね。つまりこれまでの操作で得られた\(d(i),d(j)\)は双対問題の実行可能解になっています。
STEP 3
STEP 3でやることは
「値が0の成分だけを選んで完全マッチングが得られるか調べる」
です。今回の場合例えば
1-A
2-C
3-B
4-D
を選べば完全マッチングが得られます。これを数式で表すと
\(x_{1A}=x_{2C}=x_{3B}=x_{4D}=1\)
となり、主問題の制約条件を満たしています。つまり\(x\)は主問題の実行可能解となっています。
最適解が得られているか調べる
ハンガリー法によるとこれが最適解になるということなので、本当にそうか確かめてみましょう。
最適解かどうか調べるために確かめること：
1. \(x\)が主問題の実行可能解である。
2. \(d\)が双対問題の実行可能解である。
3. \(x_{ij} = 0\) または \(d(i) + d(j) = c_{ij} \; (\forall i \in E, \forall j \in J)\)が成立する。
これまでの議論から1,2は明らかです。よって3が成り立っているかを確かめてみましょう。
ハンガリー法では完全マッチングとして採用されなかったペアに対応する変数が\(x_{ij}=0\)となるので、そのような\(i, j\)に関しては相補性条件が成立しています。そのため完全マッチングとして採用されたペアに対応する変数について考えていきましょう。
例えば\(x_{1A}=1 \ne 0\)ですが、
\(d(1)+d(A)=1+0=1=c_{1A}\)
が成立しており、相補性条件を満たします。これは偶然じゃなくて、\(x_{2C},x_{3B},x_{4D}\)に関してもそれぞれ
\(d(2)+d(C)=2+0=2=c_{2C}\)
\(d(3)+d(B)=3+0=3=c_{3B}\)
\(d(4)+d(D)=1+1=2=c_{4D}\)
が成立しており、相補性条件を満たします。
ちょっと考えてみると、\(x_{ij}=1\)とする変数は\(i\)行\(j\)列目の成分が0じゃないといけないですよね。\(i\)行\(j\)列目の成分は\(c_{ij}-d(i)+d(j)\)で表せるので
\(c_{ij}-d(i)+d(j)=0\)
が成立しているはずです。従って相補性条件を必ず満たすことが分かります。
以上をまとめると
\((i,j)\)が完全マッチングとして選ばれている
→ \(d_{i}+d_{j}=c_{ij}\)が成立する
\((i,j)\)が完全マッチングとして選ばれていない
→ \(x_{ij}=0\)が成立する
となり\(x,d\)は相補性条件を満たします。従って相補性定理より\(x,d\)は最適解であることが保証されます。
具体例2を使って考える
次に上の具体例2を使って考えていきます。この表も\(E = \{1,2,3,4\},J = \{A,B,C,D\}\)の割当問題を表しています。
\((i,j)\)成分は\(i \in E\)を\(j \in J\)に割り当てるときのコスト\(c_{ij}\)を表しています。例えば\(c_{1A}=1,c_{2C}=2,c_{3C}=6\)です。
一番左と一番上に\(d(i),d(j)\)を示しておきます。最初は\(d(i) = d(j)=0 \; (\forall i \in E, j \in J)\)とします。
STEP 1
STEP 1でやることは
「各行に対してその行の成分の最小値を引く」
です。例えば1行目の成分の最小値は\(c_{1A}=1\)なので1行目の各成分から1を引き算します。
これを各行に対して実行すると上のような表が得られると思います。この際引き算した値、つまり\(i\)行目の最小値を\(d(i)\)とします。
1行目の最小値は1なので\(d(1)=1\)、2行目の最小値は2なので\(d(2)=2\)、3行目の最小値は2なので\(d(3)=2\)、4行目の最小値は1なので\(d(4)=1\)となります。
STEP 2
STEP 2でやることは
「各列に対してその列の成分の最小値を引く」
です。今回の場合、A,C列目の最小値は全て0なので何も引き算しません。B列目の最小値は2なのでB列目の各成分から2を引き算します。D列目の最小値は1なのでD列目の各成分から1を引き算します。
さっきと同じように引いた値、つまり\(j\)列目の最小値を\(d(j)\)とします。今回の例だと\(d(A)=d(C)=0, d(B)=2,d(D)=1\)とします。
各成分の値がどうやって表されるかを考える
ここで重要なのは各成分がどうやって表されるかということです。
例えば1行A列目の成分について考えてみます。1行A列目の成分は元々\(c_{1A}\)でしたが、そこから\(d(1),d(A)\)を引きました。そのため1行A列目の成分は
\(c_{1A}-d(1)-d(A)\)
と表すことができます。
例えば3行C列目について考えてみましょう。3行C列目の成分は元々\(c_{3C}\)でしたが、そこから\(d(3),d(C)\)を引きました。そのため2行D列目の成分は
\(c_{3C}-d(2)-d(D)\)
と表すことができます。より一般に\((i,j)\)成分は
\(c_{ij}-d(i)-d(j)\)
と表すことができます。さらにこの行列の各成分は必ず0以上なので
\(c_{ij}-d(i)-d(j) \geq 0\)
が成立します。これを変形すると
\(d(i)+d(j) \leq c_{ij}\)
となります。これって双対問題の制約条件と同じ形をしていますね。つまりこれまでの操作で得られた\(d(i),d(j)\)は双対問題の実行可能解になっています。
STEP 3
STEP 3でやることは
「値が0の成分だけを選んで完全マッチングが得られるか調べる」
です。今回の場合は完全マッチングが得られないので次の操作に進みます。
STEP 4
STEP 4でやることは
「成分が0のマスを全てカバーするように縦線・横線を引く」
です。完全マッチングが得られない場合は0のマスを全てカバーするように縦線・横線を引きます。このとき引く線の本数はなるべく少なくします。今回の場合上図のように3つの線で全ての0をカバーすることができます。
STEP 5
STEP５でやることは
「各成分の値を更新する」
です。更新の仕方は
「線でカバーされていない成分からそれら成分の最小値を引く。」
「またその最小値を、縦線・横線両方でカバーされている成分に足す。」
です。線でカバーされていない成分は\((2,A),(2,B),(2,D),(4,A),(4,B),(4,D)\)の6つで、これらの成分の最小値は1です。（上図のオレンジ色で書かれた成分です）
また縦線・横線両方でカバーされている成分は\((1,C),(3,C)\)です。
\((2,A),(2,B),(2,D),(4,A),(4,B),(4,D)\)成分から1を引いて、\((1,C),(3,C)\)成分に1を足すと上図のようになります。
またこれに伴い\(d\)の値も更新しましょう。\(d(2),d(4)\)をそれぞれ1だけ大きくし、\(d(C)\)を1だけ小さくします。
なぜこのように更新するかというと、\((i,j)\)成分が\(c_{ij}-d(i)-d(j)\)で表されるという状態を保つためです。
各成分の値がどうやって表されるかを考える
それでは実際に各成分の値がどのように表されるかを考えていきましょう。例えば2行A列目の成分は0ですが、
\(c_{2A}-d_{2}-d_{A}=3-3-0=0\)
となり\(c_{2A}-d_{2}-d_{A}\)で表せていますね。他にも例えば2行C列目の成分は0ですが、
\(c_{2C}-d_{2}-d_{C}=2-3-(-1)=0\)
となり\(c_{2A}-d_{2}-d_{A}\)で表せていますね。他にも例えば3行C列目の成分は5ですが、
\(c_{3C}-d_{3}-d_{C}=6-2-(-1)=5\)
となり\(c_{3C}-d_{3}-d_{C}\)で表せていますね。より一般に、\((i,j)\)成分の値は
\(c_{ij}-d_{i}-d_{j}\)
と表せます。この操作で得られた表の各成分は0以上なので、操作後も\((i,j)\)成分は
\(c_{ij}-d(i)-d(j) \geq 0\)
を満たします。これはすなわち
「STEP 5の操作後も\(d\)は双対問題の実行可能解である」
ということを表しています。
STEP 6
値の更新ができたので再び値が0の成分だけを選んで完全マッチングが得られるか調べていきます。
今回の場合例えば
1-D
2-C
3-B
4-A
を選べば完全マッチングが得られます。これを数式で表すと
\(x_{1D}=x_{2C}=x_{3B}=x_{4A}=1\)
となり、主問題の制約条件を満たしています。つまり\(x\)は主問題の実行可能解となっています。
最適解が得られているか調べる
ハンガリー法によるとこれが最適解になるということなので、本当にそうか確かめてみましょう。
最適解かどうか調べるために確かめること：
1. \(x\)が主問題の実行可能解である。
2. \(d\)が双対問題の実行可能解である。
3. \(x_{ij} = 0\) または \(d(i) + d(j) = c_{ij} \; (\forall i \in E, \forall j \in J)\)が成立する。
これまでの議論より1,2は明らかなので、3が成り立っているかを確かめてみましょう。
ハンガリー法では完全マッチングとして採用されなかったペアに対応する変数が\(x_{ij}=0\)となるので、そのような\(i,j\)に関しては相補性条件が成立しています。そのため完全マッチングとして採用したペアに対応する変数について考えていきましょう。
例えば\(x_{1D}=1 \ne 0\)ですが、
\(d(1)+d(D)=1+1=2=c_{1D}\)
が成立しており、相補性条件を満たします。これは偶然じゃなくて、\(x_{2C},x_{3B},x_{4A}\)に関してもそれぞれ
\(d(2)+d(C)=3-1=2=c_{2C}\)
\(d(3)+d(B)=2+2=4=c_{3B}\)
\(d(4)+d(D)=2+0=2=c_{4A}\)
が成立しており、相補性条件を満たします。
ちょっと考えてみると、\(x_{ij}=1\)とする変数は\(i\)行\(j\)列目の成分が0じゃないといけないですよね。\(i\)行\(j\)列目の成分は\(c_{ij}-d(i)+d(j)\)で表せるので
\(c_{ij}-d(i)+d(j)=0\)
が成立しているはずなので相補性条件を必ず満たすことが分かります。
以上をまとめると
\((i,j)\)が完全マッチングとして選ばれている
→ \(d_{i}+d_{j}=c_{ij}\)が成立する
\((i,j)\)が完全マッチングとして選ばれていない
→ \(x_{ij}=0\)が成立する
となり\(x,d\)は相補性条件を満たします。従って相補性定理より\(x,d\)は最適解であることが保証されます。
ハンガリー法は主双対法の1つ
ハンガリー法は実行可能解ではない\(x\)と実行可能解の\(d\)を初期解として、そこから\(d\)が実行可能解であることを保ちつつ、かつ\(x,d\)が相補性条件を満たしながら解を更新して実行可能解\(x\)を見つけていくというアルゴリズムです。
このような考えに基づくアルゴリズムを主双対法(primal dual method)と言います。
おわりに
いかがでしたか。
今回の記事ではハンガリー法について解説していきました。
今後もこのような組合せ最適化に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
