線形計画問題に対する双対内点主シンプレックス法

概要

論文の詳細を見る
本論文では、線形計画問題に対する双対内点主シンプレックス法(DIPS法)を提案する。DIPS法は、標準形の線形計画問題maximize c^Tx subject to x∈ X={x≧0|Ax=b}を解くある列選択規則を持ったシンプレックス法と解釈できる一方、その双対問題minimize b^Ty subject to y∈ Y={y|A^Ty≧c}を解く内点法にもなっている。ここで、主実行可能領域Xと双対実行可能領域Yが共に空でないと仮定する。すなわち双対定理より、主問題・双対問題ともに最適解が存在する。DIPS法は、双対問題を解く内点法とみなしたとき以下の様な動きをする。双対問題の目的関数の負の方向-bが重力方向と一致し、垂直座標が目的関数値に対応しているとする。さらに、双対実行可能領域Yと同じ形の容器を考え、それにある深さの水が満たされているとする。このとき、双対問題の最適解に対応しているこの容器の底に穴を開ける。最終的に容器の水は空になるが、各深さに於ける水中に存在する極大な球を考える。水が減るに連れて、その中心は区分的線形な軌跡を描きながら容器の底、すなわち、双対問題の最適解に近づく。DIPS法は、この中心の軌跡をたどることによって最適解を求める。点列{y^k|k=1、2、……}を上で考えた極大球の中心の軌跡の節点の点列としたとき、DIPS法はそれらに対応した主実行可能基底の列{x^k|k=1、2、……}を生成し、これらは以下の様な性質を持っている。(a)kが増えるに連れて、b^Ty^kは単調に減少し、c^Tx^kは単調非減少する。(b)各繰返しkに於いて、b^Ty^<k+1>とc^Tx^kはそれぞれ未知な最適値の上界値と下界値になっている。(c)双対ギャップb^Ty^<k+1>-c^Tx^kは単調減少する。(d)有限回の繰返しで最適解を求める。
社団法人日本オペレーションズ・リサーチ学会の論文

線形計画問題に対する双対内点主シンプレックス法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク