標準形と基準形

線形計画問題の一般形は, 異なる向きの不等号や 制約条件が付いた変数と制約条件のない変数が混在しているために, 数学的に取り扱いにくい。そこで, ふつうは, 線形計画問題の一般形を特定の標準的な形に変換してから解く。 標準的な形としてよく用いられるのは, 標準形と呼ばれるものと, 基準形と呼ばれるものである。 以下でこれらについて説明する。 以下では, 特に断らない限り, は行列の実行列, は次元のベクトル, , は次元のベクトルとする。 また, が行列の実行列であることを という記法であらわし, が次元の実ベクトルであるということを という記法であらわすi) 。 さらに, 行列の第番目の列ベクトルをなどと書き, ベクトル, などの第要素をそれぞれ, などと書く。 また, とがともに次のベクトルであるとき, という記法によって, ベクトルの各成分がベクトルの対応する成分以上である, すなわ