[선형대수] 선형계획법(Linear Programming)과 Simplex method

[선형대수] 선형계획법 Linear Programming 개론

선형계획법(linear programming 줄여서 LP라고도 한다.)은 한정된 자원(제한조건)을 효율적으로 할당하여 목적함수를 최대회하거나 최소화하는 문제를 다룬다.

선형계획법이 말은 어렵지만 중학교 수학에서도 나왔던 것으로 기억한다. 문제의 예를 들면, 어떤 회사가 계산기 A와 B 두 종류를 생산하는데, 생산하는데 각각 5시간과 2시간이 소요된다. 회사는 계산기를 생산하는데 1주일에 900시간을 사용할 수 있다. A와 B를 생산하는데 드는 비용은 각각 8만원, 10만원이며, 사용가능한 자금은 2800만원이다. 대 당 이익은 각각 3만원 2만원이다. 회사의 목표는 이익을 최대화 하는 것이다.

이러한 문제를 푸는 방법은 

1) 조건을 부등식으로 나타내고, 2) 제약조건을 그래프로 표현한 다음 3)가능한 영역에서 최적의 해를 찾는 것이다.

보통 부등식은 선형부등식이고 2개의 부등식 (x>0, y>0과 같은 기본 조건제외)로 이루어져있다.

이러한 부등식은 영역의 꼭짓점이나 모서리에서 최적해를 갖는다는 사실이 증명되어있다. *1)

꼭지점을 최적해로 갖는 경우엔 해가 1개이고 모서리의 모든 점을 최적해로 갖는 경우엔 많은 해를 가진다.

함수의 최소값

목적함수의 최소값을 결정하는 문제는 가능영역에서 -f, 즉 f의 음의 최대값을 구함으로써 풀 수 있다.

이러한 방법은 가능영역(부등식을 만족하는 영역)이 볼록(convex)한 모양인 경우이다.

볼록한 모양이라는 것은 영역을 이루는 형태가 안으로 들어가는 부분이 없다는 뜻이고, 영역 내에 빈공간이 없다는 뜻이다.

*1) 목적함수의 최대값이 한 꼭지점이나 모서리에 생기는 이유?

가능영역이 있고 목적함수가 있을 때, 목적함수 직선의 y절편을 어떻게 조절하느냐에 따라서 직선이 가능영역의 안 밖으로 평행하게 움직이게 된다.

그 중 값이 최대가 되려면 자연스럽게 목적함수 직선이 가능영역에 걸치는 형태가 되어야 한다.

가능한 경우는 아래 그림과 같이 꼭지점 또는 모서리 2가지 경우가 있다.

 

선형계획 문제를 해결하기 위해 소개된 위의 그래프 방법에는 한계가 있다. 세 개 이상의 변수를 포함하는 경우에 대해 기하학적 접근은 비현실적이기 때문에 많은 변수를 가진 문제애 대해서는 대수적인 방법인 심플렉스 방법(simplex method)를 사용한다.

Simplex method는 쉽게 컴퓨터 프로그램화 할 수 있는 장점도 있다.  최적해는 심플렉스 알고리즘이라 불리는 알고리즘에서 기본 행 연산들을 사용하여 열에 영을 만든다. 심플렉스 알고리즘에서도 축들을 선택하여 열의 원소들에 영을 만드는데 사용하지만, 가우스-요르단 소거와는 다른 기준을 적용한다.

심플렉스 알고리즘

1. 선형방정식계의 첨가행렬을 구성한다. 이것을 초기 심플렉스 표(inital simpex tableau)라고 한다.

2. 마지막 행에서 마지막 원소 이외의 크기가 가장 큰 음의 원소를 찾는다(만일 둘 혹은 그 이상의 원소가 이 성질을 갖는다면 이들 중 어떤 것을 선택해도 상관없다). 만일 그런 원소들이 모두 음이 아니라면 그 표는 최종 형태이다.

3. 이 음의 원소가 들어 있는 열의 각 원소에 대해, 원소가 양이면 이 원소로 마지막 열의 대응하는 원소를 나눈다.

4. 3에서 나눈 결과가 가장 작은 행을 선택한다. 이 행과 2에서 선택된 열에 해당하는 원소를 축 원소(pivot element)라고 한다. 

5. 행연산을 사용하여 축 위치에 1을 하나 만들고, 축 열의 다른 원소들은 모두 0으로 만든다.

6. 마지막 행에서 음의 원소들이 모두 없어질 때까지 단계 2-5를 반복한다. 최종 행렬을 최종 심플렉스 표(final simplex tableau)라고 하며, 이 표로부터 최적해를 얻을 수 있다.

 

 

예제

다음의 제약조건 하에서 의 최대값을 구하자.

 

첫 번째 부등식을 만족하는 각각의 x, y 에 대해서 다음을 만족하는 음이 아닌 변수 u의 값이 존재할 것이다. 마찬가지로 두번째 부등식도 아래와 같이 표현할 수 있다. 이러한 u와 v를 원래 변수들의 느슨한 부분을 메워준다고 해서 여유변수(slack variable)라고 한다.

 

 

그리고 목적함수는 다음과 같은 형태로 쓰여진다.

 

 

이제 원래 문제는 다음 선형방정식계에서 f가 가능한 큰 값이 되도록 해를 결정하는 문제가 되었다.

 

 

심플렉스 알고리즘을 적용해보면, 우선 900/5 < 2800/8 이므로 1행이 축이된다.(1행의 x계수 5를 1로 만들것이다.)

 

 

 

 

최종 심플렉스표가 만들어졌다. 마지막 행에서 음의 원소들은 모두 제거되었고, 이 표는 다음의 선형방정식계에 대응된다.

 

 

u와 v가 양수이므로, 마지막 방정식에서 u, v = 0 일 때 f가 최대값 700을 갖는다. u, v의 값 0 을 위의 식에 대입하면 x=100, y=200을 얻는다. 이 결과는 기하학을 사용하여 얻은 결과와 일치한다.

 

 

도움이 되셨으면 공감 한번  눌러주세요^^