【最適化シリーズ NO.1】Pythonによる線形計画法の最適化
2.Pythonを使わずに数学で解く。
で表される領域は、斜線部分（境界線を含む）のようになる。
とすると、
となり、これは、傾き，傾き
で
切片が
の直線である。よって、この直線が
を通るときに、
は最大になる。
その時のの値は、
を解いて
となり、
点において最大値は13をとる。
という解き方です。高校数学でくわしく習います。
3.Python（pulp）を使って解く
数理最適化用の「PuLP」というライブラリを見つけたので、使ってみます。
プログラム
from pulp import * m = LpProblem(sense=LpMaximize) #1. 数理モデルを作成（最大化） x = LpVariable('x') # 2.変数の作成 y = LpVariable('y') m += 4 * x + 5 * y # 3.目的関数の設定 m += x >= 0 #4.変数の制約条件の作成 m += y >=0 m += x + y <= 3 m += x + 2*y <= 4 m.solve() #最適化を実行 Max_x = value(x) Max_y = value(y) MaxValue = 4 * value(x) + 5 * value(y) print("x = " + str(Max_x)) print("y = " + str(Max_y)) print("のとき、最大値" + str(MaxValue))
実行結果：
x = 2.0 y = 1.0 のとき、最大値13.0
解説
上記の問題は、目的関数 を最大化する
の値を、制約条件を満たしながら求める、というものです。なので、最適化を行うためには、
| 目的関数 | |
|---|---|
| 変数 | |
| 制約条件 |
の３つをプログラムとして記述する必要があります。
では、実際のコードを見ていきます。
STEP1. 数理モデルの作成
m = LpProblem(sense=LpMaximize) #1. 数理モデルを作成（最大化）
目的関数を最大化するための数理モデルを作製します。
目的関数を最小化したい時はこのように書きます。
m = LpProblem() #1. 数理モデルを作成（最小化）
STEP2. 変数の作成
x = LpVariable('x') # 2.変数の作成 y = LpVariable('y')
LpVariable で変数を作成します。
元の構文はこのようになっています。
LpVariable(name, lowBound=None, upBound=None, cat='Continuous', e=None)
| name | 変数名 | |
|---|---|---|
| lowbound | 変数の最小値。デフォルトは-inf | |
| upBound | 変数の最大値。デフォルトは +inf | |
| cat | 変数の種類（整数、小数（←デフォルト）等 |
使い方の例
LpVariable('y', lowbound = 0) #正の数 LpVariable('y', lowerbound = 0, upbound = 100, cat = 'Integer') #0~100の整数
STEP3. 目的関数の作成
目的関数を設定するには、次のように書きます。
m += 4 * x + 5 * y # 3.目的関数の設定
STEP4. 制約条件の作成
制約条件を設定するには、次のように書きます。
今回は4つの条件があるので、それらを順番に記述していきます。
m += x >= 0 #4.変数の制約条件の作成 m += y >=0 m += x + y <= 3 m += x + 2*y <= 4
STEP5. 最適化の実行
solve()で最適化を実行します。
m.solve() #最適化を実行
4.Python（cvxpy）を使って解く
cvxpyは、Anacondaにデフォルトでインストールされていました。
プログラム
x = cvxpy.Variable() y = cvxpy.Variable() objective = cvxpy.Maximize(4 * x + 5 * y) constraints = [0 <= x] constraints += [0 <= y] constraints += [x + y <= 3] constraints += [x + 2*y <= 4] prob = cvxpy.Problem(objective, constraints) result = prob.solve() print("x = ", x.value) print("y = ", y.value) print("のとき、最大値 = ", prob.value)
実行結果：
x = 2.000000025730404 y = 0.9999999678267295 のとき、最大値 = 12.999999942055263
解説
STEP1. 変数の作成
変数を作成します。
x = cvxpy.Variable() y = cvxpy.Variable()
STEP3. 制約条件の作成
制約条件を設定するには、次のように書きます。
今回は4つの条件があるので、それらを順番に記述していきます。
constraints = [0 <= x] constraints += [0 <= y] constraints += [x + y <= 3] constraints += [x + 2*y <= 4]
STEP4. 最適化の実行
solve()で最適化を実行します。
result = prob.solve()
