선형계획법

1. 개요[편집]

선형계획법(Linear Programming, LP)은 목적함수와 모든 제약조건이 결정변수의 일차식으로만 이루어진 최적화 문제, 그리고 그것을 푸는 방법론이다. 형태가 이보다 단순할 수 없는데도 자원 배분·수송·배합·스케줄링 같은 산업 문제의 상당수가 여기로 환원되고, 무엇보다 전역 최적해가 보장된다. 볼록 최적화의 가장 얌전한 특수 사례이자, 사실상 현대 최적화 이론 전체의 출발점.¹

목적함수가 이차식으로 올라가면 이차계획법, 제약이 행렬 부등식으로 올라가면 반정부호 계획법이다. 이 문서는 목적·제약이 전부 일차인 경우, 그리고 그 구조에서만 나오는 정점 이론·심플렉스법·쌍대성에 집중한다.

2. 표준형과 실행가능 영역[편집]

LP는 어떤 형태로 쓰여 있든 몇 가지 변형(부등식에 슬랙/잉여 변수 추가, 자유변수를 두 양수의 차로 분해, 최대화에 −1 곱하기)으로 표준형으로 바꿀 수 있다.

$$\min_{x} \; c^{\top} x \quad \text{s.t.} \quad Ax = b, \; x \ge 0$$

여기서 $A \in \mathbb{R}^{m \times n}$, $m < n$이다. 부등식만 남긴 정준형 $\max c^\top x$ s.t. $Ax \le b,\; x \ge 0$도 자주 쓰인다. 실행가능 영역 $\{x : Ax = b,\, x \ge 0\}$은 유한 개의 반공간의 교집합이므로 볼록 다면체(convex polyhedron)이고, 유계이면 다면포(polytope)가 된다.

여기서 LP의 심장인 정리가 나온다. $A$의 열 중 일차독립인 $m$개를 골라 기저 $B$로 삼고 나머지 비기저 변수를 0으로 두면 $x_B = B^{-1}b$가 유일하게 정해지는데, 이것을 기본해(basic solution)라 한다. $x_B \ge 0$이면 기본실행가능해다.

기본실행가능해 ↔ 다면체의 꼭짓점(극점)은 일대일 대응이다.

그리고 LP 기본정리: 실행가능 영역이 비어 있지 않고 목적함수가 아래로 유계이면, 최적해는 반드시 어떤 꼭짓점에서 달성된다. 무한히 많은 점을 뒤질 필요 없이 유한한 꼭짓점 목록만 뒤지면 된다는 뜻이다. 물론 그 개수는 최대 $\binom{n}{m}$이라 전수조사는 여전히 인생이 짧다.

3. 심플렉스법[편집]

1947년 조지 단츠히(George Dantzig)가 만든 심플렉스법은 꼭짓점 하나에서 출발해, 목적함수가 개선되는 모서리를 타고 이웃 꼭짓점으로 옮겨가기를 반복한다. 대수적으로는 기저에 변수 하나를 넣고 하나를 빼는 피벗(pivot) 연산이며, 태블로에 가우스-조던 소거를 한 번 돌리는 것과 같다.

한 반복의 절차는 다음과 같다.

• 감소비용 계산. 비기저 변수 $j$의 감소비용은 $\bar{c}_j = c_j - c_B^\top B^{-1}A_j$. 전부 0 이상이면 현재 꼭짓점이 최적이고 즉시 종료한다(최적성 판정).
• 진입 변수 선택. $\bar{c}_j < 0$인 것 중 하나를 고른다. 단츠히 규칙은 가장 음수인 것을 고른다 — 한 단위 움직일 때 가장 가파른 개선이지만, 실제 감소량은 스텝 길이까지 곱해야 하므로 이게 항상 최선은 아니다. 그래서 실무 코드는 최대 개선량이나 steepest-edge 규칙을 쓴다.
• 비율 검정. 진입 변수를 키우다 보면 어떤 기저 변수가 먼저 0에 닿는다. $\min_i \{ (B^{-1}b)_i / (B^{-1}A_j)_i : (B^{-1}A_j)_i > 0 \}$을 달성하는 행이 퇴출 변수다. 양수 성분이 하나도 없으면 그 방향으로 무한히 갈 수 있다는 뜻 — 무계(unbounded) 판정.
• 피벗. 해당 성분을 1로 만들고 같은 열의 나머지를 소거한다.

3.1. 퇴화와 순환[편집]

기본실행가능해에서 기저 변수 중 일부가 0이면 퇴화(degenerate)라 한다. 이때 비율 검정의 최소값이 0이 되어 꼭짓점은 그대로인데 기저만 바뀌는 헛피벗이 나온다. 헛피벗이 돌고 돌아 원래 기저로 되돌아오면 순환(cycling)이고, 알고리즘은 영원히 끝나지 않는다. 실제 예제가 존재한다.²

해결책은 두 가지다. 블랜드 규칙(Bland’s rule)은 진입·퇴출 후보 중 항상 첨자가 가장 작은 것을 고르는데, 이러면 순환이 수학적으로 불가능해져 유한 종료가 보장된다. 대신 개선 폭을 무시하니 반복 수가 늘어 실무에서는 순환이 의심될 때만 잠깐 켠다. 다른 하나는 $b$를 사전식으로 미세 섭동하는 lexicographic 규칙이다.

실전 구현은 태블로 전체를 갱신하지 않고 $B^{-1}$을 LU 분해 형태로 들고 다니며 필요한 열만 푸는 개정 심플렉스법(revised simplex)을 쓴다. 산업용 문제의 $A$는 거의 항상 희소행렬이고, 피벗마다 인수분해를 갱신(Forrest-Tomlin 등)하며 수십 회마다 재인수분해해 조건수 악화를 털어낸다.

4. 쌍대성[편집]

LP의 진짜 미학은 쌍대성이다. 원문제 $\max\{c^\top x : Ax \le b,\, x \ge 0\}$에 대해 쌍대문제는

$$\min_{y} \; b^{\top} y \quad \text{s.t.} \quad A^{\top} y \ge c, \; y \ge 0$$

• 약쌍대정리: 임의의 실행가능 $x, y$에 대해 $c^\top x \le b^\top y$. 즉 쌍대 실행가능해 하나만 있어도 원문제 최적값의 상계가 공짜로 나온다. 최적성 증명서를 손에 쥐는 것과 같다.
• 강쌍대정리: 한쪽이 유한 최적값을 가지면 다른 쪽도 그렇고 두 값이 정확히 일치한다. 쌍대 간극이 0이다. 반정부호 계획법에서는 슬레이터 조건 같은 제약자격이 추가로 필요한데, LP는 그런 것 없이 무조건 성립한다.
• 상보여유(complementary slackness): 최적에서 $y_i(b_i - a_i^\top x) = 0$, $x_j(a_j^\top y - c_j) = 0$. “제약이 느슨하면 그 그림자가격은 0, 그림자가격이 양수면 그 제약은 딱 붙어 있다.” 이는 카루시-쿤-터커 조건을 LP에 특수화한 것이고, 최적 쌍대변수 $y_i$가 곧 자원 $b_i$ 한 단위의 한계가치라는 민감도 해석을 준다.

심플렉스법이 도는 동안 원문제 실행가능성은 계속 유지되고 쌍대 실행가능성(=감소비용 비음수)이 마지막에 달성된다. 반대로 쌍대 쪽을 유지하며 도는 쌍대 심플렉스법은 제약을 하나 추가한 뒤 재최적화할 때 압도적으로 유리해서, 정수계획법의 분지한정 트리에서 절단면을 붙일 때마다 호출되는 주력 엔진이다.

5. 복잡도와 다른 해법[편집]

심플렉스법의 반복 수는 실무에서 대략 제약 개수의 2~3배 수준으로, 경험적으로는 다항식처럼 행동한다. 그런데 최악의 경우는 지수적이다. 1972년 클리-민티(Klee-Minty)는 살짝 찌그러뜨린 $n$차원 초입방체에서 단츠히 규칙이 $2^n$개 꼭짓점을 전부 방문하게 만드는 예제를 만들었다. 이후 알려진 대부분의 피벗 규칙에 대해 비슷한 반례가 나왔다.

그래서 이론적 다항시간 해법은 다른 길에서 왔다. 1979년 카치안(Khachiyan)의 타원체법이 최초의 다항시간 알고리즘이었지만 실측 성능은 처참했고, 1984년 카마카(Karmarkar)의 사영 스케일링 알고리즘이 다항시간과 실전 성능을 동시에 잡으며 내점법 시대를 열었다. 오늘날 대형 LP 솔버는 심플렉스(원/쌍대)와 내점법을 둘 다 탑재하고 문제에 따라 고른다 — 대충 말해 초대형 희소 문제는 내점법, 웜스타트가 필요한 반복 재최적화는 심플렉스 쪽이다.³ 웜스타트 이야기는 활성집합법 문서에서 더 다룬다. 실제로 심플렉스법은 LP에 특수화된 활성집합법으로 볼 수 있다.

6. 응용[편집]

• 수송·배정 문제: 공급지-수요지 비용 최소화. 계수행렬이 완전 단봉형(totally unimodular)이라 LP 해가 저절로 정수가 되는 축복받은 부류다.
• 네트워크 흐름 문제: 최대유량-최소절단 정리가 정확히 LP 쌍대성의 특수화다.
• 배합 문제: 사료·연료·합금 배합에서 성분 규격을 만족하며 원가 최소화. LP의 최초 산업 응용 중 하나.⁴
• 공학 해석과의 접점: 극한하중 해석의 하계정리(정적 허용 응력장 찾기), 강소성 문제의 선형화, 위상 최적화 초기 정식화의 순차 LP 근사 등. 비선형 문제를 매 반복에서 선형화해 LP로 푸는 순차 선형계획법(SLP)은 지금도 최적설계 현장에서 굴러다닌다.
• 게임과 학습: 2인 영합 게임의 최소최대 전략은 LP로 풀리고, 그 최적값의 존재가 폰 노이만의 최소최대 정리다. 마르코프 결정 과정의 최적 가치함수도 LP 정식화가 존재한다.

7. 관련 문서[편집]

• 이차계획법 · 반정부호 계획법
• 활성집합법 · 내점법
• 볼록 최적화 · 카루시-쿤-터커 조건
• 라그랑주 승수법 · 선형 상보성 문제
• 최적설계 · 다중기준 방법
• 희소행렬 · LU 분해
• 게임 이론 · 마르코프 결정 과정

8. Footnotes[편집]

1. 단츠히 본인이 대학원생 시절 지각해서 칠판에 적힌 문제를 숙제인 줄 알고 풀어 갔는데 알고 보니 통계학 미해결 문제 두 개였다는 일화의 주인공이다. 그 사람이 나중에 최적화 전체를 세운다. 지각은 하지 말자. ↩

2. 비일(Beale, 1955)의 3제약 예제가 고전이다. 손으로 피벗을 여섯 번 돌리면 처음 태블로로 돌아온다. 처음 겪으면 “내가 산수를 틀렸나” 싶어서 세 번쯤 다시 계산하게 된다. ↩

3. 다면체의 두 꼭짓점 사이 최단 모서리 거리가 항상 $m-n$ 이하라는 허쉬 추측이 참이었다면 다항시간 피벗 규칙의 희망이 있었는데, 2010년 산토스(Santos)가 반례를 만들어 버렸다. 심플렉스법의 최악 복잡도는 아직도 열린 문제다. ↩

4. 초기 사례인 “식단 문제”는 영양 요구량을 만족하는 최저가 식단을 구했는데, 최적해가 밀기울과 간을 몇 킬로그램씩 먹으라고 했다고 한다. 제약을 제대로 안 걸면 솔버는 정확히 시킨 대로 한다 — 이건 오늘날 형상 최적화에서도 매일 반복되는 교훈이다. ↩