書記が数学やるだけ#61 シンプレックス法で線形計画問題を解く

今回は，実際に線形計画問題を解いていく。その方法としてシンプレックス法について示す。

本記事の方針としては，最適解を求める過程を重視して，ワンステップずつ解説することとする。

問題

(1)はそのまま機械的に解けるが，(2)(3)は一工夫必要である。

解法(1)

まずはスラック変数を導入して，問題を等式に直す。

まずは初期値としてx=0，y=0とする。そうすると，①②についてxとyの値を増やしても，左辺λは正のままにすることができる。よって，λを正のままに，できるだけxとyの値を増やすことを考える。

xとyそれぞれについて，どれだけfを増やせるかを考える。

比較すると，xを増やした方がfがより増えることがいえるので，その時の値を元の式に代入する。方法としては，②で変数xとλ2を交換する。これで新たに解の候補を得る。

まだ最適解でないのは，yがまだ増やせることからいえる。なのでyをできるだけ増やす。そしてまた新たな解の候補を得る。

これが最適解なのは，fの式についてこれ以上増やせないことからいえる。

本問は高校数学の領域の基本でもある。可能領域の頂点のうち最大値となるfを求めればよい。

式が2つとか，変数が2つとかであれば，まだこのように手計算でもいける。しかし実際の問題では式も変数も大量にあることもありうる，こうなると図示自体が困難である。そういった時に，シンプレックス法は機械的に最適解を出す手段として有用である。

解法(2)

同じように，シンプレックス法で解く。

最適解でないのは，まだxとyの値が増やせることからいえる。

比較して，xを増やす方を選ぶ。

ここで，①②両方において，x=8で左辺λが0になるので，変数の交換は，λ1とλ2の2通り考えられる。

まずλ1と交換してまとめる。

すると問題が生じる。最適解でないにもかかわらず，yを増やそうにも増やせないのである。

なのでもう1パターンである，λ2と交換することにする。

すると計算が先に進み，最適解が求められる。

これは退化という現象である。

解法(3)

スラック変数を導入して，先へ進めようとすると問題が生じる。

本来，非負であるはずのλ1が負になってしまっている，これでは先に進められない。

そこで，新しい変数m（人工変数）をつけて，λ1が正になるようにする。しかし，勝手に付け加えた変数mによって，問題の式そのものが変わってしまう。

mについて，最適解でm=0になってくれさえすれば元の問題と同じである。そこで，最適解でmが0になるような制約として，目的関数に-Mmという項を加え，新しく目的関数を定める。このM（罰金）は非常に大きい数とする，こうすることでmが0でない限り目的関数が著しく減少するので，最適解ではm=0が強制される。。

このように人工変数を導入することで，問題が先に進められる。

m=0となっていることから，元の問題の最適解として差し支えない。

なお，人工変数を導入すると，非負の解がいくらでも作れるが，人工変数が0にならない場合は与えられた可能領域は空集合であり最適解が存在しない。

本記事のもくじはこちら：