logo

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

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

빌드업 1

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

실전

ζ=0+x1+x2x3=1+x1−x2x4=3−x1x5=2−x2 \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} N={1,2}B={3,4,5}(x1,x2,x3,x4,x5)=(0,0,1,3,2)ζˉ=0 \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 의 꼴을 보면 x1x_{1} 과 x2x_{2} 둘 다 증가시킬 수는 있지만, 제약조건에서 x4=3−x1x_{4} = 3 - x_{1} 과 x5=2−x2x_{5} = 2 - x_{2} 를 알고 있고 지금으로썬 큰 의미가 없어보인다. 이에 x3x_{3} 에 대한 조건을 참고해보면 x2=1+x1−x3 x_{2} = 1 + x_{1} - x_{3} 이므로 새로운 딕셔너리는 다음과 같다.

ζ=1+2x1−x3x2=1+x1−x3x4=3−x1x5=1−x1+x3 \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} N={1,3}B={2,4,5}(x1,x2,x3,x4,x5)=(0,1,0,3,2)ζˉ=1 \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

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

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

ζ=3+x3−2x5x1=1+x3−x5x2=2−x5x4=2−x3+x5 \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} N={3,5}B={1,2,4}(x1,x2,x3,x4,x5)=(1,2,0,2,0)ζˉ=3 \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 의 우변에 x3x_{3} 이 더 커질 여지가 있으니 x3x_{3} 를 진입변수로 써보면 x3=2−x4+x5 x_{3} = 2 - x_{4} + x_{5} 이므로

ζ=5−x4−x5x1=3−x4−x2=2−x5x3=2−x4+x5 \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} N={4,5}B={1,2,3}(x1,x2,x3,x4,x5)=(3,2,2,0,0)ζˉ=5 \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 가 커질 일은 없고, 최적화가 끝났음을 알 수 있다. 실제로 처음 주어진 선형계획문제 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=3x_{1} = 3 과 x2=2x_{2} = 2 를 대입해서 검산해보면 주어진 제약조건을 모두 잘 만족하고 목적 함수의 값도 정확히 ζ=ζˉ−0=5\zeta = \bar{\zeta} - 0 = 5 임을 확인할 수 있다.

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

심플렉스 메소드의 모든 것

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

같이보기

브랜드 룰

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

선형계획법에서의 쌍대성

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

  1. Matousek. (2007). Understanding and Using Linear Programming: p57~60. ↩︎

  2. Matousek. (2007). Understanding and Using Linear Programming: p59. ↩︎

  3. Vanderbei. (2020). Linear Programming(5th Edition): p0. ↩︎