線形計画法と最適化におけるシンプレックス法の理解
線形計画法の紹介
線形計画法は、線形目標関数を最適化するための数学的手法であり、線形等式および不等式の制約に従います。これは、要件が線形関係によって表される数学モデルで最良の結果を達成する方法です。この種の最適化は、経済学、工学、軍事、および事業計画などのさまざまな分野で重要です。
目的関数と制約
線形計画法では、目標は線形目的関数を最大化または最小化することです。一般的な線形計画問題は次のように表されます:
最大化または最小化: Z = 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
ここで、x 1 , x 2 , ..., x nは変数であり、c 1 , c 2 , ..., c nは目的関数の係数であり、a ijは制約の係数、b iは制約方程式の定数です。
シンプレックス法: 概要
シンプレックス法は、線形計画問題を解くために使用される一般的なアルゴリズムです。これは1947年にジョージ・ダンツィッヒによって開発されました。この方法は次の主要なステップで構成されています:
- 線形計画問題を標準形式に変換する。
- 初期の実行可能な解を見つける。
- 反復的に目的関数を改善し、最適解に到達する。
標準形式への変換
シンプレックス法を適用する前に、与えられた線形計画問題を標準形式に変換する必要があります。これは、すべての制約が等式形式であることを確認し、必要に応じて緩和、不足、人工変数を追加することを含みます。
例えば以下のような制約があると仮定します: a 11 x 1 + a 12 x 2 ≤ b 1
これを等式に変えるために、緩和変数s 1を導入します:
a 11 x 1 + a 12 x 2 + s 1 = b 1
初期実行可能解の発見
問題が標準形式になると、基本実行可能解を見つける必要があります。これは、非基本変数をゼロに設定し、方程式のシステムを解いて基本変数の値を見つける作業を含みます。
反復プロセス
シンプレックス法の基本的な目的は、実行可能な解を通じて処理し、最適解を特定することで目的関数の値を改善することです。これはピボット操作によって行われます。
例
線形計画問題の視覚的な例を見てみましょう。次のような問題があるとします:
最大化: Z = 3x 1 + 5x 2 条件: x 1 + 2x 2 ≤ 8 3x 1 + 2x 2 ≤ 12 x 1 , x 2 ≥ 0
上記の例では、制約x 1 + 2x 2 = 8および3x 1 + 2x 2 = 12が線として描画されています。緑のポリゴンで囲まれた領域がすべての条件を満たす実行可能領域です。
シンプレックス法におけるピボット操作
目的関数を改善するために、ピボット要素を選びます。入退出基準は、どの変数が基底に入り、どの変数が出るかを識別するのに役立ちます。ピボット操作によって基底を変更し、隣接の実行可能解に移動して目的関数の値を向上させます（最大化の場合）。
ピボット操作に含まれるステップ
ピボット操作は次の主要なステップを含みます:
- 入る変数を特定する:
- シンプレックス表の目的行（コスト行とも呼ばれる）を見て、係数が最も正の変数を選びます（最大化問題の場合）。これが入る変数です。
- 離れる変数を決定する:
- 下位変数を見つけるために、制限行ごとに右側の正の係数に対する最小比を計算します。
- 行操作を実行する:
- この新しい基底を反映するように表を調整します。これは、入る変数の列の他の要素をゼロに設定するピボット要素行操作を含みます。
例の続き
前述の例にこれらのステップを適用してみましょう。
初期基底のシンプレックス表
不等式を等式に変換するための初期表は、各制約に対して緩和変数s 1およびs 2で設定されます:
| x 1 | x 2 | s 1 | s 2 | 右辺 | , , 1 | 2 | 1 | 0 | 8 | , 3 | 2 | 0 | 1 | 12 | , , -3 | -5 | 0 | 0 | 0 |
入退出変数を特定しましょう:
最大化の場合、目的行で最もネガティブな係数は-5です（x 2の下）。これはx 2が入る変数であることを意味します。
離れる変数を見つけるために、x 2の正の係数に対するRHSの比を計算します:
8/2 = 4 (1行目の場合) 12/2 = 6 (2行目の場合) 最小比は4であり、1行目が離れることを示しています。
元の変数x 2を1行目に作成する行操作を実行します。
それに応じて残りの表を更新します。
最適解
目的行に負の係数が存在しないまで（最大化の場合）、類似のピボット操作を続けて、最適解が得られたことを示します。
結論
シンプレックス法は、実行可能領域の頂点を体系的に反復することで機能する効率的なアルゴリズムです。多くの変数と制約を含む線形問題に特に効率的であり、理論数学と実際の意思決定シナリオの両方でその有用性を証明しています。各ステップの注意深い実装と理解を通じて、学生は複雑な問題に対してシンプレックス法の力を効果的に活用して最適解を見つけることができます。
コメント