1. 概要
線形計画法（Linear Programming：LP）は、複数の制約条件のもとで、ある目的関数を最大化または最小化する最適解を求める数理計画法の一つです。経営資源の最適配分問題や生産計画、輸送計画など、様々な実務問題の解決に活用されています。
線形計画法の特徴は、目的関数と制約条件がすべて決定変数に関する1次式（線形式）で表現されることです。この性質により、問題を数学的に定式化し、シンプレックス法などのアルゴリズムを用いて効率的に最適解を求めることができます。現代では、専用のソフトウェアやプログラミング言語のライブラリを活用することで、大規模な問題も短時間で解くことが可能になっています。
応用情報技術者試験では、線形計画法の基本概念を理解し、簡単な問題を定式化して図解法で解く能力が求められます。
2. 詳細説明
2.1 線形計画問題の構成要素
線形計画問題は、以下の3つの要素から構成されます。
第一に、決定変数です。これは最適化したい対象を表す変数で、例えば製品Aの生産量をx₁、製品Bの生産量をx₂のように設定します。
第二に、目的関数です。最大化または最小化したい値を決定変数の1次式で表現します。例えば、利益最大化問題では「利益 = 3x₁ + 5x₂」のように表します。
第三に、制約条件です。決定変数が満たすべき条件を不等式または等式で表現します。例えば、「2x₁ + 3x₂ ≤ 12（原材料の制約）」「x₁ ≥ 0, x₂ ≥ 0（非負制約）」などです。
2.2 問題の定式化
線形計画問題を定式化する手順は以下の通りです。
- 問題の理解：何を最適化したいのか、どのような制約があるのかを明確にします
- 決定変数の設定：最適化の対象となる変数を定義します
- 目的関数の設定：最大化または最小化したい値を数式で表現します
- 制約条件の列挙：すべての制約を不等式・等式で表現します
- 非負制約の確認：通常、決定変数は0以上の値を取ります
graph TD
A[問題理解] --> B[決定変数の設定]
B --> C[目的関数の設定]
C --> D[制約条件の列挙]
D --> E[非負制約の確認]
A1[何を最適化したいか明確化
どのような制約があるか把握] --> A
B1[最適化の対象となる変数を定義
例: x₁=製品Aの生産量] --> B
C1[最大化/最小化したい値を数式化
例: 利益 = 3x₁ + 5x₂] --> C
D1[すべての制約を不等式・等式で表現
例: 2x₁ + 3x₂ ≤ 12] --> D
E1[決定変数は0以上の値
例: x₁ ≥ 0, x₂ ≥ 0] --> E
style A fill:#e1f5fe
style B fill:#e1f5fe
style C fill:#e1f5fe
style D fill:#e1f5fe
style E fill:#e1f5fe
style A1 fill:#fff3e0
style B1 fill:#fff3e0
style C1 fill:#fff3e0
style D1 fill:#fff3e0
style E1 fill:#fff3e0
2.3 図解法による解法
2変数の線形計画問題は、グラフを用いて視覚的に解くことができます。
まず、座標平面上に各制約条件を直線として描きます。これらの直線と非負制約によって囲まれた領域が実行可能領域となります。次に、目的関数の値が一定となる直線（等値線）を描き、これを目的関数を最大化（または最小化）する方向に平行移動させます。実行可能領域の境界と最後に接する点が最適解となります。
最適解は必ず実行可能領域の頂点（端点）に存在するという重要な性質があります。これは線形計画法の基本定理として知られています。
3. 実装方法と応用例
3.1 代表的な解法アルゴリズム
実際の問題解決では、以下のアルゴリズムが使用されます。
graph TD
A[開始] --> B[初期基底解の設定]
B --> C[シンプレックス表の作成]
C --> D{最適性判定
すべての被約費用が非負?}
D -->|Yes| E[最適解確定]
D -->|No| F[ピボット列の選択
最小の負の被約費用]
F --> G[ピボット行の選択
最小比率テスト]
G --> H[ピボット演算の実行
基底変数の交換]
H --> I[シンプレックス表の更新]
I --> D
E --> J[終了]
シンプレックス法は、最も広く使われている解法です。実行可能領域の頂点を効率的に探索し、最適解を見つけます。計算効率が良く、多くのソフトウェアに実装されています。
内点法は、実行可能領域の内部から最適解に接近する手法です。大規模問題に対して高速に動作する特徴があります。
現代では、Excel のソルバー機能や、Python のPuLP、scipy.optimize などのライブラリを使用することで、プログラミング知識があれば簡単に線形計画問題を解くことができます。
3.2 実務での応用例
線形計画法は様々な分野で活用されています。
配分問題の例：人員シフト最適化
時間帯別の必要人員数と各シフトパターンの関係を示す表形式のHTML図表
| 時間帯 | 6-10時 | 10-14時 | 14-18時 | 18-22時 | 22-2時 | 人件費/人 |
|---|---|---|---|---|---|---|
| 必要人員数 | 3名 | 7名 | 5名 | 8名 | 2名 | – |
| 早朝シフト（6-14時） | ○ | ○ | – | – | – | ¥8,000 |
| 日中シフト（10-18時） | – | ○ | ○ | – | – | ¥8,000 |
| 夕方シフト（14-22時） | – | – | ○ | ○ | – | ¥9,000 |
| 夜間シフト（18-2時） | – | – | – | ○ | ○ | ¥10,000 |
| フルタイム（6-22時） | ○ | ○ | ○ | ○ | – | ¥15,000 |
• ○印は該当シフトがカバーする時間帯を示します
• 各シフトパターンの配置人数が決定変数となります
• すべての時間帯で必要人員数以上を確保する必要があります
生産計画では、複数製品の最適生産量を決定します。原材料、設備能力、需要などの制約のもとで、利益を最大化する生産計画を立案できます。
輸送問題では、複数の供給地から複数の需要地への最適な輸送計画を決定します。輸送コストを最小化しながら、すべての需要を満たす配送ルートを見つけます。
線形計画法の応用分野マップ
人員配置問題では、シフト勤務の最適化などに活用されます。必要な人員数を確保しながら、人件費を最小化する勤務表を作成できます。
4. 例題と解説
ある工場で製品AとBを生産しています。以下の条件のもとで、利益を最大化する生産計画を立てなさい。
条件：
- 製品Aの利益：300円/個、製品Bの利益：500円/個
- 原材料の制約：2A + 3B ≤ 12
- 加工時間の制約：A + 2B ≤ 8
- 非負制約：A ≥ 0, B ≥ 0
解法：
- 決定変数：A = 製品Aの生産量、B = 製品Bの生産量
- 目的関数：利益 Z = 300A + 500B（最大化）
- 制約条件：
- 2A + 3B ≤ 12
- A + 2B ≤ 8
- A ≥ 0, B ≥ 0
- 図解法により、実行可能領域の頂点は (0,0), (6,0), (0,4), (4,2) となります
- 各頂点での目的関数値：
- (0,0): Z = 0
- (6,0): Z = 1,800
- (0,4): Z = 2,000
- (4,2): Z = 2,200
答え：製品Aを4個、製品Bを2個生産するとき、最大利益2,200円が得られます。
5. まとめ
線形計画法は、制約条件のもとで目的関数を最適化する強力な手法です。問題を適切に定式化することで、図解法やシンプレックス法により最適解を求めることができます。
応用情報技術者試験では、簡単な2変数問題を図解法で解く能力が求められます。定式化の手順を理解し、実行可能領域と最適解の関係を把握することが重要です。実務では、より複雑な問題に対してコンピュータを活用した解法が用いられますが、基本原理の理解が問題モデリングの基礎となります。
ご利用上のご注意
このコンテンツの一部は、生成AIによるコンテンツ自動生成・投稿システムをもちいて作成し、人間がチェックをおこなった上で公開しています。チェックは十分に実施していますが、誤謬・誤解などが含まれる場合が想定されます。お気づきの点がございましたらご連絡いただけましたら幸甚です。
