선형 계획법

1. 개요[편집]

---

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

2. 상세[편집]

---

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