みなさん，こんにちは
おかしょです．
評価関数を最小化する最適解を求める最適化手法には，さまざまな種類があります．この記事で解説する単体法は，線形計画問題と呼ばれる線形の目的関数と制約条件を持つ問題を解くことができます．
具体的には以下のような問題です．
\[
w=-2x_{1}-3x_{2}\\
\begin{eqnarray}
\left\{
\begin{array}{l}
8x_{1}+2x_{2}\leq 9\\
3x_{1}+3x_{2}\leq 12
\end{array}
\right.
\end{eqnarray}
\]
上式の不等式で表された制約条件を満たして，\(w\)で表された目的関数を最小化する最適解を求める問題を線形計画問題と呼びます．ちなみに，この\(w\)は評価関数とも呼ばれます．参考書や論文によっては評価関数と表記している場合もあるので頭の片隅に入れておいてください．
単体法は最適化計算の中では，割と簡単な手法で最適化計算が難しくて挫折した方でも解けるようになると思います．
この記事では単体法の解説の前編ということで，まずは単体法で最適解を求める原理について解説します．後編では単体表というものを使って，簡単に最適解を求める方法を解説します．単体法の原理なんてどうでもいいから，解き方だけ知りたいという方はその記事を読んでください．
この前編の記事を読むと以下のようなことがわかる・できるようになります．
- 単体法とは
- 単体法による最適化計算のやり方
この記事を読む前に
単体法では線形計画問題の標準形を解くことができます．標準形では制約条件は等式制約でなければなりません．
しかし，制約条件が必ずしも等式制約で与えられるとは限りません．
制約条件が不等式で与えられた場合はスラック変数というものを用いて，標準形に変換する必要があります．この方法については以下の記事で解説しているので，まだ読んでいない方はそちらを先に読んでおくことをおすすめします．
単体法とは
冒頭でも述べましたが，単体法とは線形計画問題を解く手法の一つです．
この手法のアルゴリズムの流れは，
『一組の実行可能基底解が与えられた時，目的関数がより低くなるような新しい実行可能基底解を求めていき，これを繰り返すことで最適解に到達します．』
いきなりこんな説明をされても用語などの意味が分からないと思うので簡単に説明します．
実行可能基底解
まず実行可能基底解というのは，線形計画問題の基底解を求めて，求められたすべての変数が負でなければその基底解のことを言います．
基底解
ここで，基底解というのは何かと言うと，非基底変数を0と置いて等式制約を解いた時の解のことを言います．
基底変数・非基底変数
さらに非基底変数というのは，基底変数以外の変数のことを言い，基底変数というのは基底行列に対応した変数のことを言います．
基底行列
基底行列というのは以下のような等式制約の係数行列\(A\)から\(rank(A)\)本の線形独立なベクトルを選び，それらを並べて作る正則行列のことを言います．
\[
Ax=b
\]
まとめ
用語の説明をされてもイメージがわきにくいと思うので，図で簡単に説明します．
まず目的関数が以下のように与えられていたとします．
この図で色の濃い方が目的関数は大きくなり，淡い方が小さくなっているとします．解としてはより色の淡い方が最適解となります．これに対して，各変数には以下のように制約条件が課されます．
この制約条件の線より下側が制約条件を満たした変数となります．つまり，上の図で言うと以下の色付けされた部分が制約条件を満たした変数となります．
この制約条件を満たす変数の中で最も目的関数を小さくできる解が最適解となります．解く前はどこが最適解なのかわからないので，原点を単体法の計算を開始する点とします．
上の図で青い点で表されているのが，最初の点は実行可能基底解になります．ここから目的関数が小さくなるように新たな実行可能基底解を求めます．これはこの後の解説を読めばわかるのですが，制約条件上を動いていくことになります．つまり，最初の点から単体法を実行すると次は
このように制約条件の上に実行可能基底解が移動します．この計算を繰り返していくと
このように制約条件を満たして目的関数を最小化する点に移動します．
単体法では上記のように目的関数がどんどん小さくなっていくように，実行可能基底解を更新していくことで最適解を求めます．
単体法を解く手順
ここからは，最適解を求めるための単体法の具体的な手順を説明していきます．言葉だけで説明していくとわかりにくいと思うので，実際に問題を解きながら解説していきます．
ここでは例題として以下の問題を解きます．
\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}
解くための準備
単体法を使って上の問題を解くには，まず不等式制約を等式制約にする必要があります．そのためにスラック変数(\(x_{3}とx_{4}\))を導入すると以下のようになります．
\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}
最小化&:&w=c^{T}x\\
制約条件&:&Ax=b\\
&&x\geq 0
\end{eqnarray}
ここで，各行列は以下のようになっています．
\begin{eqnarray}
A&=&
\begin{bmatrix}
8&2&1&0\\
3&3&0&1
\end{bmatrix}\\
b&=&
\begin{bmatrix}
9\\
12
\end{bmatrix}\\
c^{T}&=&
\begin{bmatrix}
-2&-3&0&0
\end{bmatrix}\\
x^{T}&=&
\begin{bmatrix}
x_{1}& x_{2}& x_{3}& x_{4}
\end{bmatrix}\\
\end{eqnarray}
単体法では初回の実行可能基底解が必要となります．ここでは基底変数に\(x_{3}\)と\(x_{4}\)が選ばれていたとします．これを用いて上の標準形を書き直すと以下のように書けます．
\begin{eqnarray}
w=c_{B}^{T}x_{B}+c_{N}^{T}x_{N}\\
Bx_{B}+Nx_{N}=b
\end{eqnarray}
\begin{eqnarray}
B=
\begin{bmatrix}
1&0\\
0&1
\end{bmatrix},\
N=
\begin{bmatrix}
8&2\\
3&3
\end{bmatrix},\
b=
\begin{bmatrix}
9\\
12
\end{bmatrix}\\
c_{B}^{T}=
\begin{bmatrix}
0&0
\end{bmatrix},\
c_{N}^{T}=
\begin{bmatrix}
-2&-3
\end{bmatrix}\\
x_{B}^{T}=
\begin{bmatrix}
x_{3}& x_{4}
\end{bmatrix},\
x_{N}^{T}=
\begin{bmatrix}
x_{1}& x_{2}
\end{bmatrix}\\
\end{eqnarray}
このように制約条件の基底変数の係数\(B\)が単位行列になる形式を実行可能基底形式と言います．
また，非基底変数である\(x_{1}\)と\(x_{2}\)を０と置き，制約条件を解いた時の変数の値が解となります．\(x_{1}=0,\ x_{2}=0,\ x_{3}=9,\ x_{4}=12\) 最適解かどうかはまだわかりません．
以上で単体法で最適解を求めるための準備ができました．以下では実際にどのような手順で最適解を求めていくのか解説していきます．
手順１：目的関数を小さくできるか
まず最初の手順は目的関数を小さくできるか確認することです．
最適解を求めるということは，つまり制約条件を満足して目的関数を最小化する解を見つけることです．
一番最初に与えられている実行可能基底解は，制約条件を満たしています．なので，この解も最適解の候補の一つです．ただ，この時の実行可能基底解よりも目的関数を小さくできる解があるのであれば，それを最適解としなければなりません．なので，まずは現在与えられている実行可能基底解からさらに目的関数を小さくできるか調べる必要があります．
目的関数を小さくできるかどうかを調べる方法は簡単です．目的関数の係数を見ればわかります．先ほど，非基底変数の値を０とした時の基底変数の値が解となると言いました．非基底変数の値を０と置きましたが，この時の値をほかの値にすると目的関数が小さくなるのであれば，非基底変数を０としてしまうのはもったいないです．
そこで，見るべきなのが目的関数の非基底変数にかかる係数\(c_{N}\)です．
すべての変数には非負の制約\(x\geq 0\)があるので，この係数が負の値であれば非基底変数の値を変化させることで目的関数を小さくすることができます．この目的関数の正負を調べる際に考えられるcaseが２つあります．
(a) 係数の値がすべて正
すべての係数が正である場合があります．この場合は変数の値を変更しても目的関数の値が大きくなってしまうだけなので，係数が正の変数はすべて０としておいた方が良いです．なので，ここで計算を終了して現在求められている解を最適解とします．
(b) 係数の中に負の値のものがある
係数の中に負の値があれば目的関数を小さくすることができます．目的関数を小さくすることができることがわかったら，次はどの変数を選ぶかです．
目的関数の係数の中に負の値になるものが一つしかない場合は，それに対応した変数を選べばいいのですが，負の値になる係数が複数ある場合があります．この場合は，より効率的に目的関数を小さくしていくために最も小さな係数を選ぶようにします．
今回の例の場合は目的関数が以下のように与えられていました．
\begin{eqnarray}
w=c_{B}^{T}x_{B}+c_{N}^{T}x_{N}
\end{eqnarray}
\begin{eqnarray}
c_{B}^{T}=
\begin{bmatrix}
0&0
\end{bmatrix},\
c_{N}^{T}=
\begin{bmatrix}
-2&-3
\end{bmatrix}\\
x_{B}^{T}=
\begin{bmatrix}
x_{3}& x_{4}
\end{bmatrix},\
x_{N}^{T}=
\begin{bmatrix}
x_{1}& x_{2}
\end{bmatrix}\\
\end{eqnarray}
見るべきなのは非基底変数の係数であり，係数はどちらも負の値になっています．なので\(x_{1}\)と\(x_{2}\)のどちらを選んでも目的関数を小さくできますが，より効率的に小さくするために-3にかかる変数，つまり\(x_{2}\)を選択します．
手順2：非基底変数の値を求める
手順1-bで目的関数を小さくできる非基底変数を求めました．
この手順2ではその非基底変数をどのような値にするのかを求めます．非基底変数をどのような値にでもできるのであれば，大きければ大きいほど目的関数を小さくできます．しかし，線形計画問題には制約条件があるので，非基底変数の値は制約条件を満たしていなければならないので限界があります．
先ほどの手順１では目的関数の係数を見ましたが，この手順２では制約条件の係数を調べます．
(a) 制約条件の係数がすべて負の場合
求めた非基底変数の制約条件の係数がすべて負の場合は，非基底変数の値をいくらでも大きくできるため解を求めることができません．
例えば，手順1で目的関数を小さくできる変数に\(x_{1}\)が選ばれていたとします．そして，この時の制約条件が以下のようになっていたとします．
\begin{eqnarray}
Bx_{B}+Nx_{N}=b
\end{eqnarray}
\begin{eqnarray}
B=
\begin{bmatrix}
1&0\\
0&1
\end{bmatrix},\
N=
\begin{bmatrix}
-8&2\\
-3&3
\end{bmatrix},\
b=
\begin{bmatrix}
9\\
12
\end{bmatrix}\\
x_{B}^{T}=
\begin{bmatrix}
x_{3}& x_{4}
\end{bmatrix},\
x_{N}^{T}=
\begin{bmatrix}
x_{1}& x_{2}
\end{bmatrix}\\
\end{eqnarray}
この場合，制約条件の\(x_{1}\)の係数は’-8’と’-3’なのですべて負の値になっています．このとき非基底変数\(x_{1}\)はどのような値になるのか調べてみます．
求め方は簡単です．制約条件の手順１で選んだ非基底変数以外の非基底変数をすべて0と置いて，基底変数について解けばいいだけです．
つまり，手順１で選ばれた非基底変数\(x_{1}\)以外の非基底変数\(x_{2}\)を0と置いて，基底変数\(x_{3},\ x_{4}\)について解きます．
\begin{eqnarray}
\begin{bmatrix}
1&0\\
0&1
\end{bmatrix}
\begin{bmatrix}
x_{3}\\
x_{4}
\end{bmatrix}+
\begin{bmatrix}
-8&2\\
-3&3
\end{bmatrix}
\begin{bmatrix}
x_{1}\\
0
\end{bmatrix}=
\begin{bmatrix}
9\\
12
\end{bmatrix}
\end{eqnarray}
まずは1行目の\(x_{3}\)について解きます．
\begin{eqnarray}
x_{3}-8x_{1}&=&9\\
x_{3}&=&8x_{1}+9
\end{eqnarray}
次に２行目のx_{4}について解きます．
\begin{eqnarray}
x_{4}-3x_{1}&=&12\\
x_{4}&=&3x_{1}+12
\end{eqnarray}
ここで，変数は非負制約があるので上の２式は以下のような不等式になります．
\begin{eqnarray}
8x_{1}+9&\geq&0\\
3x_{1}+12&\geq&0
\end{eqnarray}
これを\(x_{1}\)について解くと以下のようになります．
\begin{eqnarray}
x_{1}&\geq&-\frac{9}{8}\\
x_{1}&\geq&-4
\end{eqnarray}
この２つの不等式はどちらも満たしていなければ，変数の非負という制約がみたされないので，この２式を満たす変数\(x_{1}\)の値を求めなければなりません．しかし，この不等式では\(x_{1}\)の値が\(-\frac{9}{8}\)以上であれば良いということになります．さらに\(x_{1}\)にも非負の制約\(\geq 0\)があるので，結局\(x_{1}\)は０以上の値であれば何でもいいことになります．先ほども述べましたが，最適解とは最も目的関数を小さくできる解のことを言います．なので，\(x_{1}\)の解は\(\infty\)ということになってしまいます．これは最適解がないということを意味します．
このように制約条件の係数のすべてが正の値ではなく，一つでも負の値があれば\(x_{1}\leq \cdots\)という形になるので，変数に上限を設けることができます．
すべての係数が正の値の場合は上記のように解がないので，ここで計算を終了します．
(b) 制約条件の係数の中に正のものがある場合
この場合は上の(a)とは違い，非基底変数の値に限界があるため，その限界の値に非基底変数を設定すれば目的関数を最小化できます．
例えば，先ほどの例題では制約条件が以下のようになっていました．
\begin{eqnarray}
Bx_{B}+Nx_{N}=b
\end{eqnarray}
\begin{eqnarray}
B=
\begin{bmatrix}
1&0\\
0&1
\end{bmatrix},\
N=
\begin{bmatrix}
8&2\\
3&3
\end{bmatrix},\
b=
\begin{bmatrix}
9\\
12
\end{bmatrix}\\
x_{B}^{T}=
\begin{bmatrix}
x_{3}& x_{4}
\end{bmatrix},\
x_{N}^{T}=
\begin{bmatrix}
x_{1}& x_{2}
\end{bmatrix}\\
\end{eqnarray}
したがって，手順１で目的関数を小さくできる非基底変数\(x_{2}\)の制約条件の係数は’2’と’3’ですべて正であるから(b)の場合に該当します．つまり，非基底変数\(x_{2}\)は制約条件によって限界があるので解を求めることができます．
実際に\(x_{2}\)の値を求めてみましょう．
手順１で選んだ非基底変数\(x_{2}\)以外の非基底変数\(x_{1}\)を0と置いて，基底変数\(x_{3},\ x_{4}\)について解きます．
\begin{eqnarray}
\begin{bmatrix}
1&0\\
0&1
\end{bmatrix}
\begin{bmatrix}
x_{3}\\
x_{4}
\end{bmatrix}+
\begin{bmatrix}
8&2\\
3&3
\end{bmatrix}
\begin{bmatrix}
0\\
x_{2}
\end{bmatrix}=
\begin{bmatrix}
9\\
12
\end{bmatrix}
\end{eqnarray}
まずは１行目，\(x_{3}\)について解きます．
\begin{eqnarray}
x_{3}+2x_{2}&=&9\\
x_{3}&=&-2x_{2}+9
\end{eqnarray}
次に２行目のx_{4}について解きます．
\begin{eqnarray}
x_{4}+3x_{2}&=&12\\
x_{4}&=&-3x_{2}+12
\end{eqnarray}
ここで，変数は非負制約があるので上の２式は以下のような不等式になります．
\begin{eqnarray}
-2x_{2}+9&\geq&0\\
-3x_{2}+12&\geq&0
\end{eqnarray}
これを\(x_{2}\)について解くと以下のようになります．
\begin{eqnarray}
x_{2}&\leq&\frac{9}{2}\\
x_{2}&\leq&4
\end{eqnarray}
この２つの不等式はどちらも満たしていなければ，変数の非負という制約がみたされないので，この２式を満たす変数\(x_{2}\)の値を求める必要があります．また，目的関数の値を効率的に小さくしたいのでこの変数\(x_{2}\)の値はできるだけ大きくしたいです．
したがって，上の２つの不等式を同時に満たす\(x_{2}\)の最大値は４ということになります．この時の他の変数の値は，制約条件に\(x_{2}=4\)を代入することで求められます．
\begin{eqnarray}
x_{1}=0,\ x_{3}=1,\ x_{4}=0
\end{eqnarray}
これが現時点での最適解になります．
手順3：新たな実行可能基底形式を求める
実行可能基底形式では非基底変数を０と置いて解を求めます．しかし，上記の手順によって非基底変数の値を０以外の値にすることで目的関数を小さくできることがわかりました．
目的関数の値を小さくできるのにしないのはもったいないです．そこで，手順１で選んだ非基底変数を基底変数に入れて，不要な基底変数を非基底変数に入れます．この時，不要な基底変数というのは手順２で０となることがわかった変数のことです．
基底変数と非基底変数を入れ替えて実行可能基底形式を求める方法を例題で確認します．例題では手順1で非基底変数\(x_{2}\)を選択し，手順2でその値を4とすることで基底変数\(x_{4}\)が０になりました．なので，\(x_{2}\)と\(x_{4}\)を入れ替えます．そうすると，制約条件は以下のようになります．
\begin{eqnarray}
\begin{bmatrix}
1&2\\
0&3
\end{bmatrix}
\begin{bmatrix}
x_{3}\\
x_{2}
\end{bmatrix}+
\begin{bmatrix}
8&0\\
3&1
\end{bmatrix}
\begin{bmatrix}
x_{1}\\
x_{4}
\end{bmatrix}=
\begin{bmatrix}
9\\
12
\end{bmatrix}
\end{eqnarray}
実行可能基底形式を求めるには基底変数の係数を単位行列にする必要があります．そのために，まず２行目を\(\frac{1}{3}\)倍します．
\begin{eqnarray}
\begin{bmatrix}
1&2\\
0&1
\end{bmatrix}
\begin{bmatrix}
x_{3}\\
x_{2}
\end{bmatrix}+
\begin{bmatrix}
8&0\\
1&\frac{1}{3}
\end{bmatrix}
\begin{bmatrix}
x_{1}\\
x_{4}
\end{bmatrix}=
\begin{bmatrix}
9\\
4
\end{bmatrix}
\end{eqnarray}
そして１行目から２行目の２倍を引きます．
\begin{eqnarray}
\begin{bmatrix}
1&0\\
0&1
\end{bmatrix}
\begin{bmatrix}
x_{3}\\
x_{2}
\end{bmatrix}+
\begin{bmatrix}
6&-\frac{2}{3}\\
1&\frac{1}{3}
\end{bmatrix}
\begin{bmatrix}
x_{1}\\
x_{4}
\end{bmatrix}=
\begin{bmatrix}
1\\
4
\end{bmatrix}
\end{eqnarray}
以上が新たな実行可能基底形式になります．
手順4：新たな目的関数を求める
一部の非基底変数の値が決まったので評価関数を適切な方に変形します．
目的関数は基底変数\(x_{B}\)と非基底変数\(x_{N}\)を用いて以下のように表されていました．
\begin{eqnarray}
w=c_{B}^{T}x_{B}+c_{N}^{T}x_{N}
\end{eqnarray}
ここで，基底変数\(x_{B}\)は制約条件より以下のように求めることができます．
\begin{eqnarray}
Bx_{B}+Nx_{N}&=&b\\
x_{B}&=&B^{-1}b-B^{-1}Nx_{N}
\end{eqnarray}
実行可能基底形式では基底変数の係数\(B\)は単位行列なので，以下のようになります．
\begin{eqnarray}
x_{B}=b-Nx_{N}
\end{eqnarray}
この式を目的関数に代入します．
\begin{eqnarray}
w&=&c_{B}^{T}x_{B}+c_{N}^{T}x_{N}\\
&=&c_{B}^{T}(b-Nx_{N})+c_{N}^{T}x_{N}\\
&=&c_{B}^{T}b+(c_{N}^{T}-c_{B}^{T}N)x_{N}
\end{eqnarray}
この式を用いることで新たな目的関数を求めることができます．
ここで，最適解を求めるために計算を反復すると目的関数に定数項\(w’\)が現れます．この場合は，目的関数を更新する際に定数項\(w’\)も加える必要があるので注意してください．
\begin{eqnarray}
w=w’+c_{B}^{T}b+(c_{N}^{T}-c_{B}^{T}N)x_{N}
\end{eqnarray}
例題の場合はもともとの目的関数は
\begin{eqnarray}
w=c_{B}^{T}x_{B}+c_{N}^{T}x_{N}
\end{eqnarray}
\begin{eqnarray}
c_{B}^{T}=
\begin{bmatrix}
0&0
\end{bmatrix},\
c_{N}^{T}=
\begin{bmatrix}
-2&-3
\end{bmatrix}\\
x_{B}^{T}=
\begin{bmatrix}
x_{3}& x_{4}
\end{bmatrix},\
x_{N}^{T}=
\begin{bmatrix}
x_{1}& x_{2}
\end{bmatrix}\\
\end{eqnarray}
でした．上記の手順で基底変数が変わったので以下のようになります．
\begin{eqnarray}
w=c_{B}^{T}x_{B}+c_{N}^{T}x_{N}
\end{eqnarray}
\begin{eqnarray}
c_{B}^{T}=
\begin{bmatrix}
0&-3
\end{bmatrix},\
c_{N}^{T}=
\begin{bmatrix}
-2&0
\end{bmatrix}\\
x_{B}^{T}=
\begin{bmatrix}
x_{3}& x_{2}
\end{bmatrix},\
x_{N}^{T}=
\begin{bmatrix}
x_{1}& x_{4}
\end{bmatrix}\\
\end{eqnarray}
これを先ほどの目的関数の更新式に代入します．
\begin{eqnarray}
w&=&w’+c_{B}^{T}b+(c_{N}^{T}-c_{B}^{T}N)x_{N}\\
&=&0+
\begin{bmatrix}
0&-3
\end{bmatrix}
\begin{bmatrix}
1\\
4
\end{bmatrix}+\left(
\begin{bmatrix}
-2&0
\end{bmatrix}-
\begin{bmatrix}
0&-3
\end{bmatrix}
\begin{bmatrix}
6&-\frac{2}{3}\\
1&\frac{1}{3}
\end{bmatrix}\right)
\begin{bmatrix}
x_{1}\\
x_{4}
\end{bmatrix}\\
&=&-12+(
\begin{bmatrix}
-2&0
\end{bmatrix}-
\begin{bmatrix}
-3&1
\end{bmatrix})
\begin{bmatrix}
x_{1}\\
x_{4}
\end{bmatrix}\\
&=&-12+
\begin{bmatrix}
1&1
\end{bmatrix}
\begin{bmatrix}
x_{1}\\
x_{4}
\end{bmatrix}\\
&=&-12+x_{1}+x_{4}
\end{eqnarray}
以上のようにして新たな目的関数を求めることができました．
手順5：手順１からやり直す
以上の手順によって新たな実行可能基底形式と目的関数を求めることができました．これらを基にもう一度手順１から計算していきます．
単体法ではこのようにして実行可能基底形式と目的関数を更新していくことで最適解を求めることができます．
先ほどの例では，手順１に戻って目的関数の非基底変数\((x_{1},\ x_{4})\)の係数を調べるとどちらも性の値となっています．係数が負の値ではないので目的関数をこれ以上小さくすることができません．したがって，ここで計算を終了し，この時の解がこの問題の最適解ということになります．
この時の解とは手順２で求めた
\begin{eqnarray}
x_{1}=0,\ x_{2}=4,\ x_{3}=1,\ x_{4}=0
\end{eqnarray}
のことを言います．
スラック変数は問題を解くために導入した変数なので解には関係ありません．なので最適解とその時の目的関数の値は以下のようになります．
\begin{eqnarray}
x_{1}=0,\ x_{2}=4,\ w=-12
\end{eqnarray}
まとめ
線形計画問題の解法の一つである単体法を例題を解きながら解説しました．
単体法の手順をまとめると以下のようになります．
1-a. すべて正の場合は計算終了
1-b. 負の値がある場合はその中で最も小さくなる変数を求める
2. 求めた非基底変数の値を求める
2-a. 制約条件の係数がすべて負の場合は計算終了
2-b. 制約条件の係数に負の値がある場合は非基底変数の値を求める
3. 新たな実行可能基底形式を求める
4. 新たな目的関数を求める
5. 手順１からやり直す
続けて読む
今後も最適化手法の解説を当ブログで行っていく予定なので，勉強したい方はチェックしてください．ただ，研究の合間に更新しているので更新頻度は低いかもしれませんがお許しください．
Twitterでは記事の更新情報や活動の進捗などをつぶやいているので気が向いたらフォローしてください．
YouTubeでも制御工学や電子工作などの解説をしているので，ぜひのぞいてみてください．
それでは最後まで読んでいただきありがとうございました．
コメント