読者です 読者をやめる 読者になる 読者になる

メモランダム!!

自分用の端書のため,他の人が読めるようには書いていません.悪しからずm(_ _)m

線形計画法のソルバの使い方: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です.

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

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

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』は列ベースのモデリングに使用されるそうですが,正直良くわかりません.

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

今回は制約条件より { \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())