前回
2. 線形計画と凸2次計画
まずはシンプルで分かりやすいこともあり、線形計画(および凸2次計画)を扱う。また線形問題の中でという前提で双対性など他の最適化問題にも当てはまる理論を少し扱う*1。
2.2 双対性
線形計画の理論の核である双対性を議論する*2。
2.2.1 双対問題
不等式で書かれる制約条件は、上界を考えていくと、その不等式制約を等式制約に書き換えた新たな問題を考えることができる。このように等式問題に書き換えた問題は、元の問題に対して双対問題という。また元の問題を主問題と呼ぶ。主問題を双対問題に書き換えるための変数変換をスラック変換という。双対問題の双対問題は主問題である。
具体的には、主問題
に対して、
を双対問題という*3。
2.2.2 双対定理
主問題と双対問題には密接な関係がある。
定理2.2 弱双対定理 主問題
の任意の実行可能解および双対問題
の任意の実行可能解に対して、条件
が成り立つ。
が成り立つ。 )
もし主問題の目的関数の値をいくらでも小さくできるのであれば、弱双対定理より双対問題は実行可能解を持たないことが分かる。また双対問題の目的関数の値がいくらでも大きくできるのであれば、主問題は実行可能解を持たない。さらに主問題および双対問題の実行可能解であって、目的関数の値が一致するものが見つかれば、それらは最適解である。次の定理はこれの逆を保証する。
定理2.3 強定常定理 主問題
および双対問題
の双方が実行可能解を持つならば、両問題に最適解が存在し、最適解は一致する。
次に線形計画問題の最適解を特徴づける最適性条件を述べる。
定理2.4 最適性条件
の実行可能解とし、を双対問題
の実行可能解とする。これらがそれぞれの問題の最適解であるためには
が必要十分である。
以上の条件をまとめると、線形計画問題の最適解が満たすべき必要十分条件は、
で与えられる。この3つ目の条件を相補性条件といい、主問題の不等式制約と双対問題の不等式制約
の少なくとも一方が最適解において有効であることを意味する。
仮に最適解において、各について
および
のどちらが
になるかを知っていたとすると、
および
という式が少なくとも
本存在する。他に
は
本および
は
本の等式であるから、全部で
本の線形方程式が存在する。未知数の数も
の
個あるから、最適解を得るにはこの
本の線形方程式を解けばよい。無論、最適解において
および
のどちらが
なのかを事前に知ることは出来ない。すなわち最適解においてどの不等式制約が有効であるのかを見つけることが線形問題を解くことの本質であると言える。
2.3 線形計画問題の解法
線形計画問題には、単体法と内点法という代表的な解法が存在する。
2.3.1 単体法
標準形
を数値的に解くための方法として単体法が存在する。これは実行可能基底解を順々に辿ることで線形計画問題を解く手法で、1947年に
が提案したもので、未だに有用な数値解法である。
単体法の基本的な考えは、1組の実行可能基底解が与えられたときに目的関数値がより低くなるような新しい実行可能基底解を効率よく求めることである。線形計画問題の基本定理から、実行可能基底からの中に最適解が存在する。実行可能基底解の選び方は高々通りであるから、実行可能基底解を順に求めていくことで有限回の手順で最適解に到達すると期待される。
が
行列(
)
で階数は
だとして、標準的な形態での線形計画問題
を考える。
1組の基底解が与えられているとする。簡単のために行列の初めの
本の列ベクトルが線形独立だと仮定すると、基底行列と基底変換は
である。このときは正則である。また非基底変数に対応する部分を
とおく。更に目的関数の係数も同様に
とおけば、
と書ける。このとき等式制約は
と書けるから、両辺の左から
を掛けることで
を得る。これより基底変数は非基底変数
を用いて
と表せる。これを目的関数に代入することで
を得る。また単体乗数を用いれば、
とも表すことができる。
以上を踏まえ、
とおけば、目的関数および等式制約は
と整理できる。この形式を基底形式、辞書もしくは正準形と呼ぶ。またを相対費用係数と呼ぶ。基底形式において特に
であるとき、実行可能基底形式という。このときに非基底変数
とおけば現時点の実行可能基底変数
と目的関数値
が得られる。したがって1つの実行可能基底形式は1組の実行可能基底解
を決定できる。
ここでならば既に最適解が得られたことになるから、ここでは
の成分のうち負のものが存在すると仮定する。そのうちの1つを
とする。これと対応する
の成分
を少しだけ増加させると、主問題の目的関数の値は減少する。このように変更した
を用いて
と定めれば、等式制約は満たされたままである。このとき
の成分のうち、目的関数の値が減少するものが存在しなければ、
をどれだけ大きくしても不等式制約
も満たされたままになる。そのような場合を除外すれば、
の成分のいずれかが最初に
に到達するまで
を増やす。これで
になった成分が非基底変数に変化し、
が基底変数に変わった新たな実行可能基底解が得られた。このような手続を枢軸変換という。
枢軸変換により得られた実行可能基底解が非退化であれば、ある実行可能基底解から出発して枢軸変換を繰り返すことで主問題の目的関数の値はどんどん小さくなる。これを有限回繰り返すことで最適解に到達できる。これが単体法の基本的な考え方である*4。
最適解に到達したか否かを具体的に判定する方法を考える。実行可能基底形式を吟味することで、3つの場合が考えられ、2つ目は更に2つに分けられる。
(1) | 基底形式における |
|
(2) | (1)が成り立たない場合、すなわち |
|
(a) | ||
(b) | ||
(3) |
以上をまとめることで以下の定理を得る。
定理2.5 単体法の原理 実行可能な基底形式
について以下が成り立つ。