8장. 선형계획법

요약

선형계획 문제의 꼴, 실행 가능 영역과 꼭짓점, 그래프 풀이, 심플렉스 방법의 생각, 선형계획의 쌍대 문제, 정수계획과 완화

목적함수와 제약이 모두 일차식인 최적화를 선형계획법이라 합니다. 공장의 생산 계획, 물류의 수송 경로, 영양소를 맞춘 가장 싼 식단, 항공사의 승무원 배치처럼 산업에서 가장 많이 풀리는 최적화 문제입니다. 해가 언제나 실행 가능 영역의 꼭짓점에 있다는 단순한 사실에서 심플렉스 방법이 나오고, 7장의 쌍대성이 가장 깔끔하게 드러납니다.

8.1 선형계획 문제

정의 8.1. 다음 꼴의 문제를 선형계획(linear program, LP)이라 합니다.

\min_{\mathbf x}\mathbf c^\top\mathbf x \quad \text{s.t.} \quad A\mathbf x \le \mathbf b, \quad \mathbf x \ge \mathbf 0.

부등호는 좌표별입니다. 실행 가능 영역은 반공간들의 교집합, 곧 볼록 다면체(polyhedron)입니다(1장). 목적함수도 일차라 볼록이므로 선형계획은 볼록 최적화입니다.

예제 8.2 (생산 계획). 제품 A는 하나에 이익 3, 제품 B는 이익 5입니다. A 하나에 기계 시간 1과 노동 3, B 하나에 기계 시간 2와 노동 2가 듭니다. 기계 시간은 8, 노동은 12까지 쓸 수 있습니다. 이익을 최대로 하려면?

\max 3x + 5y \quad \text{s.t.} \quad x + 2y \le 8, \quad 3x + 2y \le 12, \quad x, y \ge 0.

8.2 꼭짓점 정리

정리 8.3. 선형계획에 최적해가 있고 실행 가능 영역에 꼭짓점이 있으면, 최적해 가운데 적어도 하나는 꼭짓점입니다.

직관. 목적함수의 등위선 $\mathbf c^\top\mathbf x = t$ 는 평행한 직선(평면)들입니다. $t$ 를 줄여 가며 영역을 마지막으로 스치는 곳은 꼭짓점(또는 모서리 전체)입니다.

예제 8.2 계속. 꼭짓점은 $(0, 0)$ , $(4, 0)$ , $(0, 4)$ , 그리고 두 직선의 교점 $(2, 3)$ 입니다. 이익은 각각 $0, 12, 20, 21$ 이므로 최적해는 $(2, 3)$ , 최대 이익 $21$ 입니다.

변수가 $n$ 개, 제약이 $m$ 개이면 꼭짓점은 많아야 $\binom{m + n}{n}$ 개라 유한하지만, 그 수는 기하급수적으로 많을 수 있습니다.

8.3 심플렉스 방법

심플렉스 방법(simplex method)은 꼭짓점 하나에서 출발해, 목적함수가 좋아지는 이웃 꼭짓점(모서리 하나로 연결된 꼭짓점)으로 옮겨 가기를 더 나아질 수 없을 때까지 반복합니다. 볼록이므로 이웃보다 나은 꼭짓점이 없으면 전역 최적입니다.

최악의 경우 꼭짓점을 기하급수적으로 많이 방문하는 예가 있지만, 실제 문제에서는 대개 제약 수의 몇 배 정도의 단계로 끝납니다.
내부점 방법(interior point method)은 6장의 장벽법으로 영역 안쪽을 지나 최적점에 다가가며, 다항식 시간이 보장됩니다. 현대 풀이기는 두 방법을 모두 갖추고 있습니다.

8.4 선형계획의 쌍대성

원문제 $\max\mathbf c^\top\mathbf x$ s.t. $A\mathbf x \le \mathbf b$ , $\mathbf x \ge \mathbf 0$ 의 쌍대 문제는

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

정리 8.4 (선형계획의 강한 쌍대성). 원문제와 쌍대 문제 중 하나에 최적해가 있으면 다른 하나에도 있고, 두 최적값이 같습니다.

선형계획에서는 슬레이터 조건 없이도 강한 쌍대성이 성립합니다.

예제 8.5. 예제 8.2의 쌍대 문제는

\min 8y_1 + 12y_2 \quad \text{s.t.} \quad y_1 + 3y_2 \ge 3, \quad 2y_1 + 2y_2 \ge 5, \quad y_1, y_2 \ge 0.

두 제약을 등식으로 풀면 $y_1 = 9/4$ , $y_2 = 1/4$ , 값은 $18 + 3 = 21$ . 원문제의 최댓값과 같습니다.

경제적 의미. $y_1 = 9/4$ 는 기계 시간 1단위의 잠재 가격입니다. 기계 시간을 1 늘리면 이익이 $9/4$ 늘어납니다. 노동 1단위는 $1/4$ 의 가치가 있습니다. 쌍대 문제는 “자원을 얼마에 사들여야 공장 주인이 생산 대신 팔기로 하는가”를 묻는 문제로 읽을 수 있습니다.

8.5 정수계획과 완화

변수가 정수여야 하면(트럭 수, 예/아니오 결정) 정수계획(integer program)이 되고, 일반적으로 NP-난해합니다(이산수학). 보통 정수 조건을 빼고 푼 선형 완화(LP relaxation)의 값을 상한(최대화의 경우)으로 쓰고, 분기 한정법(branch and bound)으로 영역을 나누어 정수해를 찾습니다.

예제 8.6. 예제 8.2에서 기계 시간이 9이면 선형계획의 해는 $(1.5, 3.75)$ 로 정수가 아닙니다. 반올림한 $(2, 4)$ 는 실행 불가능하므로, 정수해는 따로 찾아야 합니다.

8.6 이 장의 요약

선형계획: 일차 목적함수 + 일차 제약. 실행 가능 영역은 볼록 다면체.
최적해는 꼭짓점에 있습니다. 심플렉스 방법은 꼭짓점을 따라 이동합니다.
쌍대 문제 $\min\mathbf b^\top\mathbf y$ s.t. $A^\top\mathbf y \ge \mathbf c$ , 강한 쌍대성이 늘 성립. 쌍대 변수 = 잠재 가격.
정수계획은 어렵고, 선형 완화로 한계를 얻습니다.

쓰이는 곳. 운영 연구(물류, 스케줄링, 공급망), 최적 수송 문제(이산 분포 사이 바서슈타인 거리는 선형계획), 네트워크 흐름(최대 유량–최소 절단 정리는 선형계획의 쌍대성), 게임 이론의 혼합 전략 계산, 조합 최적화의 근사 알고리즘(LP 반올림), 전력망의 경제 급전이 선형계획을 씁니다.

문제

8.1 [계산] · 확인 문제

$\max 2x + 3y$ s.t. $x + y \le 4$ , $x + 3y \le 6$ , $x, y \ge 0$ 을 꼭짓점을 비교해 풉니다.

값	답
$x^*$	[?]
$y^*$	[?]
최댓값	[?]

정답

3
1
9

풀이

꼭짓점 $(0, 0)$ , $(4, 0)$ , $(0, 2)$ , 교점 $(3, 1)$ 의 값은 $0, 8, 6, 9$ 입니다. 최적해 $(3, 1)$ , 최댓값 9입니다.

8.2 [계산] · 확인 문제

위 문제의 쌍대 문제 $\min 4y_1 + 6y_2$ s.t. $y_1 + y_2 \ge 2$ , $y_1 + 3y_2 \ge 3$ , $y \ge 0$ 의 최솟값은?

정답

풀이

두 제약을 등식으로 풀면 $y_2 = 1/2$ , $y_1 = 3/2$ , 값 $6 + 3 = 9$ 입니다. 강한 쌍대성대로 원문제의 최댓값과 같습니다.

8.3 [계산] · 확인 문제

위 문제에서 첫째 제약을 $x + y \le 5$ 로 늘리면 최댓값은 얼마가 되나요?

힌트 1

쌍대 변수 $y_1 = 3/2$ 이 첫째 자원의 잠재 가격입니다.

정답

10.5

풀이

새 교점은 $x + y = 5$ , $x + 3y = 6$ 에서 $(4.5, 0.5)$ 이고 값은 $9 + 1.5 = 10.5$ 입니다. 증가분 $1.5$ 가 잠재 가격과 같습니다.

8.4 [계산] · 확인 문제

예제 8.6(기계 시간 9, 노동 12)에서 정수 조건을 뺀 선형 완화의 최댓값은?

정답

23.25

풀이

교점 $x + 2y = 9$ , $3x + 2y = 12$ 에서 $x = 1.5$ , $y = 3.75$ 이고 $3(1.5) + 5(3.75) = 23.25$ 입니다. 다른 꼭짓점 $(0, 4.5)$ 는 $22.5$ , $(4, 0)$ 은 $12$ 입니다.

8.5 [증명]

선형계획의 약한 쌍대성을 직접 보입니다: 원문제와 쌍대 문제의 실행 가능한 $\mathbf x$ , $\mathbf y$ 에 대해 $\mathbf c^\top\mathbf x \le \mathbf b^\top\mathbf y$ .

풀이

$\mathbf x \ge \mathbf 0$ 이고 $A^\top\mathbf y \ge \mathbf c$ 이므로 $\mathbf c^\top\mathbf x \le (A^\top\mathbf y)^\top\mathbf x = \mathbf y^\top A\mathbf x$ 입니다. 또 $\mathbf y \ge \mathbf 0$ 이고 $A\mathbf x \le \mathbf b$ 이므로 $\mathbf y^\top A\mathbf x \le \mathbf y^\top\mathbf b$ 입니다.