[경영과학] 심플렉스 방법 1

심플렉스 방법의 핵심

심플렉스 방법은 대수적 절차 중 하나이다. 그러나 내재된 개념은 기하학적이다. 이러한 기하학적 방법을 이해하면 심플렉스 방법이 어떻게 운영되는지와 왜 그렇게 효율적인지에 대해 강한 통찰력을 갖게 된다.

 

다음과 같은 예제를 살펴보자심플렉스 방법의 핵심

심플렉스 방법은 대수적 절차 중 하나이다. 그러나 내재된 개념은 기하학적이다. 이러한 기하학적 방법을 이해하면 심플렉스 방법이 어떻게 운영되는지와 왜 그렇게 효율적인지에 대해 강한 통찰력을 갖게 된다.

 

다음과 같은 예제를 살펴보자

$$\begin{align*}
\text{Maximize} \quad & z = 3x_1 + 5x_2 \\
\text{Subject to} \quad & x_1 \leq 4 \\
                       & 2x_2 \leq 12 \\
                       & 3x_1 + 2x_2 \leq 18 \\
                       & x_1 \geq 0, \quad x_2 \geq 0
\end{align*}$$

출처: https://www.researchgate.net/figure/Exemple-Wyndor-Glass-Hillier-Lieberman-1995_fig1_348755858

 

그림을 보면 분석의 핵심이 되는 3개의 제약식과 5개의 제약식의 교차점이 나타나 있다. 이 문제에서 각 제약식의 경계(constant boundary)는 관련 제약식에 의해 허용되는 경계가 되는 직선이다. 이 직선들의 교차점을 꼭짓점 해라고 부른다.

 

가능해 영역에 놓여있는 5개의 꼭지점 해들 (0,0), (0,6), (2,6), (4,3), (4,0) 은 가능 꼭지점 해가 된다. 반면, (0,9), (4,6), (6,0) 은 불가능 꼭지점해라고 부른다. 이 예제에서 각 꼭지점 해는 두 개의 제약식 경계 직선의 교차점에 놓인다. 그림의 임의의 두 개의 쌍은 하나의 제약식 경계를 공유하고 다른 쌍들은 공유하지 않는다. 이를 일반화해서 정의하면

$n$개의 의사결정변수를 갖는 어떤 선형계획 문제에 대해 두 개의 꼭지점 가능해는 그들이 $n-1$개의 제약식 경계를 공통으로 갖고 있으면 서로에 대해 인접(adjacent)하다. 두 개의 인접한 꼭지점 가능해는 공통으로 가진 제약식의 경계인 하나의 선분으로 연결된다. 그런 선분을 모서리(edge)라고 한다.

 

이 예제에서 $n = 2$이므로 하나의 제약식의 경계를 공통으로 가지면 두 개의 꼭지점 가능해는 인접하다. 예를 들면 (0,0)과 (0,6)은 $x_1 = 0$이라는 제약식 경계선을 공유하므로 인접하다.

꼭지점 가능해	인접한 꼭지점 가능해
(0,0)	(0,6) and (4,0)
(0,6)	(2,6) and (0,0)
(2,6)	(4,3) and (0,6)
(4,3)	(4,0) and (2,6)
(4,0)	(0,0) and (4,3)

 

인접한 꼭지점 해가 중요한 이유는 다음과 같은 일반적인 성질 때문이다.

최적해 검사: 최소한 하나의 최적해를 갖는 선형계획 문제에서, 임의의 꼭지점 가능해가 인접한 더 좋은 꼭지점 가능해가 없다면, 그 해는 최적해이다.

 

그러므로 예제에서 $Z = 36$이 $Z = 30$을 갖는 (0,6)과 $Z = 27$을 갖는 (4,3)보다 더 큰 $Z$를 가지므로 (2,6)이 최적해이다. 이때, 최적해에서 나오는 목적함수 $Z$의 값을 최적값이라고 한다.

 

최적해에 도달하는 방법

1. 초기화: (0,0)을 조사를 위한 초기 꼭지점 해로 선택한다. (원점은 비음 제약조건의 교차점이므로 무조건 꼭지점 가능해)

2. 최적화 검사: (0,0)이 최적해가 아니라고 판별 (더 좋은 꼭지점 가능해가 있다)

3. 다음과 같은 세 단계를 수행하여 더 좋은 인접 꼭지점 가능해 (0,6)으로 이동한다.

• (0,0)에서 나오는 2개의 가능해 영역의 모서리를 고려하여 $x_2$축을 따르는 모서리를 선택하여 그 방향으로 이동한다. ($Z$를 더 빠르게 증가)
• 처음 만나는 새로운 제약식 경계 : $2x_2 = 12$에서 정지한다. (더 이동하면 가능해 영역을 벗어남)
• 새로운 제약식 경계선의 교점에서 해 (0,6)을 구한다.

4. (0,6)이 최적해이면 멈춘다. 아니면 최적해가 나올 때까지 1,2,3을 반복한다.

 

핵심적인 해 개념들

해 개념 1: 심플렉스 방법은 꼭지점 가능해에만 초점을 둔다. 최소한 하나의 최적해를 갖는 문제에서 하나의 최적해를 찾는 것은 가장 좋은 꼭지점 가능해 하나만을 찾는 것을 필요로 한다. 가능해 개수는 무한이므로 조사할 해의 개수를 최소화한다.

 

해 개념 2: 심플렉스 방법은 초기화 -> 최적해 검사 -> 최적해이면 종료, 아니면 반복 구조를 갖는 알고리즘 중 하나이다. (위의 예시)

 

해 개념 3: 가능하면 초기 가능해를 원점으로 선택한다. 모든 의사결정변수가 비음조건 (음이 아닌 조건)을 가지면 제약식들의 교점이 원점이 되므로 초기해 선택이 가능하다.

 

해 개념 4: 주어진 꼭지점 가능해에 대해 다른 꼭지점 가능해보다 인접한 꼭지점 가능해에 관련하여 정보를 모으는 것이 계산학적으로 빠른다. 그러므로 심플렉스 방법은 항상 현재해의 인접한 꼭지점 가능해를 다음 해로 선택한다. 결과적으로 전체적인 경로는 가능해 영역의 모서리를 따라가게 된다.

 

해 개념 5: 인접한 꼭지점 가능해로 이동할 때, $Z$의 개선율이 양수인 것들 중 가장 큰 방향으로 이동해서 계산에 드는 비용을 줄인다. 만약 더 이상 양의 개선율을 보이는 모서리가 없다면, 현재해가 최적해가 된다.

 

심플렉스 방법

대수적인 절차는 방정식 체계를 푸는 절차에 기반을 두고 있다. 따라서 심플렉스 방법을 위해 제일 먼저 준비하는 절차는 기능적 부등호를 가진 제약식을 동일한 효과를 가지는 등호 제약식으로 변환하는 것이다. (비음 제약식은 제외) 이와 같은 변환은 여유 변수(Slack Variables)를 도입함으로써 가능하다.

 

예를 들어, $x1 \leq 4$ 제약식은 여유 변수 $x_3$를 도입함으로써 

$x_1 + x_3 = 4$ 및 $x_3 \geq 0$ 으로 동일한 효과를 갖도록 만들 수 있다. 같은 방법으로 위의 예제를 아래와 같은 동등한 모형으로 대체할 수 있다.

$$\begin{align*}
\text{Maximize} \quad & z = 3x_1 + 5x_2 \\
\text{Subject to} \quad & x_1 + x_3 = 4 \\
                       & 2x_2 + x_4 = 12 \\
                       & 3x_1 + 2x_2 + x_5 =  18 \\
                       & x_j \geq 0, \quad j = 1, 2, 3, 4, 5
\end{align*}$$

 

이와 같은 형태를 모형의 확장형이라 하며, 원래 형태의 문제를 원형이라고 한다.

 

확장형 모형에서 여유변수 값이 0이면, 현재해는 해당 기능 제약식의 경계선에 놓여 있는 것이 된다. 0보다 크다면 해가 제약식 경계의 가능해 영역에 놓여 있고, 0보다 작으면 해가 제약식 경계의 불가능해 영역에 놓여 있는 것을 의미한다. 따라서 모든 여유변수에는 결정변수와 마찬가지로 비음 제약조건이 붙어야 한다.

 

원래의 변수 값과 여유변수에 대해 대응하는 값을 갖도록 원래 해를 확장한 해를 확장된 해라고 한다.

예를 들면, (3,2)는 원형 모형의 가능해인데, 이를 대응하는 여유변수를 포함하여 적으면, (3,2,1,8,5)가 되고 이것이 확장된 해이다.

 

이러한 해 중 꼭짓점 해의 확장된 해를 기저해(basis solution) 라고 한다. 그 중에서 꼭짓점 가능해의 확장된 해를 기저 가능해라고 한다. 

 

꼭짓점 불가능 해 (4,6)의 확장된 해는 (4,6,0,0,-6)이다. 이때 여유변수 $x_5$의 값이 음수이므로 이 확장해는 기저 불가능해가 된다.

 

기저해의 성질

1. 각 변수는 비기저변수이거나 기저변수로 설정된다

2. 기저변수의 개수는 기능 제약식의 개수와 같다. 따라서 비기저변수의 개수는 (전체변수의 개수) - (기능 제약식의 개수)와 같다.

3. 비기저변수의 값은 0으로 설정되어 있다

4. 기저변수의 값은 방정식 체계를 풀어 얻어진다. 기저변수의 집합을 기저라고 한다.

5. 만약 기저변수가 비음조건을 만족하면, 기저해는 기저가능해이다.

 

더 쉽게 이해하기 위해 기저가능해인 (0,6,4,0,6)을 고려해 보자. 이 해는 꼭지점 가능해 (0,6)의 확장으로 얻어진다. 그러나 이 똑같은 해를 얻는 다른 방법은 $x_1$과 $x_4$를 비기저변수로 설정하여 0으로 놓고 푸는 것이다. 같은 맥락으로 놓고 보면, 비기저변수에 해당하는 값이 모두 0이라면 해당 해는 기저가능해가 되는 것이다.(3번 성질)

 

이번엔 기저가능해의 인접한 해에 대해 살펴보자. 두 개의 기저가능해가 인접한지 판단하는 아주 쉬운 방법이 있다.

2개의 기저가능해는 그들의 비기저변수 중 하나를 제외한 나머지 변수가 모두 같을 때 인접한다. 이는 두 해에서 그들의 모든 기저변수가 하나를 제외하고는 똑같이 설정되었다는 것을 의미한다.

 

예시로 살펴보면, (0,0)과 (0,6)을 고려했을 때, 확장해 (0,0,4,12,18), (0,6,4,0,6)은 인접한다. 왜냐하면 그들의 비기저변수가 $(x_1, x_2)$에서 $(x_1, x_4)$로 변경되었기 때문이다. 결과적으로 인접한 기저가능해로 이동하는 과정은 변수 중 하나를 비기저변수에서 기저변수로 바꾸고, 기저변수를 비기저변수로 바꾸는 과정인 것이다.

 

우리는 확장형을 다룰 때, 목적함수를 등식으로 다루는 것이 편리하다. 그래서 심플렉스 방법을 적용하기 전에 문제를 똑같은 방식으로 다음과 같이 바꿔 쓴다.

 

$$\begin{aligned}
\text{Maximize} \quad & z \\
\text{Subject to} \quad & z - 3x_1 - 5x_2 = 0 \\
                        & x_1 + x_3 = 4 \\
                        & 2x_2 + x_4 = 12 \\
                        & 3x_1 + 2x_2 + x_5 = 18 \\
                        & x_j \geq 0, \quad j = 1, 2, 3, 4, 5
\end{aligned}$$

 

이를 실제로 심플렉스로 푸는 방법은 다음 포스팅 심플렉스 방법 2에서 다루도록 하겠다.