『最適化手法入門』を読んでいて、Pythonで線形計画問題を解く方法が載っていたのでメモ。
CVXPYをダウンロード、インポートして使う。
CVXPYはMATLABのCVXを元にしたPythonの凸計画最適化ツール。Windowsの場合はインストールにVisual Studioのコンパイラーが必要らしいけど私のPCはVSが既にインストールされていたので、Anacondaから pip install cvxpyでインストールできた。
例2.1の問題(2.1)
import cvxpy as cp
x1, x2 = cp.Variable(), cp.Variable()
obj = cp.Maximize(20*x1 + 60*x2)
cons = [5*x1 + 4*x2 <= 80,
2*x1 + 4*x2 <=40,
2*x1 + 8*x2 <=64,
x1 >= 0,
x2 >= 0]
P = cp.Problem(obj, cons)
P.solve(verbose=True)
print(x1.value, x2.value)
ちゃんと最適解(x1, x2)=(8,6)が求まっている。
上の問題を行列で表現し、目的関数に-1をかけて最小化に書き換えたもの。
import cvxpy as cp
import numpy as np
x = cp.Variable(2)
c = np.array([-20.0, -60.0]).T
G = np.array([
[5.0, 4.0],
[2.0, 4.0],
[2.0, 8.0],
[-1.0, 0],
[0, -1.0]])
h = [80.0, 40.0, 64.0, 0.0, 0.0]
obj = cp.Minimize(c.T * x)
cons = [G * x <= h]
P = cp.Problem(obj, cons)
P.solve(verbose=True)
print(x.value)
こちらも最適解(x1, x2)=(8,6)が求まっている。
参考までにほかの人のブログ
