- 線形計画法ってなに？
- 線形計画法ってどんなことに使えるの？
- 現実の問題を線形計画法を使って解きたい…
こんにちは！しゅんです！
今回は線形計画法について解説していきます！
線形計画法は高校数学で登場する数学用語です。この記事では線形計画法がどんなことに使えるのか解説していきます。
それでは解説していきましょう！
普段は組合せ最適化の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。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以上の項が存在すると線形計画問題とはなりません。
線形計画法ってどんなことに使えるの？
線形計画法について説明されても、これが実際に世の中のどんなことに使われているかわかんないですよね。実は線形計画法は色んなところで使える便利なやつなんです。いくつかその例を見てみましょう。
生産計画
限られた資源の中から利益を最大にするために何をどれだけ生産するかを考えるときに線形計画法が使えることがあります。
このブログでも生産計画問題について詳しく解説しているので気になる方はぜひこちらの記事も見てみてください！
仕事割当
どの仕事をどの機械やどの従業員に割り当てれば仕事が最も早く終わるかを計算するときも線形計画法が使えることがあります。
少し専門的な話になりますが、通常何かを割り当てるタイプの問題は変数が0か1しか取らない「0-1変数」を使って定式化します。変数が飛び飛びの値しか取らない（離散変数）を使って定式化した問題は線形計画問題ではありません。しかし特定の問題においては0-1変数を0以上1以下の任意の実数を取りうる変数（連続変数）にしても同じ最適値が得られる場合があります。そのような特別な問題だと、線形計画問題として定式化することができます。
このブログでも割当問題について詳しく解説しているので気になる方はぜひこちらの記事も見てみてください！
人材割当
会社の人材をどの部署に割り当てたら効率的に仕事ができるかを計算するときも線形計画法が使えることがあります。
現実の問題を線形計画法を使って解いてみる
それでは最後に現実でありそうな問題を線形計画法を使って解いてみます。以下の問題を考えてみましょう。
問題：
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：10kg
背品2：20kg
としたときの材料1の合計使用量を計算してみます。製品1を1kg生産するために材料1は5kg使用され、製品2を1kg生産するために材料2は4kg使用されます。従って合計使用量は
\(5\times10+4\times20=130\)
と計算できます。しかし材料1は最大でも120kgしか使用できないので、こんなにたくさん製品を製造することができません。
このことを式にします。製品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つ以上の場合もシンプレックス法などを使えば問題を解くことができます。
おわりに
いかがでしたか。
今回の記事では線形計画法について解説していきました。
今後もこのような経営工学に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
