整数計画法による最適な製品生産数の算出

作成: 日大生産工 MA 大前

  • 限られた条件で、何かを最大化したいという欲求は、いろいろな企業に存在します。
  • これを数学的に解決しようとする分野の代表として、オペレーションズリサーチがあります。
  • ここでは、pythonによりオペレーションズリサーチを少しだけ体験し、卒業研究として仕上げることを目標とします。

これは、大前研究室の卒業研究テーマの学習資料として作成されたものです。他のゼミ生がこのページを参考にして卒業研究を行う場合は、必ず事前に相談してください。異なる研究室なのに、同じテーマが卒業研究概要集に並んでいると、問題になるかもしれません。

In [1]:
# google collabを利用している人は、はじめに以下を実行してください。
!pip install pulp

1. 考える問題

以下の問題を考えてみましょう。

  • 製品Xは1つあたり100円で売れる。
  • 製品Yは1つあたり200円で売れる。
  • 素材Aは、製品X1つにつき1個、製品Y1つにつき6個必要である。
  • 素材Bは、製品X1つにつき5個、製品Y1つにつき4個必要である。
  • 素材Aは100個、素材Bは200個しかない

このような状況のとき、製品XとYをいくつ作ると、売り上げが最大となるか？ ただし、作った製品はすべて売れるものとします。

状況がややこしいので、

  • 製品Xを10個、製品Yを20個作る

というパターンを調べてみます。

In [2]:
x = 10 # 製品Xの作成数
y = 20 # 製品Yの作成数
N_A = 1*x + 6*y # 素材Aの使用数
N_B = 5*x + 4*y # 素材Bの使用数
TotalValue = 100*x + 200*y # 売上（製品Xが1つにつき100円、製品Yが1つにつき200円）

print("製品Xの作成数: ", x, " 個")
print("製品Yの作成数: ", y, " 個")
print("素材Aの使用数: ", N_A, " 個（上限100）")
print("素材Bの使用数: ", N_B, " 個（上限200）")
print("売り上げ: ", TotalValue, " 円（← 素材Aの使用数がオーバーしているので、実現不可能）")

製品Xの作成数:  10  個
製品Yの作成数:  20  個
素材Aの使用数:  130  個（上限100）
素材Bの使用数:  130  個（上限200）
売り上げ:  5000  円（← 素材Aの使用数がオーバーしているので、実現不可能）

となりました。5000円の売り上げとなるようですが、素材Aを130個使っており、上限を超えています。つまり、「製品Xを10個、製品Yを20個作る」実現不可能であることがわかります。

これを踏まえて、改善を考えてみます。素材Aがオーバーするため、素材Aの使用数を下げなければなりません。素材Aは、製品Yを作成するときに6個も消費してしまうようです。そのため、製品Yの作成数を7個だけ減らしてみましょう。具体的には、

  • 製品Xを10個、製品Yを13個作る

としてみます。

In [3]:
x = 10 # 製品Xの作成数
y = 13 # 製品Yの作成数
N_A = 1*x + 6*y # 素材Aの使用数
N_B = 5*x + 4*y # 素材Bの使用数
TotalValue = 100*x + 200*y # 売上

print("製品Xの作成数: ", x, " 個")
print("製品Yの作成数: ", y, " 個")
print("素材Aの使用数: ", N_A, " 個（上限100）")
print("素材Bの使用数: ", N_B, " 個（上限200）")
print("売り上げ: ", TotalValue, " 円")

製品Xの作成数:  10  個
製品Yの作成数:  13  個
素材Aの使用数:  88  個（上限100）
素材Bの使用数:  102  個（上限200）
売り上げ:  3600  円

素材Aの使用数が、無事に100個未満になりました。でも、素材Aはまだちょっと余裕があります。製品Yを減らしすぎたのかもしれません。もうちょっと作れば、3600円よりも売上が上がりそうです。そのため、製品Yを少し増やし、

  • 製品Xを10個、製品Yを15個作る

にしてみましょう。

In [4]:
x = 10 # 製品Xの作成数
y = 15 # 製品Yの作成数
N_A = 1*x + 6*y # 素材Aの使用数
N_B = 5*x + 4*y # 素材Bの使用数
TotalValue = 100*x + 200*y # 売上

print("製品Xの作成数: ", x, " 個")
print("製品Yの作成数: ", y, " 個")
print("素材Aの使用数: ", N_A, " 個（上限100）")
print("素材Bの使用数: ", N_B, " 個（上限200）")
print("売り上げ: ", TotalValue, " 円")

製品Xの作成数:  10  個
製品Yの作成数:  15  個
素材Aの使用数:  100  個（上限100）
素材Bの使用数:  110  個（上限200）
売り上げ:  4000  円

素材Aの使用数がぴったり100になりました。売上も4000円までアップしました。前よりは良さそうです。 しかし、素材Bがだいぶ余っています。製品Xが10個、製品Yが15個というのは、本当に最適でしょうか？

だんだんわからなくなってきました。ここらでわかるように、このように数字を当てはめて考えていくということは、ちょっと非効率な気がします。

2. 整数計画問題

そこで登場するのが、整数計画法という手法です。この方法は少しややこしいので解説は省略しますが、

  • 最大化（最小化）したい指標（目的関数）
  • 目的関数を構成する変数は、整数
  • 守らなければならない制約（制約条件）

を設定することで、最適な答えを教えてくれる手法となります。問題そのものは整数計画問題、解き方を整数計画法と呼びます。

これを考えるため、はじめに、以下のように変数を定義します。

  • $x$: 製品Xの作成数
  • $y$: 製品Yの作成数

この際、今回の事例でいえば、目的関数と制約条件は以下のように定義できます。

  • Maximize $100x + 200y$ ← 売上を最大化したい
  • 制約1: $x + 6y \le 100$（素材Aの使用数は100個以下でなければならない）
  • 制約2: $5x + 4y \le 200$（素材Bの使用数は100個以下でなければならない）
  • 制約3: $x, y$は非負整数（製品XとYの作成数は0, 1, 2, 3など）

この条件で整数計画問題を解くコードは、下記となります。

In [5]:
from pulp import LpProblem, LpMaximize, LpVariable, value
Prb = LpProblem(sense=LpMaximize) # 最大化を考えたい（LpMaximize）
X = LpVariable('X', cat="Integer", lowBound=0) # Xは0以上の整数（制約3）
Y = LpVariable('Y', cat="Integer", lowBound=0) # Yは0以上の整数（制約3）
Prb += 100*X + 200*Y # 目的関数（最大化したい指標）
Prb += 1*X +  6*Y <= 100 # 素材Aの上限（制約1）
Prb += 5*X +  4*Y <= 200 # 素材Bの上限（制約2）
Prb.solve()
print("製品Xの作成数: ", value(X), "個")
print("製品Yの作成数: ", value(Y), "個")

製品Xの作成数:  31.0 個
製品Yの作成数:  11.0 個

製品Xを31個、製品Yを11個作ると、制約を守りながら、売上が最大化されるという結果となりました。これだけの数を作成して、素材の使用数を違反しないのか、チェックしてみます。

In [6]:
x = 31 # 製品Xの作成数
y = 11 # 製品Yの作成数
N_A = 1*x + 6*y # 素材Aの使用数
N_B = 5*x + 4*y # 素材Bの使用数
TotalValue = 100*x + 200*y # 売上

print("製品Xの作成数: ", x, " 個")
print("製品Yの作成数: ", y, " 個")
print("素材Aの使用数: ", N_A, " 個（上限100）")
print("素材Bの使用数: ", N_B, " 個（上限200）")
print("売り上げ: ", TotalValue, " 円")

製品Xの作成数:  31  個
製品Yの作成数:  11  個
素材Aの使用数:  97  個（上限100）
素材Bの使用数:  199  個（上限200）
売り上げ:  5300  円

素材AもBも、ギリギリまで使用できていることがわかります。また、売上も、今までで一番大きいことがわかりました（この結果のみで売上が最大であると主張できる証拠はありませんが、実際には5300円が最大となります）。

3. 課題

(1) 今回は、製品X、製品Y、素材A、素材Bを扱いました。これを、あなたが思う実際の製品と素材にしてください。

例えば

  • 製品X チーズバーガー
  • 製品Y ビッグマック

として、

  • 素材A パン
  • 素材B チーズ
  • 素材C ハンバーグ
  • 以下色々続く...

などです。学習が目的なので、無理矢理になっても構いません。製品と素材の種類は2より大きくてもokです。

(2) 上記について、素材の上限と、製品を作るために必要な素材数を考えてください。

(3) 上記について、製品の販売価格を決めてください。

(4) 目的関数と制約を、数式で表現してください。

(5) 上記の条件で、最適な製造数を、プログラムにより求めてください。

4. 卒業研究概要集への手引き

  • このテーマを卒業研究のテーマにしたい場合は、ここの対応をお願いします（必ず事前に相談してください）。
  • 以下、すべて含めて、A4用紙2枚にまとめてください。
  • 厳密に守る必要はありませんが、文章量の比率を目安にしてください（15%とは、A4用紙2枚分の15%という意味）。

1章 はじめに:（文章量の比率: 15%）

  • オペレーションズリサーチ、整数計画問題とは何か、それを用いたどのような先行研究があるか、まとめてください。
  • 先行研究は、簡単にで良いので、2, 3個紹介してください。

2章 整数計画問題:（文章量の比率: 30%）

  • 目的関数と制約条件とは、なんなのか説明してください。

3章 実験:（文章量の比率: 40%）

3.1節 概要:

  • 上の課題で述べた、(1) 〜 (4)を説明してください。
  • 題材は、飲食系でも、ファッションでも、なんでもいいです。あなたの好きなもので。

3.2節 結果と考察:

  • 最適な製造数として、いくつが採択されたのか記載してください。
  • 売上はいくつになったのか、記載してください。
  • 素材の使用数と制約条件を比較して、制約が違反されていないかどうか、説明してください。

4章 おわりに:（文章量の比率: 15%）

  • 今回の分析に対する感想などを記載してください。
  • 例えば、製品の製造数を手で決めることと、整数計画法を使用して決めること、どちらが良さそうか、記載してください。

参考文献:

参考にした資料を、2〜3件記載してください。以下、書き方の例です。

  • [1] 大前ほか, XXXに関する分析, XXX学会論文誌, 2020.
  • [2] XXXに関する情報, http：//xxx.ddd.ttt.com, 2020年4月20日閲覧

本文中で引用する場合は「大前らはXXXを実施している [1]。また、〜」のように、どこで引用したのか明白にしてください。