그렇다면 선형계획법이란 대체 무엇일까요? 선형계획법 Linear Programming이란 제약 조건이 연립 일차 부등식 또는 연립 일차 방정식으로 나타나고, 알고자 하는 값을 나타내는 목적 함수 또한 일차식인 경우에 이 일차식의 최댓값 또는 최솟값을 구하는 방법에 관한 이론입니다. 즉, 선형, 다시 말해 일차식으로 주어진 제약 조건 하에서 선형함수의 최댓값 또는 최솟값을 구하는 방법을 말합니다.
선형계획법 모형은 총 3가지 요소로 구성됩니다. 제품의 생산량 또는 투자 금액과 같은 기업의 활동을 나타내는 변수인 의사 결정 변수 Decision Variables, 이익 또는 비용의 최소화와 같이 의사 결정의 목표에 해당하는 목적 함수 Objective Function, 그리고 생산능력 또는 자본과 더불어 의사 결정 변수의 비음 조건과 같이 자원의 제한을 표시하는 제약 조건 Constraints이 그에 해당합니다.
이때 앞선 상황에서의 의사 결정 변수는 제품의 생산량과 소요 시간, 소모 비용이 될 것이고 목적 함수는 이익의 최대화, 그리고 제약 조건은 제한된 자금과 의사 결정 변수가 음의 값일 수 없다는 조건이 될 것입니다. 자 그러면, 글만으로는 이해가 어려울 수 있으니 선형계획법이 적용되는 예시를 살펴봅시다.


다음과 같은 상황에서 기업의 이익을 최대화하기 위해 A, B 제품의 생산 수량을 결정해야 한다고 해봅시다. A 제품의 생산량을 X, B 제품의 생산량을 Y라고 하면, 조건들을 아래와 같은 수식들로 나타낼 수 있습니다. 이때 제약 조건식을 바탕으로 좌표상에 실행 가능 영역을 표시하면 아래 그림과 같이 나타나므로 목적 함수 $Y = \frac{Z}{600} - \frac{5}{6}X$를 통해 범위 내에서 Z가 최대가 되는 의사 결정 변수 X와 Y의 값을 구할 수 있습니다.


위와 같이 기하학적 방법을 통해 선형계획 문제를 해결할 수도 있지만, 이는 의사 결정 변수가 3개만 돼도 그래프를 3차원으로 표현하기가 쉽지 않고, 의사 결정 변수가 4개가 되면 사용할 수 없습니다. 그 때문에 많은 변수를 가진 문제에 대해서는 대수적인 방법인 심플렉스법 Simplex Method을 사용합니다.
심플렉스법은 실행 가능 영역을 구성하는 수도 없이 많은 점 중에서 극점만을 해의 대상으로 하여 하나의 극점에서 인접한 극점으로 순차적으로 최적해를 탐색해 가는 방법입니다. 간단히 말하면 선형계획법에서 최적해를 구하는 알고리즘의 한 종류라고 할 수 있죠.
심플렉스법은 행렬 계산의 원리를 이용한 방법으로 그 과정은 다음과 같습니다.


여기서 진입 변수와 진출 변수는 심플렉스 표에 의해 결정이 되고, 심플렉스법의 시행 결과 최적해와 목적 함수 값을 구할 수 있습니다. 지금까지 선형계획법에 대해 알아보았는데요, 선형계획법은 경영과학뿐만 아니라 미시 경제학, 네트워크 경로의 최적화 등 다양한 분야에서 활용되고 있습니다. [링크 - 과학적 경영의 원조, 선형계획법] 선형계획 모형의 다른 해법과 심플렉스법에 대해 더 알고 싶은 친구들은 심플렉스법 뿐만 아니라 내부점법 Interior Point Method, big-M법 big-M Method, 쌍대 심플렉스 Dual Simplex Method등에 대해 더 공부해 보는 것을 추천해 드려요!!