선형계획법 편집하기

'''Linear Programming'''

== 개요 ==
1차부등식으로 주어진 여러 조건들을 만족시키면서, 최적의 결과를 내놓는 해를 찾는 방법을 말한다. [[제2차 세계 대전]] 중 군수물자 보급을 최적화하기 위해 [[미국]]이 개발하였다.

[[대한민국]]에서는 [[고등학교]] 1학년 수학 부등식 파트에 잠깐 등장하고, [[대학교]] [[경영학|경영]], [[경제학|경제]], [[수학]], [[산업공학|산업공학]]과 등에서 가르친다.

제약 조건들이 1차식으로 주어지지 않는 경우에도 적용할 수 있는 [[알고리즘]]들도 연구되고 있는데, 이를 비선형 계획법이라고 한다.

==용어==
*최대화문제 : 목적함수식의 값을 최대로 하는 문제로 보통 최대수익값을 찾는 경우에 사용한다.
*최소화문제 : 묵적함수식의 값을 최소로 하는 문제로 비용을 최소화하는 값을 찾는 경우에 사용한다.
*실행가능해 : 기하학적으로는 각각의 직선을 그리는 제약식들이 만드는 영역이 생기는에 이 영역 내부의 모든 점을 의미한다. 대수학적으로는 모든 제약조건식을 만족하는 해를 의미한다.
*실행불가능해 : 모든 제약조건식을 만족하는 해가 존재하지 않는 경우를 의미한다. 기하학적으로는 제약식들이 만드는 영역 밖에 해당하는데 만일 최적해가 이 경우에 해당한다면 선형계획법을 깔끔하게 포기해야 한다.
*최적해 : 실행가능영역 중에서 목적함수값을 충족하는 것. 보통 최소값이나 최대값 둘 중 하나의 목적값에 맞춰진다.

==푸는 법==
===[[가우스 소거법]]===
중고등학교 때 연립방정식이나 연립부등식을 배웠다면 [[가우스 소거법]]이라는 이름을 몰라도 해당 방정식을 푸는 법은 배웠을 것이다. 공식적으로는 행렬을 사용하지만, 사실 행렬을 알기 전에 이미 중학교 단계에서 기본적인 원리를 배우게 된다. 문제는 미지수가 서너개 까지는 어찌어찌 손으로 풀 수 있지만 미지수의 개수가 늘어나면 그만큼 계산에 들어가는 시간은 기하급수적으로 증가하게 된다. 즉, 이론상 풀 수는 있지만 사람의 손으로 풀 수 있는 시간 수준을 벗어나 버린다는 것. 당연히 이런 경우를 위해 컴퓨터라는 것이 있는 것이지만 대학의 관련 수업 과제는 꼭 손으로 풀어서 내게 만든다는게 함정.

===simplex method===
심플렉스법이라고도 한다. 실행가능영역 내부의 점의 갯수는 무수히 많지만 목적함수에 맞게 얻어지는 최적값은 결국 주어진 제약식들끼리 교차하는 교점, 즉 기하학적으로는 실행가능영역의 꼭지점(극점)에 해당하는 부분들 중 하나가 바로 최적값에 해당한다는 점에 착안한 것이다. 즉, 극점의 수는 무한대가 아닌 유한개로 한정되어있으므로, 이 극점들의 값을 목적함수값에 대입하여서 그 중 가장 좋은 값을 찾았다면 바로 그 극점의 값이 최적해에 해당하는 것이다.

참고로 이 극점은 실행가능 기저해(Basic Feasible Solution)라고 하기도 한다.

아무튼 이 심플렉스법이 나타나면서 최적해를 찾아내는 것은 최초의 극점으로 옮겨가면서 반복적으로 목적함수에 해당 극점의 값을 대입하면서 각각의 값을 비교하는 단순반복작업이 되었으며, 이것은 손으로 푸는데는 가우스 소거법처럼 시간이 오래 걸릴 수 있지만{{ㅈ|걸리는 시간은 가우스소거법과 비교하면 같거나 작다}} 컴퓨터의 도움을 받을 경우 상당히 빠른 시간 내에 값을 찾을 수 있는 알고리즘의 특성을 가진다.

==예제==

==관련 프로그램==
*Lingo
*[[엑셀]] : 엑셀의 도구 중 해 찾기 모델이 바로 이 선형계획법의 최적해를 찾아주는 도구이다.

{{각주}}

[[분류:선형대수학]]
[[분류:경영학]]
[[분류:산업공학]]