単純形法を用いた線形計画問題の解法
線形計画法は数学モデルで最良の結果を達成する方法です。このモデルは線形関係で表現されます。線形計画法の目的は、特定の制約に基づいて、特定の量の最大値または最小値を見つけることです。単純形法は線形計画問題を解くために使用される一般的なアルゴリズムです。
単純形法とは?
単純形法は線形計画問題を解くための段階的な手順です。この方法は、2つ以上の変数を持つ方程式やより複雑な制約を扱うように設計されています。単純形法の美しさは、単純形表と呼ばれる表形式を使用して、この問題を体系的なプロセスに変えることです。
線形計画問題
単純形法に進む前に、線形計画問題の外観を理解しましょう。一般的な線形計画問題は次のようになります：
- 最大化または最小化する目的関数。
- 線形式の不等式による制約。
- 非負数の変数。
例:
最大化: Z = 3x + 2y 以下の条件を満たす： 2x + y ≤ 18 2x + 3y ≤ 42 3x + y ≤ 24 x, y ≥ 0
ここで、Zは最大化したい目的関数です。制約は不等式で表現されます。xとy 変数はともに0以上でなければなりません。
単純形法の手順
単純形法は主に以下のステップで構成されます：
ステップ 1: 不等式を方程式に変換
不等式にスラック変数を加えて等式に変換します。スラック変数は不等式の左辺と右辺の差を表します。
制約を考慮します：
2x + y ≤ 18 2x + 3y ≤ 42 3x + y ≤ 24
スラック変数 s1, s2 および s3 を追加して変更します：
2x + y + s1 = 18 2x + 3y + s2 = 42 3x + y + s3 = 24
これにより、線形方程式はスラック変数を含み、それらは初めにゼロに設定されます。
ステップ 2: 単純形表を設定
変換した方程式から初期の単純形テーブルを作成します。テーブルは次のようになります：
| x | y | s1 | s2 | s3 | 解 | , 2 | 1 | 1 | 0 | 0 | 18 | , 2 | 3 | 0 | 1 | 0 | 42 | , 3 | 1 | 0 | 0 | 1 | 24 | , -3 | -2 | 0 | 0 | 0 | 0 |
注意: 下段は目的関数の係数を引いて形成されています。この行は最適化の判断に役立ちます。
ステップ 3: 基準要素の特定
基準要素は、解を新しい次元に変えて最適解に向けて変更するために選ばれます。この過程の主なポイントは次のとおりです：
- テーブルの下段で最も負の数を選択します。これが基準列になります。
- 基準列の係数に対する解の値の比率を計算し（ゼロと負の係数は無視）、最も小さい正の比率が基準行を決定します。
例：
比率: (18/2) = 9, (42/2) = 21, (24/3) = 8
最も小さい比率は8で、基準行に対応します。この例では、-3が下段で最も負の数であるため、基準列は3のある列です。
ステップ 4: 行操作の実行
基本的な行操作を使用して、基準要素を1にし、列の他の要素を0に調整します。このステップは最適解に向けた収束を確保します。
ステップ 5: 繰り返し
下段にこれ以上負の数がなくなるまでステップ3と4を繰り返します。この時点に到達したとき、元の初期解が最適であることがわかります。
単純形法を用いた実践例
問題
関数Z = 5x + 4yを最大化します。以下の制約に従います：
y + 2x ≤ 20 2x + 3y ≤ 30 2x + y ≤ 15 x, y ≥ 0
ステップ 1: スラック変数を用いた方程式への変換
x + 2y + s1 = 20 2x + 3y + s2 = 30 2x + y + s3 = 15
ステップ 2: 単純形表の設定
| x | y | s1 | s2 | s3 | 解 | , 1 | 2 | 1 | 0 | 0 | 20 | , 2 | 3 | 0 | 1 | 0 | 30 | , 2 | 1 | 0 | 0 | 1 | 15 | | -5|-4 | 0 | 0 | 0 | 0 |
ステップ 3: 基準要素の特定
-5が基準列になります。第3列の比率を計算します：
比率: (20/1) = 20, (30/2) = 15, (15/2) = 7.5
最も小さい正の値が7.5です。(行3、列1)の要素が基準になります。
ステップ 4: 行操作の実行
基準要素を1にします：
| x | y | s1 | s2 | s3 | 解 | , 1 | 2 | 1 | 0 | 0 | 20 | | 1 | 1.5| 0 | 0.5| 0 | 7.5 | <- 基準行 (基準要素1が作成) , 2 | 1 | 0 | 0 | 1 | 15 | | -5|-4 | 0 | 0 | 0 | 0 |
他の列要素をゼロにするために行操作を調整し、下段に負の数がなくなるまでこのプロセスを繰り返します。
ステップ 5: 最適解
繰り返し操作を通じて最終的に:
| x | y | s1 | s2 | s3 | 解 | , 1 | 0 | 1 | 1 | 0 | 5 | | 0 | 1 | 0 | 1.5| 0 | 12.5 | , 0 | 0 | -1 |-1.5| 1 | -7.5 | | 0 | 0 | 0 |0.5 | 0 | 35 |
値 x = 5 と y = 12.5 は目的関数 Z を最大化し、その値は35になります。
結論
単純形法は線形計画法において強力な最適化ツールです。複数の変数を効率的に扱い、制約によって制限される最適ポイントに導きます。手続き的な性質は、資源が限られている実際のシナリオを深く分析し、最適な利用を確保します。
コメント