선형계획법

왜 배우는가: 선형계획법은 생산계획과 자원 배분 문제를 푸는 기본 도구이며, 공장관리기술사 시험에서 모형 정식화, 그래프 해법, 민감도분석이 함께 묻는다. 답안에는 정의와 가정을 먼저 쓰고, 이어서 모형과 해법을 연결해야 감점을 줄일 수 있다.

출제 이력: 제121회 1교시 11번, 제121회 2교시 5번, 제103회 4교시 2번, 제97회 2교시 5번, 제91회 4교시 5번

1. 한 줄 정의와 핵심 키워드

선형계획법(LP)은 선형인 목적함수를 선형인 제약조건 아래에서 최대화하거나 최소화하는 해를 구하는 최적화 기법이다. 한정된 자원을 여러 활동에 나누어 배정하는 문제를 수학적 모형으로 바꾸어, 이익을 최대로 하거나 비용을 최소로 하는 배정 방법을 찾는 것이 핵심이다.

답안에 쓸 키워드는 다음과 같다.

• 의사결정변수: 생산량처럼 결정해야 할 미지수이며, 모형의 출력이 되는 값이다.
• 목적함수: 이익 최대화나 비용 최소화처럼 달성하려는 목표를 나타내는 선형식이다.
• 제약조건: 설비시간, 원자재, 인력 같은 자원의 한계를 나타내는 선형 부등식이다.
• 비음조건: 의사결정변수는 0 이상이어야 한다는 조건이다.
• 실행가능영역: 모든 제약조건을 동시에 만족하는 해의 집합이다.
• 최적해: 실행가능영역 안에서 목적함수를 최대 또는 최소로 만드는 해이다.
• 민감도분석: 계수나 자원량이 변할 때 최적해와 목적함수 값이 어떻게 바뀌는지 분석하는 절차이다.

2. 개념 풀이

선형계획법은 자원이 한정된 상황에서 목표를 최적화하는 의사결정 변수의 값을 정하는 방법이다. 여기서 선형은 목적함수와 제약조건을 이루는 식이 모두 변수의 1차식이라는 뜻이다. 기하학적으로는 제약조건이 직선(평면)으로 경계를 이루는 관계를 말한다. 따라서 선형계획법은 자원이 한정된 환경에서 수학적 모형을 세워 자원을 합리적으로 배분하는 방법이다.

일반 모형은 다음과 같이 쓴다. 목적함수는 아래 식을 최대화하거나 최소화한다.

$Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$

제약조건은 아래 식으로 표시하며, 비음조건은 모든 변수에 대해 x_j \ge 0 이다.

$a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n \le b_i \quad (i = 1, \ldots, m)$

식의 계수는 이름이 정해져 있다. 기여계수는 단위당 이익이나 비용을 나타내는 c_j이다. 기술계수는 제품 한 단위를 만드는 데 필요한 자원 소요량을 나타내는 a_{ij}이다. 우변상수는 자원의 가용량인 b_i이다. 이 세 가지가 고정된 값으로 주어져야 모형을 풀 수 있다.

두 변수 문제는 그래프로 풀 수 있다. 제약조건을 직선으로 그려 실행가능영역을 찾고, 그 영역의 꼭짓점 좌표를 목적함수에 대입해 값을 비교한다. 이것이 꼭짓점법이다. 목적함수의 최대값과 최소값은 실행가능영역이 유계일 때 꼭짓점에서 나타나므로, 영역 안의 모든 점을 검사할 필요가 없다.

변수가 3개 이상이면 그래프로 나타낼 수 없으므로 대수적 방법인 심플렉스법을 쓴다. 심플렉스법은 실행가능영역의 꼭짓점 중 하나에서 출발해 인접한 꼭짓점으로 옮겨 가며 목적함수 값을 개선하고, 더 이상 개선되지 않으면 그 점을 최적해로 판단한다.

선형계획법을 적용하려면 다음 네 가지 가정이 성립해야 한다.

• 확실성: 기여계수, 기술계수, 우변상수가 고정된 값으로 확실히 알려져 있다는 가정이다.
• 비례성: 생산량에 비례해 이익과 자원 소요량이 변한다는 가정이다. 예를 들어 1단위에 10시간이 걸리면 5단위에는 50시간이 걸린다.
• 가법성: 여러 제품이 같은 자원을 나누어 쓸 때 전체 소요량은 제품별 소요량의 합이라는 가정이다.
• 분할성: 의사결정변수가 소수 값도 가질 수 있다는 가정이다.

이 가정이 깨지면 모형의 해가 현실과 어긋나므로, 비선형 관계가 강한 문제에는 적용에 주의해야 한다.

3. 등장 배경과 필요성

생산 현장에서는 설비 가동시간, 원재료, 인력이 한정되어 있는데 제품의 조합과 생산량은 여러 가지가 가능하다. 이때 감이나 경험으로 생산량을 정하면 자원이 한 설비에 몰리거나 놀게 되어 이익이 줄어든다. 선형계획법은 이 선택지를 수식으로 정리해 자원을 가장 효율적으로 쓰는 조합을 찾게 한다는 점에서 필요하다.

이 기법은 제2차 세계대전 중 군수 물자와 병참의 배분 문제를 풀기 위해 체계화되었다. 이후 민간 기업에서 생산계획, 재고관리, 수송계획에 적용되면서 경영과학의 대표 기법이 되었다. 현재는 대규모 모형을 컴퓨터 소프트웨어로 푸는 것이 일반적이다.

공장관리에서 필요성은 여러 제품이 같은 설비를 공유할 때 어느 설비가 이익을 제한하는지 정량적으로 알 수 있다는 데 있다. 제약조건 중 자원이 모두 소진되는 설비가 병목이 되며, 그 설비의 자원을 늘렸을 때 이익이 얼마나 늘어나는지는 민감도분석으로 판단한다. 이 판단은 설비 증설이나 외주 결정 같은 자원 배분 의사결정의 근거가 된다.

4. 구성요소·원리·절차

선형계획 모형은 네 가지 구성요소로 이루어진다. 답안에는 각 구성요소의 의미와 일반식을 빠짐없이 쓰는 것이 기본이다. 선형계획법을 적용하려면 목적함수와 제약식이 모두 선형이어야 한다.