Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした