線形計画問題を標準形へ変換する方法

みなさん，こんにちは．
おかしょです．

この記事ではタイトルにある通り，線形計画問題を標準形へ変換する方法について解説していきます．

この記事を読むと以下のようなことがわかる・できるようになります．

標準形とは
線形計画問題を標準形に変換する方法

標準形とは
標準形にする方法
1. 不等式制約条件があった場合
2. 非負の制約条件があった場合
演習問題
まとめ
続けて読む
1. 共有:
2. 関連

標準形とは

線形計画問題を解くことができるアルゴリズムは様々な種類があります．
しかし，すべてのアルゴリズムは線形計画問題の標準形を解くように設計されています．

この標準形というのはどのような形式なのでしょうか．

まず，線形計画問題には様々な形があります．
例えば，等式制約がない線形計画問題，等式制約のある線形計画問題，不等式制約付きの線形計画問題などがあります．

最適化計算のアルゴリズムを構築するときに，線形計画問題のそれぞれの形に対して設計するのは非常に効率が悪いです．
そこで，線形計画問題の様々な形をすべて含むような標準形を決めて，その標準形に対してアルゴリズムを構築すれば，一つ一つアルゴリズムを構築する必要がなくなります．

このような，線形計画問題の基準となる形式を線形計画問題の標準形と言います．

線形計画問題の標準形は以下のように表されます．

$$ min \ w = c^{T}x $$

$$ subject \ to\ Ax=b\ (x\geq0) $$

上の式の$w$がこの線形計画問題の目的関数を表していて，この目的関数を最小化する$x$を求めるのが目的です．
また，subject toは制約条件のことで，等式制約や不等式先約を等式制約条件としてここにまとめられます．

不等式制約条件を制約条件として扱う方法については後程解説します．

標準形にする方法

ここからは具体例を使いながら，線形計画問題の標準形を求めていきます．

先程も述べましたが，制約条件はすべて等式制約条件としてまとめる必要があります．

不等式制約条件があった場合

例えば，以下のような不等式制約があったとします．

$$ x_{1}+3x_{2}<-5 $$

これを等式制約条件$(Ax=b)$に変換します．上の不等式を言葉で表すと

$x_{1}$と$x_{2}$の3倍を足し合わせると-5よりも小さくなる．

ということになります．これを言い換えると，

$x_{1}$と$x_{2}$の3倍に「何か」を足し合わせると-5になる．

とも言えます．この「何か」が小さければ小さいほど制約条件をぎりぎり満たすということになります．
この「何か」を$x_{3}$と置くと，不等式制約は以下のような等式制約に変換されます．

$$ x_{1}+3x_{2}+x_{3}=-5 $$

このときの$x_{3}(\geq 0)$のことをスラック変数と呼びます．

では，先程の不等式制約の不等号が逆向きであった場合はどのようになるでしょうか．

$$ x_{1}+3x_{2}>-5 $$

これを先程と同様に言葉で表すと

$x_{1}$と$x_{2}$の3倍を足し合わせると-5よりも大きくなる．

ということになります．これを言い換えると，

$x_{1}$と$x_{2}$の3倍に「何か」を引くと-5になる．

と言えます．これを式で表すと以下のようになります．

$$ x_{1}+3x_{2}-x_{3}=-5 $$

以上のように，不等式制約条件はスラック変数を導入することで等式制約条件に変換することができます．

非負の制約条件があった場合

線形計画問題の標準系はすべての変数は非負$\geq 0$であるとしています．
この非負$\geq 0$の制約条件がなかった場合，どのようにすれば標準形に変換できるのかを考えてみます．

このようなときは，スラック変数を二つ導入する必要があります．

例えば/(x_{1}\)という変数が非負の制約条件がなかった時，スラック変数$x_{2}$と$x_{3}$を導入すると

$$ x_{1}=x_{2}+x_{3} $$

と表すことができます．このとき，$x_{2}$と$x_{3}$は非負であるとします．
このようにすることで，標準形に変換することができますが
スラック変数が二つ必要なため，変数の数が2倍になるため計算量がその分多くなることに注意が必要です．

演習問題

以上の解説で，線形計画問題の標準形の求め方がわかったところで，知識を定着させるために以下のような線形計画問題を標準形に変換してみます．

$$ min \ w = 2x_{1}+3x_{2}+12x_{3} $$

\begin{eqnarray} subject \ to\ 8x_{1}+2x_{2}+4x_{3}&\geq& 9 \\ 3x_{1}+3x_{2}+x_{3}&\leq& 12\\ x_{1}\geq 0, x_{2}\geq 0, x_{3}&\geq& 0 \end{eqnarray}

スラック変数$x_{4}, x_{5} (\geq 0)$を導入すると，以下のような線形計画問題の標準形が求められます．

$$ 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}

まとめ

この記事では線形計画問題を標準形にする方法を解説しました．

線形計画問題の標準形はスラック変数を導入することで簡単に求められます．
最適化のアルゴリズムは標準形を基に設計されているので，このような変換作業は必ず必要になります．

続けて読む

最適化計算を使用すると，この記事で求めた標準形から最適解を求めます．

最適解を求める方法はさまざまですが，以下の記事では基本定理を利用して最適解を求めています．

Twitterでは記事の更新情報や活動の進捗などをつぶやいているので気が向いたらフォローしてください．

それでは最後まで読んでいただきありがとうございました．