포스테키안

2021 가을호 / 지식더하기 ①

2021-10-19 118

선형계획법
Linear Programming ; LP

 

한정된 자원을 가장 효율적으로 사용하는 방법은 무엇일까요? 여러분이 한 기업의 대표라고 생각해 봅시다. 회사는 여러 제품을 생산하는데, 이 제품을 생산하는 데 걸리는 시간, 비용, 이익 등은 모든 제품이 다를 것입니다. 또한, 앞선 요소들과 더불어 한정된 자원을 모두 고려하여 회사의 이익이 최대가 되도록 각 상품의 생산량을 조절해야겠죠. 어때요, 상상만 해도 머리가 아프지 않나요? 이렇게 복잡한 문제를 해결할 방법 중 하나가 바로 ‘선형계획법(Linear Programming ; LP)’입니다.

그렇다면 선형계획법이란 대체 무엇일까요? 선형계획법이란 제약 조건이 연립 일차 부등식 또는 연립 일차 방정식으로 나타나고, 알고자 하는 값을 나타내는 목적 함수 또한 일차식인 경우에 이 일차식의 최댓값 또는 최솟값을 구하는 방법에 관한 이론입니다. 즉, 선형, 다시 말해 일차식으로 주어진 제약 조건에서 선형함수의 최댓값 또는 최솟값을 구하는 방법을 말합니다.

선형계획법 모형은 총 3가지 요소로 구성됩니다. 제품의 생산량 또는 투자 금액과 같은 기업의 활동을 나타내는 변수인 의사 결정 변수(Decision Variables), 이익 또는 비용의 최소화와 같이 의사 결정의 목표에 해당하는 목적 함수(Objective Function), 그리고 생산능력 또는 자본과 더불어 의사 결정 변수의 비음 조건과 같이 자원의 제한을 표시하는 제약 조건(Constraints)이 그에 해당합니다. 이때 앞선 상황에서의 의사 결정 변수는 제품의 생산량과 소요 시간, 소모 비용이 될 것이고 목적 함수는 이익의 최대화, 그리고 제약 조건은 제한된 자금과 의사 결정 변수가 음의 값일 수 없다는 조건이 될 것입니다. 자 그러면, 글만으로는 이해가 어려울 수 있으니 선형계획법이 적용되는 예시를 살펴봅시다.

다음과 같은 상황에서 기업의 이익을 최대화하기 위해 A, B 제품의 생산 수량을 결정해야 한다고 가정해 봅시다. A 제품의 생산량을 X, B 제품의 생산량을 Y라고 하면, 조건들을 아래와 같은 수식들로 나타낼 수 있습니다.
목적 함수(이익)


이때 제약 조건식을 바탕으로 좌표상에 실행 가능 영역을 표시하면 아래 그림과 같이 나타나므로 목적 함수 Y = z/600 – 5/6X  를 통해 범위 내에서 Z가 최대가 되는 의사 결정 변수 X와 Y의 값을 구할 수 있습니다.

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

1. 선형계획 모형을 방정식의 형태로 정리하여 심플렉스 표를 작성한다.
2. 진입 변수를 결정한다.
3. 진출 변수를 결정한다.
4. 해를 개선하고 최적해가 아니면 2로 간다.

여기서 진입 변수와 진출 변수는 심플렉스 표에 의해 결정이 되고, 심플렉스법의 시행 결과 최적해와 목적 함숫값을 구할 수 있습니다.

지금까지 선형계획법에 대해 알아보았는데요, 선형계획법은 경영과학뿐만 아니라 미시 경제학, 네트워크 경로의 최적화 등 다양한 분야에서 활용되고 있습니다. 선형계획 모형의 다른 해법과 심플렉스법에 대해 더 알고 싶은 친구들은 심플렉스법 뿐만 아니라 내부점법(Interior Point Method), big-M법(big-M Method), 쌍대 심플렉스법(Dual Simplex Method)등에 대해 더 공부해 보는 것을 추천해 드려요!!

 

참고 자료
[1] 대한수학회, 「선형계획법」, 『수학백과』, 2015.5.
https://terms.naver.com/entry.naver?docId=3405174&cid=47324&categoryId=47324
[2] 「선형계획법(Linear Programming)과 Simplex method」, 2018.8.9.
https://greatjoy.tistory.com/29
[3] 「심플렉스(Simplex)법」, 2019.1.1.
https://blog.naver.com/ksj8406/221431580870

 

글. 무은재학부 21학번 27기 알리미 조윤경