선형계획법의 심플렉스 메소드 📂최적화이론

선형계획법의 심플렉스 메소드

빌드업 ¹

$x_{1} , x_{2} \ge 0$ 에 대해 다음과 같은 선형계획문제가 주어져 있다고 하자. $$ \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}$ 를 최대화하길 원한다. 이를 방정식 폼으로 바꾸려면 슬랙 변수^{slack variable} $x_{3}, x_{4}, x_{5} \ge 0$ 을 도입해서 $$ \begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & + & x_{3} & & & & & = & 1 \\ & & x_{1} & & & & & + & x_{4} & & & = & 3 \\ & & & & x_{2} & & & & & + & x_{5} & = & 2 \end{matrix} $$ 와 같이 나타내면 된다. 이를 다시 한 번 딕셔너리 혹은 태블로로 나타내면 원래의 $x_{1}$, $x_{2}$ 는 비기저변수^{nonbasic variable}가 되어 우변에 남고, $x_{3}$, $x_{4}$, $x_{5}$ 는 기저변수^{basic variable}가 되어 좌변으로 가서 $$ \begin{matrix} \zeta & = & & 0 & + & x_{1} & + & x_{2} \\ x_{3} & = & & 1 & + & x_{1} & - & x_{2} \\ x_{4} & = & & 3 & - & x_{1} & & \\ x_{5} & = & & 2 & & & - & x_{2} \end{matrix} $$ $$ \mathcal{N} = \left\{ 1, 2 \right\} \\ \mathcal{B} = \left\{ 3, 4, 5 \right\} $$ 와 같이 표현된다. 여기서 $\zeta = \bar{\zeta} + x_{1} + x_{2}$ 의 $\bar{\zeta}$ 는 최적해에 대한 목적 함수의 함숫값, 쉽게 말해 지금 얼마나 최적화 되었는지를 의미한다고 보면 된다. 이에 아래의 여러 방정식들을 통해 변수치환을 하다보면 $\zeta$ 의 우변에 있는 비기저변수들의 부호를 $-$ 로 통일할 수 있을지도 모른다. 그러면 모든 비기저변수에 $0$ 을 넣었을 때 $$ \zeta = \zeta_{?} - x_{?_{1}} - x_{?_{2}} $$ 꼴은 가장 큰 값이 될 것이다. 다시 말해 기저가용해를 얻는 것인데, 비기저변수의 부호 중 $+$ 가 있다는 것은 아직 $\zeta_{?}$ 가 더 커질 가능성이 있다는 것이고 모든 부호가 $-$ 라는 것은 이제 더 이상 $\zeta_{?}$ 를 커지게 할 수 없다는 의미가 된다. 이것이 바로 심플렉스 메소드^{simplex method}의 아이디어다. 단순히 대수적으로만 문제를 푸는 것 같은데 심플렉스라는 표현을 사용하는 이유는 슬랙 변수를 넣어 방정식 폼을 만든 시점에서 해공간이 심플렉스가 되기 때문이다.

실전

$$ \begin{matrix} \zeta & = & & 0 & + & x_{1} & + & x_{2} \\ x_{3} & = & & 1 & + & x_{1} & - & x_{2} \\ x_{4} & = & & 3 & - & x_{1} & & \\ x_{5} & = & & 2 & & & - & x_{2} \end{matrix} $$ $$ \mathcal{N} = \left\{ 1, 2 \right\} \\ \mathcal{B} = \left\{ 3, 4, 5 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (0,0,1,3,2) \\ \bar{\zeta} = 0 $$

실제로 위의 예제를 심플렉스 메소드로 풀어보자.

$\zeta$ 의 꼴을 보면 $x_{1}$ 과 $x_{2}$ 둘 다 증가시킬 수는 있지만, 제약조건에서 $x_{4} = 3 - x_{1}$ 과 $x_{5} = 2 - x_{2}$ 를 알고 있고 지금으로썬 큰 의미가 없어보인다. 이에 $x_{3}$ 에 대한 조건을 참고해보면 $$ x_{2} = 1 + x_{1} - x_{3} $$ 이므로 새로운 딕셔너리는 다음과 같다.

$$ \begin{matrix} \zeta & = & & 1 & + & 2x_{1} & - & x_{3} \\ x_{2} & = & & 1 & + & x_{1} & - & x_{3} \\ x_{4} & = & & 3 & - & x_{1} & & \\ x_{5} & = & & 1 & - & x_{1} & + & x_{3} \end{matrix} $$ $$ \mathcal{N} = \left\{ 1, 3 \right\} \\ \mathcal{B} = \left\{ 2, 4, 5 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (0,1,0,3,2) \\ \bar{\zeta} = 1 $$

수식에서 확인할 수 있듯 우리는 목적 함수의 함숫값을 기존 대비 $1$ 만큼 증가시켰다. 이렇게 딕셔너리를 고쳐쓰는 과정을 피벗 스텝^{pivot Step}이라 부르며², 비기저에서 기저로 들어간 $x_{2}$ 와 같은 변수를 진입 변수^{entering variable}, 기저에서 비기저로 나온 $x_{3}$ 와 같은 변수를 이탈 변수^{leaving variable}라 부른다³. 여기서 헷갈리면 안 되는게, 우리는 목적 함수 자체를 바꾼 적이 없고 앞으로도 그럴 일은 없다. 처음 빌드업에서부터 그러했듯 기존의 변수가 다른 변수로 나타날 뿐이고 원래 안 보이던 상수항이 이제 보이는 것 뿐이다.

지금의 딕셔너리에서 우리가 해야할 일은 꽤 명확해보인다. $x_{1}$ 을 증가시키면 그 양의 두배만큼 목적 함수가 커질 것 같다. 방금과 같은 이유로 $x_{5}$ 를 진입변수로 써보면 $$ x_{1} = 1 + x_{3} - x_{5} $$ 이므로

$$ \begin{matrix} \zeta & = & & 3 & + & x_{3} & - & 2x_{5} \\ x_{1} & = & & 1 & + & x_{3} & - & x_{5} \\ x_{2} & = & & 2 & & & - & x_{5} \\ x_{4} & = & & 2 & - & x_{3} & + & x_{5} \end{matrix} $$ $$ \mathcal{N} = \left\{ 3, 5 \right\} \\ \mathcal{B} = \left\{ 1, 2, 4 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (1,2,0,2,0) \\ \bar{\zeta} = 3 $$

이다. $\zeta$ 의 우변에 $x_{3}$ 이 더 커질 여지가 있으니 $x_{3}$ 를 진입변수로 써보면 $$ x_{3} = 2 - x_{4} + x_{5} $$ 이므로

$$ \begin{matrix} \zeta & = & & 5 & - & x_{4} & - & x_{5} \\ x_{1} & = & & 3 & - & x_{4} & - & \\ x_{2} & = & & 2 & & & - & x_{5} \\ x_{3} & = & & 2 & - & x_{4} & + & x_{5} \end{matrix} $$ $$ \mathcal{N} = \left\{ 4, 5 \right\} \\ \mathcal{B} = \left\{ 1, 2, 3 \right\} \\ \left( x_{1} , x_{2} , x_{3}, x_{4} , x_{5} \right) = (3,2,2,0,0) \\ \bar{\zeta} = 5 $$

을 얻는다. 이제 $\zeta$ 의 우변에는 모든 변수의 부호가 $-$ 여서 어떤 변수를 건드려도 $\zeta$ 가 커질 일은 없고, 최적화가 끝났음을 알 수 있다. 실제로 처음 주어진 선형계획문제 $$ \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} = 3$ 과 $x_{2} = 2$ 를 대입해서 검산해보면 주어진 제약조건을 모두 잘 만족하고 목적 함수의 값도 정확히 $\zeta = \bar{\zeta} - 0 = 5$ 임을 확인할 수 있다.

다음은 같은 계산을 컴퓨터로 하는 방법을 소개하는 포스트들이다:

심플렉스 메소드의 모든 것

당연하지만 이 포스트는 심플렉스 메소드의 모든 걸 설명하지 않았다. 문제 풀이 과정에서 변수를 선택하는 기준도 주먹구구식이고 항상 심플렉스 메소드가 통하는지, 속도는 얼마나 빠른지 등 배워야할 것이 산더미처럼 남아있다.

같이보기

브랜드 룰

심플렉스 메소드가 반드시 성공한다는 것을 수학적으로 이해하려면 브랜드 룰을 알아야 한다.

선형계획법에서의 쌍대성

최적화를 전공할 게 아니라 한 과목으로 다룬다면 선형계획법은 심플렉스 메소드와 쌍대성 이 두가지만 배우면 모든 걸 다 배운 것이다. 물론 그 둘 뿐이라고해서 딱히 그 과정이 쉽다는 말은 아니다.

Matousek. (2007). Understanding and Using Linear Programming: p57~60. ↩︎
Matousek. (2007). Understanding and Using Linear Programming: p59. ↩︎
Vanderbei. (2020). Linear Programming(5th Edition): p0. ↩︎