Skip to content →

最小費用流で解ける問題

N 個の区間がある。
i 番目の区間 \([L_i, R_i]\) を選ぶにはコスト \(c_i\) が掛かるが、\(L_i\) 番目から \(R_i\) 番目のパンが 1 個ずつ作れる。k 番目のパンは

  • 最初の \(a_1\) 個は \(b_{k,1}\) 円
  • 次の \(a_2\) 個は \(b_{k,2}\) 円
  • 次の \(a_3\) 個は \(b_{k, 3}\) 円
  • 次の …

で売れる。ただし、b は狭義減少列で、負の値があっても良い。得られるお金の最大値を求めよ(ARC137E)

解答略

双対問題

卸業者 A : 辺 \(e\) を関税 \(c_e\) で通れる。各頂点に散らばった A の仲間たちの需給を満たすように輸送したい。各地の下請け業者 B : 頂点 \(i\) で物価 \(\pi_i\) で売買して需給を満たしたい。B は物を瞬間移動できるため、関税が掛からない。B は A が自ら輸送するよりは高くない値段を提示することで、売買を一手に担いたい。

\(\partial x_v = b_v\) のとき、売買に掛かる費用は \(\sum \pi_vb_v\) である。\(\overline b_v \geq \partial x_v \geq \underline b_v \) の場合、\(\min(\pi_v \overline b_v , \pi_v \underline b_v)\) を費用として加える。

辺 \(e = (u, v)\) の流量 \(x_e\) が \(\underline u_e \leq x_e \leq \overline u_e\) を満たすとする。B が頂点 \(u\) で買い頂点 \(v\) で売るための費用は \(\pi_u-\pi_v\) である。従って、A は辺 \(e=(u, v)\) の単位流量当たり、少なくとも \(c_e^\pi = c_e-(\pi_u-\pi_v)\) だけ B より費用が大きい。\(c_e^\pi\) を簡約費用と呼ぶ。従って、\(\min(c_e^\pi \overline u_e, c_e^\pi \underline u_e)\) を目的関数に加える。余分な費用が掛かった際の A の流量が \(-c_e^\pi > 0\) のとき \(\overline u_e\) 、 \(-c_e^\pi < 0\) のとき \(\underline u_e\) であることはのちの相補性条件から出てくる。辺 \(e = (u, v)\) の輸送可能量が \(\infty\) ならば、\(c_{e}^\pi \geq 0\) として、売買に伴う費用を関税以下にする。

B はできるだけ高い額を提示したいので、
$$\mathrm{maximize} \quad \sum \min \left(\pi_v \overline b_v , \pi_v \underline b_v\right)+\sum\min\left(\pi_v \overline b_v , \pi_v \underline b_v\right)$$である。

以上を数式で説明すると次のようになる。
最小費用流を線形計画問題で書くと、\begin{equation*}
\begin{array}{ll@{}ll}
\text{minimize} & cx &\\
\text{subject to}&\overline b \geq Ax \geq \underline b\\
& \overline u \geq x \geq \underline u
\end{array}
\end{equation*}となり、その双対問題は\begin{equation*}
\begin{array}{ll@{}ll}
\text{maxmize} & \overline b \pi^-+\overline b \pi^+ +\overline u \lambda^- +\overline u\lambda^+ &\\
\text{subject to}& A^T (\pi^-+\pi^+)+ \lambda^+ + \lambda^- \leq c\\
& \lambda^- \leq 0 \\
& \lambda^+ \geq 0 \\
& \pi^- \leq 0 \\
& \pi^+ \geq 0 \\
\end{array}
\end{equation*}となる。なお、\(\pi_v = \pi^++\pi^-, \lambda_e=\lambda^++\lambda^-\) という変数変換をしている。この変換で最適解は変化しない。弱双対性は \(c^Tx = x^Tc \geq x^T(A(\pi^-+\pi^+)+ \lambda^- + \lambda^+) \geq \overline b \pi^- + \underline b \pi^+ + \overline u \lambda^- + \underline u \lambda^+\) のように導かれ、等号が成立するには相補性条件

  • \(c_e^\pi = \lambda_e^- + \lambda_e^+ \lor x_e =0\)
  • \(\overline b_v = \partial x_v \lor \pi_v^- = 0\)
  • \(\underline b_v = \partial x_v \lor \pi_v^+ = 0\)
  • \(\lambda_e^- = 0 \lor x_e = \overline u_e\)
  • \(\lambda_e^+ = 0 \lor x_e = \underline u_e\)

の成立が必要十分である。従って、最適解では

  • \(x_e = \underline u_e\) ならば \(0 \leq c_e^\pi\)
  • \(\underline u_e < x_e < \overline u_e\) ならば \(c_e^\pi=0\)
  • \(x_e = \overline u_e\) ならば \(c_e^\pi \leq 0\)
  • \(\overline u_e = \underline u_e\) または \(\overline u_e \lambda_e^- =0 \lor \underline u_e \lambda_e^+ = 0 \)
  • \(\overline b_v = \underline b_v\) または \(\overline b_v \pi_v^- =0 \lor \underline b_v \pi_v^+ = 0 \)

となる。

量を調節できる湧き出し、吸い込みがある場合

辺 \((u, v)\) について \(\overline b_u \geq b_u \geq 0 \) かつ \( 0 \geq b_v \geq \underline b_v \)の場合:

\begin{equation*}
\begin{array}{ll@{}ll}
\text{maxmize} & \overline \pi_u \overline b_u + \underline \pi_t \underline b_t + \overline \lambda_{(u,v)}\overline u_{(u,v)}+\cdots &\\
\text{subject to}& c_e\geq (\overline \pi_u + \underline \pi_u) – (\overline \pi_t + \underline \pi_t) + (\overline \lambda_{(u,v)} + \underline \lambda_{(u,v)})\\
& \vdots \\
& \overline\lambda \leq 0 \\
& \underline\lambda \geq 0 \\
& \overline\pi \leq 0 \\
& \underline\pi \geq 0 \\
\end{array}
\end{equation*}
自由変数 \(\overline \pi_u , \underline \pi_u , \underline \lambda_{(u,v)} \) は \( \overline \pi_u = \underline \pi_u = \underline \lambda_{(u,v)} = 0\) が最適だから

$$c_e \geq \underline \pi_t -\overline \pi_s + \overline \lambda_{(s,t)}$$
となる。

双対の等式が主問題でどうなるか

双対側で=を作りたいときは、主問題でコストの符号を反転した逆辺 rev(e) を作って、e の流量から rev(e) の流量を引いたものが元の需要供給を満たせば良い。つまり、始点側に超頂点を一つ噛ませば良い

例題

\(N\) 個の区間 \([s_i,t_i]\) は次の条件を満たさなければならない。

  • 区間のペアの集合 A が与えられる。任意の \((i, j) \in A\) について、\(i\) 番目の区間と \(j\) 番目の区間が共通部分を持ってはならない。
  • 区間のペアの集合 B が与えられる。任意の \((i, j) \in B\) について、\(i\) 番目の区間と \(j\) 番目の区間は共通部分を持たなければならない。
  • \(s\) は単調増加
  • 区間 \(i\) は長さ \(p_i\) までは単位長さ当たり \(a_i\)、\(p_i\) の超過分は単位長さ当り \(b_i\) の得点が貰える。ただし \(a_i \geq b_i\) である。得点の総和が \(W\) 以上でなければならない。

以上の条件の下で、\(\max(t_i)-\min(s_i)\) を最小化せよ。(HUPC2020H)

\(\min(s_i) = 0\) と仮定して一般性を失わない。\(\max(t_i)-\min(s_i)\) が大きいほど、得点が W 以上という条件を満たしやすいので、二分探索。\(\max(t_i),\min(s_i)\) を固定すると、得点の最大化は最小費用流の双対になる。

二部グラフ \(G =(L, R, E)\) がある。各頂点に非負整数を書き込みたい。\(i \in L\) に書き込む数を \(l_i\)、\(j \in R\) に書き込む数を \(r_j\) と置く。、各辺 \(e=\{i,j\}\) について \(l_i + r_j \geq c_{e}\) を満たさなければならない。この下で \(\sum l_i + \sum r_j\) を最小化せよ。
行列 \(a\) と数列 \(b, c\) が与えられる。\(\sum_{i < j} a_{i,}|x_i-x_j| +\sum b_i|x_i-a_i|\) を最小化する数列\(x\) を求めよ。(ICPC2020NERC O)

\(y_i=x_i-a_i\) と変数変換すると、\(\sum b_i|x_i-a_i|\) も計算できる。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA