線形計画法

線形計画法

線形計画法（LP法：Linear Programming method）とは、輸送問題、混合問題、人員配置問題、などの線形計画問題に対する最適解を得る手法です。線形計画問題は、生産量やコスト、人員などのデータが一次関数として表現でき、求めたい最適値を得るための目的関数を与えて、その目的関数の最大値、または、最小値を算出することで最適解を得るというものです。

線形計画法の考え方

線形計画法で扱う線形計画問題は、一次関数で表現できる制約式と目的関数が与えられます。

最大化の制約式は、

（最小化の場合は、不等号が「≧」となります。）　

目的関数は、

で表現できるものとします。

このとき、制約式にスラック変数と呼ばれる変数x_(n+1)、x_(n+2)、…、x_(n+m)を導入して、制約式の不等式を等式に変形します。変形すると次のように記述できます。

目的関数は、右辺を左辺に移行して

のように式変形します。

このとき、制約式と目的関数をひとつの行列で表現します。

この行列を係数行列と呼びます。

係数行列は、

と記述されます。

この係数行列x_1~ x_n　の係数が１となるように掃き出し演算を行うことによって、最終的に目的関数の最適値が求まります。

アルゴリズム

①最下行（目的関数の係数）の中から最小なもの（絶対値最大）がある列Yを探します。＜列探索＞

②最小値≧０なら終了します。

③①で求めたY列にある各行の要素で各行の右端要素を割ったものが最小となる行Xを探します。＜行探索＞

④X行Y列をピボットにして掃き出し演算を行います。

この手順で、制約条件を満たし、目的関数の値が最大（最小）となるような掃き出し演算を行います。

線形計画法の例

ここでは、次のような問題を考えてみます。

R_1の限界線は、

R_2の限界線は、

R_3の限界線は、

となります。条件として、

が存在します。

目的関数は、売上高の関数で

で表せます。ここでは、目的関数Zを上式を1万で割った値とします。

以上の式より、係数行列を書くと次のようになります。

この係数行列に対して最下段（目的関数）の行で最小値の列を選択します。この例では、「ー２」の１列目が最小となります。

１列目を選択して、右端の要素を選択した列の値でそれぞれ割り、最小値となる行を選択します。ここでは、7000の3行目が最小となります。

これで１列目と３行目を選択できました。選択した３行１列の値「３」がピボットとなります。このピボットにより掃き出し演算をします。

ピボット行を３で割った後、各行の１列目を０にします。

以降、ここまでの手順を繰り返します。

係数行列の最下段（目的関数）の最小値の列を選択します。

最小値は、２列目の-1/3なので、各行２列目の値で右端の要素を割り、最小値となる行を選択します。ここでは、3000となる2行目が最小となります。

これにより、次のピボットは、２行２列に決定され、掃き出し演算を行います。

２行目の各要素に3/7をかけて２行２列の値を１とします。

その状態で、２行目以外の各行の２列目の値を０になるように演算します。

ここまでで、２回目のピボット掃き出し演算が終了です。

係数行列の最下段の最小値が０以上なので、演算はここで終了となります。

このとき、係数行列の右端の列が最適解となります。

最適解は、（x_1,x_2）=（6,000,3,000）のときに最大の売り上げとなり、その時の売り上げは、15,000万円となります。

最適解を図式化すると下図のように書けます。求めた最適解は、図中の点Aとなります。

プログラム例

先ほどの例のサンプルプログラムを記述します。

プログラムを実行した結果は、次のようになります。

c:\prog\algorithm>LPM
x 0 = 6.000000
x 1 = 3.000000
z = 15.000000
test end