オペレーションズ・リサーチにおいて、ビッグM法は単体法を用いて線形計画問題を解く手法です。ビッグM法は単体法を「より大きい」制約を含む問題に拡張します。これは、制約を、もし存在するとしても最適解の一部にはならない大きな負の定数に関連付けることによって行われます
アルゴリズム
単体法は、線形最大化問題を解くための元祖であり、現在でも最も広く使われている手法の1つです。最適な目的関数を持つ点は、線形計画（LP）の実行可能領域の形状である単体の頂点上で到達する必要があることは明らかです。単体の頂点上の点は基底として表されます。したがって、大域的最適解に到達するまで基底を改善することを目的とする単体法を適用するには、まず実行可能基底を見つける必要があります
自明な基底（すべての問題変数が0）は、必ずしも単体の一部ではありません。すべての制約（非負性を除く）が小なり制約であり、右辺に正の定数がある場合にのみ、Big M法は実現可能です。Big M法は、余剰変数と人工変数を導入してすべての不等式をその形に変換し、それによって単体を高次元に拡張して自明な基底で有効にします。LPの標準的な定式化に固有の問題変数に対する正値制約のため、単体は常に頂点となります。「Big M」は、人工変数に関連付けられた大きな数を指し、文字Mで表されます。
アルゴリズムの手順は次のとおりです。
- 不等式制約を乗算して、右側が正になるようにします。
- 問題が最小化である場合は、目的関数に -1 を掛けて最大化に変換します。
- 任意の「より大きい」制約に対して、余剰s iと人工変数a iを導入します(以下に示すように)。
- 大きな正の値 M を選択し、人工変数を乗算する形式の項を目的関数に導入します。
- 以下制約の場合、すべての制約が等式になるようにスラック変数 s iを導入します。
- 通常の単体法を使用して問題を解きます。
例えば、x + y ≤ 100 はx + y + s 1 = 100 となり、x + y ≥ 100 はx + y − s 1 + a 1 = 100 となります。これらの人工変数は0となるように示さなければなりません。最大化しようとする関数は、すべての人工変数の和を含むように書き直されます。そして、行簡約を適用して最終解を得ます。
M の値は、人工変数が実行可能な解決策の一部にならないように、十分に大きな値に選択する必要があります。
M が十分に大きい場合、問題が実行不可能である場合にのみ、最適解には基底内の人工変数 (つまり正の値) が含まれます。
しかし、Mの適切な値を事前に選択することは容易ではありません。Mの値を指定する必要性を克服する方法は[1]に記載されています。単体法の初期基底を求める他の方法としては、初期段階で別の線形計画問題を解く方法があります。
その他の用法
目的関数で使用される場合、Big M法は、制約または制約セットの違反が大きな正のペナルティ定数Mに関連付けられている線形最適化問題の定式化を指すことがあります
混合整数線形最適化において、「Big M」という用語は、制約条件自体に大きな項が使用されていることを指すこともあります。例えば、zが2値変数（0または1）である論理制約は、ある2値変数が1つの値を取る場合にのみ変数の等価性を保証する一方で、その2値変数が反対の値を取る場合は変数を「オープン」のままにすることを意味します。十分に大きなMとzの2値変数（0または1）の場合、制約条件は次のようになります。
のとき、 となることを確認してください。そうでない場合、 のとき、 となり、変数 x と y は、その差の絶対値が で制限される限り、任意の値を取ることができることを示しています（したがって、M は「十分に大きい」必要があります）。したがって、論理制約を MILP 問題に「エンコード」することが可能です。
参照
- 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法
参考文献
