線形最適化についてまとめ、Pythonを使って、基本的な線形最適化問題を解いてみます。
後半に参考書籍も紹介しています。
線形最適化とは？
線形最適化（Linear Programming）とは、「ある目的を最大化または最小化するために、複数の条件（制約）のもとで最適な値を求める数学的手法」です。
「限られた資源（お金・時間・材料など）をうまく配分して、利益を最大にしたり、コストを最小にしたりする方法」です。
線形最適化は、さまざまな分野で使われています。
例を挙げます。
- 製造業
限られた工場ラインや原材料で、最も利益が出る製品構成を決める - 物流
トラックの積載量や移動時間の制約を守りながら、最短ルートで配送する - マーケティング
限られた広告予算で、最も効果の高い媒体に配分する - ダイエットプラン
摂取カロリーや栄養バランスの条件を満たしつつ、食費を最小化する
これらの問題はすべて「目的関数（最大化・最小化）」と「制約条件（～しなければならない）」を数式で表せば、線形最適化で解くことができます。
なぜ「線形」なのか？
「目的関数」や「制約条件」がすべて一次式（＝直線で表される式）だからです。
たとえば 3x + 4y や x + 2y ≤ 8 は直線を表します。このように「変数の次数が1である」ことが、線形最適化の特徴です。
線形最適化の数学的理解
一般的に線形最適化問題は以下の式で表されます。
\(\text{minimize }cTx\)
\(\text{subject to }Ax ≤ b, x∈ℝ\)
\(\text{minimize }\)の後に記載されているのが最適化対象の目的関数、\(\text{subject to }\)の後ろに記載されているのが制約条件です。
\(x\) は変数のベクトル、目的関数の係数が\(c\)（ベクトル）、制約式の係数が\(A\)（行列）です。\(b\) は制約式の定数です。
目的関数が線形関数、制格式が線形式で、制約式で表される制約条件のもとに、目的関数を最小化（または最大化）する変数の値を見つける問題が線形最適化問題です。
目的関数（Objective Function）
最大化 or 最小化したい式（例：利益、距離、コストなど）
例：\(\text{maximize }3x + 4y\)
制約条件（Constraints）
満たさなければならない制約（材料の量や時間など）
例：\(x + 2y ≤ 8 x ≥ 0 y ≥ 0\)
これらを満たす \(x, y\) の最適な組み合わせ を求めます。
生産計画の最適化
例題
今回は以下の問題を解いてみます。
下表の原料でサンドイッチを製造して販売します。パンは何枚でも使えるとします。
| ハム | 1000枚 |
| レタス | 5 kg |
| チーズ | 400枚 |
下表の3種類のサンドイッチを製造する場合、各サンドイッチを何個ずつ製造、販売すれば売上げを最大化できるかという問題を解いてみます。「レタスサンドは人気がなさすぎて作っても売れない」というようなことは考えません。
| サンドイッチ | 売価 | ハム | レタス | チーズ |
| レタスサンド | 150円 | 2枚 | 15 g | |
| ハム2倍サンド | 200円 | 4枚 | 10 g | |
| チーズレタスハムサンド | 300円 | 2枚 | 10 g | 2枚 |
レタスサンドを \(x_{1}\)個、ハム2倍サンドを \(x_{2}\)個、チーズレタスサンドを \(x_{3}\)個製造する場合、目的関数は売価の最大化のため、以下のとおりとなります。
\(\text{maximize}\)
\(50 × x_{1} + 200 × x_{2} + 300 × x_{3}\)
制約式は各原料の使用量に上限があるため、以下のとおりとなります。
\(\text{subject to}\)
\(2 × x_{1} + 4 × x_{2} + 2 × x_{3} ≤ 1000\)
\(15 × x_{1} + 10 × x_{2} + 10 × x_{3} ≤ 5000\)
\(2 × x_{3} ≤ 400\)
Python実装
動作確認したpython、モジュールのバージョンは以下のとおりです。
python 3.6.0
mypulp 0.0.9Pythonで実装します。mypulpというモジュールを使用するため、インストールしておきます。
pip install mypulp続いて最適化計算を実装します。
from mypulp import *
# モデル生成
model = Model()
# 変数生成
# vtype='C'は連続変数（デフォルトも'C'）
x1 = model.addVar(vtype='C', name='x1_Lettuce')
x2 = model.addVar(vtype='C', name='x2_Double_Ham')
x3 = model.addVar(vtype='C', name='x3_Cheese_Lettuce_Ham')
# 変数宣言後updateする
model.update()
# 目的関数
model.setObjective(150 * x1 + 200 * x2 + 300 * x3, GRB.MAXIMIZE)
# 制約
model.addConstr(2 * x1 + 4 * x2 + 2 * x3 <= 1000)
model.addConstr(15 * x1 + 10 * x2 + 10 * x3 <= 5000)
model.addConstr(2 * x3 <= 400)
# 最適化計算
model.optimize()
# 計算結果を出力
print('Sales', ':', model.ObjVal)
for v in model.getVars():
print(v.VarName, ':', v.X)コードの実行結果は以下のとおりです。
Sales : 97500.0
x1_Lettuce : 150.0
x2_Double_Ham : 75.0
x3_Cheese_Lettuce_Ham : 200.0レタスサンド150個、ハム2倍サンド75個、チーズレタスハムサンド200個を製造することで、売上げが97,500円に最大化されることがわかります。
物流における配送ルート最適化
線形最適化は、物流業界でも非常に重要な役割を果たしています。
特に「配送ルートの最適化」は、コスト削減・納期短縮・燃料効率向上といった観点から、多くの企業で導入されています。
課題例 複数の店舗への配送
たとえば、以下のような状況を考えてみます。
- ある物流センターから、複数の店舗に商品を配送したい。
- 各店舗には異なる数量の需要がある。
- トラックの積載量には上限がある。
- 移動距離が短いほど、燃料費や人件費が抑えられる。
このときに、「どのトラックがどの店舗に、どのルートで配送すべきか？」をうまく決めることで、全体の配送コストを最小限に抑えることができます。
線形最適化でのモデル化
この課題は以下のように線形最適化で表現できます。
変数
\(x_{ij}\) … トラック \(i\) が店舗 \(j\) に配送する荷物の量
目的関数（最小化）
総移動距離 × 単位コスト（または時間、CO2排出量など）
$$\text{minimize} ∑ distance_{ij} × x_{ij}$$
制約条件
各トラックの積載量を超えない
$$∑ x_{ij} ≤ 容量_{i}$$
各店舗の需要を満たす
$$∑ x_{ij} ≥ 需要_{j}$$
負の値（マイナスの荷物）にならない
$$x_{ij} ≥ 0$$
参考書籍
こちらの本を参考にしました。Pythonでの最適化計算の方法やビジネスへの応用について、詳しく書かれています。
まとめ
基本的な線形最適化問題、Pythonコードをまとめました。Pythonについては、モジュールを利用することですぐに最適化計算を行うことができます。
