線形計画法の解法

線形計画法を解くためには、いくつかの主要な解法があります！

ここでは２つの変数を持つ線形計画問題に適用できる直観的な解法である「図式解法」と、許容解の空間を移動しながら最適解を探すアルゴリズムである「シンプレックス法」について説明します！

図式解法

まずは前のレッスンの製品の生産問題を例に、図式解法で最適解を求めていきます。

まずは制約条件をグラフにプロットしてみましょう！

3つの制約条件から1次方程式をグラフ化する要領で図示していきます。

２つの式と非負制約を基に、制約条件を満たす範囲をグレーで塗りつぶしたものは以下のようになります！

図式化が完了したら、実際に図から最適解になりそうなところを見ていきます！具体的には全部で4点あるグレーの制約条件の頂点に着目することで最適解を見つけることが出来ます！

それでは実際に以下の4つの頂点についてそれぞれ評価し、最大化していきたい合計利益を計算します！

2点目と3点目はそれぞれの1次方程式の切片です！

4点目についてはオレンジと青のグラフの交点であり、連立方程式を計算して求めましょう！

そして頂点の各点における目的関数の値は以下になります。

最適解は、これらの頂点の中で目的関数の値が最大となる点です。

上記よりこの例では、(0, 90)が最適解でありZ=2700となります。

つまり、今回の例では、製品Aを1個も作らずに全て製品Bを生産するのが利益の面で最適解であるといった結果が確認できました！

シンプレックス法

続いて、シンプレックス法について簡単に説明します！

シンプレックス法は、線形計画法の中でも広く使用されていて、一言で表すと「許容解の空間を移動しながら最適解を探すアルゴリズム」となっています！

実際には少し複雑な計算等も発生しますがここでは割愛します。

簡単ですがシンプレックス法についても紹介しました！

メリットしては、非常に高い精度で最適解を求めることができ、かつ効率的に解を求めることができる点が挙げられます！

反対にデメリットとしては、初期解の選択が適切でないと計算が非効率になる可能性がある点や、高次元空間での計算量が膨大になることがある点が挙げられるでしょう。