첫 번째 주의 AlgoShitPo에서 Ryute의 지목을 받아 Simplex Method를 작성하게 된 ahgus89입니다.
서론
Simplex Method는 Linear Programming(LP) 문제를 해결하는 방법 중 하나입니다.
LP는 무엇일까요? 위키백과에 따르면, “주어진 선형 조건을 만족시키면서 선형인 목적 함수를 최적화하는 문제” 라고 합니다.
중학교 때 배운 부등식의 영역 문제를 생각해봅시다. 다음과 같은 문제가 있습니다.
물건 $P$, $Q$를 만들 예정인데, 재료 $A$, $B$가 각각 $100g$씩 있습니다. $P$ $1g$를 만들 때는 $A$를 $1g$, $B$를 $2g$ 사용하며, $Q$ $1g$를 만들 때는 $A$를 $3g$, $B$를 $1g$ 사용합니다. $P$ $1g$당 이익은 $50$원, $Q$ $1g$당 이익은 $60$원 이라고 할 때, 얻을 수 있는 최대 이익은 얼마일까요?
이런 문제는 $A$, $B$의 제한된 양을 바탕으로 부등식을 세우고, 이익에 해당하는 함수를 최대화하는 지점을 찾으면 쉽게 풀 수 있었습니다. LP는 이런 문제의 일반화된 버전이라고 생각할 수 있습니다. 주어진 부등식, 구해야 할 함수가 모두 1차함수(선형) 인 경우를 LP라고 부르고, 이를 푸는 여러 가지 방법이 있습니다.
식 세우기
위의 문제를 직접 풀어볼까요? $P$를 $x_1 g$, $Q$를 $x_2 g$ 만들어서 $f$의 이익을 얻는다고 합시다. 그러면 아래와 같은 식이 등장합니다.
\[x_1 + 3x_2 \leq 100\] \[2x_1 + x_2 \leq 100\] \[f = 50x_1 + 60x_2\] \[x_1, x_2 \geq 0\]중학교 때는, 제약 조건에 해당하는 식을 좌표평면에 그려서 해를 쉽게 찾을 수 있었지만, 변수와 식의 개수가 많아지면 이 방법은 쓰기 힘들어집니다.
Simplex Method
위 두 식을 만족하는 $x_1$, $x_2$에 대해 아래 식을 만족하는 변수 $x_3$, $x_4$가 존재합니다.
\[x_1 + 3x_2 + x_3 = 100\] \[2x_1 + x_2 +x_4 = 100\] \[x_1, x_2, x_3, x_4 \geq 0\]이러한 $x_3$, $x_4$를 여유 변수(slack variable)이라고 부릅니다.
이제 문제는 위와 같은 방정식에서 $-50x_1 -60x_2 + f = 0$ 인 $f$를 최대화하는 것입니다.
이를 행렬로 나타내면 다음과 같습니다.
\[\begin{pmatrix} 1&3&1&0&0&100 \\\ 2&1&0&1&0&100 \\\ -50&-60&0&0&1&0 \end{pmatrix}\]이렇게 만들어진 행렬에, 기본 행 연산만을 적용하여 해를 찾을 수 있습니다.
기본 행 연산은 다음과 같은 세 가지 연산을 의미합니다.
- 두 행을 서로 교환합니다.
- 한 행에 0이 아닌 실수를 곱합니다.
- 한 행에 다른 행의 실수배를 더합니다.
해를 찾는 알고리즘은 다음과 같습니다.
- 마지막 행에서 마지막 원소를 제외하고, 가장 작은 원소를 찾습니다. 그 원소가 음수가 아니면, 알고리즘을 종료합니다.
- 나머지 행들 중 $마지막\space원소 \over 1에서\space찾은\space원소가\space있는\space열의\space원소$가 최대인 행을 찾는다.
- 행연산을 이용해 1에서 찾은 원소가 있는 열의 원소 중 그 행에 해당하는 원소를 1로 만들고, 나머지를 0으로 만듭니다.
- 1로 돌아갑니다.
이렇게 얻은 행렬의 마지막 행은, 마지막 원소를 제외하고 모든 원소가 음이 아닙니다.
따라서 그 방정식에서 $f$를 제외한 다른 모든 원소가 $0$인 경우의 해(마지막 원소)가 우리가 원하는 해가 됩니다.
예시
위에서 찾은 행렬인 $\begin{pmatrix} 1&3&1&0&0&100 \\ 2&1&0&1&0&100 \\ -50&-60&0&0&1&0 \end{pmatrix}$로 문제를 풀어봅시다.
최솟값인 $-60$이 있는 두 번째 열을 보겠습니다. $100/3 < 100$ 이므로 첫 번째 행을 선택합니다.
$ \begin{pmatrix} 1&3&1&0&0&100 \\ 2&1&0&1&0&100 \\ -50&-60&0&0&1&0 \end{pmatrix} \approx \begin{pmatrix} 1\over3&1&1\over3&0&0&100\over3 \\ 2&1&0&1&0&100 \\ -50&-60&0&0&1&0 \end{pmatrix} \approx \begin{pmatrix} 1\over3&1&1\over3&0&0&100\over3 \\ 5\over3&0&- 1\over3&1&0&200\over3 \\ -30&0&20&0&1&2000 \end{pmatrix} $
최솟값인 $-30$이 있는 첫 번째 열을 보겠습니다. $100 > 40$ 이므로 두 번째 행을 선택합니다.
$ \begin{pmatrix} 1\over3&1&1\over3&0&0&100\over3 \\ 5\over3&0&- 1\over3&1&0&200\over3 \\ -30&0&20&0&1&2000 \end{pmatrix} \approx \begin{pmatrix} 1\over3&1&1\over3&0&0&100\over3 \\ 1&0&- 1\over5&3\over5&0&40 \\ -30&0&20&0&1&2000 \end{pmatrix} \approx \begin{pmatrix} 0&1&2\over5&0&0&20 \\ 1&0&- 1\over5&3\over5&0&40 \\ 0&0&26&18&1&3200 \end{pmatrix} $
마지막 행의 모든 원소가 음이 아니므로, 알고리즘을 종료합니다.
마지막 행을 다시 써보면, $26x_3 + 18x_4 + f = 3200$이 됩니다. 따라서 $x_3 = x_4 = 0$ 일 때 $f = 3200$으로 최대가 되고, 이때 $x_1 = 40, x_2 = 20$이 됩니다.
시간 복잡도
마지막 행이 모두 음이 아닌 원소가 될 때 까지 계속 행연산을 진행하는데, 마지막 행의 각 원소가 음수일 수 있으므로, 가능한 상태가 $O(2^n)$개가 됩니다. 실제로 이런 최악의 경우가 존재하고, 따라서 다항 시간에 작동하지 않을 수 있습니다.
다만 현실적인 상황에서, 또는 랜덤 데이터에서는 평균 다항 시간에 작동함이 알려져 있고, 실제로도 매우 빠르게 작동합니다.
항상 다항 시간을 보장하는 여러 방법이 있고, 특히 Min-cost flow로 바꾸어 풀 수 있다고 합니다. 더 자세한 내용을 알고 싶다면 여기를 참고합시다.
연습 문제로는 이 문제가 있습니다.