Python SciPy : 線形計画問題を解く

かくあき

SciPy では関数 linprog で線形計画問題を解くことができます。

関数について

linprog は ver0.15.0 から SciPy に追加されました。計算アルゴリズムはシンプレックス法です。 Python で線形計画問題を解く場合、PuLP というパッケージを使うのが人気のようですが、簡単な問題なら linprog で十分だと思います。

例

適当な例を解いてみます。

linprog は目的関数を最小化するベクトルから解を求めます。問題を目的関数の最大化としたい場合は式の係数の符号を反転させ、結果の符号も反転して読む必要があります。

import numpy as np
from scipy.optimize import linprog

c = [-3, -2]
A = [[2, 1], [1, 1]]
b = [6, 4]
x0_bounds = (None, None)
x1_bounds = (1, None)
res = linprog(c, A_ub=A, b_ub=b, bounds=(x0_bounds, x1_bounds))

res

    fun: -10.0
message: 'Optimization terminated successfully.'
    nit: 3
  slack: array([ 0.,  0.,  1.])
 status: 0
success: True
      x: array([ 2.,  2.])

この例を図にすると以下のようになります。

import matplotlib.pyplot as plt

x = np.linspace(0, 4, 100)

y0 = (-3*x+10)/2
y1 = -2*x+6
y2 = -x+4
y3 = np.ones_like(x)

y4 = np.minimum(y1, y2)

plt.figure()
plt.plot(x, y0, "--", label="objective function")
plt.plot(x, y1, label="2x+y<=6")
plt.plot(x, y2, label="x+y<=4")
plt.plot(x, y3, label="y>=1")
plt.plot(res.x[0], res.x[1], "o")
plt.fill_between(x, y3, y4, where=y4>y3, facecolor='yellow', alpha=0.3)
plt.ylim(0, 5)
plt.legend(loc=0)

plt.show()

ちなみに PuLP で解くと以下のようになります。 PuLP は目的関数を最大化するベクトルから解を求めます。

import pulp

x = pulp.LpVariable("x")
y = pulp.LpVariable("y")
problem = pulp.LpProblem("A simple maximization objective",
                         pulp.LpMaximize)
problem += 3*x + 2*y, "The objective function"
problem += 2*x + y <= 6, "1st constraint"
problem += x + y <= 4, "2nd constraint"
problem += y >= 1, "3rd constraint"
problem.solve()

[x.value(), y.value()]

[2.0, 2.0]

関数について

例

コメント