双対を取ります。

双対についてはwata氏のスライドが非常に参考になります。

まず、元の問題は以下と同値です。

maximize

• \((\sum C_{i}x_{i})\)

s.t

• \(\sum A_{i}x_{i}\leq 1\)

• \(\sum B_{i}x_{i}\leq 1\)

• \(\forall i\;0\leq x_{i}\)

これの双対を取ると以下のようになります。

minimize

• \(y+z\)

s.t

• \(\forall i \;C_{i}\leq yA_{i}+zB_{i}\)

• \(0\leq y,z\)

この問題はシンプルに解くことができて、例えば \(y+z\) の値で二分探索することで解けます。

具体的には \(y+z=X\) とすると、 \(y\) を消すことができて、 以下の条件を全て満たす \(z\) が存在すれば答えは \(X\) 以下、そうでないなら 答えは \(X\) より大きいという判定をすればよいです。

• \(\forall i\;C_{i}-A_{i}X\leq (B_{i}-A_{i})z\)
• \(0\leq z\leq X\)

実装例 c++