ぷろえんじにあ
TRIZ・ITソフトウェアキーワードリスト TOP
1 解説
Karmarkar法は、シンプレックス法のように許容領域の端点(基底解)を探索するのではなく許容領域の内点の点列を生成するところに特徴がある。つまり、許容領域の任意の内点xから出発し、適当なステップ幅αを用いると、xの点列は最適解に収束することを示した。この方法は、大規模な問題に対してシンプレックス法よりも高速計算ができる。
1984 年に Karmarkarによって提案された新解法は、理論的に多項式オーダの計算量で線形計画問題を解くことができるだけでなく、当時線形計画問題を解く方法の代名詞であった単体法よりも実際に高速に問題を解けるということで、多くの研究者等の注目を集めている。.この解法が起爆剤となり、その後m多くの内点法が研究されるようになった。
2 所見
特になし