2020年3月16日月曜日

Pythonで線形計画問題を解く

『最適化手法入門』を読んでいて、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)が求まっている。
参考までにほかの人のブログ



0 件のコメント: