Pythonの数値計算ライブラリ SciPy には線形計画問題を解くための scipy.optimize.linprog という関数が存在します。
この関数を使って、線形計画問題を実際にといてみます。
例として次のような線形計画問題を考えましょう
maximize
subject to
目的関数の右辺に -1 をかけて、目的関数の最大化を目的関数の最小化に変えます。
minimize
これを行列で表します。
あとは、行列をリストで表現し、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_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というようにしてアクセスできます。
Siguniang's Blog 