PuLP を使ってみた

遅ればせながら PuLP の使い方について勉強しました。

案件で使えるレベルとは程遠いですが、まぁ経験が大事ということで。

基本

最初に PuLP の使い方を 勉強します。

大まかにいうと モデルを作って解決するだけです。 モデルには目的関数や制約条件関数を細かく設定できます。

LpVariable

• 一意な変数名 と 定義域、変数の型 を指定します

LpProblem

• 解決すべき問題の種類を指定することでモデルを定義します。
• モデルの制約条件がある場合、条件式を加算代入で注ぎ足していきます。 条件式は前述した LpVariable で定義した変数を使って作成します。
• 問題の種類は LpMaximize (最大), LpMinimize (最小) のいずれかです。

最初は 適当な線形の目的関数に 適当な制約条件を追加し、 その前後で最大値、最小値 がどのように変化するか見ていきましょう。

座標プロットのところはちょっとわかりにくかったですかね？

• objective_function は x, y 座標を受け取って係数をかけて返却する単純な 目的関数です
• 格子状の平面が 目的関数です
  • この格子は私が自力で座標を指定して描画してるもので勝手に描画されたりはしません
  • 格子は matplotlib の plot_wireframe という関数で描画できます。
    • 詳しくは [Python] matplotlib の Surface (3D) プロット 座標について
• 最初は プロットが 変数自体の定義域の制限により格子上下端に配置されていて、 制約条件を 与えると動ける範囲で 最大、あるいは最小の点に移動します。
  • 意味のない制約条件を与えると、座標が変わらないこともあります。
    • 最小値はの点は1つカブらせたので2つしかないです

線形計画法

続いて、応用としてつとむさんが作成した以下の問題を解いてみます。斎藤さんだぞ。 (最適化における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をどれだけ作成すればよいか求めよ。

PuLP を使って解いてみます。

とても簡単ですね。

PuLP を使わずに解くとこんな感じ

本当はアニメーションで 目的関数が上下移動するようにしたんですが、 静止画でしか保存できないようなので制約条件下で切片が最大になったときの目的関数を表示しています。

魔方陣

最後に魔方陣を解きます。 魔方陣のルールは Wikipedia を参照。

魔方陣（まほうじん、英：Magic square）とは、n×n 個の正方形の方陣に数字を配置し、縦・横・対角線のいずれの列についても、その列の数字の合計が同じになるもののことである。 特に1から方陣のマスの総数 n2 までの数字を1つずつ過不足なく使ったものを言う。

魔方陣を通して組合せ最適化を学ぶ を参考にしました。 斉藤さんだぞ。(毎回言うやつ)

重要なのは 必要な条件を漏れなく制約条件として追加してあげることです。 一つでも抜けると正しい解は得られません。

今回はセルの抽出を用途として pandas も使っています。

ただの写経では面白くないので、応用として 違う大きさの 魔方陣も作っています。

6x6 の魔方陣は多分処理に数時間かかってます。放置してたので正確な時間はわかりませんが。

斎藤さんによると、条件を満たす全ての組み合わせを確認しているため遅いようです。

DataFrameの値がどのように抽出されるか見たい方はこちら

参考 https://docs.pyq.jp/python/math_opt/pulp.html http://examist.jp/mathematics/math-2/locus-area/senkeikeikakuhou/ https://www.youtube.com/watch?v=aZd_HJxcU_k http://momijiame.tumblr.com/post/109973628251/python-pulp-%E3%81%A7%E9%AD%94%E6%96%B9%E9%99%A3%E3%82%92%E8%A7%A3%E3%81%8F