数理最適化問題をPuLPを使って解いてみた

2020.10.09

こんにちは。イノベーション本部の野村です。

今回は数理最適化問題をPythonのPuLPを使って解いてみたので
ご紹介したいと思います。

数理最適化とは

数理最適化とは、数理的なアプローチで最適な解を得るための課題解決手法になります。
オペレーションズリサーチの１分野として発展し、世の中の幅広い分野の問題解決に役立っています。
・・と言ってもイマイチよく分からないと思うので、具体的に見ていきましょう。

はじめに

突然ですが、みなさんは以下の問題が解けるでしょうか？

倉庫（x, y）から、ある特定の書籍を書店（A, B, C）へトラックで配送します。
配送コストが以下の表であるとき、どの倉庫からどの書店へ何冊ずつ書籍を送れば、配送コストを最も抑えることができるでしょうか。
（ただし、倉庫x からは少なくとも5冊以上、各書店へ送ることとする）

	書店A	書店B	書店C	供給量
倉庫 x	5円	5円	3円	140冊
倉庫 y	10円	7円	8円	100冊
需要量	120冊	40冊	80冊

※配送コストは１冊あたりの配送にかかる単価
※供給量は1日に各倉庫から全書店(A~C)へ配送される書籍の総量
※需要量は1日に各書店へ倉庫(x,y)から配送される書籍の総量

いかがしょう、数ある組合せの中からすぐに最適解を見つけるのはなかなか難しいのではないでしょうか。
そこで標題にあるPythonのモデラーであるPuLPを使ってこの問題を解いてみましょう。

やってみる

まず数理最適化では、数式を利用して対象の問題を数理モデル化（定式化）します。
定式化するにあたり、以下の３つの要素を決めていきます。

変数
目的関数（最大化、もしくは最小化したい関数値）
制約条件

今回の場合、それぞれ以下のようになります。

変数
　倉庫x から書店A,B,Cへ配送する書籍の数量をそれぞれ、xA冊、xB冊、xC冊とする
　倉庫y から書店A,B,Cへ配送する書籍の数量をそれぞれ、yA冊、yB冊、yC冊とする
　※"xA"は(x * A)ではなく、"xA"という一つの変数

目的関数
今回は配送コストを最小にしたいので、
　z = (5円 × xA冊) + (5円 × xB冊) + (3円 × xC冊) + (10円 × yA冊) + (7円 × yB冊) + (8円 × yC冊)
が最小となる各変数の値を求めます。
制約条件
まず、需要量と供給量が制約条件になります。
　xA + xB + xC = 140
　yA + yB + yC = 100
　xA + yA = 120
　xB + yB = 40
　xC + yC = 80
また倉庫x からは最低限5冊以上送られるので、
　xA, xB, xC >= 5
　yA, yB, yC >= 0
となります。

３つの要素が決まったら、PythonのモデラーであるPuLPを使ってモデル化し、
それをソルバーに与えることで解が得られます。
ソルバーには無料のものや有料のものがありますが、PuLPにもCBCという無料のソルバーが同梱されているので
そちらを使って解きます。

環境はGoogle Colabを利用しました。

In [1]:

# PuLPのインストールおよびインポート
  !pip install pulp
  import pulp

In [2]:

# 数理モデルのオブジェクト化
  problem = pulp.LpProblem()

In [3]:

# 変数の定義
  xA = pulp.LpVariable('xA', lowBound = 5)
  xB = pulp.LpVariable('xB', lowBound = 5)
  xC = pulp.LpVariable('xC', lowBound = 5)
  yA = pulp.LpVariable('yA', lowBound = 0)
  yB = pulp.LpVariable('yB', lowBound = 0)
  yC = pulp.LpVariable('yC', lowBound = 0)

In [4]:

# 目的関数の設定
  problem += (5 * xA) + (5 * xB) + (3 * xC) + (10 * yA) + (7 * yB) + (8 * yC)

In [5]:

# 制約条件の追加
  problem += xA + xB + xC == 140
  problem += yA + yB + yC == 100
  problem += xA + yA == 120
  problem += xB + yB == 40
  problem += xC + yC == 80

In [6]:

# 数理モデルの確認
  print(problem)

NoName:
  MINIMIZE
  5*xA + 5*xB + 3*xC + 10*yA + 7*yB + 8*yC + 0
  SUBJECT TO
  _C1: xA + xB + xC = 140

  _C2: yA + yB + yC = 100

  _C3: xA + yA = 120

  _C4: xB + yB = 40

  _C5: xC + yC = 80

  VARIABLES
  5 <= xA Continuous
  5 <= xB Continuous
  5 <= xC Continuous
  yA Continuous
  yB Continuous
  yC Continuous

In [7]:

# 実行
  status = problem.solve()
  print("Status", pulp.LpStatus[status])

Status Optimal

In [8]:

# 結果の表示
  print("xA", xA.value())
  print("xB", xB.value())
  print("xC", xC.value())
  print("yA", yA.value())
  print("yB", yB.value())
  print("yC", yC.value())

  print("z", problem.objective.value())

  xA 55.0
  xB 5.0
  xC 80.0
  yA 65.0
  yB 35.0
  yC 0.0
  z 1435.0

PuLPを使って解いた結果、以下の最適解が得られました。

	書店A	書店B	書店C
倉庫 x	55冊	5冊	80冊
倉庫 y	65冊	35冊	0冊

配送コスト：1,435円

まとめ

今回は、数理最適化問題をPythonのPuLPで解いてみました。
数理最適化という問題解決アプローチを利用することで、世の中の様々な課題を解決することができるようになります。

ただし、現時点で万能というわけではなく、現実に即した複雑な条件を加味したり、問題の規模が大きくなるにつれ
その組合せの数も膨大になり現在の計算機では解けないほどの時間がかかる、いわいるNP困難な問題になることもあります。

その為、よりヒューリスティックな解法や量子コンピュータを用いたアプローチなどが注目されています。

日々精進したいと思います！

TOPに戻る

ENGINEER BLOG

数理最適化問題をPuLPを使って解いてみた

数理最適化とは

はじめに

やってみる

まとめ