線形計画法（Linear Programming、LP）

線形計画法とは？

線形計画法（Linear Programming、LP）は、数理計画の一分野で、リソースの最適な割り当てを求めるために使用される数学的手法です。線形計画法は、線形の制約条件の下で線形目的関数を最適化する問題を扱います。線形計画法は、運用管理、生産計画、輸送問題、スケジューリングなど、多くの実用的な応用があります。

数理計画

数理計画は、最適化問題を扱う数学の一分野で、特定の制約条件の下で目的関数を最小化または最大化する解を見つけることを目的としています。線形計画法は、数理計画の中でも、目的関数と制約条件が線形である特殊なケースを扱う手法です。

制約条件

制約条件は、問題に関連するリソースや条件を表す線形の等式または不等式です。これらの制約条件は、問題の解が満たすべき条件を定めます。例えば、生産計画の問題では、生産能力や原材料の使用量、労働時間などの制約が考慮されます。

目的関数

目的関数は、最適化の対象となる線形関数で、通常は利益の最大化やコストの最小化などの目標を表します。線形計画法の目的は、制約条件の範囲内で目的関数を最適化する解を見つけることです。

線形計画法の問題

最大化（または最小化）:
c1 * x1 + c2 * x2 + ... + cn * xn

制約条件:
a11 * x1 + a12 * x2 + ... + a1n * xn <= b1
a21 * x1 + a22 * x2 + ... + a2n * xn <= b2
...
am1 * x1 + am2 * x2 + ... + amn * xn <= bm

変数の制約:
x1, x2, ..., xn >= 0

ここで、
c1, c2, ..., cnは目的関数の係数、
a11, a12, ..., amnは制約条件の係数、
b1, b2, ..., bmは制約条件の右辺値、
x1, x2, ..., xnは最適化の対象となる変数
です。

線形計画法の問題は、シンプレックス法や内点法などのアルゴリズムを使って効率的に解くことができます。これらのアルゴリズムは、線形計画法の問題の特性を利用して、解を効率的に探索する方法を提供します。

シンプレックス法（Simplex Method）

シンプレックス法は、1947年にジョージ・ダンツィグによって開発された線形計画法の最も広く使われているアルゴリズムです。シンプレックス法は、最適解に到達するまで、制約条件の交点（基底解）を辿って解空間を探索します。シンプレックス法は、実用上は非常に効率的であることが多いですが、最悪の場合の計算量は指数的に増加することが知られています。

内点法（Interior Point Method）

内点法は、1980年代に開発された線形計画法のアルゴリズムで、解空間の内部から最適解に近づいていくアプローチを採用しています。内点法は、最適解を効率的に見つけることができ、最悪の場合でも多項式時間で計算できることが理論的に証明されています。内点法は、大規模な線形計画問題に対してシンプレックス法よりも高速であることが多いです。 線形計画法は、PythonのSciPyやCVXPYなどのライブラリを使って実装することができます。これらのライブラリは、シンプレックス法や内点法などの効率的なアルゴリズムを提供し、線形計画法の問題を簡単に解くことができます。

線形計画法は、多くの実用的な問題に対して効果的な解法を提供していますが、制約条件や目的関数が非線形である場合には、非線形最適化手法を検討する必要があります。非線形最適化には、凸最適化、二次計画法（Quadratic Programming）、混合整数計画法（Mixed Integer Programming）などの手法があります。

Pulpを使って、pythonで線形計画法を実行する

例1. 数式を使った最小化問題

線形計画問題を解決するためにPuLPというライブラリを使用しています。 このコード全体では、制約条件x + y <= 2の下で目的関数-4*x + yを最小化する変数xとyの値を求めています。 コードの解説は以下の通りです。

1. PuLPライブラリをインポートします。

2. 線形計画問題を定義します。問題の名前は"myProblem"で、目的関数を最小化するように設定されています。

3. 変数xとyを定義します。xは連続変数で、0から3の範囲内で変化します。yも連続変数で、0から1の範囲内で変化します。

4. 制約条件を追加します。この問題では、x + y <= 2という制約があります。

5. 目的関数を設定します。この問題では、-4*x + yという式を最小化することが目的となります。

6. 問題を解決します。solveメソッドを使って問題を解決し、その結果をstatusに格納します。

7. 解決のステータス（解が得られたかどうか）を表示します。

8. 問題の内容（変数や制約、目的関数）を表示します。

9. 変数xとyの最適解を表示します。

10. 目的関数の最適値を表示します。

import pulp

prob = pulp.LpProblem("myProblem", pulp.LpMinimize)
x = pulp.LpVariable("x",0,3,cat="Continuous")
y = pulp.LpVariable("y",0,1,cat="Continuous")
prob += x + y <= 2
prob += -4*x + y
status = prob.solve()
print(pulp.LpStatus[status])
print(prob)
print("x=", x.value())
print("y=", y.value())
print("f(x)= %f" %prob.objective.value())

以下のようなアウトプットが出てきて、この問題の解を教えてくれます

Optimal
myProblem:
MINIMIZE
-4*x + 1*y + 0
SUBJECT TO
_C1: x + y <= 2

VARIABLES
x <= 3 Continuous
y <= 1 Continuous

x= 2.0
y= 0.0
f(x)= -8.000000

例2. ジュースの製造の例

あるジュース製造工場で、３種類のミックスジュース館を製造する。１缶当たりの価格は、リンゴオレンジジュース300円、オレンジレモンジュース280円、レモンリンゴジュース420円である。

1. リンゴオレンジジュース：リンゴ 40g, オレンジ 30g, レモン 5g

2. オレンジレモンジュース：リンゴ 5g, オレンジ 50g, レモン 10g

3. レモンリンゴジュース：リンゴ 20g, オレンジ 10g, レモン 50g

今、リンゴが2kg, オレンジが3kg, レモンが1kg使えるものとする。 全体の出荷額が最大となるようにするには、各ジュースを何缶ずつ製造すれば良いか？

x1はリンゴオレンジジュース, x2はオレンジレモンジュース, x3はレモンリンゴジュースとする。

この問題は線形計画問題として定式化できます。全体の出荷額を最大化するために、各ジュースを何缶ずつ製造すれば良いかを求めるプログラムをPythonのPuLPを使って書いてみます。

import pulp

# 問題の定義
prob = pulp.LpProblem("JuiceProduction", pulp.LpMaximize)

# 変数の定義
x1 = pulp.LpVariable("x1", 0, None, cat="Integer")
x2 = pulp.LpVariable("x2", 0, None, cat="Integer")
x3 = pulp.LpVariable("x3", 0, None, cat="Integer")

# 目的関数
profit = 300 * x1 + 280 * x2 + 420 * x3
prob += profit

# 制約条件
prob += 40 * x1 + 5 * x2 + 20 * x3 <= 2000  # リンゴ
prob += 30 * x1 + 50 * x2 + 10 * x3 <= 3000  # オレンジ
prob += 5 * x1 + 10 * x2 + 50 * x3 <= 1000   # レモン

# 問題を解く
status = prob.solve()

# 結果を表示
print("Status:", pulp.LpStatus[status])
print("x1 (リンゴオレンジジュース) =", x1.value())
print("x2 (オレンジレモンジュース) =", x2.value())
print("x3 (レモンリンゴジュース) =", x3.value())
print("最大出荷額 (円):", prob.objective.value())

以下のアウトプットが出てきました：

Status: Optimal
x1 (リンゴオレンジジュース) = 41.0
x2 (オレンジレモンジュース) = 33.0
x3 (レモンリンゴジュース) = 9.0
最大出荷額 (円): 25320.0

例3. 電子機器の輸送

電子機器の輸送について考える。 倉庫Xに電子機器が20個、倉庫Yには電子機器が22個ある。 電子機器の注文数はA店が18個、B店が14個、C店が10個である。 倉庫Xからの輸送費は、A店は¥125、B店は¥160、C店は¥175である 倉庫Xからの輸送費は、A店は¥145、B店は¥92、C店は¥125である 輸送費を最小にする配送計画を求めよ。

この問題は輸送最適化問題であり、線形計画問題として定式化できます。PythonのPuLPを使って輸送費を最小にする配送計画を求めるプログラムを書いてみます。

import pulp

# 問題の定義
prob = pulp.LpProblem("TransportationProblem", pulp.LpMinimize)

# 変数の定義
xa = pulp.LpVariable("xa", 0, None, cat="Integer")
xb = pulp.LpVariable("xb", 0, None, cat="Integer")
xc = pulp.LpVariable("xc", 0, None, cat="Integer")
ya = pulp.LpVariable("ya", 0, None, cat="Integer")
yb = pulp.LpVariable("yb", 0, None, cat="Integer")
yc = pulp.LpVariable("yc", 0, None, cat="Integer")

# 目的関数
cost = 125 * xa + 160 * xb + 175 * xc + 145 * ya + 92 * yb + 125 * yc
prob += cost

# 制約条件
prob += xa + xb + xc <= 20  # 倉庫Xの在庫
prob += ya + yb + yc <= 22  # 倉庫Yの在庫
prob += xa + ya == 18       # A店への需要
prob += xb + yb == 14       # B店への需要
prob += xc + yc == 10       # C店への需要

# 問題を解く
status = prob.solve()

# 結果を表示
print("Status:", pulp.LpStatus[status])
print("倉庫XからA店へ =", xa.value())
print("倉庫XからB店へ =", xb.value())
print("倉庫XからC店へ =", xc.value())
print("倉庫YからA店へ =", ya.value())
print("倉庫YからB店へ =", yb.value())
print("倉庫YからC店へ =", yc.value())
print("最小輸送費 (円):", prob.objective.value())

以下のように解答が得られます

Status: Optimal
倉庫XからA店へ = 18.0
倉庫XからB店へ = 0.0
倉庫XからC店へ = 2.0
倉庫YからA店へ = 0.0
倉庫YからB店へ = 14.0
倉庫YからC店へ = 8.0
最小輸送費 (円): 4888.0