선형 계획법(Linear programming)

빵집에서 하루에 식빵 x판과 케이크 y판을 굽습니다. 한 판에 남는 이익은 식빵이 3만 원, 케이크가 2만 원입니다. 재료와 시간에는 한계가 있습니다. 식빵 한 판에는 밀가루 2 kg, 케이크 한 판에는 1 kg이 들고 밀가루는 하루 10 kg뿐입니다($2x + y \le 10$). 오븐은 어느 것이든 한 판에 한 시간씩 하루 6시간 쓸 수 있습니다($x + y \le 6$). 장식하는 일손은 식빵에 한 시간, 케이크에 세 시간이 들고 하루 15시간이 있습니다($x + 3y \le 15$). 이익 $3x + 2y$를 가장 크게 하려면 무엇을 몇 판 구워야 할까요?

목표도 제약도 모두 일차식이라서 이런 문제를 선형 계획법이라 합니다. 여기서 '계획(programming)'은 컴퓨터 프로그램이 아니라 군대의 작전 계획표를 뜻하던 말입니다. 제약을 모두 지키는 점 (x, y)들은 평면에서 직선 몇 개로 잘라 낸 볼록 다각형⁠(convex polygon)⁠, 곧 안의 어느 두 점을 이어도 그 선분이 밖으로 나가지 않는 다각형을 이룹니다. 부등식 하나가 평면을 직선으로 반 잘라 한쪽을 남기고, 그런 반평면 몇 개가 겹친 곳이기 때문입니다. 이 다각형을 실현 가능 영역⁠(feasible region)⁠이라 합니다.

이익이 같은 계획들, 예컨대 $3x + 2y = 12$인 점들은 한 직선 위에 있고, 이익의 값을 바꾸면 이 직선이 화살표 c 방향으로 나란히 옮겨 갑니다. c는 이 직선들에 수직입니다(내적⁠(dot product)⁠ $c \cdot x$가 같은 점들이니까요). 가장 큰 이익을 찾는 일은 이 직선을 c 쪽으로 밀어 가다가 다각형에서 떨어지기 직전의 마지막 점을 찾는 일이고, 그 마지막 자리에는 언제나 꼭짓점이 있습니다. 화살표를 돌려 보면 답이 이 꼭짓점에서 저 꼭짓점으로 건너뛸 뿐, 변의 가운데에 머무는 일은 없습니다. c가 어떤 변과 꼭 수직이 되는 순간에만 그 변 전체가 한꺼번에 답이 됩니다.

꼭짓점 원리. 정확히 말하면 이렇습니다. 실현 가능 영역이 비어 있지 않고, 꼭짓점이 적어도 하나 있으며(x, y ≥ 0 같은 조건이 있으면 늘 그렇습니다), 목표가 한없이 커지지 않는다면, 가장 좋은 답 가운데 적어도 하나는 꼭짓점입니다. 조건이 하나라도 빠지면 틀립니다. 예컨대 영역이 반평면 $x \le 1$ 하나뿐이고 목표가 x라면, 직선 x = 1 전체가 답인데 꼭짓점은 없습니다. 영역이 유한한 다각형일 때 까닭은 간단합니다. 선분 위에서 일차함수는 한쪽 끝으로 갈수록 한결같이 커지거나 작아지므로, 가장 큰 값은 끝점에서 나옵니다. 다각형 안의 점 P를 지나는 선분을 양 끝이 변에 닿도록 그으면 한쪽 끝이 P보다 좋거나 같고, 그 끝이 놓인 변에서 같은 논리를 한 번 더 쓰면 꼭짓점에 이릅니다. 그러니 어떤 점도 가장 좋은 꼭짓점보다 나을 수 없습니다. 그래서 무한히 많은 계획 대신 꼭짓점 몇 개만 비교하면 됩니다. 빵집의 꼭짓점은 (0, 0), (5, 0), (4, 2), (1.5, 4.5), (0, 5)이고 이익은 각각 0, 15, 16, 13.5, 10만 원이니 답은 식빵 4판, 케이크 2판입니다.

단체법. 변수가 수천 개면 꼭짓점의 수가 천문학적으로 많아서 모두 비교할 수 없습니다. 1947년 조지 댄치그가 내놓은 단체법(simplex method)은 한 꼭짓점에서 출발해 이웃한 꼭짓점 가운데 목표가 더 좋은 쪽으로 모서리를 따라 옮겨 가다가, 더 나은 이웃이 없으면 멈춥니다. 대부분의 산에서는 이웃보다 높다고 가장 높은 봉우리라는 보장이 없지만, 여기서는 있습니다. 영역이 볼록하고 목표가 일차식이라서, 어느 꼭짓점에서 모든 이웃보다 좋으면 영역 전체에서 가장 좋습니다(국소에서 전체로). 단체법은 실제 문제에서 놀랄 만큼 빠르지만, 1972년 빅터 클리와 조지 민티는 꼭짓점을 거의 모두 들르게 만드는 문제를 만들어 최악의 경우 걸음 수가 변수의 수에 대해 지수적으로 늘 수 있음을 보였습니다(점근 표기법⁠, asymptotic notation⁠). 계산량이 변수의 수에 대한 다항식⁠(polynomial)⁠으로 묶이는 방법은 1979년 레오니트 하치얀의 타원체법(답을 품은 타원체를 반으로 자른 뒤, 남은 절반을 품는 조금 더 작은 타원체로 바꾸기를 되풀이하는 방법)이 처음이고, 1984년 나렌드라 카르마카르의 내점법⁠(interior-point method)⁠은 모서리 대신 영역의 안쪽을 가로질러 가는 실용적인 방법이 되었습니다. 한편 '케이크를 2.5판 구울 수는 없다'처럼 답이 정수여야 하면 문제는 훨씬 어려워집니다. 정수 계획법⁠(integer programming)⁠은 NP-난해⁠(NP-hard)⁠, 곧 이것을 빠르게 풀면 NP에 속한 모든 문제를 빠르게 풀 수 있게 되는 문제입니다. 그런 풀이법은 알려져 있지 않고, 없으리라고 널리 믿어집니다(P 대 NP 문제⁠(P versus NP problem)⁠).

그림자 가격⁠(shadow price)⁠과 쌍대성⁠(duality)⁠. 밀가루를 kg으로 바꿔 보세요.

밀가루 1 kg이 늘 때 이익이 늘어나는 만큼을 밀가루의 그림자 가격이라 합니다. 처음 그림의 이익 (3, 2)에서 밀가루와 오븐 시간의 그림자 가격은 모두 1만 원이고, 일손은 남아도니 0입니다. 이 가격표에는 놀라운 성질이 있습니다. 식빵 한 판이 쓰는 자원을 이 가격으로 셈하면 2 × 1 + 1 × 1 + 1 × 0 = 3만 원, 케이크는 1 × 1 + 1 × 1 + 3 × 0 = 2만 원으로, 두 제품 모두 이익과 꼭 같거나 그 이상입니다. 그래서 어떤 계획이든

$$3x + 2y \;\le\; 1 \cdot (2x + y) + 1 \cdot (x + y) + 0 \cdot (x + 3y) \;\le\; 1 \cdot 10 + 1 \cdot 6 + 0 \cdot 15 = 16$$

입니다(x, y ≥ 0이라서 앞의 부등호가 성립하고, 제약 때문에 뒤의 부등호가 성립합니다). 16만 원보다 더 버는 계획은 없다는 증명서가 가격표 하나로 끝납니다. 이렇게 자원마다 가격 y를 매겨 '모든 제품의 자원 값이 이익 이상'이라는 조건 아래 자원 전체의 값을 가장 작게 하는 문제를 원래 문제의 쌍대 문제라 합니다. 위와 같은 식으로, 조건을 지키는 가격표는 어느 것이든 이익의 상한⁠(upper bound)⁠을 줍니다. 더 나아가 한쪽 문제에 가장 좋은 답이 있으면, 가장 싼 가격표의 값은 가장 큰 이익과 꼭 같습니다(쌍대 정리⁠, duality theorem⁠). 1947년 가을 댄치그가 프린스턴에서 이 문제를 설명하자 존 폰 노이만은 자신이 1928년 증명한 게임 이론⁠(game theory)⁠의 최소최대 정리⁠(minimax theorem)⁠와 같은 구조임을 알아보고 곧바로 쌍대 정리를 짐작했다고 전합니다(프린스턴 고등연구소). 증명은 1951년 데이비드 게일, 해럴드 쿤, 앨버트 터커가 출판했습니다. 최대화 뒤에 늘 짝이 되는 최소화가 숨어 있다는 이 원리는 쌍대성의 대표적인 예입니다.

역사. 일차 부등식을 연립해 푸는 방법은 1820년대 조제프 푸리에가 이미 적었지만 오래 잊혔습니다. 1939년 레닌그라드의 레오니트 칸토로비치는 합판 공장에서 기계마다 어떤 목재를 얼마나 맡길지 정하는 문제를 받고 『생산의 조직과 계획의 수학적 방법』을 썼습니다. 그는 제약마다 붙는 승수, 곧 오늘날의 그림자 가격으로 답을 찾고 그 경제적 뜻까지 말했지만, 가격을 계획의 도구로 삼는 생각은 소련 체제에서 의심을 받아 널리 퍼지지 못했습니다. 미국에서는 1941년 프랭크 히치콕이 공장에서 도시로 물건을 나르는 수송 문제를, 네덜란드 출신의 찰링 쿠프만스가 전시 선박 운항 문제를 다루었습니다(최적 수송⁠, optimal transport⁠). 1947년 미국 공군의 보급 계획을 맡은 조지 댄치그는 문제를 일반적인 꼴로 적고 단체법을 내놓았습니다. 첫 시험대 가운데 하나는 경제학자 조지 스티글러가 1945년에 낸 문제, 곧 음식 77가지로 영양소 9가지를 채우는 가장 싼 식단이었는데, 1947년 미국 국립표준국에서 계산원 아홉 명이 탁상 계산기로 약 120인일을 들여 풀었습니다. 스티글러가 어림으로 찾은 한 해 39.93달러보다 조금 싼 39.69달러가 답이었습니다. 1975년 노벨 경제학상은 자원의 최적 배분 이론으로 칸토로비치와 쿠프만스에게 돌아갔습니다.

이어지는 곳. 선형 계획은 여러 이름난 정리를 품고 있습니다. 관로망의 최대 흐름⁠(maximum flow)⁠이 가장 좁은 절단⁠(cut)⁠과 같다는 최대 흐름 최소 절단 정리⁠(max-flow min-cut theorem)⁠, 이분 그래프⁠(bipartite graph)⁠에서 가장 큰 짝짓기의 크기와 가장 작은 꼭짓점 덮개⁠(vertex cover)⁠의 크기가 같다는 쾨니그의 정리와 홀의 정리⁠(Hall's theorem)⁠는 모두 쌍대 정리의 특별한 경우이고, 흙을 옮기는 가장 싼 방법은 최적 수송입니다. 부등식 대신 등식 제약만 있으면 연립일차방정식⁠(system of linear equations)⁠이 되고, 목표가 매끄러운 곡면이면 기울기를 따라 내려가는 경사 하강법⁠(gradient descent)⁠과 제약마다 승수를 붙이는 라그랑주 승수법이 같은 역할을 합니다. 영역과 목표가 모두 볼록하다는 점에서 선형 계획은 볼록 최적화⁠(optimization)⁠의 가장 단순한 경우이고, 쌍대 정리도 그 틀에서 넓혀집니다. 가장 좋은 것을 고르는 일 전반은 가장 좋은 것 고르기에서, 가능한 조합이 폭발하는 문제는 동적 계획법⁠(dynamic programming)⁠과 욕심쟁이 알고리즘⁠(greedy algorithm)⁠에서 이어집니다.