線形計画法①・最適生産計画

線形計画法と最適生産計画

線形計画法(Linear Programming: LP) とは, 対象の問題の制約や目的が1次式で表される線形計画問題において, 制約を満たしながら,目的を達成する計画(変数)を導出するための手法です. また, 最適生産計画 は,利益を最大化するために, 製品の生産に要する原材料や部品などのコストや在庫数を最適化する問題のことであり, ここでは線形計画問題の一つとして扱います.

最初に次の例題を考えます.

例題

A社では2種類の製品A,Bを生産しています. 製品Aを1kg作るには原料1が5kg,原料2が3kg,原料3が2kg必要です. 製品Bを1kg作るには原料1が3kg,原料2が4kg,原料3が1kg必要です. 倉庫には原料1が100kg,原料2が80kg,原料3が90kgあります. 製品Aの利益は1kg当たり10万円,製品Bの利益は1kg当たり8万円であるとき, 最大の利益を得るには,製品A,Bをどれだけ生産すれば良いでしょうか.

製品(kg) 原料1(kg) 原料2(kg) 原料3(kg) 利益(万円)
A 5 3 2 10
B 3 4 3 8

この問題を定式化するために, 目的関数制約条件 を定義します. 製品Aの生産数を$x$,製品Bの生産数を$y$とすると,目的関数を表す利益は次のように定義できます.

$$ 利益 = 10x + 8y $$

原料1,原料2,原料3の制約条件を定義します. 原料が倉庫にある在庫を超えないことが条件となります.

$$ 原料1の制約条件: 5x + 3y \leq 100 $$

$$ 原料2の制約条件: 3x + 4y \leq 80 $$

$$ 原料3の制約条件: 2x + 3y \leq 90 $$

上記の制約条件を満たしながら,目的関数を最大化することが狙いです(問題によっては最小化の場合もある). 目的関数と制約条件はいずれも1次式で表されていることに注意してください.

問題の特徴を理解するために,制約条件を変形し,$y$について解いてみましょう.

$$ 原料1の制約条件: y \leq \frac{100 - 5x}{3} $$

$$ 原料2の制約条件: y \leq \frac{80 - 3x}{4} $$

$$ 原料3の制約条件: y \leq \frac{90 - 2x}{3} $$

$x$を0から25に変化させたときの$y$をグラフで表します. $y$は全ての制約条件を満たす必要があることから, 実行可能解 は3本の直線より下の範囲となります. 例えば,$x=10$,$y=10$は範囲内にあるため実行可能解です.

Image from Gyazo

この実行可能解の範囲で,目的関数が最大となる$x$と$y$の組み合わせを探します. ある$x$において,利益が最大となるのは,$y$が一番下の直線上にあるときです. 例えば,$x=10$のときは,原料2の制約条件が対象となり,$y=12.5$となります(生産数は整数のため実際は$y=12$).

Image from Gyazo

上記の考え方に基づき,$x$を変化させたときの利益をグラフで表します. この結果,$x=15$のときに利益が最大となることがわかります($y=8$のとき).

Image from Gyazo

データセット

ここでは,次のCSV形式のデータセットを利用します. 下記のURLからファイルをダウンロードしてください. 上述と同じ最適生産計画の問題です.

dataset7.csv

製品,原料1,原料2,原料3,利益
A,5,3,2,10
B,3,4,3,8

Excelで最適生産計画

Excelのソルバーを利用して最適生産計画を解きましょう. ダウンロードしたファイルをExcelで開いてください.

変数

B5にAの生産量$x$,B6にBの生産量$y$を入力します. ここでは仮に$x=5$,$y=5$を入力しておきます.

Image from Gyazo

目的関数

B8に目的関数を表す=B5*E2+B6*E3を入力します. $x=5$,$y=5$であるため,目的関数は$10 \cdot 5 +8 \cdot 5=90$となります.

Image from Gyazo

制約条件

B10に原料1の制約条件,B11に原料2の制約条件,B12に原料3の制約条件を入力します. それぞれ,=B5*B2+B6*B3=B5*C2+B6*C3=B5*D2+B6*D3で表されます. また,D10,D11,D12に,原料の上限(在庫)を入力しておきます.

Image from Gyazo

ソルバー

データ・タブからソルバーを選択します. ソルバーのパラメータに,目的セル(目的関数),変数セル(変数),制約条件の対象(制約条件)を設定します. このとき,$x$と$y$は生産数であるため,制約条件として 整数(int) を設定しておきます. また,解決方法は シンプレックスLP(シンプレックス法) を選択します.

Image from Gyazo

Image from Gyazo

最後に解決ボタンをクリックすると,最適な$x$と$y$が導出されます. この結果,$x=15$,$y=8$が最適解であり,そのときの利益は$214$となることが分かります. また,この解が全ての制約条件を満たしていることも分かります.

Image from Gyazo

Pythonで最適生産計画

Pythonを利用して最適生産計画を解きましょう. Jupyter Labを起動して,Pytohn 3のノートブックを開きます. ノートブックの名前は chapter8.ipynb とします. pandasmatplotlibnumpyなどのライブラリをインポートしておきましょう. ここでは,最適化問題を解くために PuLPを新たにインポートします.

import pandas as pd
import matplotlib.pyplot as plt
import japanize_matplotlib
import numpy as np
from pulp import *

データセットの読込

read_csv関数でデータセットを読み込みます.

df = pd.read_csv("dataset7.csv")
display(df)

Image from Gyazo

変数

PuLPを利用して変数を定義します. 変数$x$と$y$は,0以上の整数であるため,下限を表すlowBound=0,データのカテゴリを表すcat="Integer"を設定します. この他に,上限を表すupBoundを設定することができます.

# 変数
x = LpVariable("x", lowBound=0, cat="Integer")
y = LpVariable("y", lowBound=0, cat="Integer")

問題

最適生産計画の問題を定義します. ここで,LpMaximizeは最大化を表しています. 最小化を表す場合はLpMinmizeを設定します.

# 問題
problem = LpProblem("最適生産計画", LpMaximize)

目的関数

目的関数を定義します.

# 目的関数
problem += x * df["利益"][0] + y * df["利益"][1]

制約条件

制約条件を定義します(条件に名前を付けることができます).

# 原料1の制約条件
problem += x * df["原料1"][0] + y * df["原料1"][1] <= 100, "原料1の制約条件"

# 原料2の制約条件
problem += x * df["原料2"][0] + y * df["原料2"][1] <= 80, "原料2の制約条件"

# 原料3の制約条件
problem += x * df["原料3"][0] + y * df["原料3"][1] <= 90, "原料3の制約条件"

問題の確認

定義した問題を確認してみましょう. 目的関数,制約条件,変数の条件などを確認することができます.

print(problem)
最適生産計画:
MAXIMIZE
10*x + 8*y + 0
SUBJECT TO
原料1の制約条件: 5 x + 3 y <= 100

原料2の制約条件: 3 x + 4 y <= 80

原料3の制約条件: 2 x + 3 y <= 90

VARIABLES
0 <= x Integer
0 <= y Integer

解決

solve()関数で問題を解きます. この関数の戻り値が1(Optimal)のときは,最適解が得られたことを表します.

# 最適化
# 1: Optimal Solution Found
# 0: No Solution Found
# -1: No Solution Exists 

status = problem.solve()
print(LpStatus[status])
Optimal

導出された最適解を確認しましょう. Excelのソルバーで導出された解と同じ,$x=15$,$y=8$が最適解となったことが分かります. また利益の最大値が214となったことも確認できます.

# 最適化された変数の確認
print(x.varValue)
print(y.varValue)

# 利益
print(problem.objective.value())
15.0
8.0
214.0

課題

制約条件に原料4のデータを加えて,利益を最大とする$x$と$y$を導出してください. このとき,製品Aを1kg作るには原料4が3kg,製品Bを1kg作るには原料4が2kg必要とします. また,原料4の在庫は50kgとします.

df2 = df.assign(原料4=[3, 2]) 
display(df2)

Image from Gyazo

Jupyter Labで作成したノートブックを保存し,ダウンロードして提出してください. ノートブックをダウンロードするには,メニューから Download を選択します. ノートブックのファイル名は chapter8.ipynb としてください.

参考書籍

愛知県名古屋市にある椙山女学園大学 文化情報学部 向研究室の公式サイトです. 専門は情報科学であり,人工知能やデータベースなどの技術要素を指導しています. この公式サイトでは,授業で使用している教材を公開すると共に, ベールに包まれた女子大教員のミステリアスな日常を4コマ漫画でお伝えしていきます. サイトに関するご意見やご質問はFacebookまたはTwitterでお問い合わせください.