トップ > 数理計画用語集 > 完全単模行列

数理計画用語集

完全単模行列

読み:かんぜんたんもぎょうれつ
英名:Totally Unimodular Matrix
関連行列単体法ヒッチコック輸送問題

任意の小行列式が 0, 1, -1 の値をとる整数行列のことをいう.

整数線形計画問題において,係数行列が完全単模行列となるとき,連続緩和問題の最適基底解が整数計画問題最適解になる.したがって,単体法で解くと整数解が得られる.これは,完全単模行列の任意の基底行列は,逆行列が再び整数行列になっていることから分かる.