シンプレックス法

シンプレックス法は線形計画法の問題を解くために使われるアルゴリズムで、線形制約に従って線形関数の最大または最小値を見つけることが関与します。線形計画法は、経済学、工学、軍事、ビジネス、科学などのさまざまな分野で重要な最適化ツールです。

線形計画法の紹介

線形計画法は、最適解を求める数式モデルを表現する一連の方程式と不等式を扱います。線形計画法の問題では、線形目標関数を線形の等式および/または不等式制約に従って最適化（最大化または最小化）することを目的とします。線形計画法の一般的な形式は次のように示されます：

最大化（または最小化）： c 1 x 1 + c 2 x 2 + ... + c n x n

以下の制約に従って：
a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1
a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2,
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m

x 1 , x 2 , ..., x n ≥ 0

シンプレックス法とは何か？

シンプレックス法は、目的関数の最適値を見つけるために可行領域のコーナーポイント（または頂点）を体系的に調べる反復手順です。この手順では、一つの頂点から他の頂点へと移動し、各ステップで目的関数の値を改善し、最良の可能な値が達成されるまで続けます。

シンプレックス法の手順

1. 問題を標準形に変換する。
2. 実行可能な初期解を特定する。
3. 更なる改善が不可能になるまで、より良い解を見つけるために作業を続ける。
4. 解を評価し解釈する。

ステップ1: 標準形への変換

シンプレックス法を適用するには、線形計画法の問題を標準形に変換する必要があります。これには以下が含まれます：

• すべての制約を線形方程式の形式にすること。
• 不等式を等式に変換するために余剰変数を導入すること。
• すべての変数が非負であることを確かめること。

次の例を考えてみましょう：

最大化： 3x 1 + 5x 2

以下の制約に従って：
x 1 + 2x 2 ≤ 8
3x 1 + 2x 2 ≤ 12

x 1 , x 2 ≥ 0

余剰変数の導入:

x 1 + 2x 2 + s 1 = 8
3x 1 + 2x 2 + s 2 = 12

x 1 , x 2 , s 1 , s 2 ≥ 0

余剰変数s 1とs 2は、制約からの未使用のリソースを表します。

ステップ2: 初期解を特定する

意思決定変数（ここではx 1とx 2）をゼロに設定し、余剰変数を制約値と等しくすることで、初期基本可行解が特定されます。

例では、初期解は次のようになります：

x 1 = 0, x 2 = 0, s 1 = 8, s 2 = 12

ステップ3: 解を改善するために繰り返す

再帰を実行するために、テーブルが作成されます。目的行には目的関数の負の係数が含まれています。再帰には次のことが含まれます：

• 目的は、行の中で最も負の係数を持つ変数を選択することです。
• 最小比例テストを使用して変数を削除する。
• ピボットして解を更新する。

初期タブロー:
| basis | x 1 | x 2 | s 1 | s 2 | right hand side |
| S 1 | 1 | 2 | 1 | 0 | 8 |
| S 2 | 3 | 2 | 0 | 1 | 12 |
| z | -3 | -5 | 0 | 0 | 0 |

反復1:

入った変数はx 2（z行の最も負の係数:-5）です。

最小比率のため：RHS / Coefficient of x 2 = min(8/2, 12/2) = 4、したがってs 1は削除変数です。

ピボットしてs 1をx 2と置き換える。

ピボット後タブロー:
| basis | x 1 | x 2 | s 1 | s 2 | right hand side |
| x 2 | 0.5 | 1 | 0.5 | 0 | 4 |
| S2 | 2.0 | 0 | -1 | 1 | 4 |
| z | -0.5 | 0 | 2.5 | 0 | 20 |

反復2:

新しいzラインの最も負の係数は-0.5（x 1のため）です。

最小比率を使用するとき：RHS / Coefficient of x 1 = min(4/0.5, 4/2) = 2、したがってs 2は削除変数です。

ピボットしてs 2をx 1と置き換える。

ピボット後タブロー:
| basis | x 1 | x 2 | s 1 | s 2 | right hand side |
| x 2 | 0.5 | 1 | 0.5 | 0 | 4 |
| x1 | 1 | 0 | -0.5 | 0.5 | 2 |
| Z | 0 | 0 | 3 | 0.5 | 22 |

目的関数の値は22に改善され、もはや負の係数は存在しないので、現在の解は最適です。

視覚的な例

グラフの影のかかった領域は、すべての制約が重なる可行領域を示しています。最大値が達成される最適解のポイントは円で示されています。

ステップ4：解を評価し解釈する

シンプレックス法は、可行領域内で意思決定変数の最適な値を提供します。最終テーブルから、最適解を決定できます：

x 1 = 2, x 2 = 4

目的関数の値：22

これは、目的関数3x 1 + 5x 2の最大値が22であることを意味します。x 1 = 2およびx 2 = 4の場合です。

シンプレックス法の特性

• シンプレックス法は、可行領域のエッジに沿って移動し、解が最適解に到達するまで各ステップで改善または同じままにすることを保証します。
• 大規模な線形計画法の問題に適した形で、線形目標関数を制約と共に効率的に扱います。
• この方法は通常最初から始まりますが、標準形に問題を変換するためにいくつかの前処理が依然として必要です。
• アルゴリズムは有限であり、最適解に収束するか、与えられた制約に対して解が存在しないことを認識します。

利点と限界

シンプレックス法の利点には、線形計画法の問題に対する正確な最適解を提供できること、およびフォーム≤の制約に限定されず多様な問題に適用できることがあります。しかし、この方法にはいくつかの限界があります：

利点

• 正確な解を提供する。
• 複雑な問題を効率的に扱える。
• 広く知られ、使用されているため、多くのライブラリやソフトウェアでサポートされています。

限界

• 非常に大きなデータセットでは計算量的に高価になる可能性。
• 非線形問題には直接機能しない。
• サイクリングが問題になる可能性があります（時々ですが、反サイクリング戦略で対応可能）。

結論

シンプレックス法は、特にオペレーションズリサーチの分野で最適化の強力なツールであり続けています。それは、線形制約を伴う最適化問題を構造化したアプローチで解決する手段を提供します。この方法を現実の問題解決に信頼性と正確性を持って適用するためには、強みと限界の両方を理解することが重要です。

コメント