조지 단치히, 최적화의 탄생과 현대 응용

[한국정보기술신문] 우리는 매일 아침 출근길에 최단 경로를 찾거나, 학교 급식 재료를 계산하며 예산을 고민한다. 이런 일상 속 고민은 사실 ‘최적화 문제’의 한 예다. 최적화 문제란 주어진 자원과 제약 조건 하에서 최대 이익을 내거나 최소 비용을 만드는 해를 찾는 것이다.

선형계획법(linear programming)은 이러한 최적화 문제 중에서도 ‘목표함수와 제약 조건이 모두 선형식으로 표현되는’ 문제를 다룬다. 선형계획법을 통해 우리는 회사의 생산 계획, 물류 운송, 금융 투자 등 다양한 분야에서 효율적인 의사결정을 내릴 수 있다.

이 선형계획법을 창시한 인물이 바로 조지 단치히(George Dantzig, 1914~2005)다. 단치히는 1940년대 말 당시 미국 국방부의 요청을 받아 전투 지원 물자 배분 문제를 해결하기 위해 선형계획법의 핵심 알고리즘인 ‘심플렉스(simplex) 방법’을 고안했다.

단치히의 연구는 곧 전후 산업 전반에 확산됐다. 오늘날 우리는 물류 차량의 최적 노선 설계, 제조 공정의 자원 배분, 항공사 승무원 스케줄링, 네트워크 대역폭 할당 등 무수히 많은 문제에서 선형계획법을 활용하고 있다.

단치히, 최적화의 아버지를 만나다

조지 단치히(George Dantzig)는 1914년 미국 오하이오 주에 태어났다. 어린 시절부터 수학에 재능을 보였으며, 인디애나 대학에서 통계학 박사 학위를 받은 뒤 제2차 세계대전 중 미 공군을 위해 일했다.

전쟁 말기 단치히는 군부대가 전투 지원 자원을 어떻게 할당할지 고민하는 과제를 맡았다. 당시 컴퓨터 성능이 충분치 않아 가능한 모든 경우를 계산하기는 불가능했다. 가능한 조합의 수는 우주에 존재하는 입자 수보다 많았기 때문이다.

이에 단치히는 목표함수와 제약 조건을 모두 선형식으로 가정해 문제를 수학적으로 모델링했다. 목표함수를 최대화하거나 최소화하기 위해 반복 계산을 수행하는 새로운 알고리즘을 고안했고, 이를 ‘심플렉스 방법’이라고 불렀다.

1947년 단치히가 발표한 이 방법은 ‘조건을 만족하는 해를 하나 골라 시작하고, 인접한 기본 해(basic feasible solution)를 따라가며 최적해에 도달한다’는 원리다. 이 과정을 통해 계산해야 할 해의 수를 극적으로 줄여, 실제 문제를 빠르게 해결할 수 있었다.

단치히는 이후 민간 연구기관과 학계로 옮겨가 선형계획법 이론을 확장했으며, 1963년에는 《Linear Programming and Extensions》라는 대표 저서를 발표했다. 이 책을 통해 심플렉스 방법과 관련 이론이 전 세계 연구자들에게 널리 보급되었다.

선형계획법의 원리와 구조

선형계획법이란, 수학적으로 ‘최대화 또는 최소화하려는 선형 목표함수(f = c₁x₁ + c₂x₂ + … + cₙxₙ)를 특정 제약 조건(a₁₁x₁ + a₁₂x₂ + … + a₁ₙxₙ ≤ b₁ 등 선형 부등식) 아래에서 최적값을 찾는 방법’이다.

이때 변수 x₁, x₂, …, xₙ은 0 이상의 값을 갖는 비음수 변수이다. 모든 제약 조건을 만족하는 해 집합은 ‘가능 영역(feasible region)’이라 불리는 다각형(2차원) 혹은 다면체(고차원)로 표현되며, 최적해는 항상 이 영역의 꼭짓점(vertex)에서 발생한다.

심플렉스 알고리즘은 우선 가능한 영역의 한 꼭짓점에서 시작해, 인접한 꼭짓점으로 이동하면서 목표함수 값을 매 단계 향상시킨다. 최적해에 도달하면 더 이상 값이 개선되지 않아 알고리즘이 종료된다.

수학적으로 볼 때 이는 기하학적으로 ‘다면체의 꼭짓점을 따라 최적점을 찾아가는’ 방법이다. 모든 꼭짓점을 일일이 탐색할 필요 없이, 현재 꼭짓점에서 목표함수를 가장 빠르게 늘릴 수 있는 방향으로 이동함으로써 계산량을 줄였다는 것이 핵심이다.

다만 최악의 경우 심플렉스 알고리즘이 모든 꼭짓점을 방문해야 할 수도 있지만, 실제 응용에서는 평균적으로 매우 효율적인 성능을 보인다. 이를 계기로 선형계획법은 실용적인 최적화 기법으로 자리매김했다.

이후 이론이 발전하면서 대규모 문제를 해결하기 위한 내부점 방법(interior point method)도 고안되었다. 내부점 방법은 경계(꼭짓점)를 따르지 않고 다면체 내부를 통과하면서 최적해로 수렴하기 때문에, 특정 유형 문제에서 보다 빠른 성능을 낸다.

선형계획법의 응용: 산업에서 일상까지

선형계획법이 출현한 이후 수십 년 동안 수많은 산업 분야에서 최적화 모델이 개발되었다. 대표적으로 항공 산업에서는 항공기 승무원 스케줄링, 항공편 운항 스케줄 최적화 등에 선형계획법을 활용한다.

물류·운송 분야도 마찬가지다. 택배 회사는 하루 배송 물량을 최대한 효율적으로 배분해 배송 비용을 최소화하기 위해 선형계획법 모델을 사용한다. 실제로 미국의 대형 유통사 UPS는 선형계획법에 기반한 최적 노선 설계 시스템으로 연간 수백만 달러의 비용을 절감했다.

제조업에서도 생산 계획과 공정 제어에 선형계획법이 도입되어 왔다. 공장 라인의 생산량을 제한하면서 원자재 비용을 최소화하거나, 완제품 재고를 고려해 공급망 전체를 최적화하는 문제도 모두 선형계획법으로 풀 수 있다.

금융 분야 역시 선형계획법 응용 사례가 많다. 포트폴리오 최적화, 자금 배분, 헤지 전략 수립 등 다양한 투자 의사결정 문제를 수학적으로 모델링해 최적화 알고리즘을 적용한다. 이를 통해 투자 위험은 줄이고 기대 수익은 극대화할 수 있다.

통신 네트워크 설계, 전력망 운영, 에너지 최적화 등에서도 선형계획법은 핵심 기법으로 쓰인다. 예를 들어, 전력 회사는 발전량과 전송 용량을 고려해 생산 비용과 송전 손실을 최소화하는 모델링을 선형계획법으로 수행한다.

최근에는 인공지능(AI)과 빅데이터 기술이 결합되며 ‘데이터 기반 최적화’가 주목받고 있다. 대규모 실시간 데이터를 수집해 선형계획법 모델에 입력함으로써, 수요 예측과 자원 배분을 더욱 정밀하게 수행할 수 있다.

한국에서의 선형계획법 연구와 교육

국내 학계에서는 1970년대부터 선형계획법 관련 연구가 활발히 수행되었다. 서울대, 고려대, 연세대 등 주요 대학의 공업수학·산업공학·경영공학과에서 전담 교과목이 개설되었고, 관련 논문도 다수 발표됐다.

특히 한국과학기술원(KAIST)과 포스텍은 1980~1990년대에 최적화 기법 연구의 선두에 서서, 복합 시스템을 다루는 혼합정수계획법(mixed-integer programming) 연구를 이끌었다. 이를 통해 선형계획법 기반의 산업 솔루션을 국내 기업에 제공하는 성과를 올렸다.

현재 한국정보올림피아드, 전국수학경시대회 등 대회에서도 선형계획법은 알고리즘 문제의 핵심 주제로 다뤄진다. 고교생들은 이를 통해 기초 개념을 습득하고, 대학에서는 더 심화된 수업을 통해 최적화 연구자로 성장한다.

정부 차원에서도 산업 최적화 기술의 중요성을 인식해, 중소기업 대상 최적화 컨설팅, 연구 지원 사업 등이 진행 중이다. 중소 제조업체에게 생산 라인 효율화, 재고 관리 최적화 같은 실질적인 솔루션을 제공하기 위해 선형계획법 전문가가 파견되기도 한다.

교육 현장에서는 최신 소프트웨어 도구(예: CPLEX, Gurobi, Xpress)와 오픈소스 솔버(예: GLPK, CBC)를 활용해 학생들이 직접 모델을 구현하고 실험할 수 있도록 장려하고 있다. 이를 통해 이론과 실습을 결합한 현장 교육이 이루어진다.

또한 대학원 연구실에서는 선형계획법을 기반으로 한 머신러닝 최적화, 네트워크 플로우, 확률적 최적화 등 고급 연구가 활발하다. 국내 연구진은 국제 학회(ICML, NeurIPS 등)에 논문을 발표하며 글로벌 경쟁력을 입증하고 있다.

선형계획법의 한계와 극복 과제

선형계획법은 목표함수와 제약이 모두 선형일 때만 적용 가능하다. 현실 문제는 종종 비선형 요소를 포함하며, 이 경우 비선형계획법(nonlinear programming)으로 확장해야 한다. 이 과정에서 계산 복잡도가 급격히 상승한다.

심플렉스 알고리즘은 평균적으로는 효율적이지만, 최악의 경우 지수 시간(exponential time)이 걸릴 수 있다. 이를 극복하기 위해 내부점 방법 같은 다변량 기법이 고안되었고, 특정 문제에서는 더 나은 성능을 보인다.

대규모 데이터와 복합 제약 조건을 가지는 문제에서는 메모리·연산량 문제가 발생한다. 이를 해결하기 위해 분산 컴퓨팅(Distributed Computing), 그래픽처리장치(GPU) 가속, 클라우드 기반 최적화 플랫폼이 활용된다.

또한, 실시간 최적화가 필요한 환경에서는 근사(heuristic) 기법이나 메타휴리스틱(Metaheuristics)이 함께 쓰인다. 유전 알고리즘, 시뮬레이티드 어닐링, 군집 최적화 등이 대표적인 예다.

학계는 앞으로 선형계획법과 비선형 최적화 기법, 확률적 모델을 결합해 더 복잡한 문제를 풀기 위한 연구를 지속하고 있다. 예컨대, 불확실성 환경에서 의사결정을 지원하는 ‘강인 최적화(robust optimization)’가 주목받고 있다.

최적화의 미래와 우리의 역할

단치히가 1947년 심플렉스 방법을 고안한 이후 70여 년이 지났다. 선형계획법은 여전히 현실 문제 해결의 핵심 도구로 자리매김하고 있으며, AI·빅데이터 시대에도 그 중요성은 줄어들지 않는다.

특히 4차 산업혁명 시대에는 자율주행차, 스마트 그리드, 스마트 팩토리 등 실시간 최적화가 필수적인 분야가 확대되고 있다. 이런 환경에서 선형계획법 기반 최적화 모델은 실제 서비스의 심장 역할을 하게 될 것이다.

최적화는 더 이상 수학자나 연구자의 전유물이 아니다. 기업 실무자, 공공 정책 담당자, 학생 등 누구나 직면한 문제를 수치 모델로 바꾸고, 최적해를 찾는 과정을 통해 효율적인 의사결정을 할 수 있다.

앞으로 우리 사회는 최적화 기법을 더욱 폭넓게 활용하게 될 것이다. 이를 위해 학생들은 기본 수학 개념을 탄탄히 다지고, 대학에서는 현실 문제를 수학 모델로 푸는 연습을 게을리하지 말아야 한다.

정부와 기업도 최적화 기술을 내부 업무 프로세스에 적극 도입하고, 전문가 양성을 위한 교육 프로그램을 확대해야 한다. 이를 통해 비용 절감, 생산성 향상, 자원 효율적 사용이라는 선순환을 만들 수 있다.

마지막으로, 최적화 기법은 기술 그 자체만으로 의미를 갖지 않는다. 실제 문제 맥락을 깊게 이해하고, 모델을 적절히 가정하며, 결과를 해석해 의사결정에 반영하는 ‘인간의 지혜’가 함께할 때 비로소 가치를 발휘한다.

단치히가 제시한 선형계획법 정신은 ‘복잡한 문제를 단순하게 모델링하고, 수학적 기법으로 최적해를 찾아내라’는 메시지다. 2025년에도 우리는 이 메시지를 되새기며 보다 나은 미래를 설계해야 할 것이다.

한국정보기술신문 인공지능분과 김주호 기자 news@kitpa.org