SciPyで線形計画問題を解く

scipy_logo

Pythonの数値計算ライブラリ SciPy には線形計画問題を解くための scipy.optimize.linprog という関数が存在します。
この関数を使って、線形計画問題を実際にといてみます。

例として次のような線形計画問題を考えましょう

maximize

z = x_1 + 2 x_2

subject to

\\ x_1 + 3 x_2 \leq 24 \\ 4 x_1 + 4 x_2 \leq 48 \\ 2 x_1 + x_2 \leq 22 \\ x_1, x_2 \geq 0

目的関数の右辺に -1 をかけて、目的関数の最大化を目的関数の最小化に変えます。

minimize

z = - x_1 -2 x_2

これを行列で表します。

z = \begin{bmatrix} -1 & -2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}  \\  \begin{bmatrix} x_1 & 3 x_2 \\ 4 x_1 & 4 x_2 \\ 2 x_1 & x_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} 24 \\ 48 \\ 22 \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}.

あとは、行列をリストで表現し、SciPyプログラム(linear-prog.py)に落とします。

# vim: set fileencoding=utf-8
c = [-1, -2] # 目的関数
A = [[1, 3], [4, 4], [2, 1]] # 決定変数の係数
b = [24, 48, 22]

# 決定変数の下限、上限
x0_bounds = (0, None)
x1_bounds = (0, None)

from scipy.optimize import linprog
res = linprog(c, A_ub=A, b_ub=b, bounds=(x0_bounds, x1_bounds),
              options={"disp": True})
print res

実行します。

$ python linear-prog.py
Optimization terminated successfully.
         Current function value: -18.000000
         Iterations: 2
  status: 0
   slack: array([ 0.,  0.,  4.])
 success: True
     fun: -18.0
       x: array([ 6.,  6.])
 message: 'Optimization terminated successfully.'
     nit: 2

linprog関数の引数で {"disp": True} にしていると

Optimization terminated successfully.
         Current function value: -18.000000
         Iterations: 2

のブロックのメッセージが表示されます。

“Optimization terminated successfully.” というメッセージからわかるように、問題は無事とけました。

出力結果をもう少し詳しく見てみましょう。

status: 0

最適化の終了ステータスです。

最適解を見つけられると 0 になります。
指定されたイテレーション内にとけないなど、とけなかった時は1以上の値になります。

slack: array([ 0., 0., 4.])

制約の不等式を等式標準形に直します。

subject to
\\ x_1 + 3  x_2 + x_3 = 24 \\ 4  x_1 + 4 x_2 + x_4 = 48 \\ 2  x_1 + x_2 + x_5 = 22 \\ x_1, x_2, x_3, x_4, x_5 \geq 0

目的関数が最小値を取るとき、このスラック変数 x_3, x_4, x_5 はそれぞれ 0, 0, 4 の値を取ります。

fun: -18.0

目的関数の最小値です。

x: array([ 6., 6.])

目的関数が最小値を取るとき、決定変数 x_1, x_2 はともに 6 を取ります。

nit: 2

nit number of iterations のことで、シンプレクス法のイテレーション数です。

補足

線形計画問題を解くためには SciPy よりも PuLP を使っている人のほうが多いように見受けられます。

現在のところ、ソルバーとしてシンプレクス法しか対応していません。

目的関数で最大値を求めることはできません。
-1 をかけて、最小値問題に帰着させます。

最適結果オブジェクト(上の例では res) からは、各種属性 x, slack, success, status, nit, message に対して res.slackというようにしてアクセスできます。

参考リンク

Advertisements
Tagged with: ,
Posted in algorithm, python

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives

Error: Twitter did not respond. Please wait a few minutes and refresh this page.

%d bloggers like this: