5 Simplex Method와 양키스
2017 October
George Bernard Dantzig (ˈdæntsɪɡ)가 1974년에 개발한 단체법(Simplex Method)을 보기 전에 Simplex Mothod의 뿌리인 Dynamic Programming을 보자.
잠깐, Dynamic Programming의 번역어를 아는가? 동적 계획법 혹은 다이나믹 프로그래밍이 익숙할 것이다. 이 용어는 수학자 리처드 벨만(Richard E. Bellman)이 정의한 용어인데, 당시 Dynamic Programming이라고 한 이유를 그의 자서전(Eye of the Hurricane: An Autobiography)에서 볼 수 있다.
나는 RAND 코퍼레이션에서 1950년의 가을을 보냈다. 여기에서 내게 주어진 첫 과제는 다단계 의사 결정 프로세스에 대해 적절한 용어를 명명하는 것이었다. ’동적 계획법’이라는 이름이 어디에서 왔는지 궁금하지 않은가? 1950년대는 내가 수학에 대해 연구하기에는 좋지 못한 시기였다. 우리는 그 때 워싱턴에서 윌슨이라는 사람과 함께 일하고 있었다. 윌슨은 연구라는 것에 대해 굉장히 병적인 공포를 가지고 있었다. 사람들이 그 앞에서 연구에 대해 이야기를 꺼내면 그는 완전히 미치다시피 했다. 그러나 불행히도 RAND는 공군 소속의 회사였고, 윌슨은 그 공군의 간부인 국방 위원장이었다. 그래서 내가 RAND 안에 있었을 때 윌슨을 비롯한 공군들이 내가 수학에 대해 연구하는 것을 보이지 않게 막는다는 것을 알 수 있었다. 처음 올 때는 나는 위의 문제에 대해 ’의사 결정 프로세스’라는 이름을 사용했지만, 여기에서 ’프로세스(Process)’라는 단어를 사용하는데 여러가지 차질이 생겨버리고 만 것이다. 그래서 나는 사람들이 알지 못하게 ’계획법(Programming)’이라는 단어를 붙였다. 또한 나는 이 프로세스가 다단계(multistage)로 이루어져 있으며, 시가변(time-varying)적인 성질을 가진 것으로부터 ’동적(Dynamic)’라는 단어를 사용했다. 이 단어야말로 내가 연구하는 알고리즘의 성질을 정확하게 짚어내었고, 게다가 윌슨에게도 피해를 입히지 않으며 공군도 이 단어에선 꼬투리를 잡지 못했으니 그야말로 일석이조의 효과를 누린 것이다.
프로그래밍으로 푼다는 의미보다는 수학적 모형을 만들어 해를 구해 최적 의사결정을 도모하는 수리 계획법(Mathematical Programming)에 가깝다.
수리 계획법에는 세가지 구성요소가 있는데, 의사 결정 변수(decision variable)와 목적 함수(objective function) 그리고 제약조건(constraints)이다. 그리고 종류에는 목적함수와 제약조건식이 1차식으로 표현되는 선형계획법(LP), 1차식으로 표현되지 않는 모형을 비선형계획법(NLP), 의사결정변수가 정수값만을 가지고 있는 정수계획법(IP), 목적함수가 여러개의 목표를 포함하고 있는 경우 목표계획법(GP), 여러 단계에 걸쳐 변수의 값을 결정하는 모형 동적계획법(DP)가 있다.
본론으로 들어와 선형계획법의 예를 보자.
제품 A, B를 만드는 회사에서 이익을 최대화하기 위해 생산계획을 수립하려고 한다. 공장 세개를 가지고 있다고 했을 때 제품의 이익을 정리한 표는 다음과 같다.
| 공장 | 제품1 | 제품2 | 가용시간 |
|---|---|---|---|
| 1 | 1 | 0 | 4 |
| 2 | 0 | 2 | 12 |
| 3 | 3 | 2 | 18 |
| 이익 | 3000 | 5000 |
제품 1을 \(x_1\), 제품2를 \(x_2\)라 하자. 그러면 최대화할 식을 \(Max: 3x_1 + 5x_2\) 로, 제약조건을 이렇게 할 수 있다.
\(x1 \leq 4 \\ 2x_2 \leq 12 \\ 3x_1 +2x_2 \leq 18 \\x_1, x_2 \ge 0\)
\(x_1, x_2\)의 값은 음수가 아니어야 한다.연립부등식으로 풀면 \(x_2\)의 식을 얻을 수 있다.
\(x_2 \leq 9 - \frac{3}{2}x_1\)
앞의 실행가능조건(feasibility condition)을 이용하여 그래프를 그리면 다음과 같다.
0보다 크면서 선 안의 영역이 실행가능영역이다. \(x_1 = 2 , x_2 = 6\)이 되면서 \((2,6)\)라는 값이 목적함수(최대화할 식)의 최적해가 된다. 이처럼 도해법은 가장 직관적인 방법이다. 그러나 변수가 3개 이상이 되면 표현하기가 어려워지며 4개 이상이면 적용이 불가능하다. 이러한 문제를 일반적으로 해결 할 수 있는 방법이 필요하게 된다.
단체법(Simplex method)
댄치그가 개발한 단체법의 기본 개념은 최적해 후보에 대한 최적여부를 체계적으로 검토하여 가장 빠른 시간내에 최적해를 찾아내고자 하는 것이다. 단체법을 적용하기 전에 가장 해야할 일은 부등식을 등식으로 바꾸는 표준형(standard form)을 적용하는 것이다. 예를 들어 \(2x_1 \leq 50\) 이라면 여유 변수(slack variable) S를 더하여 \(2X_1 + S_1 = 50\)으로 만들면 된다.
가령 미지수가 3개, 조건식이 3개인 변수인 문제가 있다고 가정하고 여유 변수, 즉 미지수가 3개나 더 추가가 될 경우에는 어떻게 해야할까. 일반적으로는 풀 수 없다. 그러나 여유 변수를 \(0\)으로 두면 미지수가 줄어들게 된다. 그리고 최초의 \(0\)이 아닌 값, 미지수를 기저가능(Basic feasible)해라고 한다.
기저가능해가 원점\((0,0)\)부터 시작한다고 하면 여유변수는 다음과 같을 것이다.
\(x_1 + s_1 = 4 \\ 2x_2 + s_2 = 12 \\ 3x_1 + 2x_2 + s_3 = 18 \\ s_1 = 4, s_2 = 12, s_3= 18\)
하지만 이렇게 구한 값들은 목적함수에서 \(0\)이다. 목적함수를 최대화하기 위해 인접한 해, 꼭지점 값을 이동하면서 최적해를 찾으면 된다. 어느 방향\((x,y)\)으로 이동할 것인가가 문제가 되는데, \(3x_1 + 5x_2\) 계수가 가장 큰 \(x_2\)를 기저 변수로 선택하고 이동하면 될 것이다.
정리하면,
1. 표준형으로 변형하면 원점이 최초의 해가 된다.
2. 여유변수가 기저변수, 다른 변수는 비기저변수.
3. 최적화 검사 : 목적함수가 증가(감소) 여부, 인접한 더 좋은 해가 없다면 그 해가 최적해
4. 진입기저변수 선택.문제를 바꿔서 설명해보겠다.
\(Max \; z=2x_1 + x_2 \\ x_1 + 5x_2 \leq 8 \\ 2x_1 + 3x_2 \leq 6 \\ 3x_1 + x_2 \leq 6\)
제약조건을 여유변수를 이용하여 등식으로 바꾼다.
\(2x_1 - x_2 - z = 0 \\ x_1 - 5x_2 + s_1 = 8 \\ 2x_1 - 3x_2 + s_2 = 6 \\ 3x_1 + x_2 + s_3 = 6\)
원점 \((0,0)\)에서 시작하면 초기가능해(혹은 CPS)를 얻을 수 있다. 물론 이 문제에서 원점은 최적값에는 못미치는 값이다. 단체법은 각 단계마다 목적 등식의 계수를 확인한 다음 최대값을 다음 단계의 기준으로 선택한다. 이 과정에서 기저변수를 \(z, s_1, s_2, s_3\)로 하여 시작한다. 그런 다음 새로운 기저 변수는 목적 등식에서 가장 큰 계수를 갖는 \(x_1\)이다. 변수 \(x_1\)이 어떻게 바뀌는지 알아보기 위해 비율 계수를 \(a\), 값을 \(b\)인 $ $로 값이 큰 방정식을 선택한다. 앞의 식에서 비율은 각각 \(\frac{1}{8}\), \(\frac{2}{6}\), \(\frac{3}{6}\) 이 나오는데 마지막 비율의 값이 가장 크다. 그리고 마지막 비율은 마지막 등식에서 나오므로 \(x_1\)으로 치환될 기저 변수는 \(s_3\)가 된다. 실제로 이 과정은 가우스 소거법을 사용한다. 마지막 등식을 이용하여 다른 등식에 적절한 수를 곱하여 마지막 등식을 제외한 모든 등식에서 \(x_1\)을 제거한다. \(x_1\)을 제거하는 과정을 끝내면 다음과 같다. \(-z - \frac{2}{3}s_3+ \frac{1}{3}x_2= -4 \\s_1- \frac{1}{3}s_3+ \frac{14}{3}x_2=6 \\ s_2-\frac{2}{3}s_3+\frac{7}{3}x_2=2 \\x_1+\frac{1}{3}s_3+\frac{1}{3}x_2=2\)
나머지 비기저변수를 0으로 하면 새로운 기저 변수를 얻을 수 있다. 따라서 비기저변수인 s_3, x_2를 0으로 하면 다음과 같은 값을 얻을 수 있다.
\(z=4, s_1=6, s_2=2, x_1 =2\)
앞의 그래프를 보면 \((2,0)\), 즉 극점에 도달한 것을 알 수 있다. 이전 값인 \((0,0)\) 보다는 큰 값이다. 그리고 같은 방법을 반복하는데 이번에는 \(x_2\)에 가장 큰 계수가 있는지 확인한다. 가장 큰 계수/상수는 두번째 등식의 \(\frac{14}{18}\)이다. 따라서 새 기저변수는 두번째 등식에 있는 기저변수 \(s_1\)을 치환하는 \(x_2\)다. 앞의 과정을 두 번 반복하면 \(x_1=\frac{12}{7}\)과 \(x_2=\frac{6}{7}\)가 나오면서 \(z\)의 최대값인 \(\frac{30}{7}\)이 나올것이다. 이는 \(4.29\)에 가까운 값이다.
이번 글에선 목적함수를 최대화하는 방법을 알아보았지만, 목적함수를 최소화하는 문제도 있고 부등식이 무한대인 선형 프로그램도 있다. 단체법이 흥미롭다면 카치안(L. G. Kachian)의 타원체 알고리즘(ellipsoid algorithm)을 공부해보면 좋을것이다.