ビッグMメソッド

オペレーションズ リサーチにおいて、Big M 法は、単体アルゴリズムを使用して線形計画問題を解く方法です。Big M 法は、単体アルゴリズムを「より大きい」制約を含む問題に拡張します。これは、制約を、存在する場合の最適解の一部にはならない大きな負の定数に関連付けることによって行われます。

シンプレックス法は、線形最大化問題を解くための元祖であり、現在でも最も広く使用されている方法の 1 つです。ただし、これを適用するには、原点 (すべての変数が 0 に等しい) が実行可能な点である必要があります。この条件は、すべての制約 (非負値を除く) が小制約であり、右側に正の定数がある場合にのみ満たされます。Big M 法では、余剰変数と人工変数を導入して、すべての不等式をその形式に変換します。「Big M」は、人工変数に関連付けられた大きな数を指し、文字 M で表されます。

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

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

たとえば、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 の多くの用途の 1 つは、たとえば、特定のバイナリ変数が 1 つの値を取る場合にのみ変数の等価性を保証するが、バイナリ変数が反対の値を取る場合は変数を「オープン」のままにしておくことを意味します。この例の 1 つは次のとおりです。十分に大きな M と z のバイナリ変数 (0 または 1) の場合、制約は次のようになります。

${\displaystyle xy\leq Mz}$

${\displaystyle xy\geq -Mz}$

のとき、 であることを確認します。そうでない場合、 のとき、 となり、変数 x と y は、その差の絶対値が で制限される限り、任意の値を取ることができることを示します(したがって、M は「十分に大きい」必要があります)。 ${\displaystyle z=0}$${\displaystyle x=y}$${\displaystyle z=1}$${\displaystyle -M\leq xy\leq M}$${\displaystyle M}$

• 2段階法（線形計画法）は、>=制約のある問題を解決するための別のアプローチです。
• Karush-Kuhn-Tucker 条件は、不等式制約を伴う非線形最適化問題に適用されます。

文献

• グリーヴァ、イゴール。ナッシュ、ステファン G.ソーファー、アリエラ（2009年3月26日）。線形および非線形の最適化(第 2 版)。工業数学協会。ISBN 978-0-89871-661-0。

議論

• シンプレックス - ビッグ M メソッド、リン・キレン、ダブリン シティ大学。
• ビッグ M メソッド、businessmanagementcourses.org
• ビッグMメソッド、マーク・ハッチンソン
• 最近導入されたパラメータなしの変種である数値無限Mを使用したBig-M法
• 実行不可能かつ非有界な線形計画問題に対する3段階単体法、M=1のBig M法