こんにちは！しゅんです！
今回は線形計画法について解説していきます！
線形計画法は高校数学で登場する数学用語です。この記事では線形計画法がどんなことに使えるのか解説していきます。
それでは解説していきましょう！
普段は統計検定2級の記事とかを書いています。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
線形計画法ってなに？
高校数学の範囲に線形計画法という単元があります。これはある条件を満たすように関数の最大値、最小値を求める問題です。例えば下のような問題です。
・\(x \geq 0\)
・\(y \geq 0\)
・\(x+y \leq 2\)
で表される領域内で関数 \(x+2y\) を最大にする点とその最大値を求めよ。
この問題の解き方をおさらいしましょう。\(x+2y = k\)とおいてグラフを描いて\(k\)の最大値を求めるんでしたね。
今回の場合だと\(k\)が最大となるのは図の右側の状態になったときです。
つまり「\(x=0, \; y=2\)のとき、\(x+2y\)は最大値4をとる」というのがこの問題の答えになります。
文字が3つ以上でも解くことができる
恐らく高校数学では未知の文字が\(x,\;y\)の2つで線形計画法をやっていたと思います。しかし実は文字数が3つ以上になっても解けるんです。例えば下の問題なんかも線形計画問題です。
・\(w \geq 0\)
・\(x \geq 0\)
・\(y \geq 0\)
・\(z \geq 0\)
・\(w+x+y+z \leq 2\)
で表される領域内で関数 \(w+2x+3y+4z\) を最大にする点とその最大値を求めよ。
これは文字が4つの問題ですが線形計画問題に分類され、線形計画法で解くことができます。もちろん文字数が4つだと図で表すことができないので、シンプレックス法などを使って解きます。
線形計画問題をざっくり言うと数式が全部1次式で表されてる問題のことです。だから例えば最大値を求めたい関数が\(w+x^2+y^3+z^4\)など、次数が2以上の項が存在すると線形計画問題とはなりません。
線形計画法ってどんなことに使えるの？
一見すると何に使われているかわかんない線形計画法ですが、実は色んなところで使える便利なやつなんです。いくつかその例を見てみましょう。
生産計画
限られた資源の中から利益を最大にするために何をどれだけ生産するかを考えるときに線形計画法が使えることがあります。
仕事割当
どの仕事をどの機械に割り当てれば仕事が最も早く終わるかを計算するときも線形計画法が使えることがあります。
人材割当
会社の人材をどの部署に割り当てたら効率的に仕事ができるかを計算するときも線形計画法が使えることがあります。
現実の問題を線形計画法を使って解いてみる
それでは最後に現実でありそうな問題を線形計画法を使って解いてみます。
以下の問題を考えてみましょう。
2種類の製品を生産することを考える。製品1を1kg作るのに材料1が5kg、材料2が2kg使われ、製品2を1㎏作るのに材料1が4kg、材料2が4kg使われる。1日のうちに使える材料がそれぞれ材料1が120kg、材料2が80kgである。また製品1は1kg当たり2万円で売れ、製品2は1kg当たり3万円で売れる。このとき利益が最大になるようにするには製品1,2をそれぞれ何kgずつ生産すれば良いだろう。
文章のままだと何言ってるか分かりづらいので表にまとめてみます。
| 材料1（kg） | 材料2（kg） | 利益（万円） | |
| 製品1 製品2 | 5 4 | 2 4 | 2 3 |
| 使用量上限 | 120 | 80 |
表でまとめるとこんな感じです。さあこの問題をどうやって解けばよいでしょうか。1つずつ解説していきます。
目的関数を設定する
この問題は利益を最大化するように問題を解きます。ということで利益を表す関数を設定しましょう。
製品1の生産量を\(x\)、製品2の生産量を\(y\)と置きます。このときの利益を\(x,\;y\)を使って表すと以下のようになります。
\(2x+3y\)
例えば製品1を3kg、製品2を4kg生産した場合の利益は\(2×3+3×4=18\)（万円）となりますね。
このように最大最小を求めたい関数を目的関数と言ったりします。
制約条件を設定する
次に製品を生産するときの条件について考えてみましょう。材料1の使用上限が120kgなので、例えば製品1を100kg生産しようとすると、材料1が500kg必要になるので100個も生産することはできません。
このことを式にします。製品1の生産量を\(x\)、製品2の生産量を\(y\)と置いたとき、材料1に関する条件は下のようになります。
\(5x+4y \leq 120\)
同じように材料2についても条件を考えると下の式が出てきます。
\(2x+4y \leq 80\)
また、製品1,2の生産量\(x,y\)は0以上である必要があります。以上のことをまとめて今回の問題の条件を全て式で表すと下のようになります。
\(5x+4y \leq 120\)
\(2x+4y \leq 80\)
\(x \geq 0\)
\(y \geq 0\)
このような満たさなければいけない条件を制約条件って言ったりします。
問題を解く
これまでの話で問題を以下のように定式化することができました。
・\(5x+4y \leq 120\)
・\(2x+4y \leq 80\)
・\(x \geq 0\)
・\(y \geq 0\)
で表される領域内で関数\(2x+3y\)を最大にする点とその最大値を求めよ。
この領域を図示してみましょう。
### 上のグラフをpythonで描画するコード例 ###
import matplotlib.pyplot as plt
import numpy as np
# 方程式: 5x + 4y = 120, 2x + 4y = 80
# 範囲: x >= 0, y >= 0
# xの範囲を指定
x = np.linspace(0, 30, 100) # 0から30の範囲を100点で分割
# 方程式を満たすyの値を計算
y1 = (120 - 5*x) / 4
y2 = (80 - 2*x) / 4
# グラフを描画
plt.plot(x, y1, color = "red", alpha =0.7, label="5x + 4y = 120", linewidth = 2)
plt.plot(x, y2, color = "blue", alpha = 0.7, label="2x + 4y = 80", linewidth = 2)
plt.fill_between(x, np.minimum(y1, y2), color="orange", alpha=0.5)
plt.xlabel("x")
plt.ylabel("y")
plt.xlim(0, 30)
plt.ylim(0, 30)
plt.legend()
plt.grid(True)
plt.show()次に\(2x+3y=k\)が取りうる範囲を調べてみましょう。
### 上のグラフをpythonで描画するコード例 ###
import matplotlib.pyplot as plt
import numpy as np
# 方程式: 5x + 4y = 120, 2x + 4y = 80
# 範囲: x >= 0, y >= 0
# xの範囲を指定
x = np.linspace(0, 30, 100) # 0から30の範囲を100点で分割
# 方程式を満たすyの値を計算
y1 = (120 - 5*x) / 4
y2 = (80 - 2*x) / 4
y3 = (200/3 - 2*x) / 3
y4 = (90 - 2*x) / 3
y5 = (40 - 2*x) / 3
# グラフを描画
plt.plot(x, y1, color = "black", alpha =0.3, linewidth = 2)
plt.plot(x, y2, color = "black", alpha = 0.3, linewidth = 2)
plt.plot(x, y3, color = "blue", alpha = 1, label = "2x+3y=200/3", linewidth = 3)
plt.plot(x, y4, color = "purple", alpha = 1, label = "2x+3y=90", linewidth = 3)
plt.plot(x, y5, color = "violet", alpha = 1, label = "2x+3y=40", linewidth = 3)
plt.plot(40/3, 40/3, color = "black", label = "x=40/3, y=40/3", marker= "o", markersize = 10, alpha = 1)
plt.fill_between(x, np.minimum(y1, y2), color="gray", alpha=0.3)
plt.xlabel('x')
plt.ylabel('y')
plt.xlim(0, 30)
plt.ylim(0, 30)
plt.legend()
plt.grid(True)
plt.show()
\(k\)の値として\(40, 90, \frac{200}{3}\)の3つを使ってグラフを描いてみました。
\(k=40\)のピンク色の直線を見るとまだ\(k\)を大きくできそうです。逆に\(k=90\)の紫色の直線を見ると領域の外に出てしまっているのでもう少し\(k\)を小さくする必要があります。
以上のことを考えると\(k\)が最大となるのは青色の直線のときで、\(k=\frac{200}{3}\)となります。またこのときの黒点の座標は\((x,y)=(\frac{40}{3},\frac{40}{3})\)となります。
つまり今回の問題の答えは「製品1,2をそれぞれ\(\frac{40}{3}kg\)ずつ生産することで利益を最大にすることができ、その利益は\(\frac{200}{3}\)万円となる」になります。
今回扱った問題は変数が\(x,y\)の2つだけでしたが、現実の問題は変数が何十個、何百個になることもあります。しか前の章でも言ったように変数が3つ以上の場合もシンプレックス法などを使えば問題を解くことができます。
おわりに
いかがでしたか。
今回の記事では線形計画法について解説していきました。
今後もこのような経営工学に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
