数理最適化について

python 数理最適化
  • ある目的関数を最大化または最小化するような解（パラメタ）を求めたい
    • 数理最適化がそんなとき使える
  • 複数の制約が課せられた条件下でのパラメタも求められる
    • 数理最適化すげえ
例題
材料AとBから合成できる化学製品XとYをたくさん作成したい。
Xを1kg作るのに、Aが1kg、Bが3kg必要である。
Yを1kg作るのに、Aが2kg、Bが1kg必要である。
また、XもYも1kg当りの価格は100円である。
材料Aは16kg、Bは18kgしかないときに、XとYの価格の合計が最大になるようにするには、
XとYをどれだけ作成すればよいか求めよ。
  • このときの目的関数は「XとYの価格の合計」
    • XとYの重量をxとyとすると目的関数は「100*(x +y)」
    • これを最大化させるxとyの組を求めたい
    • 制約条件がないならxとｙを大きくすれば目的関数をいくらでも大きくできる
    • つまり実数解なし
  • 今回は材料AとBに対していくつか条件があり、xとyはどんな値でも取れるわけではない
    • 材料AとBの重量をaとbとする
    • 条件１：Xをxだけつくるには、Aがx、Bが3xの材料が必要
    • 条件２：Yをyだけつくるには、Aが2y、Bがyの材料が必要
    • 条件３：Ａは16、Bは18の材料しかない
    • これらを数式にしてまとめると、xとyは以下の2つの制約式を満たさねばならない
      • x + 2y <= 16
      • 3x + y <= 18
  • よって、例題を数式で書き直すと
制約式 x + 2y <= 16と3x + y <= 18を満たすxとyのもとで、
目的関数100*(x +y)を最大化するxとyの組を求めよ
  • 高校数学でやったことあるよね
  • 線形計画法ってやつ
  • pythonだと pulp というソルバーを使って、この問題を解くことができる 
from pulp import *
m = LpProblem(sense=LpMaximize) # 目的関数を最大化するよ～
x = LpVariable('x', lowBound=0) # 求めたいパラメタ１
y = LpVariable('y', lowBound=0) # 求めたいパラメタ２
m += 100 * x + 100 * y # 目的関数
m += x + 2 * y <= 16 # 材料Aの制約条件
m += 3 * x + y <= 18 # 材料Bの制約条件
m.solve() # ソルバーの実行
print(value(x), value(y)) # 4, 6