logo

Pythonで線形計画問題を解く方法 📂最適化理論

Pythonで線形計画問題を解く方法

概要

scipyパッケージを使えばいい1。行列形で示された線形計画問題のA,b,cA, \mathbf{b}, \mathbf{c}を入れて使う。

コード

Maximizex1+x2subject to−x1+x2≤1x1≤3x2≤2 \begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 1 \\ & & x_{1} & & & \le & 3 \\ & & & & x_{2} & \le & 2 \end{matrix}

簡単な例として、x1,x2≥0x_{1} , x_{2} \ge 0でこのような最大化問題を解いてみよう。生エビの寿司屋ではこの問題をシンプレックス・メソッドを使って手で解いてみて、その答え(x1∗,x2∗)=(3,2)\left( x_{1}^{\ast}, x_{2}^{\ast} \right) = (3,2)を知っている。この線形計画問題は

OptimizecTxsubject toAx≤b \begin{matrix} \text{Optimize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} \le \mathbf{b} \end{matrix}

このような形でc=(1,1)\mathbf{c} = (1,1)、A=[−111010]A = \begin{bmatrix} -1 & 1 \\ 1 & 0 \\ 1 & 0 \end{bmatrix}、b=(1,3,2)\mathbf{b} = (1,3,2)であるから、次のように書き換えて解ける。

c = [-1, -1]
A = [[-1, 1], [1, 0], [0, 1]]
b = [1, 3, 2]
x1_bounds = (0, None)
x2_bounds = (0, None)
from scipy.optimize import linprog
res = linprog(c, A_ub=A, b_ub=b, bounds=[x1_bounds, x2_bounds])

ここでc = [1,1]ではなくc = [-1,-1]を使った理由は、linprog()のデフォルトの最適化方向が最小化のためだ。その方向を反転させるだけで、結果は既にわかっているように(x1,x2)=(3,2)=\left( x_{1}, x_{2} \right) = \left( 3,2 \right) =array([3., 2.])だ。

>>> res
     con: array([], dtype=float64)
     fun: -4.99999999998958
 message: 'Optimization terminated successfully.'
     nit: 4
   slack: array([2.00000000e+00, 2.76267897e-12, 7.65787433e-12])
  status: 0
 success: True
       x: array([3., 2.])

環境

  • OS: Windows
  • python: v3.9.7
  • scipy v1.7.3

参考文献

  1. https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html ↩︎