189
167

More than 1 year has passed since last update.

PuLP による線型計画問題の解き方ことはじめ

Last updated at Posted at 2014-09-18

PuLP とは何か

線形計画問題を解く Python パッケージ。
https://code.google.com/p/pulp-or/
https://pythonhosted.org/PuLP/index.html

線形計画問題とは、目的関数と制約条件が1次式で表される最適化問題。
たとえば、

  • コストと利益が異なるいくつかの製品を、決まった数量作るときに、利益が最大になるような量の組み合わせを見つける。
  • パズルを解く

などが線形計画問題の一つ。

PyConJP 2014 で紹介されていたので使い方を調べてみると、
結構使いやすいのでまとめてみた。

インストール方法

sudo pip install pulp

手順

線形計画問題オブジェクトを作る

これが問題をすべて表現する。
コンストラクタには問題の名前と、目的関数を最小化するか最大化するかを選ぶ。

import pulp
problem = pulp.LpProblem('Problem Name', pulp.LpMinimize) # 最小化する場合
problem = pulp.LpProblem('Problem Name', pulp.LpMaximize) # 最大化する場合

変数オブジェクトを作る

線形計画で使う変数を作る。
作り方は2種類ある。大量の変数があるときは 2 を使うことが多そう。

(1) 1つずつ作る

pulp.LpVariable('name', 0, 1, 'Continuous') 

変数は前から順に、
1. 変数名
2. 変数の最小値
3. 変数の最大値
4. 変数の種類。連続値 (float) なら 'Continuous', 整数なら 'Integer', 2値変数なら 'Binary'

このコードで、変数名 name で、0から1の連続値をとる変数を生成できる。

(2) リストを渡してまとめて作る

var = pulp.LpVariable.dicts('VAR', ([1,2,3], ['a', 'b']), 0, 1, 'Continuous')

変数は前から順に、
1. 変数名の prefix
2. 変数名の postfix のリストのタプル
3. 変数の最小値
4. 変数の最大値
5. 変数の種類

3-5 は前と同じ。

このコードを実行すると、最小値 0, 最大値 1, で連続値をとる
変数群 VAR_1_a, VAR_1_b, VAR_2_a, ... を持つディクショナリが手に入る。
アクセス方法は var[1]['a'] こんな感じ。
これは今後の記事で使う予定。

目的関数を作る

変数を使って式を作り、数理計画問題オブジェクトに足す これがすごい。

たとえば、 ab の和を最小化したいときは

import pulp

problem = pulp.LpProblem('test', pulp.LpMinimize)
a = pulp.LpVariable('a', 0, 1)
b = pulp.LpVariable('b', 0, 1)
problem += a + b

この状態で problem を print すると、問題が表示される。

test:
MINIMIZE
1*a + 1*b + 0
VARIABLES
a <= 1 Continuous
b <= 1 Continuous

制約条件を作る

変数を使って比較を作り、数理計画問題オブジェクトに足す これもすごい。

たとえば、変数 ab の変数について、
1. a は 0以上
2. b は 0.1以上
3. ab の和は 0.5
という制約を作りたいときは、

problem += a >= 0
problem += b >= 0.1
problem += a + b == 0.5

反不等号 (<=, =>) しか使えなかった。

解く

problem.solve()

これだけ。

制約条件によっては解けない場合があるので、結果を知りたいときは、

status = problem.solve()
print pulp.LpStatus[status]

で Optimal が出れば OK

結果を取り出す。

problem に追加した変数の value メソッドを呼ぶと、値が手に入る。

まとめると

import pulp

problem = pulp.LpProblem('sample', pulp.LpMinimize)

a = pulp.LpVariable('a', 0, 1)
b = pulp.LpVariable('b', 0, 1)

problem += a + b

problem += a >= 0
problem += b >= 0.1
problem += a + b == 0.5

status = problem.solve()
print "Status", pulp.LpStatus[status]

print problem

print "Result"
print "a", a.value()
print "b", b.value()

結果は、

Status Optimal
sample:
MINIMIZE
1*a + 1*b + 0
SUBJECT TO
_C1: a >= 0

_C2: b >= 0.1

_C3: a + b = 0.5

VARIABLES
a <= 1 Continuous
b <= 1 Continuous

Result
a 0.4
b 0.1

189
167
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
189
167