オーダーメイドコース
icon
icon

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

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

テックアカデミーマガジンは受講者数No.1のプログラミングスクール「テックアカデミー」が運営。初心者向けにプロが解説した記事を公開中。現役エンジニアの方はこちらをご覧ください。 ※ アンケートモニター提供元:GMOリサーチ株式会社 調査期間:2021年8月12日~8月16日  調査対象:2020年8月以降にプログラミングスクールを受講した18~80歳の男女1,000名  調査手法:インターネット調査

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

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

 

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

 

田島悠介

今回は、Pythonに関する内容だね!

大石ゆかり

どういう内容でしょうか?

田島悠介

最適化問題を解く方法について詳しく説明していくね!

大石ゆかり

お願いします!

 

最適化問題(数理最適化問題)とは

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

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

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

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

 

最適化問題を解く方法

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

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

pip install pulp

 

[PR] 未経験からWebエンジニアを目指す方法とは

実際に書いてみよう

線形計画法を使った例題

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

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

  • ひき肉 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講座を開催しています。

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