조지 댄치그(George Dantzig)

조지 댄치그(단치히로도 적습니다)는 1914년 미국 오리건주 포틀랜드에서 태어났습니다. 아버지 토비어스 댄치그는 러시아 제국에서 태어나 파리에서 푸앵카레에게 배운 수학자였고, 아인슈타인이 칭찬한 대중 수학책 『수: 과학의 언어』(1930)를 썼습니다. 조지가 어른이 된 1940년대의 가장 큰 계산 문제는 전쟁이었습니다. 미 육군 항공대는 수만 대의 비행기와 수십만 명의 승무원, 부품, 연료, 훈련을 언제 어디에 얼마나 배치할지를 정해야 했는데, 이 '계획'은 모두 손으로, 경험과 규칙에 따라 짜였습니다. 가장 좋은 계획을 찾는 것은커녕, 서로 맞아떨어지는 계획 하나를 만드는 데에도 몇 달이 걸렸습니다. 군대에서 이런 일정표를 '프로그램'이라 불렀고, 댄치그가 세운 분야의 이름 '선형 프로그래밍', 곧 선형 계획법의 '프로그래밍'은 컴퓨터 프로그램이 아니라 이 계획을 뜻합니다.

나이 세 ·

그는 1936년 메릴랜드 대학을 졸업하고 미시간에서 석사를 마친 뒤, 1939년 버클리에서 폴란드 출신 통계학자 예지 네이만의 대학원생이 되었습니다. 이때의 일화는 사실이지만 전설처럼 퍼졌습니다. 어느 날 수업에 늦게 온 그는 칠판에 적힌 두 문제를 숙제로 알고 베껴 가서 며칠 동안 끙끙댄 끝에 풀어 냈고, 늦어서 죄송하다며 네이만에게 냈습니다. 그 두 문제는 숙제가 아니라 네이만이 예로 적은 통계학⁠(statistics)⁠의 유명한 미해결 문제였습니다. 몇 주 뒤 흥분한 네이만이 그의 집 문을 두드렸고, 두 풀이는 뒤에 그의 박사 논문이 되었습니다. 이 이야기는 훗날 '긍정적인 생각의 힘'을 말하는 설교와 자기계발서에까지 변형되어 쓰였고, 댄치그는 인터뷰에서 몇 번이고 진짜 사정을 바로잡아야 했습니다.

1941년 전쟁이 나자 그는 박사 과정을 멈추고 워싱턴의 육군 항공대 통계 관리국에서 전투 분석과 계획을 맡았습니다. 탁상 계산기로 거대한 일정표를 맞추는 일이었습니다. 1946년 박사 학위를 받은 뒤 그는 공군 감사관실의 수학 자문으로 돌아가, 이 계획을 기계적으로 계산할 방법을 찾는 과제를 받았습니다. 경제학자 바실리 레온티예프가 경제의 부문들 사이의 투입과 산출을 일차 방정식의 표로 적은 것에서 힌트를 얻은 그는, 계획의 목표와 제약을 모두 일차식으로 적었습니다. 목표는 무엇을 최대로(또는 최소로) 하는 것이고, 제약은 '비행기 수는 이만큼을 넘을 수 없다', '연료는 이만큼 이하'처럼 등호가 아닌 부등호입니다. 위의 식이 그 일반형입니다. 새로운 것은 부등식이었습니다. 등식으로 된 연립일차방정식⁠(system of linear equations)⁠은 가우스 소거법⁠(Gaussian elimination)⁠으로 풀면 되지만, 부등식으로 둘러싸인 수많은 가능한 계획 가운데 가장 좋은 하나를 기계적으로 고르는 일반적인 방법은 서방에 알려져 있지 않았습니다(소련의 칸토로비치가 1939년에 낸 방법은 그때 서방에서 아무도 몰랐습니다).

작은 예로 보면 모양이 드러납니다. 공장에서 제품 X는 기계 1을 1시간, 기계 2를 1시간 쓰고 이익이 3이며, 제품 Y는 기계 1을 1시간, 기계 2를 3시간 쓰고 이익이 4입니다. 기계 1은 4시간, 기계 2는 6시간 쓸 수 있습니다. X를 $x$개, Y를 $y$개 만든다면 $x + y \le 4$, $x + 3y \le 6$을 지키며 $3x + 4y$를 최대로 해야 합니다. 부등식들을 만족하는 점들은 평면에서 네 꼭짓점 (0, 0), (4, 0), (3, 1), (0, 2)를 가진 볼록한 다각형을 이룹니다. 이익이 같은 점들은 평행한 직선들이고, 이 직선을 이익이 커지는 쪽으로 밀어 가면 다각형에 마지막으로 닿는 곳은 반드시 꼭짓점(또는 모서리)입니다. 네 꼭짓점의 이익은 0, 12, 13, 8이니 답은 X 3개, Y 1개로 이익 13입니다. 변수가 수백 개면 이 도형은 수백 차원의 다면체가 되고 꼭짓점은 천문학적으로 많아지지만, 답이 꼭짓점에 있다는 사실은 그대로입니다.

1947년 여름 그가 만든 단체법(심플렉스법)은 이 다면체의 꼭짓점을 모두 조사하지 않습니다. 한 꼭짓점에서 출발해, 모서리를 따라 이익이 커지는 이웃 꼭짓점으로 한 걸음씩 옮겨 가다가, 더 좋은 이웃이 없으면 멈춥니다. 위의 예에서 이익이 한 개당 더 큰 Y부터 늘리는 댄치그의 규칙을 따르면 (0, 0)에서 (0, 2)로, 다시 (3, 1)로 가서 멈춥니다(다른 규칙이면 (4, 0)을 거칠 수도 있습니다). 도형이 볼록하고 목표가 일차식이기 때문에, 어느 이웃보다도 못하지 않은 꼭짓점이면 전체에서 가장 좋은 꼭짓점이고, 멈춘 곳이 곧 답입니다. 한 걸음은 연립방정식의 한 변수를 다른 변수로 바꾸는 소거 한 번이어서, 탁상 계산기로도, 곧 등장할 컴퓨터로도 기계적으로 할 수 있었습니다. 같은 해 국립 표준국은 경제학자 조지 스티글러가 제기한 식단 문제, 곧 필요한 영양소를 모두 채우는 가장 싼 식단을 이 방법으로 풀었습니다. 방정식 9개, 미지수 77개의 문제를 사람들이 탁상 계산기로 푸는 데 모두 120인일쯤이 걸렸고, 답은 1939년 물가로 한 해 39.69달러였습니다. 스티글러가 어림으로 찾은 식단은 39.93달러였습니다.

1947년 10월 그는 프린스턴 고등연구소로 폰 노이만을 찾아갔습니다. 그의 회고에 따르면 설명을 시작하자 폰 노이만이 요점만 말하라고 재촉했고, 그가 1분 만에 문제를 적어 보이자 폰 노이만은 '아, 그거' 하더니 한 시간 넘게 선형 계획법의 쌍대 이론을 강의했습니다. 폰 노이만은 막 모르겐슈테른과 게임 이론⁠(game theory)⁠ 책을 펴낸 참이었고, 두 사람 영합 게임⁠(zero-sum game)⁠의 최소최대 정리⁠(minimax theorem)⁠에서 같은 구조를 짐작한 것입니다. 쌍대 이론을 위의 예로 보면 이렇습니다. 누군가 공장의 기계 시간을 빌리려고 시간당 값 $p_1$, $p_2$를 부른다고 합시다. 공장이 받아들이려면 제품 하나를 만드는 데 드는 시간을 빌려주는 값이 그 제품의 이익 이상이어야 합니다($p_1 + p_2 \ge 3$, $p_1 + 3p_2 \ge 4$). 빌리는 쪽이 치를 수 있는 가장 적은 총액 $4p_1 + 6p_2$는 $p_1 = 2.5$, $p_2 = 0.5$일 때의 13으로, 공장의 최대 이익과 정확히 같습니다. 이 값들이 기계 한 시간이 더 생길 때 늘어나는 이익, 곧 그림자 가격입니다(쌍대성⁠, duality⁠).

1948년 경제학자 티알링 쿠프만스는 '선형 구조 속의 계획'이라는 긴 이름 대신 '선형 계획법'이라 부르자고 제안했고, 1949년 시카고의 콜스 위원회가 연 학회에서 수학자와 경제학자들이 이 새 도구를 두고 처음 한자리에 모였습니다. 댄치그가 프린스턴의 앨버트 터커를 찾아가 문제를 소개한 것을 계기로 터커와 그의 제자 데이비드 게일, 해럴드 쿤은 쌍대 정리⁠(duality theorem)⁠를 엄밀하게 증명했고, 쿤과 터커는 이것을 일차식이 아닌 문제로 넓혔습니다. 1952년 댄치그는 공군의 싱크탱크인 랜드 연구소로 옮겼습니다. 그곳에서 레스터 포드와 레이 풀커슨은 철도망의 최대 흐름⁠(maximum flow)⁠과 최소 절단⁠(cut)⁠을 연구했고, 댄치그는 풀커슨, 셀머 존슨과 함께 1954년 미국 49개 도시를 한 번씩 도는 가장 짧은 길, 곧 외판원 문제⁠(traveling salesman problem)⁠를 풀었습니다. 선형 계획의 답이 정수⁠(integer)⁠가 아닐 때 그 답을 잘라 내는 부등식을 하나씩 더해 가는 이 방법은 오늘날 정수 계획법⁠(integer programming)⁠의 기본 기술입니다. 그 뒤 불확실한 수요를 다루는 확률적 계획법(1955), 거대한 문제를 작은 문제들로 쪼개는 댄치그–울프 분해(1960)도 그의 손에서 나왔습니다.

단체법은 이상할 만큼 빨랐습니다. 실제 문제에서는 제약의 수의 몇 배쯤의 걸음이면 대개 끝났습니다. 그런데 1972년 빅터 클리와 조지 민티는 특별히 비틀어 놓은 입방체 모양의 문제에서 단체법이 꼭짓점 $2^n$개를 모두 거쳐 가게 만들 수 있음을 보였습니다. 최악의 경우 걸음 수가 변수의 수에 따라 지수적으로 늘어난다는 뜻입니다(점근 표기법⁠, asymptotic notation⁠). 선형 계획 문제를 다항식 시간⁠(polynomial time)⁠에 푸는 방법이 있는지는 1979년 소련의 레오니트 하치얀이 타원체법⁠(ellipsoid method)⁠으로 처음 답했지만, 이 방법은 실제로는 느렸습니다. 1984년 나렌드라 카르마르카르의 내부점법⁠(interior-point method)⁠은 이론과 실제에서 모두 빨라, 다면체의 겉면을 따라 걷는 대신 속을 가로지르는 새로운 길을 열었습니다. 단체법이 왜 실제로는 빠른지는 2001년 대니얼 스필먼과 텅샹화가 입력을 조금 흔들면 평균적으로 다항식 시간에 끝난다는 '평활 분석⁠(smoothed analysis)⁠'으로 설명했습니다(P 대 NP 문제⁠(P versus NP problem)⁠).

그는 1960년 버클리, 1966년 스탠퍼드의 교수가 되어 운용 과학(오퍼레이션스 리서치)을 가르쳤고, 1963년의 『선형 계획법과 그 확장』은 이 분야의 경전이 되었습니다. 1975년 국가 과학 훈장을 받았지만, 같은 해 노벨 경제학상은 선형 계획법을 따로 세운 소련의 레오니트 칸토로비치와 쿠프만스가 받았고 그의 이름은 빠졌습니다. 그는 2005년 스탠퍼드에서 세상을 떠났습니다. 2000년 한 과학 잡지가 뽑은 '20세기의 10대 알고리즘⁠(algorithm)⁠'에는 단체법이 튜키의 고속 푸리에 변환⁠(fast Fourier transform)⁠과 함께 올라 있습니다.

선형 계획법은 이제 보이지 않는 곳에서 매일 돌아갑니다. 1950년대 정유 회사들이 휘발유 배합에 처음 썼고, 항공사의 승무원과 항공기 배치, 전력망의 발전량 결정, 공급망과 물류, 광고 예산 배분이 모두 거대한 선형 계획 문제입니다. 통계와 기계 학습⁠(machine learning)⁠에서도 쓰입니다. 오차의 제곱 대신 절댓값⁠(absolute value)⁠의 합을 가장 작게 하는 회귀는 선형 계획 문제로 풀리고, 상수 하나로 맞출 때 그 답은 중앙값⁠(median)⁠입니다(선형 회귀). 한정된 자원 속에서 가장 좋은 것을 고르는 수학이라는 최적화의 현대적인 모습은 그의 1947년 여름에서 시작되었습니다(가장 좋은 것 고르기).

이어지는 곳. 그가 세운 문제는 선형 계획법이고, 그 짝이 되는 가격의 이야기는 쌍대성에 있습니다. 같은 생각을 8년 먼저 소련에서 떠올린 사람은 칸토로비치이고, 흙을 옮기는 특수한 경우는 최적 수송⁠(optimal transport)⁠, 짝짓기의 경우는 홀의 정리⁠(Hall's theorem)⁠와 최대 흐름 최소 절단입니다. 한 걸음 한 걸음 더 좋은 쪽으로 가는 방법의 연속판은 경사 하강법⁠(gradient descent)⁠이고, 쌍대 정리의 뿌리가 된 게임 이론은 폰 노이만의 페이지에 있습니다.

관계.

• 함께 연구 존 폰 노이만 — 1947년 10월 선형 계획 문제를 설명하자 폰 노이만이 게임 이론에서 짐작한 쌍대 이론을 즉석에서 펼쳐 보였고, 이것이 선형 계획법 쌍대 정리의 출발점이 되었습니다.
• 영향을 줌 해럴드 쿤 — 1948년 그가 프린스턴의 앨버트 터커를 찾아가 선형 계획법을 소개한 것을 계기로 터커, 게일, 쿤이 1951년 쌍대 정리를 엄밀하게 증명했습니다.
• 영향을 줌 데이비드 게일 — 게일은 터커, 쿤과 함께 댄치그가 연 선형 계획법의 쌍대 정리를 증명하고 게임 이론과의 관계를 밝혔습니다.

연표.

• 1936년 메릴랜드 대학을 졸업하다
• 1939년 버클리에서 네이만의 칠판에 적힌 미해결 문제 두 개를 숙제로 알고 풀다
• 1941년 육군 항공대 통계 관리국에서 전시 계획을 맡다
• 1946년 버클리에서 박사 학위를 받고 공군 감사관실의 수학 자문이 되다
• 1947년 단체법을 만들고 프린스턴에서 폰 노이만을 만나다
• 1952년 랜드 연구소로 옮기다
• 1954년 49개 도시의 외판원 문제를 풀다
• 1960년 버클리의 교수가 되다
• 1963년 『선형 계획법과 그 확장』을 펴내다
• 1966년 스탠퍼드로 옮기다
• 1975년 국가 과학 훈장을 받다