[Modeling] 파이썬으로 선형계획법 최적화하기 | SciPy

선형계획법. 영어로는 Linear Programming(LP) 라고 한다. 말은 그럴싸해보이고 뭔가 어려워보일 수도 있지만, 수학적인 기초 적용방법에 대해서는 이미 중고등학교 때 일차 부등식의 해를 구하는 단원에서 문제 해결방법에 대해 충분히 학습했다.

 

지금은 이렇게 중등 수학으로 분류되어 있지만, 2차 세계대전 군수 자원의 효율적 배분 등을 위해서 적극적으로 이용된 꽤나 유서가 깊은 분야이다. 현재도 경영 경제 분야에서 활발히 사용되고 있고, 선형계획법의 특수한 경우인 네트워크 흐름 같은 문제에 대한 알고리즘이 연구되고 있다고 한다.

 

최근에 하나의 최적화 문제를 시뮬레이션을 해야 했었는데, 그 기반이 되는 논문이 선형계획법을 사용했기 때문에 Python을 통해 시뮬레이션을 했던 내용 중 가장 핵심이 됐던 LP에 대해 간단히 정리하고자 한다.

 

나 같은 경우는 자원의 사용을 최대화가 아닌, 최소화하는 문제였어서 옆에서 확인할 수 있는 형태를 푸는 것었다. 옆의 사진은 행렬식이기 때문에 어느정도 감안해서 위의 모양대로 처리해주는 것이 필요하다. 

 

이 문제를 풀기 위해 Scipy.org에서 만들어준 scipy.optimize.linprog를 이용하면, 다음과 같이 접근하면 된다.

 

 

from scipy.optimize import linprog

c = [...]           				# ... 은 x의 변수 개수에 맞춰 작성
A = [[...], ... ,[...]]  			# A 처럼 2-D Array는 안에 있는 리스트 개수 = 조건의 개수
b = [...]
Aq = []								# equality 조건은 필요조건이 아님
bq = []
Bound = []

res = linprog(c, A_ub=A, b_ub=b, A_eq=Aq, b_eq=bq, bounds=Bound)

사실 여기서 언급한 거 외에도, 다양한 옵션이 있지만 그건 너무 세부적인 사항이라 제외하였다.

 

Scipy.org에서 제공하는 예제를 통해 살펴보면, 사용에 대해 금방 익힐 수 있다. 옆 그림과 같은 최소화 문제가 있다 고 하자. 우리가 배웠던 중고등학교 때 최대 최소 문제로 바꿔서 읽는다면, x0를 x로 x1을 y로 치환해서 -x+4y가 최소로 값을 갖는 문제로 생각할 수 있다.

 

그렇게 바꿔놓고 본다면, 직접 손으로 써서 풀 수 있는 분도 여럿 있으리라 생각하지만, python을 이용하면 좀 더 빠르게 풀 수 있다. 코드는 아래와 같이 작성가능하다.

 

from scipy.optimize import linprog

c = [-1, 4]
A = [[-3, 1], [1, 2]]
b = [6, 4]
x0_bounds = (None, None)
x1_bounds = (-3, None)

res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds])
print(res)

결과 값은 아래와 같다. 다른 값들은 우리가 풀고싶은 문제의 본질과 조금은 거리가 있는 부가적인 설명들이고, 따라서 우리가 체크해야 할 것들은 message, status, success만 큰 문제없이 성공여부를 알려줬을 때 x가 우리가 원하는 해라는 것만 이해하면 충분하다.

 

     con: array([], dtype=float64)
     fun: -21.99999984082494
 message: 'Optimization terminated successfully.'
     nit: 6
   slack: array([3.89999997e+01, 8.46872439e-08]
  status: 0
 success: True
       x: array([ 9.99999989, -2.99999999]) 

 

 

 

출처: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html