선형계획법은 목적 함수와 제약 조건을 모두 선형식으로 표현하고, 제약을 만족하는 범위에서 목적 함수의 최댓값이나 최솟값을 구하는 방법이다.[3][4] 목적 함수는 이익처럼 크게 만들려는 값이나 비용·생산시간처럼 줄이려는 값을 나타내며, 제약 조건은 선택 가능한 해의 범위를 정한다.[1][3]
1. 개요
2. 모형의 구성과 정식화
선형계획 모형은 의사결정 변수, 목적 함수, 제약 조건으로 구성된다.[3] 의사결정 변수는 제품 생산량이나 투자 금액처럼 결정할 활동의 크기를 나타내며, 목적 함수는 그 선택으로 달성하려는 목표를 선형식으로 표현한다.[3]
기업의 이익을 최대화하는 문제라면 제품별 생산량이 변수가 되고 이익이 목적 함수가 된다.[3] 생산능력이나 자본의 한도는 제약 조건으로 표현하며, 생산량처럼 음수가 될 수 없는 변수에는 비음 조건을 둔다.[3][4]
선형계획법에서는 목적 함수를 최대화하거나 최소화하는 형태로 설정할 수 있다.[1] 임업의 목재 수확량 또는 생산량의 현재가치 최대화와 목재 생산비용 최소화가 각각 그 예다.[1]
3. 가능 영역과 최적해
모든 제약 조건을 만족하는 변수 값의 집합을 가능 영역이라고 한다.[4] 변수 두 개로 된 문제에서는 이 영역을 좌표 평면의 영역으로 나타내고, 그 안에서 목적 함수값을 비교해 최적해를 찾을 수 있다.[3]
선형계획 모형에서 제약 조건은 연립 일차 부등식이나 방정식으로 나타나며, 변수는 비음 조건을 가질 수 있다.[3][4] 가능 영역은 두 차원에서는 다각형으로, 고차원에서는 다면체로 표현될 수 있고 최적해는 그 영역의 꼭짓점에서 발생한다.[4]
변수가 많아지면 좌표 그림으로 가능 영역을 확인하기 어려워지므로 대수적 알고리즘을 이용한다.[3] 이때 가능 영역의 구조는 심플렉스법처럼 꼭짓점을 따라 해를 탐색하는 방법의 바탕이 된다.[3][4]
4. 심플렉스법과 내부점 방법
심플렉스법은 가능 영역의 한 꼭짓점에서 시작해 인접한 꼭짓점으로 이동하면서 목적 함수값을 개선하는 알고리즘이다.[3][4] 선형계획 모형을 방정식 형태로 정리해 심플렉스 표를 만들고, 표를 이용해 진입 변수와 진출 변수를 정한 뒤 해를 개선한다.[3]
더 이상 목적 함수값을 개선할 수 없으면 알고리즘은 최적해와 목적 함수값을 구한 것으로 종료한다.[3] 심플렉스법은 모든 가능 해를 하나씩 살피는 대신 꼭짓점 사이를 이동해 해를 탐색한다.[4]
내부점 방법은 꼭짓점이나 다면체의 경계를 따라가는 대신 영역의 내부를 통과해 최적해를 찾는 방법이다.[4] 선형계획법에는 심플렉스법과 내부점 방법을 포함한 여러 알고리즘이 있으며, 내부점 방법은 특정 유형의 대규모 문제에서 활용된다.[2][4]
5. 적용 분야와 사례
기업의 생산 계획에서는 제품별 생산량을 변수로 두고, 제한된 생산능력과 자원을 제약 조건으로 표현해 이익을 최대화할 수 있다.[3] 목적 함수를 비용이나 생산시간 최소화로 설정하는 문제도 선형계획법의 형태로 나타낼 수 있다.[1]
임업에서는 목재수확생산을 최대화하거나 목재 생산량의 현재가치를 최대화하는 목표를 세울 수 있다.[1] 목재 생산비용을 최소화하는 모형도 구성할 수 있다.[1]
물류 운송에서는 운송을 효율적으로 배분하는 문제를, 제조업에서는 생산 공정의 자원 배분 문제를 다룰 수 있다.[4] 항공사 승무원 스케줄링과 통신 네트워크의 대역폭 할당도 선형계획법의 활용 사례로 제시된다.[4]