線形計画法について調べてみた1

線形計画法について調べてみた1

　線形計画法とはシステム工学、Industrial Engineering(IE)、Operations Research(OR)等で広く使われている手法で、ある条件（線形式で与えられる）のもと、ある目的（こちらも線形式で与えられる）が最大もしくは最小となるような変数値を求めるものです。

なお、上記のような問題を線形計画問題と呼びます。またこの手法は1947年にDantzigにより考案されてから、様々な分野で広く使われています。

　さっそくですが、高校の教科書にも出てくるような、簡単な線形計画問題を見てみましょう。また生産条件は表1のようになっているとします。

【問題】　ある2種類の製品P₁,P₂はそれぞれ2種類の原料M₁,M₂から作られるものとする。P₁とP₂の生産条件が以下のようになっているとき、利益を最大にするにはP₁と P₂はそれぞれいくら生産すればよいか。

　この表の見方としては、製品P₁を1トン作るのにM₁が1トン、M₂が3トンが必要で、その利益が10万円となります。また、製品P₂を1トン作るのにM₁を5トン、M₂が5トン必要で、その利益が7万円となります。なお製品P₁の生産量をx₁トン、P₂の生産量をx₂トンとすると、表1の生産条件は以下のようになります。

　ここで利益を最大にするようP₁の生産量とP₂の生産量を決めることになりますが、利益が大きいP₁ばかりを作ると、原料M₂が余ってしまいます。したがって、P₁のみを作ればいいわけではないことが分かります。

また、上記制約条件を満たす領域は下図で与えられます。この領域内にて、目的関数が

最大になる点を探します。探し方としては10x₁ + 7x₂ = k(一定）として,

ｋを変化させつつ、kが最大となる点を探します。ちなみに今回の場合は、②式とx軸の交点(x₁,x₂) = (40,0)において目的関数の値が最大となります。

　しかしながら、製品の種類が3つ、4つと増えた場合はどうでしょうか。この作図法では求められません。実際の問題、例えば石油化学プラントにて月の生産計画を立てる際には数千もの変数を扱わなければなりません。では変数が増えた場合はどのように解くのでしょうか。次回に続きます。