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\) で物価 \(p_i\) で売買して需給を満たしたい。B は物を瞬間移動できるため、関税が掛からない。B は A が自ら輸送するよりは高くない値段を提示することで、売買を一手に担いたい。

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

辺 \(e = (u, v)\) の流量 \(x_e\) が \(\underline u_e \leq x_e \leq \overline u_e\) を満たすならば、B に頼むことで余分に掛かった費用 \(\max(-c_e^\pi \overline u_e , -c_e^\pi \underline u_e) =\max(- c_e^\pi, 0) \overline u_e +\min(-c_e^\pi, 0) \underline u_e\) を A には請求しない。余分な費用が掛かった際の 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} \left(\sum (\max(p_v, 0) \overline b_v+\min(p_v, 0) \underline b_v)+\sum(\min(c_e^\pi, 0) \overline u_e +\max(c_e^\pi, 0) \underline u_e)\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 \overline \pi+\underline b \underline \pi+\overline u \overline \lambda +\underline u \underline \lambda &\\
\text{subject to}& A^T (\overline \pi+\underline \pi)+\underline \lambda + \overline \lambda \leq c\\
& \overline\lambda \leq 0 \\
& \underline\lambda \geq 0 \\
& \overline\pi \leq 0 \\
& \underline\pi \geq 0 \\
\end{array}
\end{equation*}となる。弱双対性は
\(c^Tx = x^Tc \geq x^T(A(\overline\pi+\underline\pi)+\overline \lambda + \underline \lambda) \geq \overline b \overline \pi + \underline b \underline \pi + \overline u \overline \lambda + \underline u \underline \lambda\)
のように導かれ、等号が成立するには相補性条件

  • \(c_e^\pi = \overline \lambda_e + \underline \lambda_e \lor x_e =0\)
  • \(\overline b_v = \partial x_v \lor \overline \pi_v = 0\)
  • \(\underline b_v = \partial x_v \lor \underline \pi_v = 0\)
  • \(\overline \lambda_e = 0 \lor x_e = \overline u_e\)
  • \(\underline \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 \overline \lambda_e =0 \lor \underline u_e \underline \lambda_e = 0 \)
  • \(\overline b_v = \underline b_v\) または \(\overline b_v \overline \pi_v =0 \lor \underline b_v \underline \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