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

심플렉스 방법의 대수학적 접근

이전 포스팅에 이어서 심플렉스 방법의 개념의 요점을 정리하도록 하겠다. 전에 다뤘던 예제를 다시 가져와 보자.

$$
\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}
$$

 

참고로, 이 형태는 심플렉스를 적용하기 위해 목적함수식과 기능제약식을 모두 등호 제약식으로 변환한 형태이다 (심플렉스 방법 1의 마지막 부분에 언급했었다)

 

심플렉스 방법 1" target="_blank" rel="noopener" data-mce-href="http://심플렉스 방법 1">http://심플렉스 방법 1

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

 

 

1. 초기화:

초기 기저가능해로 $x_1$과 $x_2$를 비기저변수로 설정한다. 이는 원점을 초기 기저가능해로 설정하겠다는 의미이다. 그러므로 초기 기저가능해는 (0, 0, 4, 12, 18)이다.

 

2. 촤적화 검사:

목적함수는 다음과 같다.

$Z = 3x_1 + 5x_2$

따라서 초기 목적함수 값은 $Z = 0$이다. 기저해 $(x_3, x_4, x_5)$ 중 어떤 것도 목적함수에서 0이 아닌 계수를 갖지 않으므로 비기저변수 $(x_1, x_2)$의 계수는 이들이 0에서 한 단위만큼 증가할 때 $Z$의 개선율을 나타낸다. 이 예제에서는 (3,5)이다. 전 포스팅에서도 언급했었지만 개선율이 양수인 상황이므로 현재해는 최적해가 아니다.

 

3. 이동방향의 결정 (반복 중 단계 1):

이제 인접한 기저가능해로 이동해야 하는데, 어떤 방향으로 이동해야 하는지는 $Z$의 개선율을 따져보면 된다. 2에서 (3,5)인 것을 알았다. 개선율이 더 큰 방향으로 이동해야 목적함수 값을 더 빨리 개선시킬 수 있으므로 이 경우에는 $x_2$방향으로 이동한다. 이때, $x_2$를 진입 기저변수 (혹은 진입 변수)라고 부른다.

 

4. 어디서 정지할 지 결정(반복 중 단계 2):

인접한 기저가능해로 이동을 시작했으면 이동을 멈추기까지 얼마나 증가해야 하는지를 생각해야 한다. $Z$를 증가시키더라도 가능해 영역을 벗어나지 않아야 한다. 기저변수를 증가시키는 것은 다음 등식들에서 기저변수들의 값의 변화를 의미한다.

$x_1 = 0$ 이므로

$$x_3 = 4$$

$$x_4 = 12 - 2x_2$$

$$x_5 = 18 - 2x_2$$

 

이 때, 다른 기저변수들의 비음조건이 깨지지 않아야 하므로 $(x_3, x_4, x_5)$에 대해 $x_2$의 상한을 구해보면 다음과 같다.

$$x_3 = 4 \geq 0 \quad, \text{상한 없음}$$

$$x_4 = 12 - 2x_2 \geq 0 \quad, x_2 \leq 6$$

$$x_5 = 18 - 2x_2 \geq 0 \quad, x_2 \leq 9$$

 

따라서 $x_2$는 6까지만 증가해야 하고, 이때, $x_4$의 값이 0으로 떨어지기 때문에 다음 반복에서의 새로운 비기저변수가 된다. 이때 $x_4$가 기저변수에서 탈락했다고 하여 탈락변수(혹은 퇴출 기저변수)라고 한다. 그리고 이와 같이 진입 기저변수의 증가 상한을 결정하는 방법을 최소비율검사라고 한다.

 

만약 최소비율검사대로 심플렉스 방법을 진행하지 않으면 어떻게 될까?

 

위 상황에서 만약 $x_2$를 9까지 증가시킨다고 해보자. 그러면 $x_4$의 값이 -6으로 음수가 되므로 기저 불가능해가 되어 가능해 영역을 벗어나게 될 것이다. 따라서 진입 기저변수를 증가시킬 때는 무조건 최소비율검사를 따라야 한다.

 

위의 과정을 계속 반복하다 보면 $Z$값이 개선될 것이고, 결과적으로 최적해에 도달할 수 있게 된다.

 

표 형태의 심플렉스 방법

심플렉스 방법을 수행하기에 가장 좋은 형태는 심플렉스 표를 사용하는 것이다. 다음은 다루는 예제 상황을 심플렉스 표 형태로 정리한 것이다.

(a) 대수적 형식			(b) 표 형식
			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
(0) $Z - 3x_1 - 5x_2 = 0$			$Z$	(0)	1	-3	-5	0	0	0	0
(1) $x_1 + x_3 = 4$			$x_1$	(1)	0	1	0	1	0	0	4
(2) $2x_2 + x_4 = 12$			$x_2$	(2)	0	0	2	0	1	0	12
(3) $3x_1 + 2x_2 + x_5 = 18$			$x_3$	(3)	0	3	2	0	0	1	18

 

 

이제 표를 이용해서 심플렉스 방법을 수행해보자.

 

우선, 예제에서 첫 탈락변수 결정을 위한 최소비율검사를 적용해보자. 심플렉스 표 상에서는 (0) 행에 해당하는 요소들 중 절댓값이 가장 큰 변수를 진입 기저변수로 선택하면된다. 표에서 해당 열이 굵게 표시되었다. 이를 피봇 열이라고 한다

(a) 대수적 형식			(b) 표 형식
			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
(0) $Z - 3x_1 - 5x_2 = 0$			$Z$	(0)	1	-3	-5	0	0	0	0
(1) $x_1 + x_3 = 4$			$x_3$	(1)	0	1	0	1	0	0	4
(2) $2x_2 + x_4 = 12$			$x_4$	(2)	0	0	2	0	1	0	12
(3) $3x_1 + 2x_2 + x_5 = 18$			$x_5$	(3)	0	3	2	0	0	1	18

 

다음은 최소비율검사를 적용해서 탈락변수를 결정하면 되는데, 비율을 구할 때는 피봇 열에서 양의 값을 갖는 계수를 선택하고 $(2,2)$, 이를 가지고 같은 행의 우변을 나눈다. $(\frac{12}{2}, \frac{18}{2}) = (6,9)$ 따라서 (2) 행에 해당하는 기저변수인 $x_4$가 탈락변수가 된다. 이떄 해당 행을 피봇 행이라고 한다. 

(a) 대수적 형식			(b) 표 형식
			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
(0) $Z - 3x_1 - 5x_2 = 0$			$Z$	(0)	1	-3	-5	0	0	0	0
(1) $x_1 + x_3 = 4$			$x_3$	(1)	0	1	0	1	0	0	4
(2) $2x_2 + x_4 = 12$			$x_4$	(2)	0	0	2	0	1	0	12
(3) $3x_1 + 2x_2 + x_5 = 18$			$x_5$	(3)	0	3	2	0	0	1	18

 

이렇게 되면 피봇 열과 피봇 행이 만나는 지점이 생기는데, 여기에 해당하는 값을 피봇이라고 한다. 붉은색으로 표시하였다.

(a) 대수적 형식			(b) 표 형식
			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
(0) $Z - 3x_1 - 5x_2 = 0$			$Z$	(0)	1	-3	-5	0	0	0	0
(1) $x_1 + x_3 = 4$			$x_3$	(1)	0	1	0	1	0	0	4
(2) $2x_2 + x_4 = 12$			$x_4$	(2)	0	0	2	0	1	0	12
(3) $3x_1 + 2x_2 + x_5 = 18$			$x_5$	(3)	0	3	2	0	0	1	18

 

피봇에 해당하는 값을 기준으로 가우스 소거법의 기초 행 연산을 적용한다.

 

1. 피봇 행을 피봇 수로 나눈다. 이것을 단계 2와 3의 새로운 피봇 행으로 결정한다.

2. 피봇 열에서 피봇 행이 아닌 각 행이 음의 계수를 가지면, 이 계수의 절댓값을 새로운 피봇 행에 곱하여 각 행에 더한다.

3. 피봇 열에서 피봇 행이 아닌 각 행이 양의 계수를 가지면, 이 계수의 절댓값을 새로운 피봇 행에 곱하여 각 행에서 뺀다.

 

그러면 다음과 같이 한 번 반복한 형태의 심플렉스 표가 원래 테이블 아래에 붙게 된다.

반복			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
0			$Z$	(0)	1	-3	-5	0	0	0	0
			$x_3$	(1)	0	1	0	1	0	0	4
			$x_4$	(2)	0	0	2	0	1	0	12
			$x_5$	(3)	0	3	2	0	0	1	18
1			$Z$	(0)	1	-3	0	0	$\frac{5}{2}$	0	30
			$x_3$	(1)	0	1	0	1	0	0	4
			$x_2$	(2)	0	0	1	0	$\frac{1}{2}$	0	6
			$x_5$	(3)	0	3	0	0	-1	1	6

 

위 표와 같이 $Z$값이 개선되었고, 우변 상수 값이 새롭게 업데이트됨을 확인할 수 있다. 초록색으로 표시하였다. 그리고, $x_2$가 $x_4$대신 기저변수로 진입한 것을 볼 수 있다. 파란색으로 표시하였다.

 

이제 마찬가지로 반복 1에서 다시 최소비율검사로 다음 탈락변수를 결정해보자. 아래와 같이 결정할 수 있다.

반복			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
0			$Z$	(0)	1	-3	-5	0	0	0	0
			$x_3$	(1)	0	1	0	1	0	0	4
			$x_4$	(2)	0	0	2	0	1	0	12
			$x_5$	(3)	0	3	2	0	0	1	18
1			$Z$	(0)	1	-3	0	0	$\frac{5}{2}$	0	30
			$x_3$	(1)	0	1	0	1	0	0	4
			$x_2$	(2)	0	0	1	0	$\frac{1}{2}$	0	6
			$x_5$	(3)	0	3	0	0	-1	1	6

 

이번에는 $x_1$이 진입변수, $x_5$가 탈락변수로 결정되었다. 피봇은 3이다.

피봇을 기준으로 다시 가우스 소거법에 의한 기초 행 연산을 적용해보면,

반복			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
0			$Z$	(0)	1	-3	-5	0	0	0	0
			$x_3$	(1)	0	1	0	1	0	0	4
			$x_4$	(2)	0	0	2	0	1	0	12
			$x_5$	(3)	0	3	2	0	0	1	18
1			$Z$	(0)	1	-3	0	0	$\frac{5}{2}$	0	30
			$x_3$	(1)	0	1	0	1	0	0	4
			$x_2$	(2)	0	0	1	0	$\frac{1}{2}$	0	6
			$x_5$	(3)	0	3	0	0	-1	1	6
2			$Z$	(0)	1	0	0	0	$\frac{3}{2}$	1	36
			$x_3$	(1)	0	0	1	0	$\frac{1}{3}$	-$\frac{1}{3}$	2
			$x_2$	(2)	0	0	1	0	$\frac{1}{2}$	0	6
			$x_1$	(3)	0	1	0	0	-$\frac{1}{3}$	$\frac{1}{3}$	2

 

반복 2까지 진행하고 나면 최적해 $(2,6)$에 도달하고 최적값 $Z = 36$을 얻게 된다. 현재해가 최적해인지 확인하는 방법은 (0)행에 해당하는 계수 중에서 음수가 남아있는지 확인하면 된다. 음수가 남아있다는 것은 목적함수값을 더 개선시킬 여지가 있다는 뜻이기 때문이다. 그러나 반복 2의 경우 음수인 값이 존재하지 않으므로 현재해가 최적해라고 결론지을 수 있다.

 

심플렉스 방법에서의 동등한 상태 해결

지금까지 심플렉스 방법에서 여러 선택 규칙 (최소비율검사, 진입변수, 탈락변수 등)에 대해 배웠다. 마지막으로, 이 규칙들이 동등한 상태를 갖거나 애매함 때문에 명확한 결정을 하지 못할 때, 어떻게 할지에 대해 논의해보자.

 

1. 진입 기저변수의 동등한 상태

만약 목적함수가 $Z = 3x_1 + 3x_2$ 였다면 $x_1$과 $x_2$가 동일한 음의 계수를 갖게 된다. 이럴 때는 임의로 하나를 선택하면 되는데, 일반적으로는 앞에 있는 것을 선택한다. 

 

2. 탈락변수의 동등한 상태

최소비율에 근거해서 탈락변수가 여러 개 생기는 상황도 발생할 수 있다. 이런 경우는 가장 위에 있는 변수를 탈락시킨다.

1번과 2번 처럼 가장 앞이나 위에 있는 변수를 선택하는 규칙을 블랜즈 규칙이라고 한다. 블랜즈 규칙을 따르면 무조건 최적해에 도달할 수 있다고 알려져 있다.

 

3. 탈락변수가 없을 때

진입변수는 있지만 탈락변수가 없는 상황도 발생할 수 있다. 이런 경우는 목적함수 $Z$값을 무한히 증가시킬 수 있다. 이런 경우를 unbounded라고 하며 이 경우에는 최적해가 없다.

 

4. 복수의 최적해

만약 위의 예제에서 $Z = 3x_1 + 2x_2$로 목적함수를 변경하고, 심플렉스를 적용해보면 반복 2에서 비기저변수 $x_3$가 행 (0)에서 0의 계수를 갖게 된다. $x_3$를 진입변수로 삼고 다시 한 번 반복을 적용하면 비기저변수 $x_4$에 해당하는 계수의 값이 0이 된다. 이렇게 최종 테이블에서 비기저변수에 해당하는 목적함수의 계수가 0인 경우, 복수의 최적해를 갖는다. 이런 경우에는 해를 다음과 같이 표현한다.

 

$(x_1, x_2, x_3, x_4, x_5)$ = w1(2, 6, 2, 0, 0) + w2(4, 3, 0, 6, 0)$

$w1 + w2 = 1, \quad w1 \geq 0, w2 \geq 0$

 

이러한 형태를 두 해의 볼록집합 (convex combination)이라 칭한다.

 

 

지금까지 심플렉스 방법의 핵심과 이를 표 형식으로 푸는 방법에 대해 정리해보았다. 그러나 우리가 다룬 예제는 기능 제약식이 모두 등식이며 모든 변수가 비음이고, 목적함수가 최대화 형태인 문제이다. 이러한 문제는 표준형이라고 한다. 그러나 모든 상황에서의 문제가 표준형인 것은 아니다. 다음 포스팅 심플렉스 방법 3에서는 표준형이 아닌 문제들을 다루는 법에 대해 얘기하도록 하겠다.