파이썬으로 선형계획문제 푸는 법
개요
scipy 패키지를 사용하면 된다1. 행렬 꼴로 나타난 선형계획문제의 $A, \mathbf{b}, \mathbf{c}$ 를 넣어서 쓴다.
코드
$$ \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} $$
간단한 예제로써 $x_{1} , x_{2} \ge 0$ 에서 위와 같은 최대화 문제를 풀어보자. 생새우초밥집에서는 이 문제를 심플렉스 메소드를 써서 손으로 풀어보았고 그 답 $\left( x_{1}^{\ast}, x_{2}^{\ast} \right) = (3,2)$ 를 알고 있다. 이 선형계획문제는
$$ \begin{matrix} \text{Optimize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} \le \mathbf{b} \end{matrix} $$
위와 같은 꼴에서 $\mathbf{c} = (1,1)$, $A = \begin{bmatrix} -1 & 1 \\ 1 & 0 \\ 1 & 0 \end{bmatrix}$, $\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()의 기본적인 최적화 방향이 최소화기 때문이다. 그 방향만 반전해주면 최대화와 마찬가지고, 그 결과는 우리가 이미 알고 있던 것처럼 $\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