線形計画法
線形計画法（LP）は、与えられた数学モデルで最良の結果を達成する方法を決定するための数学的方法です。その機能は線形関係によって表されます。線形計画法は、線形の目的関数を最適化するための技法であり、線形の等式および線形の不等式制約に従います。
線形計画問題の主要な要素は以下の通りです：
- 目的関数：最適化する必要のある関数で、通常は最大化または最小化されます。
- 決定変数：出力を決定する変数で、通常
x,y,zなどで表されます。 - 制約：決定変数に対する制限や制約で、しばしば線形の不等式や方程式の形式です。
- 非負制約：決定変数は非負であると仮定され、つまり、すべての値はゼロまたは正です。
線形計画問題の定式化
線形計画法を理解するために、次の例を考えてみましょう：
ある会社が椅子とテーブルの2つの製品を製造していると想像してください。各椅子は利益に30ドルを寄与し、各テーブルは50ドルを寄与します。この会社には労働と材料の制限があります。椅子を一つ作るのに2時間の労働と3単位の材料が必要です。テーブルを一つ作るのに4時間の労働と2単位の材料が必要です。会社には最大で100時間の労働力と120単位の材料が利用可能です。
利益を最大化するために、次のように線形計画問題を定式化できます：
最大: 利益 = 30x + 50y 以下の条件のもとで: 2x + 4y ≤ 100 （労働制約） 3x + 2y ≤ 120 （物理制約） x ≥ 0, y ≥ 0 （非負制約）
グラフによる表現
2つの変数の線形計画問題は、図によって解決し、表現できます。次のようになります：
可能領域は、すべての制約を満たす全ての点の集合です。上記では灰色で塗りつぶされています。最適解はこの領域にあります。この例では、制約の交差点に最適な戦略があり、赤い点で表現されています。
単体法
2つ以上の変数がある場合、図による表現は不可能です。したがって、線形計画問題を解くために単体法という反復法を使用します。
単体法は次のステップを含みます：
- 可能領域の初期のコーナーポイントから始めます。
- 可能領域の各頂点で目的関数を評価します。
- 目的関数の値を改善する隣接する頂点に移動します。
- さらなる改善が不可能になるまで、このプロセスを続けます。
- 現在の頂点点が目的関数の最大または最小値を提供します。
単体法を使用した例
次の線形計画問題を考えてみましょう：
最大化: Z = 3x1 + 2x2 以下の条件のもとで: x1 + x2 ≤ 4 x1 - x2 ≤ 2 x1, x2 ≥ 0
単体法を用いた解決手順：
- s1およびs2の緩和変数を含めて不等式を等式に変換します：
- 初期の単体表を作成します：
- Zの行で最も負の係数をもつピボット列を見つける：
- 比率を計算してピボット行を見つけます。
- ピボット要素を
1にし、ピボット列の他のすべての要素を0にするためのピボット操作を行います。 - 目的行に負の係数が残っていないまでこのプロセスを繰り返します。
x1 + x2 + s1 = 4
x1 - x2 + s2 = 2
| x1 | x2 | S1 | S2 | 解 | |
|---|---|---|---|---|---|
| S1 | 1 | 1 | 1 | 0 | 4 |
| S2 | 1 | -1 | 0 | 1 | 2 |
| Jade | -3 | -2 | 0 | 0 | 0 |
最も負の値は-3（x1の列）です。
行s1の場合: 4/1 = 4
行s2の場合: 2/1 = 2
最小の正の比率を持つ行を選びます：行s2。
線形計画における双対性
すべての線形計画問題、つまり主問題は、双対問題と呼ばれる別の線形計画問題に変換することができます。双対問題と主問題の解は、目的関数の値に制限を提供します。
例：
主問題： 最大化: Z = 3x1 + 4x2 以下の条件のもとで: 2x1 + 3x2 ≤ 8 3x1 + 3x2 ≤ 6 x1, x2 ≥ 0
その双対は以下の通りです：
最小化: W = 8y1 + 6y2 以下の条件のもとで: 2y1 + y2 ≥ 3 3y1 + 3y2 ≥ 4 y1, y2 ≥ 0
主問題と双対問題の目的関数は相互に結びついています。一方を解くことで他方に洞察または制限を与えます。
線形計画の応用
線形計画法は様々な分野で広く使用されています：
- 製造業：最適な生産水準と在庫の決定。
- 金融：リスクを最小限に抑えてリターンを最大化するポートフォリオの設計。
- 輸送：ネットワーク全体の貨物配送コストの最小化。
- 食事計画：すべての栄養要件を満たす最も手頃な食事の決定。
- 電気通信：最適な帯域幅の割り当てとネットワーク分析。
線形計画の制約
広範な応用にもかかわらず、線形計画法にはいくつかの制約があります：
- モデルは線形性に基づいていますが、現実のシナリオは必ずしも線形ではありません。
- 係数の確実性を仮定していますが、実際のデータは不確定または変動する可能性があります。
- 解はすべての制約を完全に満たす必要がありますが、必ずしも可能ではありません。
- 一部の実際の問題では重要な整数変数を直接的に扱わないことがあります。
結論
線形計画法は、与えられた制約の下で最適解を見つけるための枠組みを提供します。主に線形の目的関数を最適化することに重点を置いていますが、その原則はオペレーションズリサーチや経営科学の基礎となります。整数線形計画法や非線形計画法などの革新と最適化により、より複雑なシナリオへの適用が拡大します。
コメント