線形計画問題に対する内点法とその応用に関する研究
【研究分野】社会システム工学
【研究キーワード】
線形計画問題 / 内点法 / カーマーカー法 / 数理計画問題 / 組み合せ最適化 / カ-マ-カ-法
【研究成果の概要】
平成3年度および4年度に計画した研究目標は以下通りであった。
1.主双対内点法の計算効率の向上および評価に関する基礎研究。
2.非凸型2次計画問題および組合せ最適化問題への内点法の適用に関する基礎研究。
3.内点法を中心とする線形計画法のソフトウェアに関する基礎研究。
4.内点法の一般化に関する基礎研究。
研究目標1に関しては,
(1)内点法の各反復でのステップ長をコントロールする新手法の提案,
(2)内点法の初期点に関する研究
を行い理論的な成果を得るとともに,研究目標3と関連して,これらの成果を主双対内点法のソフトウェアに組み込んだ計算実験を行いその有効性を検証した。研究目的2に関しては、非凸型2次計画問題および組合せ最適化問題そのものについての研究成果はあげたが、内点法を適用出来るまでには研究は進んでいない。これはこれらの問題がもともと非常に難しい問題であることが主な原因であり、今後もこの方向で研究を続ける必要がある。研究目標の4に関しては、上述の線形計画問題に関する結果を一般の凸型計画問題に拡張することが出来、充分な成果をあげたと言える。
【研究代表者】