ビッグMメソッド

オペレーションズ・リサーチにおいて、ビッグM法は単体法を用いて線形計画問題を解く手法です。ビッグM法は単体法を「より大きい」制約を含む問題に拡張します。これは、制約に、たとえ最適解が存在したとしても、その最適解には含まれない大きな負の定数を関連付けることによって行われます。

アルゴリズム

単体法は、線形最大化問題を解くための元祖であり、現在でも最も広く用いられている手法の一つです。最適目的関数を持つ点は、線形計画（LP）の実行可能領域の形状である単体の頂点上で到達する必要があることは明らかです。単体の頂点上の点は基底として表されます。したがって、基底を大域的最適値に到達するまで改善することを目的とする単体法を適用するには、まず実行可能基底を見つける必要があります。

自明な基底（すべての問題変数が0）は、必ずしも単体の一部ではありません。すべての制約（非負性を除く）が小なり制約であり、右辺に正の定数がある場合にのみ、Big M法は実現可能です。Big M法は、余剰変数と人工変数を導入してすべての不等式をその形に変換し、それによって単体を高次元に拡張して自明な基底で有効にします。LPの標準的な定式化に固有の問題変数に対する正値制約のため、単体は常に頂点となります。「Big M」は、人工変数に関連付けられた大きな数を指し、文字Mで表されます。

アルゴリズムの手順は次のとおりです。

不等式制約を乗算して、右側が正になるようにします。
問題が最小化である場合は、目的関数に -1 を掛けて最大化に変換します。
任意の「より大きい」制約に対して、余剰s _iと人工変数a _iを導入します(以下に示すように)。
大きな正の値 M を選択し、人工変数を乗算する形式の項を目的関数に導入します。
以下制約の場合、すべての制約が等式になるようにスラック変数s _{iを導入します。}
通常の単体法を使用して問題を解きます。

例えば、x + y ≤ 100 はx + y + s ₁ = 100 となり、x + y ≥ 100 はx + y − s ₁ + a ₁ = 100 となります。これらの人工変数は0となるように示さなければなりません。最大化しようとする関数は、すべての人工変数の和を含むように書き直されます。そして、行簡約を適用して最終解を得ます。

M の値は、人工変数が実行可能な解決策の一部にならないように、十分に大きな値に選択する必要があります。

M が十分に大きい場合、問題が実行不可能である場合にのみ、最適解には基底内の人工変数 (つまり正の値) が含まれます。

しかし、Mの適切な値を事前に選択することは容易ではありません。Mの値を指定する必要性を回避する方法は^{[ 1 ]}に記載されています。単体法の初期基底を求める他の方法としては、初期段階で別の線形計画問題を解くことが挙げられます。

その他の用途

目的関数で使用される場合、Big M メソッドは、制約または制約セットの違反が大きな正のペナルティ定数 M に関連付けられている線形最適化問題の定式化を指すことがあります。

混合整数線形最適化において、「Big M」という用語は、制約条件自体に大きな項が使用されていることを指すこともあります。例えば、zが2値変数（0または1）である論理制約は、ある2値変数が1つの値を取る場合にのみ変数の等価性を保証する一方で、その2値変数が反対の値を取る場合は変数を「オープン」のままにすることを意味します。十分に大きなMとzの2値変数（0または1）の場合、制約条件は次のようになります。 $z=0\iff x=y$

xy\leq Mz

xy\geq -Mz

のとき、となることを確認してください。そうでない場合、のとき、となり、変数 x と y は、その差の絶対値がで制限される限り、任意の値を取ることができることを示しています（したがって、M は「十分に大きい」必要があります）。したがって、論理制約を MILP 問題に「エンコード」することが可能です。 $z=0$ $x=y$ $z=1$ $-M\leq xy\leq M$ $M$