線形計画法について調べてみた(代数による方法)
線形計画法について調べてみた2
さて、前回は図解法による線形計画問題について載せましたが、変数が多くなってくるとこの方法では手に負えません。そこで代数による方法を考えてみましょう。
まず問題は前回と同じで以下のようにな
っているとします。
ここで制約条件①~④までを満たす、x1, x2の組み合わせとして(x1, x2) = (0, 0)の組み合わせがあることがわかります。このとき、目的関数の値は0です。ここから目的関数を増加させていきましょう。目的関数の係数が10と7なので、とりあえず係数が大きいx1を大きくすることで目的関数を大きくしましょう。
さて、x1を大きくするという方針は決まりましたが、制約条件①、②があるので大きくできる値には限りがあります。制約条件①をみるとx1 = 90が最大、制約条件②をみるとx1 = 40(120÷3)であることがわかります。制約条件①、②は同時に満たす必要があるため、x1= 40がとりうる最大のx1であることが分かります。(このとき制約条件②よりx2 = 0)
このときの状況は下記のようになります。
さて目的関数⑤をさらに大きくするにはどうすればいいでしょうか。
⑤式よりパターンとしては3パターン考えられます。
1. x1→増、x2→増
2. x1→増、x2→減
3. x1→減、x2→増
しかしながら②'よりx1はこれ以上大きくできないため、パターン3、つまりx1を減らしつつ、x2を増やして式⑤を大きくすることを考えましょう。
ここで、②'にはもう余裕がないため、②’を満たしつつx1を減らして、x2を増やすことを考えます。そうするとそれぞれの係数が3と5なので、x1を1減らすとx2は3/5増やせることがわかります。このとき目的関数は -10 + 7 × 3/5 = -29/5 < 0 より減少してしまうことがわかります。(x1を1減らしてもx2は最大3/5までしか増やせないです。)
したがって、これ以上目的関数を大きくすることはできないので(x1, x2) = (40, 0)が最適解であることがわかります。
次回はまた別の問題を例にしてもう少し具体例を扱ってみます。