はむ吉(のんびり)の練習ノート

主にプログラミングについて、思いついたことや、試してみたこと、学んだことを、覚え書きを兼ねてまとめます。

yukicoder No.453 製薬会社:解き方と解答例

現在、yukicoderではAdvent Calendar Contest 2016が開催されています。この記事では、その第4日に出題された、No.453 製薬会社 - yukicoderという問題について、解き方とコードの例を示します。

問題の趣旨

二つの薬品C, Dがあり、これらを組み合わせて二つの製品A, Bを作れる。各製品1 kgを作るのに必要な両薬品の量(kg)は下表の通りである。また、製品A, Bの売価はそれぞれ1000円/kg、2000円/kgである。使用可能な薬品C, Dの量(kg)c, d*1が与えられるので、両製品の売価の合計の最大値を求めよ。

製品A 製品B
薬品C 3/4 2/7
薬品D 1/4 5/7

解き方

使用する薬品C, Dの量をx(\ge 0), y(\ge 0)とすると、最大化すべき売価の合計はv(x, y)=1000x + 2000yと表されます。すると、この問題は次の条件\eqref{1}, \eqref{2}のもとでv(x,y)を最大化するという、一種の線形計画問題になります。
\begin{eqnarray}\frac{3}{4}x + \frac{2}{7}y &\le& c\tag{1}\label{1}\\ \frac{1}{4}x + \frac{5}{7}y &\le& d\tag{2}\label{2}\end{eqnarray}

線形計画法、すなわち線形計画問題を解く方法としてはwikipedia:シンプレックス法などがあります。しかしながら、本問の場合には変数がx,yの二つなので、この方法を使う代わりに、座標平面上において条件に対応する領域Eと直線l:1000x + 2000y = vの位置関係に注意すれば、この問題を解くことができます。具体的には、Eとある点(x_0, y_0)を共有するように直線lを動かしたときの、直線ly切片v/2000の最大値に注目すればよいことになります。

二式\eqref{1}、\eqref{2}の等号をとった式が意味する直線をそれぞれl_1, l_2とすると、3本の直線の位置関係に着目すれば、次図に示す(i)-(iii)の3つの場合があるとわかります。ここで、紫色の斜線で示したのが領域Eであり、緑色の点Pはこの中でv(x,y)を最大たらしめる(x, y)を意味します。

f:id:hamukichi_nbr:20161210145851p:plain

なお、私はGeoGebraで作成したインタラクティブな図(yukicoder No.453の図解 - GeoGebra)で、c, d(x, y)を動かしてこの場合分けを考えました。

結局、求める最大値をVとすると、これは以下のように具体的に書き表されます。あとはこれをコードにすればよいだけです。

  • (i) 5c/2 \le dのときV=v(0, 7c/2)
  • (ii) c/3 \le d \le 5c/2のときV=v(20c/13 - 8d/13, -7c/13 + 21d/13)
  • (iii) (0\le) d\le c/3のときV=v(4d, 0)

コードの例

Haskellによるコードは、たとえば次のようになります。

import Control.Applicative ((<$>))
import Text.Printf (printf)

computeMax :: RealFloat a => a -> a -> a
computeMax c d
    | 3.5 * c <= 1.4 * d = v 0 $ 3.5 * c
    | 1 / 3 * c <= d && 1.4 * d < 3.5 * c = v xp yp
    | otherwise = v (4 * d) 0
    where
        v x y = 1000 * x + 2000 * y
        xp = 20 / 13 * c - 8 / 13 * d
        yp = -7 / 13 * c + 21 / 13 * d

main :: IO ()
main = do
    [c, d] <- fmap read . words <$> getLine :: IO [Double]
    printf "%.12f\n" (computeMax c d)

補足:SciPyを使ったコード

yukicoderでは現在利用できませんが、SciPyのscipy.optimize.linprogを使い、シンプレックス法でこの問題を解くコードは次のようになります。なお、scipy.optimize.linprogでは対象となる関数を「最小化」するので、ここではv(x,y)の最大化を-v(x,y)の最小化と読み替えています。

#!/usr/bin/env python3

import scipy.optimize


c = [-1000, -2000]
A = [[3 / 4, 2 / 7], [1 / 4, 5 / 7]]
xb = (0, None)
yb = (0, None)


def main():
    b = [int(x) for x in input().split()]
    res = scipy.optimize.linprog(c, A_ub=A, b_ub=b, bounds=(xb, yb))
    print("{:.12f}".format(-res.fun))


if __name__ == '__main__':
    main()

感想

レベル★★★ということで少し身構えましたが、落ち着いてよく見ると、以前おそらく数学の問題として解いたことがあるような問題であるとわかり、安心しました。なんだか懐かしい気持ちになりました。シンプレックス法を自分で実装できるようにしたほうがよいのだろうかと、考えています。また、GeoGebraの便利さを再確認しました。

*1:問題文中ではC, Dとなっていますが、この記事ではc, dとします。

広告を非表示にする