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

初心者向けにPythonで最適化問題を解く方法について解説しています。ナップザック問題は、商品の重さが色々ある中で何を入れればナップザックの価値が最大化するのかという問題です。解法には動的計画法など様々なものがあります。

TechAcademyマガジンはオンラインのプログラミングスクールTechAcademy [テックアカデミー]が運営する教育×テクノロジーのWebメディアです。初心者でもすぐ勉強できる記事が2,000以上あります。

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

Pythonについてそもそもよく分からないという方は、Pythonとは何なのか解説した記事をまずご覧ください。

 

なお本記事は、TechAcademyのPythonオンライン講座の内容をもとにしています。

 

田島悠介

今回は、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を使って機械学習の基礎を学ぶPythonオンライン講座を開催しています。

初心者向けの書籍を使って人工知能(AI)や機械学習について学ぶことができます。

現役エンジニアがパーソナルメンターとして受講生に1人ずつつき、マンツーマンのメンタリングで学習をサポートし、最短4週間で習得することが可能です。

また、現役エンジニアから学べる無料のプログラミング体験会も実施しているので、ぜひ参加してみてください。