みなさん，こんにちは
おかしょです．
最適化計算には様々な種類があります．
線形で表現できる問題や非線形で表される問題，さらに制約があるものないものなどがあります．
今回は，それらの中の線形計画問題の解き方について解説していきます．
最適化について学習し始めた方や復習をしたい方には参考になると思います．
この記事を読むと以下のようなことがわかる・できるようになります．
- 最適化手法の基本
- 基本定理とは
- 最適化計算の流れ
この記事を読む前に
最適化手法は様々ありますが，すべては線形計画問題の標準形を対象として考えられています．
線形計画問題の標準形への変換方法をご存じでない方は，以下の記事を先に読んでおくことをおすすめします．
基本定理とは
最適化問題を解くための手法はたくさんあります．
例えば，単体法や二段階法，内点法などがあります．
この記事で解説する線形計画問題の基本定理はすべてのアルゴリズムの基礎となっています．
そのため，最適化計算を学び始めたばかりの方は基本定理をまず最初に学ぶ必要があります．
この基本定理とは，以下のような定理となっています．
線形計画問題の標準形が与えられている時
- 実行可能解が存在するなら，実行可能基底解が必ず存在する．
- 最適解が存在するなら，実行可能基底解の中に最適解が存在する．
上記のものが線形計画問題の基本定理です．
いきなり実行可能解や実行可能基底解などと言われても意味が分からない方もいると思うので，解説していきます．
線形計画問題の標準形
まず，線形計画問題の標準形というのは
$$ min \ w = c^{T}x $$
$$ subject \ to\ Ax=b\ (x\geq0) $$
このような形をしています．
実行可能解
実行可能解というのは，字を見ればわかるかもしれませんが制約条件\(Ax=b\ (x\geq0)\)を満たす\(x\)のことを言います．
実行可能基底解
そして，実行可能基底解というのは説明が難しいので具体例を用いて説明します．
例えば，以下のような線形計画問題を考えます．
$$ min \ w = 2x_{1}+3x_{2}+12x_{3} $$
\begin{eqnarray} subject \ to\ 8x_{1}+2x_{2}+4x_{3}-x_{4}&=& 9 \\ 3x_{1}+3x_{2}+x_{3}+x_{5}&=& 12\\ x_{1}\geq 0, x_{2}\geq 0, x_{3}&\geq& 0, x_{4}\geq 0, x_{5}\geq 0, \end{eqnarray}
この形は線形計画問題の標準形となっていて，先程の式に当てはめると
\begin{eqnarray}
min \ w &=& c^{T}x\\
subject \ to\ Ax &=& b\ (x\geq0)\\
x=
\begin{bmatrix}
x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ x_{5}\\
\end{bmatrix}
&,&\ c=
\begin{bmatrix}
2\\ 3\\ 12\\ 0\\ 0\\
\end{bmatrix}\\
A=
\begin{bmatrix}
8 & 2 & 4 & -1 & 0\\
3 & 3 & 1 & 0 & 1\\
\end{bmatrix}
&,&\ b=
\begin{bmatrix}
9\\ 12\\
\end{bmatrix}
\end{eqnarray}
このとき，等式制約の係数\(A\)の中から\(rank\ A\)本の線形独立なベクトルを一組選びます．
このベクトルを並べた時にできる正則行列のことを基底行列\(B\)と言います．
上の問題の場合，\(rank\ A=2\)であるからてきとうなベクトルとして1列目と2列目を選び出します．
これを並べると，基底行列\(B\)ができます．
$$ B =
\begin{bmatrix}
8 & 2\\
3 & 3\\
\end{bmatrix} $$
この基底行列に対応する変数を基底変数と呼びます．
つまり，\(Ax=b\)の計算をした時に\(A\)の1列目と2列目が掛けられる変数は\(x_{1}\)と\(x_{2}\)であるから，これらが基底変数\(x_{B}\)となります．
そして，それ以外の変数\(x_{3}\)，\(x_{4}\)，\(x_{5}\)は非基底変数(x_{N}\)と呼ばれます．
この基底変数と非基底変数を縦に並べたベクトルを基底解と言い
$$ x =
\begin{bmatrix}
x_{B}\\
x_{N}\\
\end{bmatrix} $$
この基底解の変数がすべて非負，つまり負ではない時の基底解を実行可能基底解と呼びます．
長くなりましたが，実行可能基底解というのはこういう変数のことを言って，基本定理によるとこの中に最適解が存在することになります．
最適解の求め方
この実行可能基底解というのは，基底変数の取り方によって複数存在します．
そのため，その複数ある実行可能基底解の中から最適解を選ばなければなりません．
この最適解を求める方法で最も簡単なものが，すべての実行可能基底解を求めて試してみるという方法です．
例えば，以下のような問題があったとします．
$$ min \ w = 2x_{1}+3x_{2} $$
\begin{eqnarray} subject \ to\ 8x_{1}+2x_{2}&\geq& 9 \\ 3x_{1}+3x_{2}&\leq& 12\\ x_{1}\geq 0, x_{2}&\geq& 0 \end{eqnarray}
この問題の標準形を求めると，以下のようになります．
$$ min \ w = 2x_{1}+3x_{2} $$
\begin{eqnarray} subject \ to\ 8x_{1}+2x_{2}-x_{3}&=& 9 \\ 3x_{1}+3x_{2}+x_{4}&=& 12\\ x_{1}\geq 0,x_{2}\geq 0, x_{3}&\geq& 0, x_{4}\geq 0 \end{eqnarray}
この問題を行列で表記すると次のようになります．
\begin{eqnarray}
min \ w &=& c^{T}x\\
subject \ to\ Ax &=& b\ (x\geq0)\\
x=
\begin{bmatrix}
x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\
\end{bmatrix}
&,&\ c=
\begin{bmatrix}
2\\ 3\\ 0\\ 0\\
\end{bmatrix}\\
A=
\begin{bmatrix}
8 & 2 & -1 & 0\\
3 & 3 & 0 & 1\\
\end{bmatrix}
&,&\ b=
\begin{bmatrix}
9\\ 12\\
\end{bmatrix}
\end{eqnarray}
行列\(A\)のrankは2なので基底変数を2つ選びます．
まずは\(x_{1}\)と\(x_{2}\)を選んでみます．
このとき，基底変数\(x_{B}\)，非基底変数\(x_{N}\)，基底行列\(B\)は以下のようになります．
$$ x_{B} =
\begin{bmatrix}
x_{1}\\
x_{2}\\
\end{bmatrix} ,\ x_{N}=
\begin{bmatrix}
x_{3}\\
x_{4}\\
\end{bmatrix} ,\ B=
\begin{bmatrix}
8 & -1\\
3 & 0\\
\end{bmatrix} $$
ここで，非基底変数のすべての要素をゼロとすると，等式制約から基底解を求めることができます．
$$ x_{N} =
\begin{bmatrix}
x_{3}\\
x_{4}\\
\end{bmatrix} =
\begin{bmatrix}
0\\
0\\
\end{bmatrix} $$
と置くと
$$ Ax=b \rightarrow Bx_{B}=b $$
となるから，基底変数\(x_{B}\)は
$$ x_{B} =
\begin{bmatrix}
x_{1}\\
x_{2}\\
\end{bmatrix} =
\begin{bmatrix}
\frac{1}{6}\\
\frac{23}{6}\\
\end{bmatrix} $$
と求められます．
従って，基底解は\(\begin{bmatrix}
1/6 & 23/6 & 0 & 0\\
\end{bmatrix}\)となります．
全ての要素が負ではないため，実行可能基底解でこれが最適解かもしれません．
まだ，この結果は最適解の候補なので注意してください．
候補から正真正銘の最適解になるには目的関数の値を比べる必要があります．
今回のように基底変数をとった時の目的関数の値は\(71/6\)です．
他の基底変数を試して，目的関数を求めた時に\(71/6\)よりも小さくなるものがなければ，今回の実行可能基底解が最適解ということになります．
それでは，他の基底変数の取り方を試してみましょう．
基底変数\(x_{1}\)と\(x_{3}\)を選んだ場合，基底解を先程と同様にして求めると\(\begin{bmatrix}
4 & 0 & 23 & 0\\
\end{bmatrix}\)となり，すべての要素が負ではないため実行可能基底解となります．
このときの目的関数は8です．
次に基底変数\(x_{1}\)と\(x_{4}\)を選んだ場合，基底解は\(\begin{bmatrix}
9/8 & 0 & 0 & 69/8\\
\end{bmatrix}\)となり，実行可能基底解となります．
このときの目的関数は9/4です．
次に基底変数\(x_{2}\)と\(x_{3}\)を選んだ場合，基底解は\(\begin{bmatrix}
0 & 4 & -1 & 0\\
\end{bmatrix}\)となります．
ここで，3要素目が負の値となりました．
従って，この基底解は実行可能基底解ではないので最適解の候補にはなりません．
次に基底変数\(x_{2}\)と\(x_{4}\)を選んだ場合，基底解は\(\begin{bmatrix}
0& 9/2 & 0 & -3/2\\
\end{bmatrix}\)となり，これも実行可能基底解ではありません．
最後に基底変数\(x_{3}\)と\(x_{4}\)を選んだ場合，基底解は\(\begin{bmatrix}
0 & 0 & -9 & 12\\
\end{bmatrix}\)となり，これも実行可能基底解ではありません．
ということは，最も目的関数を小さくできた基底変数の取り方は\(x_{1}\)と\(x_{4}\)を選んだ時でした．
従って，最適解はこのときの実行可能基底解なので\(\begin{bmatrix}
9/8 & 0 & 0 & 69/8\\
\end{bmatrix}\)となります．
最適解を図で確認
最後に目的関数や制約条件，基底解などを図で確認してみます．
今回の問題を図で表すと以下のようになります．
この図で灰色に塗りつぶされている部分は実行可能解を表しています．
オレンジの線と緑の線が制約条件の境界線
濃淡の異なる青い線は目的関数を表していて，色が濃いほど目的関数の値は低くなります．
この図を見ると明らかなように緑色の線と青色の線が\(x_{1}\)の軸上で交わる時が最適解となります．
今回求められた，最適解はその座標を表していることがわかります．
また，求められた実行可能基底解はすべて灰色の三角形の頂点の座標を表していることがわかります．
まとめ
この記事では例題を通して，線形計画問題の基本定理の解説を行ってきました．
最後にもう一度まとめると
線形計画問題の標準形が与えられている時
- 実行可能解が存在するなら，実行可能基底解が必ず存在する．
- 最適解が存在するなら，実行可能基底解の中に最適解が存在する．
これが線形計画問題の基本定理になります．
この定理を知らないと最適化計算のアルゴリズムを理解するのが難しくなりますので，必ず理解しましょう．
続けて読む
制御系の設計では最適化手法を用いたものが数多くあります．
このブログでは，最適化手法を用いていない制御系についても解説しています．
以下の記事ではPID制御について解説しているので，興味のある方は参考にしてください．
Twitterでは記事の更新情報や活動の進捗などをつぶやいているので気が向いたらフォローしてください．
それでは最後まで読んでいただきありがとうございました．
コメント