スポンサーリンク

【Python】基本的な線形最適化問題を解いてみる

記事内に広告が含まれています。

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 g2枚
各サンドイッチの売価と原料使用量

レタスサンドを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.9

Pythonで実装します。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で解いてみました。モジュールを利用することですぐに最適化計算を行うことができます。

スポンサーリンク
Python
著者SNS
タイトルとURLをコピーしました