この問題は、問題を線形計画問題 (LP) としてみて、その双対をとることで解きやすくなるというテクニックの練習問題です。

---

線形計画問題としての定式化

\(i\) 番目の左側頂点に何個カメラを置いたかを \(l_i\)
\(i\) 番目の右側頂点に何個カメラを置いたかを \(r_i\)
とおきます。すると、この問題は、

\(l_i+r_j \ge C_{i,j}\)

\(l_i \ge 0\)

\(r_i \ge 0\)

\(l_i,r_i \in \mathbb{Z}\)

という条件の下で

\(\sum_i A_il_i + \sum_i B_ir_i\)

の値を最小化せよという問題となります。

ここで、この場合においては、整数性の条件 (\(l_i,r_i \in \mathbb{Z}\)) を無視して実数の範囲で最適化しても答えが変わらないことが示せます。 (証明は後述)

したがって、以下のように書けることが分かりました。

\(\mathrm{minimize} \sum_i A_il_i + \sum_i B_ir_i\)
\(\mathrm{subject\ to}\) \(l_i+r_j \ge C_{i,j}\), \(l_i \ge 0\), \(r_i \ge 0\) (ただし各変数は実数の範囲を動くものとする)

このように、いくつかの実数変数に対し、一次不等式の形をした制約が与えられ、別の一次式を最適化する問題を線形計画問題といいます。

---

双対を取る

目的関数 (\(\sum_i A_il_i + \sum_i B_ir_i\)) の自明な下界について考えてみましょう。 まず、

\(l_i+r_j \ge C_{i,j}\)

であることが分かっているので、それに適当な非負実数係数 \(k_{i,j}\) をかけた

\(k_{i,j}(l_i+r_j) \ge k_{i,j} C_{i,j}\)

が成り立つことが分かります。一般に、任意の非負実数係数 \(k_{i,j}, p_i, q_i\) に対し、制約の線形結合

\(\sum_{i,j} k_{i,j} (l_i+r_j) + \sum_i p_i l_i + \sum_i q_i r_i \ge \sum_{i,j} k_{i,j} C_{i,j}\)

が成り立つことが分かります。とくに、上の式の左辺が目的関数と一致するとき、上の式の右辺が目的関数の自明な下界を与えることが分かります。

双対定理とは、このようにして得られる自明な下界のうち最もよいものが実際に最適解になっているというものです。つまり、

\(\sum_{i,j} k_{i,j} (l_i+r_j) + \sum_i p_i l_i + \sum_i q_i r_i = \sum_i A_il_i + \sum_i B_ir_i\)

という条件の下での

\(\sum_{i,j} k_{i,j} C_{i,j}\)

の最大値が答えとなります。これは、以下と同値となります。

\(\mathrm{maximize} \sum_{i,j} C_{i,j}k_{i,j}\)
\(\mathrm{subject\ to}\)
\(\sum_i k_{1,i} \le A_1\) , \(\sum_i k_{2,i} \le A_2, \dots, \sum_i k_{L,i} \le A_L\)
\(\sum_i k_{i,1} \le B_1\) , \(\sum_i k_{i,2} \le B_2, \dots, \sum_i k_{i,R} \le B_R\)
全ての \(k_{i,j}\) について、 \(k_{i,j} \ge 0\)

双対問題を解く

この双対問題は最小費用流で解ける形をしています。

全ての \(1 \le i \le L\) について頂点 \(U_i\) 、 \(1 \le i \le R\) について頂点 \(V_i\) を用意し、これに加え特別な頂点 \(S,T\) を用意した上で、以下の辺を張る。

• \(S\) から \(U_i\) に、流量上限 \(A_i\) の辺を張る。
• \(U_i\) から \(V_j\) に、流量上限の無い辺を \(1\) 本張る。なお、この辺にフローが流れている時、流量 \(1\) ごとに \(C_{i,j}\) の賞金を貰うことが出来る。
• \(V_i\) から \(T\) に、流量上限 \(B_i\) の辺を張る。

\(S\) から \(T\) にフローを好きな量流すことができるとき、貰える賞金の最大値を求めよ。

この問題は、ACLにも実装がある、最小費用流を用いて解くことが出来ます。

整数性の証明

ある最適解において、整数でない変数があったとします。 このとき、十分絶対値の小さな変数 \(\delta\) に対し、左側の整数でない変数をすべて \(+\delta\) し、 右側の整数でない変数をすべて \(-\delta\) したものは制約を満たし、また目的関数の変化は \(\delta\) の一次式となります。 この一次式が減らない方向に \(\delta\) を次にいずれかの変数が整数にぶつかるまでずらしていくことで、より整数変数の多い最適解が得られます。 この操作を繰り返すことで全てが整数の最適解があることが示せます。

二部グラフの最小頂点被覆と最大独立集合

この問題は、二部グラフの最小頂点被覆を一般化したものとなっています。 二部グラフの最小頂点被覆は最大マッチングと等しいという定理はコンテストで時々出題されます。(証明はこの問題の簡単な場合となります。) また、一般にグラフにおいて頂点集合が独立集合であることとその補集合が頂点被覆であることが同値なので、 二部グラフの最大独立集合は (頂点数) - (最大マッチング) であるという定理も時々出題されます。

関連記事

双対性についてより深く学びたい方は こちらのスライド をお読みください。