[OR/최적화]Operation Research(경영과학/운영과학) - 4.심플렉스

2020/04/26 - [Data Science&Analysis] - [OR/최적화]Operation Research(경영과학/운영과학) -3. LP(선형계획법)

[OR/최적화]Operation Research(경영과학/운영과학) -3. LP(선형계획법)

1. 심플렉스 

심플렉스는 선형계획법을 풀이하기 위한 하나의 방법론으로 오늘날 가장 널리 사용되는 방법론 입니다. 심플렉스 방법론은 대수적 방법론이지만 우리는 기하학적 특성을 함께 확인할 수 있습니다. 아래는 기하학적 형태의 기본적인 심플렉스 모형입니다.

 

그림 1. Wyndor 유리회사 최적화 사례의 제약식과 목적함수

• 제약식을 통해 그려진 경계선들을 "제약식의 경계(Constant Boundary)" 입니다. 
• 제약식의 경계 내부의 파란 색칠 영역이 "가능한 해의 영역" 입니다.
• 제약식의 교점이 되는 빨간 점을 "꼭짓점 해(Coner Point Solutions__CPF)"입니다.

 

2. 심플렉스의 해

1) 기본적인 풀이법 

우리는 그림 1의 그래프를 통해 각각의 CPF와 인접한 CPF 해를 확인할 수 있습니다. 가령 CPF (0,0)의 인접한 CPF 해는 (0,6)과 (4,0)이 됩니다. 심플렉스는 이렇게 도출된 해를 목적함수에 대입하여 "최적해"를 찾습니다. 이 방법을 정리하면 아래와 같은 방식으로 진행됩니다.

 

1. 초기화 : 원점을 초기 CPF 해로 설정 (따로 계산이 불필요하기 때문입니다.)
2. 최적화 검사 : 목적함수에 CPF 해와 인접한 CPF 해를 대입하여 해당 CPF 해가 최적해인지 확인한다.
3. 반복 : 최적해가 아닌 경우 다른 CPF 해로 이동하며 최적화 검사를 반복한다.

2) 심플렉스의 핵심적인 해 개념

파란 색칠 영역 즉 가능한 해의 영역에는 무한개의 해가 존재합니다. 심플렉스는 이러한 무한개의 해 집합을 유한개의 적은 수로 줄이는 간략화를 통해 오늘날 가장 널리 쓰이는 방법론이 될 수 있었습니다. 또한 유한개의 해를 확인하는 문제로 축소하기 위해 심플렉스에서 표현하는 해(solution)는 몇 가지 개념적 특성을 갖습니다.

 

1. 심플렉스 방법은 CPF 해에 대해서만 초점을 둡니다. 최소 하나의 최적해를 갖는 문제에서 가장 좋은 해는 CPF해 이기 때문입니다.
2. 가능한 초기 CPF 해는 원점(0,0)을 사용합니다. 다양한 의사결정 변수들이 존재할 때 시간을 단축하고 올바른 답을 찾는 가장 쉬운 방식이기 때문입니다.
3. 최적화 검사를 실시할 때 기준 CPF 해의 인접한 CPF 해만을 확인합니다. 이 방법이 계산학적으로 가장 빠르며, 이때 최적해가 아닌 경우 다음 CPF 해로의 이동은 무조건 인접한 CPF 해를 선택합니다. 
4. 다음 CPF 해로의 이동은 무작위 선택이 아닌 현재 CPF에서 값의 개선률이 가장 높은 CPF 해로 이동합니다. 가령 그림 1에서 목적함수는 X2의 영향력이 더 크기 때문에 (0,0)에서 X2 축을 따라 (0,6)으로 이동합니다.

3. 심플렉스 확장식

그림 2. Wyndor 유리회사 최적화 사례의 제약식의 확장

심플렉스 방식은 기본적으로 컴퓨터를 사용해 해를 구하게 되고, 컴퓨터는 대수적 문제풀이 방식을 요구합니다. 대수적 절차는 방정식 체계를 푸는 절차에 기반하기 때문에 기능적 부등호를 가진 제약식을 등호를 가진 제약식으로 변환해야 합니다.(비음 조건 제외) 이러한 변환을 위해 여유 변수(slack variables)를 사용합니다. 

그림 2의 확장형은 그림 1의 제약식 원형을 변형한 형태로 X3, X4, X5 3개의 여유 변수를 통해 식을 등호 형태로 바꾼 형태입니다. 위와 같은 변형은 여유 변수로 표현되는 식이 기존 제약조건의 필요충분조건이 되기 때문입니다. 이러한 변형으로 우리는 몇 가지 새로운 용어를 사용하게 됩니다.

• 확장된 해(augmented solution) : 기존 의사결정변수의 값을 여유 변수에 대응하는 값을 갖도록 확장한 해
• 기저해(basic solution) : 가능한 모든 꼭짓점 해의 확장형
• 기저가능해(BF solution) : 확장된 CPF 해 ex. 원형 CPF 해 (0,0) => BF 해 (0,0,4,6,18)
• 이때, 기저해는 다음 성질을 갖습니다.

또한 기저해는 아래와 같은 특징을 갖습니다.

• 각 변수는 반드시 기저 변수이거나 비 기저 변수이다.
• 기저 변수 개수 = 기능 제약식 개수
• 비 기저 변수 값은 항상 0
• 기저 변수가 비음의 조건을 만족하는 기저해가 기저 가능해이다.

일반적으로 대부분 문제들은 그림 1, 2와 달리 다양하고 많은 제약조건이 있기 때문에 간단하게 표현하기 어렵습니다. 때문에 앞서 언급했듯 우리는 일반적으로 문제를 해결하기 위해 컴퓨터를 사용합니다. 본문의 방식으로 식을 확장한 후 행렬 형태의 표현식으로 수정함으로써 우리는 컴퓨터를 활용해 보다 쉽게 문제를 풀 수 있습니다.