Pythonで最適化問題を解く方法を現役エンジニアが解説【初心者向け】

Pythonで最適化問題を解く方法について解説します。

そもそもPythonについてよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。

 

なお本記事は、TechAcademyのオンラインブートキャンプPython講座の内容をもとに紹介しています。

 

 

最適化問題（数理最適化問題）とは

数理最適化問題(Mathematical Optimization Problem)とは、ある制約条件の中で、最もよい解(最大値や最小値)を選択することです。

有名なものが「ナップザック問題」です。これは「積載量の決まったナップザックに、複数種類の荷物(価格と重量が異なる)を入れる時、最も価格の高くなる組み合わせは何か」という問題を解くものです。

「ナップザック問題」の場合はナップザックの積載量という制約条件のもとで、荷物の合計価格という目的関数を最大化することになります。

制約条件や目的関数を線形方程式や線形不等式で表せるので、「ナップザック問題」は線形計画問題というパターンに分類されています。

 

最適化問題を解く方法

最適化問題には様々なバリエーションがあるので、解き方も様々です。ここでは、PuLPというモジュールを使って、線形計画法の問題を解いてみます。

以下のコマンドでPuLPをインストールします。

pip install pulp

 

[PR] Pythonで挫折しない学習方法を動画で公開中

実際に書いてみよう

線形計画法を使った例題

こちらの線形計画法の例題を用います。以下に内容を転記します。

あるレストランで、手持ちの材料からハンバーグとオムレツを作って利益を最大にしたいと考えています。手持ちの材料は以下の通りです。

• ひき肉 3800 [g]
• タマネギ 2100 [g]
• ケチャップ 1200 [g]

商品を作るのに必要な材料の量は以下の通りです。

• ハンバーグ 1 個あたり、ひき肉 60 [g]、タマネギ 20 [g]、ケチャップ 20 [g]
• オムレツ 1 個あたり、ひき肉 40 [g]、タマネギ 30 [g]、ケチャップ 10 [g]

販売価格は以下の通りです。

• ハンバーグ 400 [円/個]
• オムレツ 300 [円/個]

総売上を最大にするには、ハンバーグとオムレツを幾つずつ作れば良いでしょうか。

ソースコード

from pulp.pulp import LpProblem
from pulp.pulp import LpVariable
from pulp.constants import LpMaximize


# 今回の問題では総和を最大化するので LpMaximize を指定する
problem = LpProblem('Restaurant', LpMaximize)

# 使用する変数
hamburg = LpVariable('Hamburg')
omelet = LpVariable('Omelet')

# 目的関数
problem += 400 * hamburg + 300 * omelet

# 制約条件
problem += 60 * hamburg + 40 * omelet <= 3800  # ひき肉の総量は 3800g
problem += 20 * hamburg + 30 * omelet <= 2100  # 玉ねぎの総量は 2100g
problem += 20 * hamburg + 10 * omelet <= 1200  # ケチャップの総量は 1200g

# 解く
problem.solve()

# 結果表示
print('ハンバーグの個数: {hamburg}'.format(hamburg=hamburg.value()))
print('オムレツの個数: {omelet}'.format(omelet=omelet.value()))

 

実行結果

• ハンバーグの個数: 30.0
• オムレツの個数: 50.0

解説

最初にpulpモジュールをインポートしました。売上最大化が目的なので、LpMaximizeを指定しました。

目的関数と制約条件を設定し、線形計画法を解きました。ハンバーグ30個、オムレツ50個という最適解を得られました。

監修してくれたメンター

橋本紘希 システムインテグレータ企業勤務のシステムエンジニア。 開発実績: Javaプログラムを用いた業務用Webアプリケーションや、基幹システム用バッチアプリケーションなどの設計構築試験。

 

 

TechAcademyでは、初心者でもPythonを使った人工知能（AI）や機械学習の基礎を習得できるオンラインブートキャンプPython講座を開催しています。

挫折しない学習方法を知れる説明動画や、現役エンジニアとのビデオ通話とチャットサポート、学習用カリキュラムを体験できる無料体験も実施しているので、ぜひ参加してみてください。