初めに
企業や組織では、限られた資源をどのように配分するかという意思決定が日々行われています。
例えば、
- 生産計画において、どの商品をどれだけ生産するべきか
- 配送計画において、どの車両にどの荷物を割り当てるべきか
- 人員配置において、どの従業員をどの業務に割り当てるべきか
といった問題があります。
これらの問題には共通して、「制約条件を満たしながら、コストを最小化したい」「利益を最大化したい」という目的があります。
このような問題を数学的に定式化し、最適な解を求める手法の一つが線形計画法（Linear Programming、LP）です。
線形計画法は数理最適化の中でも最も基本的な手法であり、多くの最適化アルゴリズムやソルバーの基礎となっています。
本記事では、線形計画法の概要を説明した後、具体例を通して問題の定式化と解き方を紹介します。また、線形計画法の限界と、その発展形である整数計画法（IP）・混合整数計画法（MIP）についても解説します。
線形計画法とは
線形計画法（Linear Programming、LP） は、
- 目的関数が 1次式
- 制約条件も すべて1次式
で表される最適化問題を解く手法です。
ここでいう 1次式 とは、例えば次のような形の式です。
- $2x+3y$
- $5x−y$
このように、変数を定数倍して足し合わせた形で表され、変数同士を掛けたり、二乗したりしない式を指します。
1次式で定義された関数（1次関数）のグラフは直線で表されます。
線形計画法の具体例
問題設定
ある施設で、1日分の食事を 2種類の食品 を組み合わせて用意します。1kgあたりのカロリー、タンパク質、コストは次の通りです。
| 食品 | カロリー | たんぱく質 | コスト |
|---|---|---|---|
| 食品A | 400 kcal | 10 g | 200 円 |
| 食品B | 200 kcal | 30 g | 300 円 |
2000kcal以上、タンパク質60g以上摂取できるなかで、食事全体のコストの最小値を求めよ。また、その時の食品A、食品Bの量（kg）をそれぞれ求める。
解説
食品Aと食品Bの使用量を、それぞれ
- $x$：食品Aの使用量［kg］
- $y$：食品Bの使用量［kg］
とする。
食品A・Bの栄養価より、次の条件を満たす必要がある。
- カロリー条件：$400x + 200y \geq 2000$
- たんぱく質条件：$10x + 30y \geq 60$
また、使用量は負にならないため
- $x \geq 0$
- $y \geq 0$
を満たす必要がある。
食品A、Bのコストはそれぞれ 1kg あたり 200円、300円であるから、
食事全体のコストは $200x + 300y$ で表される。
本問では、この値を 最小化 する。
制約条件 $400x + 200y \geq 2000,10x + 30y \geq 60 $ を満たす $x, y$ の範囲は、平面上で図の濃い紫色の部分（境界を含む）である。
一方、食事全体のコスト（目的関数）を $200x+300y=k$ とおくと、
$$
y = -\frac{2}{3}x + \frac{k}{300}
$$
となり、このグラフの y 切片 $\frac{k}{300}$ が最小のとき $200x+300y=k$ は最小となることがわかる。
$(x, y)$ は制約条件を満たす必要があるため、図より $y = -\frac{2}{3}x + \frac{k}{300}$ の $y$ 切片が最小となるのは、この直線が下図の点Aを通るときである。
制約条件の交点は
$$
\begin{cases}
400x + 200y = 2000 \\
10x + 30y = 60
\end{cases}
$$
を解くと、$(x, y) = \left(\frac{24}{5},\; \frac{2}{5}\right)$ である。また、このときのコストは
$$
200 \times \frac{24}{5} +300 \times \frac{2}{5} = 960 + 120 = 1080
$$
となる。
以上より
- 食品Aの使用量：$\frac{24}{5}$ kg
- 食品Bの使用量：$\frac{2}{5}$ kg
- 食事全体の最小コスト：$1080$ 円
となる。
補足
上記では数学Ⅱで学ぶグラフを用いた解法を紹介しています。実際のアルゴリズムで最適化をする場合は、シンプレックス法（単体法）や内点法がベースとなった手法が使われています。
線形計画法の応用
線形計画法の限界
先ほどの例では、食品A・食品Bの量を kg（重さ） で扱っているため、
- $x = 4.8$ [kg]
- $y = 0.4$ [kg]
のような小数の解も現実的に意味を持ちます。
一方、次のように問題設定を少し変えてみます。
ある施設で、パック詰めされた食品を使って1日分の食事を用意します。各食品は 1パック単位でしか利用できません。
| 食品 | カロリー | たんぱく質 | コスト |
|---|---|---|---|
| 食品A（1パック） | 400 kcal | 10 g | 200 円 |
| 食品B（1パック） | 200 kcal | 30 g | 300 円 |
2000kcal以上、たんぱく質60g以上摂取できるように、食事全体のコストを最小化したいとします。
この問題を先ほど同じ手法（線形計画法）でそのまま解くと、
- 食品A：$4.8$ パック
- 食品B：$0.4$ パック
といった現実には意味を持たない解が得られてしまいます。
整数計画法（IP）・混合整数計画法（MIP）
変数が整数の場合の線形計画法は、整数計画法（Integer Programming、IP）や混合整数計画法（Mixed Integer Programming、MIP） として扱われます。
整数計画法（IP）：すべての変数が整数値を取る線形最適化手法
混合整数計画法（MIP）：整数変数と連続変数を混在して扱う線形最適化手法
です。
整数変数では、
- 解の候補が飛び飛びになる
- 線形計画法のように単純な図形として扱えない
といった特徴があり、計算の難易度は線形計画法より高くなります。（NP困難）
しかし、現実の業務では「整数でなければ意味を持たない判断」 が非常に多いため、整数計画法、混合整数計画法は数理最適化の実務において欠かせない手法です。
最後に
本記事では、線形計画法（Linear Programming、LP）の基本的な考え方について解説しました。
線形計画法は、
- 目的関数が一次式で表される
- 制約条件が一次式で表される
- 制約条件を満たす範囲の中から最適な解を求める
という特徴を持つ最適化手法です。
さらに、線形計画法では変数が連続値として扱われるため、パック数や人数のような「整数でなければ意味を持たない問題」では適切な解が得られない場合があることも紹介しました。
このような問題に対応するために、実務では整数計画法（IP）や混合整数計画法（MIP）が広く利用されています。
線形計画法は数理最適化の最も基本的な手法であり、多くの最適化アルゴリズムやソルバーの基礎となっています。まずは「変数・制約条件・目的関数」で問題を表現する考え方を理解することが、数理最適化を学ぶ第一歩となります。
コメント