基底行列

基底行列#

  • 読み: きていぎょうれつ

  • 英名:

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

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

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

関連