Pythonを使って、基本的な線形最適化問題を解いてみます。後半に参考書籍も紹介しています。
線形最適化問題とは
一般的に線形最適化問題は以下の式で表されます。
minimize cTx
subject to Ax ≤ b, x∈ℝ
minimizeの後に記載されているのが最適化対象の目的関数、subject toの後ろに記載されているのが制約条件です。xは変数のベクトル、目的関数の係数がc（ベクトル）、制約式の係数がA（行列）です。bは制約式の定数です。
目的関数が線形関数、制格式が線形式で、制約式で表される制約条件のもとに、目的関数を最小化（または最大化）する変数の値を見つける問題が線形最適化問題です。
例題
今回は以下の問題を解いてみます。
下表の原料でサンドイッチを製造して販売します。パンは何枚でも使えるとします。
| ハム | 1000枚 |
| レタス | 5 kg |
| チーズ | 400枚 |
下表の3種類のサンドイッチを製造する場合、各サンドイッチを何個ずつ製造、販売すれば売上げを最大化できるかという問題を解いてみます。「レタスサンドは人気がなさすぎて作っても売れない」というようなことは考えません。
| サンドイッチ | 売価 | ハム | レタス | チーズ |
| レタスサンド | 150円 | 2枚 | 15 g | |
| ハム2倍サンド | 200円 | 4枚 | 10 g | |
| チーズレタスハムサンド | 300円 | 2枚 | 10 g | 2枚 |
レタスサンドをx1個、ハム2倍サンドをx2個、チーズレタスサンドをx3個製造する場合、目的関数は売価の最大化のため、以下のとおりとなります。
maximize
50 × x1 + 200 × x2 + 300 × x3
制約式は各原料の使用量に上限があるため、以下のとおりとなります。
subject to
2 × x1 + 4 × x2 + 2 × x3 ≤ 1000
15 × x1 + 10 × x2 + 10 × x3 ≤ 5000
2 × x3 ≤ 400
Python実装
動作確認したpython、モジュールのバージョンは以下のとおりです。
python 3.6.0
mypulp 0.0.9Pythonで実装します。mypulpというモジュールを使用するため、インストールしておきます。
pip install mypulp続いて最適化計算を実装します。
from mypulp import *
# モデル生成
model = Model()
# 変数生成
# vtype='C'は連続変数（デフォルトも'C'）
x1 = model.addVar(vtype='C', name='x1_Lettuce')
x2 = model.addVar(vtype='C', name='x2_Double_Ham')
x3 = model.addVar(vtype='C', name='x3_Cheese_Lettuce_Ham')
# 変数宣言後updateする
model.update()
# 目的関数
model.setObjective(150 * x1 + 200 * x2 + 300 * x3, GRB.MAXIMIZE)
# 制約
model.addConstr(2 * x1 + 4 * x2 + 2 * x3 <= 1000)
model.addConstr(15 * x1 + 10 * x2 + 10 * x3 <= 5000)
model.addConstr(2 * x3 <= 400)
# 最適化計算
model.optimize()
# 計算結果を出力
print('Sales', ':', model.ObjVal)
for v in model.getVars():
print(v.VarName, ':', v.X)コードの実行結果は以下のとおりです。
Sales : 97500.0
x1_Lettuce : 150.0
x2_Double_Ham : 75.0
x3_Cheese_Lettuce_Ham : 200.0レタスサンド150個、ハム2倍サンド75個、チーズレタスハムサンド200個を製造することで、売上げが97,500円に最大化されることがわかります。
参考書籍
こちらの本を参考にしました。Pythonでの最適化計算の方法やビジネスへの応用について、詳しく書かれています。
まとめ
基本的な線形最適化問題をPythonで解いてみました。モジュールを利用することですぐに最適化計算を行うことができます。
