みなさん，こんにちは
おかしょです．
前編の記事で単体法という最適化手法を使うと，なぜ最適解を得られるのかを解説しました．例題を用いながら途中計算まで詳しく書いたので，説明が長くなってしまいました．
この記事はその後編で，単体表というものを使って最適解を求める方法を解説します．単体表を使うと行列の計算が必要ないので，連立方程式を習った中学生くらいの方でも最適解を求めることができると思います．
また，この記事でも前編と同じ問題を解きながら解説していきます．使用する例題は以下になります．
\begin{eqnarray}
最小化&:&w=-2x_{1}-3x_{2}\\
制約条件&:&
\left\{
\begin{array}{l}
8x_{1}+2x_{2}\leq 9\\
3x_{1}+3x_{2}\leq 12
\end{array}
\right.\\
&&x_{1}\geq 0,\ x_{2}\geq 0
\end{eqnarray}
この記事を読むと以下のようなことがわかる・できるようになります．
- 単体表の書き方
- 単体表の計算方法
この記事を読む前に
この記事ではどうして単体法で最適解を求めることができのかといったことは解説しません．とにかく最適解が求められればそれでいいという方は，このままこの記事を読んでください．そもそも単体法とは何なのか，どうして最適解を求めることができるのかについて知りたい方は以下の記事を読んでおくことをおすすめします．
単体表の書き方
単体表はフランス語で”simplex tableau”と言います．参考書によってはシンプレックス・タブローと書かれている場合もあるので覚えておいてください．
冒頭でも述べましたが，この単体表というのは単体法をするためのツールです．前編の記事で解説した方法とは全く違う計算をしているように思えますが，意味は変わりません．ただ，普通に行列の計算をするよりも単体表を使って解いた方がはるかに簡単に解けます．
さて，具体的な計算方法を解説する前に最適化問題を解くための準備をする必要があります．
まずは単体法をするには以下のような仮定があります．
- 最適化問題は線形計画問題の標準形であること
- 一組の実行可能基底解が与えられていること
これらの仮定の詳細の解説はまず1つ目の条件は前編の記事で行っているので，ここでは簡単に説明します．
まず１つ目の線形計画問題の標準形というのは，先ほどの例題の制約条件を不等式制約から等式制約に変換すれば標準形になります．次に２つ目の実行可能基底解というのは，制約条件を満たす解のことです．これら２つの条件を満たしていれば，単体表で最適化問題を解くことができます．
単体表で先ほどの問題を解くために，まずはスラック変数を導入して不等式制約を等式制約に変換します．スラック変数についてはこちらを参考にしてください．
\begin{eqnarray}
最小化&:&w=-2x_{1}-3x_{2}\\
制約条件&:&
\left\{
\begin{array}{l}
8x_{1}+2x_{2}+x_{3}=9\\
3x_{1}+3x_{2}+x_{4}=12
\end{array}
\right.\\
&&x_{1}\geq 0,\ x_{2}\geq 0,\ x_{3}\geq 0,\ x_{4}\geq 0
\end{eqnarray}
そして，実行可能基底解は以下のように与えられているとします．
\begin{eqnarray}
x_{1}= 0,\ x_{2}=0,\ x_{3}=9,\ x_{4}=12
\end{eqnarray}
つまり，基底変数は\(=0\)となっていない\(x_{3}\)と\(x_{4}\)です．
以上で単体法を使う準備ができました．
次は単体表の書き方です．まず以下のような表を準備します．
\begin{array}{c|c|cccc|c|c}
\hline
反復回数 & 基底 & x_{1} & x_{2} & x_{3} & x_{4} & 定数 & 比率 \\
\hline
& & & & & & & \\
& & & & & & & \\
\hline
& & & & & & & \\
\end{array}
この表に基底変数や制約条件，目的関数を解加えていきます．この表で一番上の行にある変数の数は問題によって異なるので，解きたい問題に合わせて用意してください．今回の場合は例題の変数がスラック変数も含めて４つあるので，上の表のようになりました．
制約条件などの情報を上の表に書き加えると以下のようになります．
\begin{array}{c|c|cccc|c|c}
\hline
反復回数 & 基底 & x_{1} & x_{2} & x_{3} & x_{4} & 定数 & 比率 \\
\hline
& x_{3} & 8 & 2 & 1 & 0 & 9 & \\
0 & x_{4} & 3 & 3 & 0 & 1 & 12 & \\
\hline
& -w & -2 & -3 & 0 & 0 & 0 & \\
\end{array}
“基底”の列の２行目と３行目には基底変数（\(x_{3}\)と\(x_{4}\)）を書きます．実行可能基底解は\(x_{3}=9,\ x_{4}=12\)だったので”定数”の列に各値を書きます．”基底”と”定数”の間の列には制約条件を書き込みます．一番下には目的関数の情報を書き込んでいきます．
上のような表ができたら単体法を解くための準備ができました．この時点では，ただ問題を書き込んだだけなので反復回数は０としています．この反復回数は特に計算に必要なわけではないのでなくても構いませんが，反復回数は最適化手法の性能評価に用いられる値なので書いておいて損はないと思います．
単体表の計算方法
それでは実際に解いていきます．
手順1：目的関数の係数を調べる
まずは目的関数の係数に注目します．表の一番下の行です．ここで，各変数の列で負の値になっているものを探します．上の表の場合は\(x_{1}\)と\(x_{2}\)の列が’-2’と’-3’となっています．どちらも負の値なので，どちらを選んでも問題ありませんが効率的に最適解を求めるためにより小さな値の’-3’を選択します．
\begin{array}{c|c|cccc|c|c}
\hline
反復回数 & 基底 & x_{1} & x_{2} & x_{3} & x_{4} & 定数 & 比率 \\
\hline
& x_{3} & 8 & 2 & 1 & 0 & 9 & \\
0 & x_{4} & 3 & 3 & 0 & 1 & 12 & \\
\hline
& -w & -2 & (-3) & 0 & 0 & 0 & \\
\end{array}
この時に負の値がない場合は目的関数を小さくすることができないので，あきらめて計算を終了します．
手順2：基底変数を入れ替える
表の上の方を見ると，この’-3’は\(x_{2}\)の係数であることがわかります．つまり，\(x_{2}\)の値を大きくすることで目的関数を小さくすることができます．そのため，\(x_{2}\)を非基底変数から基底変数に変えます．この時\(x_{3}\)と\(x_{4}\)のどちらと入れ替えるのか決める必要があります．
そこで，表の一番右にある比率の欄を埋めます．この比率は以下の式で求めることができます．
\begin{eqnarray}
比率=\frac{定数}{制約条件の選択した変数の係数}
\end{eqnarray}
この時に制約条件の選択した変数の係数が負の値の時がありますが，その場合は比率の計算はする必要ありません．また，係数がすべて負の値の場合は解が有界ではないので計算を終了します．
今回の例の場合は，どちらの係数も正の値なので，上式を用いて表を作ると以下のようになります．
\begin{array}{c|c|cccc|c|c}
\hline
反復回数 & 基底 & x_{1} & x_{2} & x_{3} & x_{4} & 定数 & 比率 \\
\hline
& x_{3} & 8 & 2 & 1 & 0 & 9 & \frac{9}{2}\\
0 & x_{4} & 3 & 3 & 0 & 1 & 12 & 4\\
\hline
& -w & -2 & -3 & 0 & 0 & 0 & \\
\end{array}
ここで，比率が小さい方と同じ行にある基底変数と先ほど選択した変数を入れかえます．上の表の場合は比率は9/2よりも4の方が小さいので，基底変数\(x_{4}\)を\(x_{2}\)に変えます．
\begin{array}{c|c|cccc|c|c}
\hline
反復回数 & 基底 & x_{1} & x_{2} & x_{3} & x_{4} & 定数 & 比率 \\
\hline
& x_{3} & 8 & 2 & 1 & 0 & 9 & \frac{9}{2}\\
0 & x_{2} & 3 & (3) & 0 & 1 & 12 & 4\\
\hline
& -w & -2 & -3 & 0 & 0 & 0 & \\
\end{array}
手順3：掃き出す
基底変数を入れ替えたら，比率の小さい行と先ほど選択した変数の列が交差した要素を軸にして掃き出し（ピボット）をします．掃き出しとは軸となる要素を’1’にして同じ列の要素が’0’になるようにする操作のことを言います．
今回の例の場合は，上の表でかっこ（）でくくってある’3’を軸にして掃き出します．掃き出すには，まず比率の小さい行を3で割ります．そして，上の行から比率の小さい行を2倍したものを引き，下の行に比率の小さい行を3倍したものを足します．このようにすることで，表は以下のようになります．
\begin{array}{c|c|cccc|c|c}
\hline
反復回数 & 基底 & x_{1} & x_{2} & x_{3} & x_{4} & 定数 & 比率 \\
\hline
& x_{3} & 6 & 0 & 1 & -2/3 & 1 & \\
1 & x_{2} & 1 & 1 & 0 & 1/3 & 4 & \\
\hline
& -w & 1 & 0 & 0 & 1 & 12 & \\
\end{array}
手順4：手順１に戻って繰り返す．
これで表を使った計算は一通り終わりです．あとは手順１に戻って目的関数の係数から調べていきます．そのため，先ほどの手順３の時点で表の一番左の列の反復回数は’0’から’1’に変更します．
上の表を手順１に戻して，目的関数の係数を調べるとすべて正の値となっています．したがって，これ以上目的関数を小さくすることができないので，計算を終了します．
この時の最適解は基底変数の値は表の同じ行で定数の列にある値になります．非基底変数はすべて’0’が最適解になります．また，その時の目的関数の値は表の一番下の行の定数の欄に書いてある値になります．
つまり，例題の最適解は
\begin{eqnarray}
x_{1}=0,\ x_{2}=4,\ x_{3}=1,\ x_{4}=0\\
w=-12
\end{eqnarray}
となります．これは前編の記事で求めた最適解と一致します．
まとめ
この記事では単体表を使って最適解を求める方法を解説しました．最適化計算と聞くと難しそうに聞こえますが，単体表を使うと非常に簡単に解くことができます．いろいろな問題を解いて試してみてください．
ここで，単体表で最適解を求める手順を最後にまとめておきます．
- 目的関数の係数を調べる
- 基底変数を入れ替える
- 掃き出す
- １に戻ってやり直す
続けて読む
今回は線形計画問題という最適化計算の中でも特に簡単な問題の解き方を解説しました．今後も最適化手法の解説を行い，もっと難しい問題にもチャレンジできるように記事を更新していきますのでチェックしてください．
Twitterでは記事の更新情報や活動の進捗などをつぶやいているので気が向いたらフォローしてください．
YouTubeでも制御工学や電子工作などの解説をしているので，ぜひのぞいてみてください．
それでは最後まで読んでいただきありがとうございました．
コメント