선형 계획법

위 그림은 선형 계획법의 예시로서, 최적화 문제

[math(\displaystyle\max_{x_1,\,x_2}100x_1+40x_2\quad{\rm s.t.}\begin{cases}10x_1\leq100\\100x_1+50x_2\leq3000\end{cases})]

의 해가 [math(x_1=10,\,x_2=40)]이고 그때의 목적함수의 값이 [math(2600)]임을 그래프로 나타낸 것이다.

1. 개요2. 상세3. 관련 문서

[clearfix]

1. 개요

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

2. 상세

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

선형 계획법

1. 개요

2. 상세

3. 관련 문서

분류