선형 계획법

수학에서 선형 계획법(Linear Programming)은 최적화 문제의 일종으로 주어진 선형 조건들을 만족시키면서 선형인 목적 함수를 최적화하는 문제이다. 선형 계획법은 운용 과학, 미시 경제학, 네트워크 경로 최적화 등 많은 분야에서 사용되고 있으며, 선형 계획법의 특수한 경우인 네트워크 흐름과 같은 문제들에 대해서는 여러 특화된 알고리즘들이 연구되어 왔다.

예 [편집]

예를 들어 홍길동씨가 빵 가게를 운영한다고 하자. 두 가지 종류의 빵을 판매하는데, 초코빵은 고급 빵으로 밀가루 100g과 초콜릿 10g이 필요하고 밀빵은 보통 빵으로 밀가루 50g만이 필요하다. 재료비를 제하고 초코빵을 팔면 100원이 남고 밀빵를 팔면 40원이 남는다고 하자. 오늘 홍길동 씨는 밀가루 3000g과 초콜릿 100g을 재료로 갖고 있다. 만든 빵을 다 팔 수 있고 더 이상 재료 공급을 받지 않는다고 가정한다면, 홍길동씨는 이익을 극대화 하기 위해서 어떤 빵을 얼마나 만들어야 할까? 이 문제를 풀기 위해 다음과 같은 선형 계획 문제를 만들 수 있다.

목적: $\max_{\mathbf{x}} 100 x_1 + 40 x_2$
조건:	$100 x_1 + 50 x_2 \le 3000,$
	$10 x_1 \le 100,$
	$x_1,\,x_2 \ge 0.$

여기서 $x_1$ 은 초코빵을 $x_2$ 는 밀빵의 개수를 의미하는 변수이다. 오늘 홍길동씨가 가장 많은 이익을 남기는 방법은 가능한 한 많은 초코빵을 만들고 남는 밀로 밀빵을 만드는 것이다. 따라서 초코빵 10개와 밀빵 40개를 만들면 되겠다.

표준형 [편집]

선형 계획 문제는 수식으로 어떻게 표현하느냐에 따라 다른 형태를 가질 수 있다. 하지만 선형 계획 문제의 최적해를 찾는 알고리즘을 개발하기 위해 일괄된 형태의 문제가 필요하다. 다행히도 부등식은 등식으로 등식은 부등식으로 변환하는 간단한 방법이 있다. 예를 들어 $x_1 + x_2 \le b_1$ 과 같은 부등식은 $x_1 + x_2 + s_1 = b_1,\,s_1 \ge 0$ 와 같은 등식과 간단한 조건으로 이루어진 형태로 바꿀 수 있고, $2x_1 + 3x_2 = b_1$ 과 같은 등식은 $2x_1 + 3x_2 \ge b_1$ 과 $2x_1 + 3x_2 \le b_1$ 의 두 부등식으로 변환할 수 있다. 따라서 특정한 형태의 표준형을 정하고 표준 문제의 최적해를 구하는 알고리즘을 구하면 어떠한 문제에도 적용할 수 있을 것이다. 선형 계획 문제의 표준형은 저자마다 다르지만 보통 다음과 같다.