数理最適化（単体法①）
単体法（Simplex method）についてまとめていきたいと思います。
単体法は、線形計画問題を解くための方法の1つです。
長年にわたって使用されている実用的な方法です。
単体法が使われる理由
・高速に解を見つけることができる
・アルゴリズムが理解しやすい
・さまざまな制約条件や目的関数に対応できる
線形計画問題は、目的関数と呼ばれる線形関数を最大化または最小化する問題です。
この問題のキーポイントは、解が凸多角形（すなわち凸集合）の頂点の一つに存在するということです。（線形計画問題を参照）
全頂点を調べる方法
凸多角形の各頂点で目的関数の値を計算し、その中から最適な値を見つけ出します。
この方法は直感的で理解しやすいですが、頂点の数が多い場合、計算量が非常に増加します。
頂点の数は、制約条件の数をm、変数の数をnとしたとき、理論的には最大で
$$
\begin{pmatrix} m+n \\ n \end{pmatrix} = \cfrac{(m+n)!}{m!n!}
$$
となります。
例えば、制約条件が20、変数が10あったとします。
そうすると、m=20、n=10 となり、
$$
\begin{pmatrix} 30 \\ 10 \end{pmatrix} = \cfrac{30!}{20!10!} = 30,045,015
$$
30,045,015個の頂点を求めなければなりません。
計算量が膨大になります。
単体法
単体法は、この凸多角形の頂点を効率的に巡るアルゴリズムです。
頂点から頂点へと移動しながら、最適解に近づいていきます。
この方法の利点は、不要な頂点を調査せずに、最適解へと直接的に近づけることです。
そのため、比較的計算量が少なくて解を求めることができます。
下図は、全頂点を調べる方法と、単体法との探索との比較のイメージを視覚化したものです。
赤線が単体法での探索経路です。
全頂点を調べる場合と比べ、単体法では少ない頂点の探索で最適解を求めることができます。
単体法の流れ
最適化問題を標準形へ変換
問題の制約から基底解を選択
基底解から出発して、目的関数を改善できる方向に解を移動
最適解に到達したかどうかをチェック
知らない言葉がいくつか出てきました。
これらも含め、単体法を解いていくときに必要な用語を先にまとめていきたいと思います。
用語
標準形
スラック変数 と サープラス変数
基底解 と 基底変数・非基底変数
標準形
標準形とは、以下の条件をすべて満たすものです。
・目的関数：最大化問題の線形関数
・制約条件：全て等式（＝）で表現 ※左辺＝右辺という形式
左辺、右辺、共に非負
・変数：全ての変数が非負
※非負とは、0以上の値しかとらないということ
例えば、以下のようなものを標準形と言います。
目的関数：最大化 z=3x+5y
制約条件：2x+3y+a=6
4x+y+b=4
x≥0, y≥0
スラック変数 と サープラス変数
線形計画問題を標準形に変換するときに、制約条件を等式（＝）に変換しないといけません。
その際に用いるのが「スラック変数」「サープラス変数」です。
線形計画問題の標準形への変換の流れと合わせて説明します。
[線形計画問題]
目的関数：最大化 z=3x+5y
制約条件：2x+3y≤6
4x+y≥4
y≤3
x≥0, y≥0
これを、標準形に変換します。
制約条件の不等式を等式に変換する際、新たな変数を追加することで等式に変換できます。
この新たな変数を、「スラック変数」「サープラス変数」と言います。
スラック変数、サープラス変数を用いると、以下のように変換できます。
制約条件：2x+3y+s1=6 ※s1≥0 はスラック変数
4x+y−s2=4 ※s2≥0 はサープラス変数
y+s3=3 ※s3≥0 はスラック変数
不等式が≤の場合の変数：スラック変数
不等式が≥の場合の変数：サープラス変数
スラック変数・サープラス変数は、等式が成り立つように値を変化させる変数です。
基底解 と 基底変数・非基底変数
先ほどのスラック変数・サープラス変数の例で示した制約条件には、変数が5個（x, y, s1, s2, s3）存在します。
5個の変数を3個の数式で解くのは難しいです。
変数を減らすことで、問題を解くことができます。
その変数を減らす方法が、特定の変数を0に固定化してしまうという手法です。
制約条件：2x+3y+s1=6
4x+y−s2=4
y+s3=3
これの、s1とs2を0に固定してしまうとします。
そうすると、以下の式となります。
制約条件：①2x+3y=6
②4x+y=4
③y+s3=3
①と②から、x=0.6, y=1.6 となることがわかります。
③から、s3=1.4 となることがわかります。
このように、多くの解の中の1つを求めることが可能となります。
0に固定した変数を「非基底変数」、
固定しなかった変数を「基底変数」
と呼びます。
そして、この時の目的関数の解を「基底解」と呼びます。
この基底解が、0以上の時有効な解となります。
このような有効な解のことを、「実行可能な基底解」と呼びます。
流れと用語がわかったので、例題を解きながら単体法の解き方を学んでいこうと思います。
次回、単体法②でまとめていきます。
この記事が気に入ったらサポートをしてみませんか？