線形計画法について調べてみた（代数による方法）-2
線形計画法について調べてみた（代数による方法）-2
前回に引き続き、代数による線形計画法の解き方について具体例を用いて考えていきます。 今回は前回よりもう少し抽象的なことも考えていきます。
今回は以下の問題を例にして、考えていきます。
ところで、一般的に最適化問題は関数が最大もしくは最小となる解を求める問題ですが、どちらの場合でも統一的に考えれるように最大化問題は目的関数の符号を反転させて最小化問題にしましょう。すなわち以下の問題を解きます。
また、前回のブログでも書いたように最適解を探す際には、制約条件を満たしつつ変数の値を変えていきます。不等式ではわかりづらいため等式に変形して扱うことにします。つまり
ここで変数はすべて非負とします。また不等式を等式にするために投入したs1,s2,s3をスラック変数と呼びます。
また以下のようにおきます。
そうすると対象の問題は以下のようになります。
このように標準的な形に線形計画問題を記述することができました。
さて、では今回対象の問題を解いていきましょう。
まず、制約式①～③を満たす解として(x1,x2,x3,s1,s2,s3) = (0,0,0,200,250,300)が容易にわかります。ここから目的関数をより小さくすることができるかどうか調べましょう。
目的関数の係数ベクトルcをみると、x1,x2,x3の符号が負です。したがって、これらを大きくすると目的関数はより小さくなります。またもっとも係数が小さいx2の値から大きくしていきましょう。このとき、x1,x3は0なので、制約①～③を満たすようにを大きくすると最大50まで大きくすることができます。このとき目的関数は
となります。
ここで目的関数をみるとx2を減らして、x1,x3を増やすことでより目的関数を小さくできそうです。x2を50まで大きくしましたが、これは制約式②によるものなので、この式を満たしつつ目的関数の値を変化させることを考えます。式②を使って、式④からx2を消すと
z = 5x1+6/5x3+6/5s2-300となります。また、x2が50のとき、x1 = 0、x3 = 0、s2 = 0であり、それらの変数の係数が正であるため、これ以上目的関数の値を小さくできないため、(x1, x2, x3)=(0,50,0)が最適解であり、このときの目的関数の値は-300となります。
