線形計画法について調べてみた（代数による方法）

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

　さて、前回は図解法による線形計画問題について載せましたが、変数が多くなってくるとこの方法では手に負えません。そこで代数による方法を考えてみましょう。

sy0807j.hatenablog.com

まず問題は前回と同じで以下のようにな

っているとします。

　ここで制約条件①～④までを満たす、x₁, x₂の組み合わせとして(x₁, x₂) = (0, 0)の組み合わせがあることがわかります。このとき、目的関数の値は0です。ここから目的関数を増加させていきましょう。目的関数の係数が10と7なので、とりあえず係数が大きいx₁を大きくすることで目的関数を大きくしましょう。

さて、x₁を大きくするという方針は決まりましたが、制約条件①、②があるので大きくできる値には限りがあります。制約条件①をみるとx₁ = 90が最大、制約条件②をみるとx₁ = 40(120÷3)であることがわかります。制約条件①、②は同時に満たす必要があるため、x₁= 40がとりうる最大のx₁であることが分かります。（このとき制約条件②よりx₂ = 0)

このときの状況は下記のようになります。

さて目的関数⑤をさらに大きくするにはどうすればいいでしょうか。

⑤式よりパターンとしては3パターン考えられます。

1.　x₁→増、x_２→増

2.　x₁→増、x_２→減

3.　x₁→減、x_２→増

 しかしながら②'よりx₁はこれ以上大きくできないため、パターン3、つまりx₁を減らしつつ、x₂を増やして式⑤を大きくすることを考えましょう。

ここで、②'にはもう余裕がないため、②’を満たしつつx₁を減らして、x₂を増やすことを考えます。そうするとそれぞれの係数が3と5なので、x₁を1減らすとx₂は3/5増やせることがわかります。このとき目的関数は -10 + 7 × 3/5 = -29/5 < 0 より減少してしまうことがわかります。（x₁を1減らしてもx₂は最大3/5までしか増やせないです。）

したがって、これ以上目的関数を大きくすることはできないので(x₁, x₂) = (40, 0)が最適解であることがわかります。

次回はまた別の問題を例にしてもう少し具体例を扱ってみます。