線形計画法のソルバの使い方：Python

最近，線形計画法のソルバを使ってあれこれしました．使うために色々調べたわけですが，時間が立つと調べた内容を忘れそうなので記録しておきます．

線形計画法のソルバはPuLPというライブラリから呼び出して使います．

PuLPインストール

方法は色々有るようですが，私の場合はコマンドプロンプトから，

pip install pulp

と打ってインストールしました．

例題を解いてみる

こういう最適化問題があるとします．
　 ${ \displaystyle \max ~{ 4x_{ 1 }+3x_{ 2 } } }$
　 ${ \displaystyle s.t\\ \begin{cases} 2x_{ 1 }+3x_{ 2 }\le 15 \\ 2x_{ 1 }+x_{ 2 }\le 9 \\ x_{ 1 }\ge 0,x_{ 2 }\ge 0 \\ \end{cases} }$

　これは ${ \displaystyle x_1=3,~x_2=3 }$ が答えなのですが，本当にそうなるかを試します．

バッチ処理版

細かいところを説明する前に，まずは全体像をお見せします．バッチ処理で書くとこんな感じです．

#　(1)ライブラリ呼び出し
import pulp 

#　(2)問題の定義
lp = pulp.LpProblem('lp', pulp.LpMaximize)

#　(3)変数の設定
x1 = pulp.LpVariable('x1', 0)
x2 = pulp.LpVariable('x2', 0)

#　(4)評価関数の生成
lp += 4*x1 + 3*x2

#　(5)制約条件の生成
lp += 2*x1 + 3*x2 <= 15
lp += 2*x1 + x2 <= 9

#　(6)最適化問題の確認
print(lp)

#　(7)求解
lp.solve()

#　(8)結果の確認
print('x1=',x1.value())
print('x2=',x2.value())

これを読み込むと，

lp:
MAXIMIZE
4*x1 + 3*x2 + 0
SUBJECT TO
_C1: 2 x1 + 3 x2 <= 15

_C2: 2 x1 + x2 <= 9

VARIABLES
x1 Continuous
x2 Continuous

x1= 3.0
x2= 3.0

おぉ．ちゃんと ${ \displaystyle x_1=3,~x_2=3 }$ が出力されました．

解説

(1)ライブラリの呼び出し

これは何も説明する必要はないと思います．

import pulp

(2)問題の定義

pulp.LpProblemで最大化問題か最小化問題かを設定するそうです．引数はそれぞれ下記のようになります．

pulp.LpProblem(『1.問題の名前』, 『2.最大化or最小化』)

『1.問題の名前』で問題の名前を決めるらしいです．
『2.最大化or最小化』では最小化問題ならLpMinimize ，最大化問題なら LpMaximizeと入力します．デフォルトではLpMinimizeです．

これに関しても，下記のリンク先に英語で載っていますので，ご参考にしていただければと思います．

pulp: Pulp classes — PuLP v1.4.6 documentation

今回は最大化問題なので次のように書きました．

lp = pulp.LpProblem('lp', pulp.LpMaximize)

(3)変数の生成

pulp.LpVariableで変数を作ります．引数はそれぞれ

pulp.LpVariable(『1.名前』, 『2.変数の最小値』,『3.変数の最大値』, 『4.連続値or離散値or01』, 『5.e』)

を意味するらしいです．要するに

『1.名前』では変数の名前を入力する
『2.変数の最小値』では，文字通り変数の最小値を入力します．何も入れないと設定されないようです．
『3.変数の最大値』では，同じく最大値を入力します．何も入れないと設定されないようです．
『4.連続値or離散値or01』では Integer(整数計画問題), Binary(0,1) or Continuous(連続値)を入力するそうです．デフォルトではContinuous(連続値)だそうです
『5.e』は列ベースのモデリングに使用されるそうですが，正直良くわかりません．

ということみたいです．下記のリンク先に英語で書いてあるので，こちらも御覧ください．

pulp: Pulp classes — PuLP v1.4.6 documentation

今回は制約条件より ${ \displaystyle x_{ 1 }\ge 0,x_{ 2 }\ge 0 }$ なので，下記のように入力しました．

x1 = pulp.LpVariable('x1', 0)
x2 = pulp.LpVariable('x2', 0)

(4)評価関数の生成

評価関数はさっき作ったオブジェクトに足していくみたいです．

lp += 4*x1 + 3*x2

(5)制約条件の生成

制約条件もさっき作ったオブジェクトに足していくみたいです．

lp += 2*x1 + 3*x2 <= 15
lp += 2*x1 + x2 <= 9

(6)最適化問題の確認

さっき作ったオブジェクトlpを出力すれば問題が表示されます．どういう問題を解くか？というのが見れます．

print(lp)

と書くと

lp:
MAXIMIZE
4*x1 + 3*x2 + 0
SUBJECT TO
_C1: 2 x1 + 3 x2 <= 15

_C2: 2 x1 + x2 <= 9

と出力されます．

(7)求解

さっきのオブジェクトに，.solve()モジュールをくっつけます．

lp.solve()

(8)計算結果の確認

変数に.value()モジュールをくっつければ，結果が見れます．

print(x1.value())
print(x2.value())

参考

nullege.com
scaron.info