Python入門トップページ

線形計画問題を Python で解く

目次

1. 準備
2. 例題1

目次に戻る

準備

PuLP というモジュールを使えば，線形計画問題を Python で簡単かつ高速に解くことができる．

PuLP は Anaconda をインストールしただけではインストールされていないので，まずは PuLP をインストールする．PuLP のインストールは「Anaconda Prompt」または「Anaconda Powershell Prompt」で pip install pulp を実行すれば良い．なお，学内の情報処理実習室では pip install pulp --user のように --user オプションを指定する必要があるかもしれません．また，インストールされているモジュールの一覧は pip list で確認できる．Jupyter Notebook のマジックコマンドを利用しても構いません．

目次に戻る

例題1

次の線形計画問題を Python で解いてみよう．

まずは PuLP モジュールをインポートする．もしもエラーが表示されたら，準備を参考に，PuLP をインストールしよう．

モジュールのインポートfrom pulp import *

次に問題オブジェクトを生成しよう．問題オブジェクトは LpProblem() 関数で生成できる．このとき sense 引数には，最大化問題を解きたい場合には sense=LpMaximize を，最小化問題を解きたい場合には sense=LpMinimize を指定する．なお，sense 引数を省略した場合は，最小化問題として生成される．

問題オブジェクトの生成problem = LpProblem(name='例題1', sense=LpMaximize)

続いて，変数オブジェクトを生成する．x1 と x2 の2変数の問題を解きたいので，LpVariable 関数を2回呼び出す．このとき，x1 と x2 の最小値制約を lowBound = 0 のように指定することができる．

変数オブジェクトの生成x1 = LpVariable('x1', lowBound=0)
x2 = LpVariable('x2', lowBound=0)

いよいよ目的関数を設定する．目的関数は次のとおり既に生成した問題オブジェクト problem に足すように代入すれば設定できる．

目的関数の設定problem += 3 * x1 + 4 * x2

さらに，制約式を追加しよう．次のとおり目的関数と同様に問題オブジェクト problem に足すだけで設定できてしまう．

制約式の設定problem += x1 +  x2 <= 5
problem += x1 + 2 * x2 <= 7
problem += x1 <= 4
problem += x2 <= 3

なお，制約式には次のような演算子が利用できる．「等しい」は == のように = を2つ並べて書くことに注意する必要がある．

ここで，設定した問題を表示し，その内容を確認しよう．

問題の確認print(problem)

例題1:
MAXIMIZE
3*x1 + 4*x2 + 0
SUBJECT TO
_C1: x1 + x2 <= 5

_C2: x1 + 2 x2 <= 7

_C3: x1 <= 4

_C4: x2 <= 3

VARIABLES
x1 Continuous
x2 Continuous

問題を解く前に，現在の問題のステータスを確認しておく．もちろん，まだ解かれていない Not Solved である．

問題のステータスを確認print("Status : ", LpStatus[problem.status])

Status :  Not Solved

変数の一覧とその値も確認しておく．変数 x1 と x2 が定義されているが，値はまだ設定されていない．

for v in problem.variables():
  print(v.name, "=", v.varValue)

x1 = None
x2 = None

solve() 関数で問題を解く．

問題を解くproblem.solve()

1

問題が解けたようなので，再度ステータスを確認する．最適解 (Optimal solution) が得られたことがわかる．

print("Status : ", LpStatus[problem.status])

Status :  Optimal

変数の値を確認する．これらの値が目的関数を最大化する変数の値です．

for v in problem.variables():
    print(v.name, "=", v.varValue)

x1 = 3.0
x2 = 2.0

最大化された目的関数の値を確認する．

print("z = ", value(problem.objective))

z =  17.0

すべてのコードをまとめると次のようになる．

# モジュールをインポート
from pulp import *

# 問題オブジェクトを作る
problem = LpProblem(name='例題1', sense=LpMaximize)
# 変数オブジェクトを作る
x1 = LpVariable('x1', lowBound=0)
x2 = LpVariable('x2', lowBound=0)
# 目的関数を設定する
problem += 3 * x1 + 4 * x2
# 制約条件を作る
problem += x1 +  x2 <= 5
problem += x1 + 2 * x2 <= 7
problem += x1 <= 4
problem += x2 <= 3

# 問題を表示する
print(problem)

# 問題を解く
problem.solve()

# 問題のステータス
print("Status : ", LpStatus[problem.status])

# 結果を表示しよう
for v in problem.variables():
    print(v.name, "=", v.varValue)

# 最適解を計算する
print("z = ", value(problem.objective))

例題1:
MAXIMIZE
3*x1 + 4*x2 + 0
SUBJECT TO
_C1: x1 + x2 <= 5

_C2: x1 + 2 x2 <= 7

_C3: x1 <= 4

_C4: x2 <= 3

VARIABLES
x1 Continuous
x2 Continuous

Status :  Optimal
x1 = 3.0
x2 = 2.0
z =  17.0

なお，pulp の LpVariable で作成した変数は通常の Python 変数とは異なります．したがって，次のように print(x1) としても値を表示できません．

print(x1)

x1

LpVariable で作成した変数の型は LpVariable 型です．

type(x1)

pulp.pulp.LpVariable

これら LpVariable 型変数の値を表示するには，次のような方法があります．

print(x1.varValue)
print(x1.value())
print(value(x1))

3.0
3.0
3.0

よって，3つ目の書き方を使う場合には，次のような方法で最適解を自分で計算することも可能です．

# 最適解を計算する
z = 3 * value(x1) + 4 * value(x2)
print("z =", z)

z = 17.0

ここで説明しているように，ライブラリのインポートで from ライブラリ名 import * の書き方を避ける場合は，次のように pulp ライブラリで定義される関数や定数の全てに pulp. を付ける必要があります．入力は面倒になりますが，それらが pulp で定義された関数であることが明確になるという利点もあります．

プログラムの全体# モジュールをインポート
import pulp

# 問題オブジェクトを作る
problem = pulp.LpProblem(name='例題1', sense=pulp.LpMaximize)
# 変数オブジェクトを作る
x1 = pulp.LpVariable('x1', lowBound=0)
x2 = pulp.LpVariable('x2', lowBound=0)
# 目的関数を設定する
problem += 3 * x1 + 4 * x2
# 制約条件を作る
problem += x1 +  x2 <= 5
problem += x1 + 2 * x2 <= 7
problem += x1 <= 4
problem += x2 <= 3

# 問題を表示する
print(problem)

# 問題を解く
problem.solve()

# 問題のステータス
print("Status : ", pulp.LpStatus[problem.status])

# 結果を表示しよう
for v in problem.variables():
    print(v.name, "=", v.varValue)

# 最適解を計算する
print("z = ", pulp.value(problem.objective))

目次に戻る