トップ > 数理計画用語集 > 基底行列

数理計画用語集

基底行列

読み:きていぎょうれつ
関連単体法

単体法における用語の一つ.n 行 m 列の係数行列におけるn 本の独立な列ベクトルから構成される正則行列のことをいう.

基底行列が,その逆行列と右辺ベクトル(定数ベクトル)の積が非負の場合,実行可能基底解と呼ばれる実行可能解が得られる.最適解は,もし存在すれば実行可能基底解の中にあることが知られている.

単体法における一反復では,基底行列の列ベクトルと非基底行列の列ベクトルを入れ替える.その際,毎回逆行列を計算しなおすのではなく,LU 分解を更新することによって高速化が図れる.