Pythonで線形計画問題を解く

『最適化手法入門』を読んでいて、Pythonで線形計画問題を解く方法が載っていたのでメモ。

CVXPYをダウンロード、インポートして使う。

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)が求まっている。

参考までにほかの人のブログ

Python製凸最適化モデリングツールCVXPYの使い方 - MyEnigma