선형 계획법

수학에서 선형 계획법(線型計劃法, 영어: linear programming 리니어 프로그래밍^[*])은 최적화 문제의 일종으로 주어진 선형 조건들을 만족시키면서 선형인 목적 함수를 최적화하는 문제이다. 선형 계획법은 운용 과학, 미시 경제학, 네트워크 경로 최적화 등 많은 분야에서 사용되고 있으며, 선형 계획법의 특수한 경우인 네트워크 흐름과 같은 문제들에 대해서는 여러 특화된 알고리즘들이 연구되어 왔다.

선형 계획법은 운용 과학 중에서 가장 일반적인 기법이다. 선형 계획법은 가변 요소 사이에 일차 방정식이 성립할 경우, 즉 선형(線型)의 관계가 있을 때, 변화의 한계를 정할 때에 사용하는 방법으로, 생산계획·수송계획 등 문제에 선형 계획법이 이용되고 있다. 할당 문제도 이 수법으로 풀어진다. 가령 판매 과장이 세일즈맨을 각 지역으로 할당하는 문제에 직면하고 있다고 하자. 세일즈맨에게는 제각기의 특성이 있어서 세일즈맨에 따라 적절한 지역이 다르고, 몇몇 세일즈맨은 매우 우수하여 어느 지역이라도 담당할 수 있으며 더욱이 다른 세일즈맨보다 더 좋은 업적을 올릴 수가 있다. 판매과장의 문제는 세일즈맨의 지역할당을 통하여 전체의 판매량을 최대로 함에 있을 것이다. 이 경우 만약 세일즈맨이 각각의 지역에 있어서 상대적 효율을 수량화 할 수 있다고 하면 간단한 선형 계획법의 수법을 써서 최적의 할당을 정할 수가 있다.

예

이익이 최대가 될 때는 이익을 나타내는 직선이 해가 존재할 수 있는 영역 중 원점에서 가장 떨어진 점 (10, 40)에 접할 때이다. $100x_{1}+40x_{2}=2600$

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

목적: $\max _{\mathbf {x} }100x_{1}+40x_{2}$
조건:	$100x_{1}+50x_{2}\leq 3000,$
	$10x_{1}\leq 100,$
	$x_{1},\,x_{2}\geq 0.$

여기서 $x_{1}$은 초코빵을 $x_{2}$는 밀빵의 개수를 의미하는 변수이다. 그림을 참고하면 오늘 홍길동 씨가 가장 많은 이익을 남기는 방법은 초코빵 10개와 밀빵 40개를 만드는 것이고, 그렇게 해서 얻을 수 있는 이익은 2600원이다.

표준형

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

목적: $\max _{\mathbf {x} }\mathbf {c} ^{T}\mathbf {x}$
조건:	$\mathbf {Ax} \leq \mathbf {b} ,$
	$\mathbf {x} \geq 0.$

여기서 $\mathbf {A}$는 $m\times n$ 행렬이고 $\mathbf {c}$와 $\mathbf {x}$는 $n$차원 벡터이며 $\mathbf {b}$는 $m$차원 벡터이다.

쌍대성

모든 선형 계획 문제에는 그에 대응하는 쌍대 문제가 있다. 쌍대 문제의 해는 원 문제의 해에 대한 정보를 담고 있기 때문에 매우 중요하고 유용하다.

원 문제가 최소화 문제라면 쌍대 문제는 최대화 문제가 되는데, 쌍대 문제의 최적값이 원 문제의 최적값보다 크지 않다는 것이 약한 쌍대성 정리, 사실 이 두 최적값이 같다는 것이 강한 쌍대성 정리이다.

목적: $\max _{\mathbf {x} }\mathbf {c} ^{T}\mathbf {x}$
조건:	$\mathbf {Ax} \leq \mathbf {b} ,$
	$\mathbf {x} \geq 0.$

위와 같이 표준형으로 나타낸 선형 계획 문제가 있을 때, 그 쌍대 문제는 아래와 같이 나타낼 수 있다.

목적: $\min _{\mathbf {y} }\mathbf {b} ^{T}\mathbf {y}$
조건:	$\mathbf {A^{T}y} \geq \mathbf {c} ,$
	$\mathbf {y} \geq 0$

알고리즘

단체법

 이 부분의 본문은 단체법 (알고리즘)입니다.

단체법은 제2차 세계 대전 당시 조지 댄치그가 군수 물자 보급의 최적화를 위하여 선형 계획법 문제를 해결하기 위하여 개발하였다.

내부점법

내부점법(Interior point method)은 나렌드라 카르마르카르(마라티어: नरेंद्र करमरकर, 영어: Narendra Karmarkar)가 1984년에 개발했다. 단체법과는 다르게, 최적해를 실현가능영역(영어: feasible region)의 내부에서 찾아간다.

같이 보기

• 비선형 계획법
• 넌제로섬 게임

외부 링크

• “Linear programming”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Linear programming”. 《Wolfram MathWorld》 (영어). Wolfram Research. 

이 문서에는 다음커뮤니케이션(현 카카오)에서 GFDL 또는 CC-SA 라이선스로 배포한 글로벌 세계대백과사전의 내용을 기초로 작성된 글이 포함되어 있습니다.