선형계획법

선형계획법(線型計劃法, 영어: Linear Programming)은 1차부등식으로 주어진 여러 조건들을 만족시키면서, 최적의 결과를 내놓는 해를 찾는 방법을 말한다. 제2차 세계 대전 중 군수물자 보급을 최적화하기 위해 미국이 개발하였다.

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

제약 조건들이 1차식으로 주어지지 않는 경우에도 적용할 수 있는 알고리즘들도 연구되고 있는데, 이를 비선형계획법이라고 한다. 여담으로 비선형계획법의 예시 중 하나가 바로 게임이론이다.

용어

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

푸는 법

가우스 소거법

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

simplex method

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

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

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

여담으로 과거 컴퓨터의 연산성능이 떨어지던 시기에는 이 해를 찾는 알고리즘 자체를 간소화하는 것이 상당히 중요한 산업공학도의 업무 중 하나였다. 한정된 컴퓨터의 성능으로 빠른 시간 내에 원하는 값을 찾아내야 하기 때문. 물론 컴퓨터 발명 이후 수십 년 동안 컴퓨터의 성능 자체가 비약적으로 향상되었다고 하더라도 모든 선형계획법 문제에서 최적해를 찾을 수 있는 것은 아니다. 경우에 따라서는 무한루프에 빠져서, 혹은 교차점이 존재하지 않는 최악의 경우에는 최적해를 찾아내지 못하는 경우가 발생하고는 한다.

관련 소프트웨어

• Lingo
• 마이크로소프트 엑셀: 엑셀의 도구 중 해 찾기 모델이 바로 이 선형계획법의 최적해를 찾아주는 도구이다.

같이 보기

• 휴리스틱 기법