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()
15062601.png

ちなみに 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]

コメント

Comments powered by Disqus
書籍更新情報
2017-02-18
Pythonによる科学技術計算 基礎編
1.4版への更新が可能になりました。
サポートページはこちら
電子書籍
Pythonによる科学技術計算 基礎編
電子書籍
線形代数(1): Pythonによる科学技術計算 実践編