2차대전 때 본격적으로 시작된 최적화 연구
2차 대전이 한창이던 20세기 중반, 이때부터 최적화라는 학문 분야가 시작되었다. 미국이 2차 대전에 승리한 이유 중의 하나로 미군의 무한정한 군수물자 투입을 꼽는 사람들이 있다. 하지만, 물자는 결코 무한정일 수 없다. 그러니, 미국의 군수물자 운용이 무한정인 것 처럼 보인 것에는 최적화의 공로가 있었음을 인정하지 않을 수 없다. 유한한 자원을 무한한 상상력과 창의로 무한정인 것 같아 보이게 사용한 것일 뿐이다.
수학적으로는 다항선형등식(System of linear equalities)의 해를 구하는 방법에서 다항부등식(System of linear inequalities)의 해를 구하는 체계적 방법이 등장한 것이었지만, 그것도 수학적으로 새로운 발견은 아니었다. 단지 이미 알려진 수학적 방법들을 적절하게 배열한 것에 지나지 않는다. 그러나, 그것이 가져온 효과는 엄청난 것이었다. 이제 이 방법은 다항 부등식의 수많은 해들 중에 어떤 소기의 목적을 측정하는 선형함수를 극대화하는 해를 구하는 방법으로 발전하여 선형계획법(Linear Programming)이라는 분야를 탄생시킨 것이다.
이런 선형계획법은 몇 가지 주목할 방향으로 발전되는데, 먼저 우리가 사는 세상이 선형적이지 않다는 생각에서, 앞서 말한 선형계획법은 비선형계획법(Nonlinear Programming)으로 발전한다. 또한 우리가 삶에서 다루는 많은 재화, 예를 들어, 자동차나 비행기, 기계들과 같이 그 단위가 조각으로 나누면 의미가 없는 비연속적인 정수들이 많다는 생각에서 정수계획법(Integer Programming)으로 발전한다. 또한 우리의 의사결정이 한번에 이루어 지는 것이 아닌, 동적으로 연결되어 연속적으로 행해지는 의사결정에 의해 이루어 진다는 생각에서 동적계획법(Dynamic Programming)이 생겨나게 된다. 또한, 여러 주체의 상호 작용에 의해 결과가 나오는 경우를 다루기 위해 게임이론(Game theory)이 태동된다. 이러한 일련의 변화는 골방에서 도를 닦는 듯 하는 순수 수학자들의 전유물이던 수학을 응용수학이라는 분야로 끌어내게 된다.
물론 이러한 발전에 디지털 컴퓨팅의 발전이 함께 했다는 것에 주목하지 않을 수 없다. 인간의 암산이나, 종이와 연필을 써서 손으로 계산할 수 있는 문제의 크기는 인간의 계산 실수와 절대적인 힘의 부족으로, 아무리 쉬운 문제도 어느 정도 이상의 크기가 되면 다룰 수 없어진다. 그러나, 계산 기계, 즉 컴퓨터의 개발과 보급은 전에는 인간이 계산할 수 있다고 상상할 수 조차 없었던 크기의 문제를 놀라운 시간 안에 계산해 낼 수 있도록 하였다. 이론적인 측면에서 보면, 수학의 관심이 “어떻게 계산할 수 있는가”에서 “어떻게 빨리 계산할 수 있는가”로 바뀌었으며, 이를 주요 관심사로 하는 계산복잡도이론(Computational Complexity Theory)이 등장하게 되었다. 이제 수학은 순수 과학의 영역에서 공학의 일부로 발전되어가고 있었던 것이다.
계산 복잡도라는 것에 대한 이해를 위해, 간단한 예로, N개의 대안을 배열하는 문제를 생각해보자. 실제적인 현실 문제로는 각각 N명의 남녀가 각각의 파트너를 정하는 문제가 이런 경우의 예라 할 수 있겠다. 이런 문제의 해는 남자든 여자든 한쪽은 주어진 고정 순서로 해 놓고, 다른 한쪽을 모든 가능한 배열로 나열하여 검토하는 문제라 할 수 있다. 이때, N개의 대안이 한 줄로 세워질 수 있는 경우의 수는 모두 N!(N Factorial)이 된다. 이제, 사전에 주어진 자료로 N명이 모두 N명에 대해 선호도를 나타냈으며, 그 선호도가 모든 가능한 개개 짝에 대해 합해져서 그 짝이 선택될 때 충족되는 선호도의 만족 정도를 나타내게 되었다고 생각해 보자. 이때, 전체의 선호도 만족을 극대화하는 최적의 파트너 결정을 하는 문제를 생각할 수 있다.
만일 N이 크지 않다면, 별 문제가 없다 단순히 모든 가능한 배열을 만들어 그 점수를 계산해 보면 될 것이나, N이 40명 정도만 되어도 40!은 우리의 상상을 초월하는 크기의 문제가 된다. 40!은 10의 40승 보다도 훨씬 큰 수인데, 이 수를 단순히 헤아리는 것만을 생각해보자. 10의 10승은 100억이며, 일년은 100억초가 되지 못한다. 따라서 40!을 단순히 헤아리기만 한다고 해도, 10 Giga(100억) 헤르쯔 (현재 최첨단 펜티엄 칩이 5기가 헤르쯔도 되지 않는 것을 기억하라.) CPU 100억대(세계인구에 한 사람 당 한대보다 많은 수)가 동시에 병렬로 100억년을 세어야 하는 수이다. 만일 N이 70명만 되어도, 70!은 우주에 존재한다고 추정하는 현재까지 발견된 가장 작은 소립자의 개수보다도 많은 수가 된다.
그러나, 놀라운 것은 이 문제에서 N이 수천 혹은 수만이 되어도, 적절한 최적화 기법을 이용한다면, 현재의 펜티엄 컴퓨터 한대로 수 초 혹은 수 분 안에 최적해를 구할 수 있다는 것이다. 이것이 최적화 이론의 매력이다. 단순한 대안의 탐색과는 비교할 수 없는 엄청난 효율을 가진 방법론의 개발, 이것에 사로잡힌 분야가 최적화이다.
‘우리는 진정 최적화를 바라고 있나’
1976 노벨 경제학상은 미국의 Koopman, 소련의 Kantorovich에게 주어졌다. “한계자원의 최적 활용”에 대한 그들의 연구 공적이 인정되어서였으며 그 핵심연구 결과가 바로 선형계획이론이다. “Beautful Mind”라는 영화에서 그려진 Nash가 또한 Game 이론으로 1994년에 노벨 경제학상을 받았다. 그 외에도 최적화 이론과 관련된 노벨 경제학상은 여러 개 있으며, 최근 들어 더욱 많아지고 있다.
하지만, 이런 찬란한 최적화 이론의 역사를 계속 얘기하기보다, 조금 재미있는 이야기로 이글을 마무리하기로 하자. 그것은 “우리는 최적화를 진정 원하고 할 수 있으면 최적해를 찾으려 하는가?”라는 질문에 대한 검토이다. 지금까지 이 글에 나타난 논조로는 “모든 사람은 살아있는 한 무의식 중에도 하는 것이 최적화이니, 우리는 모든 의사결정 문제에서 최적해를 찾으려 노력한다”라고 주장하여야 하겠지만, 정말 그럴까?
최적화 이론이 한창 개발되던 1960년대에, 한 재미있는 연구결과가 발표되었다. 그 연구는 “최소 비용의 식생활”이라는 문제를 선형계획으로 풀었다. 당시에 얻을 수 있는 모든 대표적인 식품 60여종을 조사하여, 일년에 필요한 영양가를 충족하기 위해 가장 적게 지불할 수 있는 식품 구입안을 만드는 문제였다. 그 최적해가 도출 되었을 때, 가장 먼저 사람들을 놀라게 한 것은 그 액수가 터무니 없이 작았다는 것이다. 계산에 착오가 있는가 알아 보았지만, 그렇지 않았다. 당시 임금으로 불과 한 두주의 평균 단순 노동임금으로 한 사람에게 일년 동안 필요한 영양을 충족하는 식품의 구입이 가능했다는 것이다. 결론은, 먹는 문제에 대해서는 누구도 엄격한 최적화를 수행하고 있지 않다는 것이다. 아마 요즘의 젊은이들은 이렇게 주문할지 모른다. “맛과 향은 최대화하고, 칼로리는 최소화해 주세요. 그리고, 환상적인 음악과 분위기만 있다면, 꼭 뭘 먹지 않아도 됩니다.”
최적화 이론은 주어진 조건 안에서 최적해를 구하는 것을 다룬다. 어려운 최적화 문제를 좀더 효율적인 계산 방법을 만들어, 누구보다도 빠르게 계산해 내는 재미, 그것이 최적화 분야가 추구하는 최고의 가치이다. 그러나, 최적화 이론은 그 가치가 왜 중요한가에 대한 해답을 주지는 않는다. 삶의 목표를 정하고, 자신의 젊음을 무엇과 바꿀 것인가에 대한 해답은 혼자만의 고뇌와 잠 못 이루는 밤들로부터 얻어지는 것이다. 세상의 어떤 수학적인 이론도 그것에 해답을 줄 수 없다. 물론 가장 최단시간에 그 가치가 무엇인가에 대한 해답을 얻는 것이 목표라면, 최단시간에 고뇌를 끝내기 위한 수리 모형은 가능할 것도 같지만 말이다.
저작권자 © 포항공대신문 무단전재 및 재배포 금지
