[경영과학] 심플렉스 - 민감도 분석

지난 주에 심플렉스 테이블의 행렬형 구조를 다루면서 초기테이블에 따라 특정 단계의 테이블 (혹은 최종 테이블)이 어떻게 구성되고, 변화하는지에 대해 살펴보았다. 그리고 '최적해 사후 분석' 포스팅에서 목적함수나 제약식의 변화에 따라 최적해가 변하는 민감도 분석에 대해서 살짝 다뤘었다. 오늘 포스팅에서는 심플렉스 테이블을 활용한 민감도 분석의 확장형 모델에 대해서 학습해보도록 하겠다.

 

심플렉스 테이블의 행렬형 구조" target="_blank" rel="noopener" data-mce-href="http://심플렉스 테이블의 행렬형 구조">http://심플렉스 테이블의 행렬형 구조

[경영과학] 심플렉스 테이블의 행렬형 구조

 

기초적 통찰

우선 심플렉스 테이블의 임의 반복 단계의 테이블의 구조를 다시 살펴보면 다음과 같다.

 

<심플렉스 테이블의 행렬형 구조>

반복			기저변수	방정식	계수						우변
					Z	원 변수들			여유변수들
0			$Z$	(0)	1	$-c$			0		0
			$x_B$	(1, .., m)	0	$A$			$I$		$b$

 

반복			기저변수	방정식	계수						우변
					Z	원 변수들			여유변수들
Any			$Z$	(0)	1	$c_BB^{-1}A - c$			$c_BB^{-1}$		$c_B B^{-1} b$
			$x_B$	(1, .., m)	0	$B^{-1}A$			$B^{-1}$		$B^{-1}b$

그리고 우리는 초기 테이블에 다음과 같은 작업을 해줌으로써 특정 반복 단계의 테이블을 얻을 수 있음을 알고 있다.

\[
\left[
\begin{array}{c|c}
1 &  c_BB^{-1}  \\
\hline
0 & B^{-1} 
\end{array}
\right]
\left[
\begin{array}{c|ccc}
1 & -c & 0 & 0 \\
\hline
0 & A & I & b
\end{array}
\right]
=
\left[
\begin{array}{c|ccc}
1 & c_B B^{-1} A - c & c_B B^{-1} & c_B B^{-1} b \\
\hline
0 & B^{-1} A & B^{-1} & B^{-1} b
\end{array}
\right]
\]

 

따라서 이 형태를 조금 변형해서 Row 0와 Row 1~m에 대한 부분을 써보면 다음과 같이 나타낼 수 있다.

 

Row 0 =  $\begin{bmatrix}
-c & 0 & 0 \\
\end{bmatrix} + c_BB^{-1}\begin{bmatrix}
A & I & b \\
\end{bmatrix}$

Rows 1 ~m = $B^{-1} \begin{bmatrix}
A & I & b \\
\end{bmatrix}$

 

우선 이와 같이 표현되는 구조를 이해하는 것은 앞으로 최적해에 관한 기초적 통찰을 하는 데 중요하므로 인지하고 넘어가도록 한다.

 

이제 최적해가 구해졌다고 가정을 하고, 심플렉스 최종 테이블의 행렬 구조식에 대해 다음과 같은 새로운 기호들을 도입해서 재정의하도록 한다.

• $S^{*} = B^{-1}$ : 행 1~m까지 있는 여유변수들의 계수들
• $A^{*} = B^{-1}A$ :  행 1~m까지 있는 원 변수들의 계수들
• $y^{*} = c_B B^{-1}$ : 행 0에 있는 여유변수의 계수들
• $z^{*} - c = c_B B^{-1} A - c$ : 행 0에 있는 원 변수의 계수들
• $Z^{*} = c_B B^{-1} b$ : 목적함수의 최적값
• $b^{*} = B^{-1} b$ : 행 1~m까지의 우변상수 값, 즉 현재 기저가능해

이것을 다시 참조하여 초기표와 벡터 $t, T$에 대해 다음과 같이 초기표와 최종표가 표현된다고 했을 때,

 

초기 테이블
행 0	$t =  \begin{bmatrix} -c & 0 & 0 \\ \end{bmatrix}$
행 1 ~ m	$T =  \begin{bmatrix} A & I & b \\ \end{bmatrix}$
전체 행렬	$ \begin{bmatrix} t \\ T \end{bmatrix} = \begin{bmatrix} -c & 0 & 0 \\  A & I & b \\ \end{bmatrix}$

 

최종 테이블
행 0	\[ t^* = \begin{bmatrix} z^* - c & y^* & Z^* \end{bmatrix} \]
행 1 ~ m	\[ T^{*} = \begin{bmatrix} A^{*} & S^{*} & b^{*} \end{bmatrix} \]
전체 행렬	\[ \begin{bmatrix} t^{*} \\ T^{*} \end{bmatrix} = \begin{bmatrix} z^{*} - c & y^{*} & Z^{*} \\ A^{*} & S^{*} & b^{*} \end{bmatrix} \]

 

다음과 같은 형태로 새롭게 적을 수 있다.

 

(1) $t^{*} = t + y^{*}T = \begin{bmatrix}
y^{*}A - c & y^{*}& y^{*}b \\
\end{bmatrix}$

(2) $T^{*} = S^{*}T =  \begin{bmatrix}
S^{*}A & S^{*}& S^{*}b \\
\end{bmatrix}$

 

$y^{*}, S^{*}$의 정의와 심플렉스 테이블의 행렬형 구조의 최종 테이블 형태와 비교해보면 위 두 식은 유효한 식임을 알 수 있다.

 

민감도 분석

이제는 위의 기초적 통찰을 이용해서 민감도 분석을 수행해 보겠다. 민감도 분석은 크게 제약식의 우변상수가 변하는 경우와 목적함수 식의 계수가 변하는 경우를 살펴보도록 하겠다. 이전에 다뤘던 예제를 가져와 보자. 

반복			기저변수	방정식	계수						우변
					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
최종			$Z$	(0)	1	0	0	0	$\frac{3}{2}$	1	36
			$x_3$	(1)	0	0	0	1	$\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

 

위 테이블은 앞서 지속적으로 다뤘던 예제의 초기 테이블과 최종 테이블만 뽑아서 가져온 것이다. 이제 이 예제를 통해서 우변상수 $b$의 변화에 따른 목적함수의 최적값과 기저가능해가 어떻게 변하는지 살펴볼 것이다.

 

1) 우변상수가 변하는 경우

우선, 우변상수 $b$가 변화하는 경우를 살펴보도록 하겠다.

 

공식들을 이용하면,

$$b^{*} = S^{*}b$$

\[
Z^{*} = y^{*} b
\]

 

이렇게 목적함수와 기저가능해가 $b$의 함수로써 변한다는 사실을 알 수 있다. 그런데 우리는 최종 테이블로부터 $y^{*}$와 $S^{*}$를 알고 있기 때문에 새로운 $b$값에 대해 심플렉스 방법을 재적용할 필요가 전혀 없다.

 

예를 들어, 우변상수 중 $b_2$ (두 번째 우변상수)가 12에서 13으로 증가했다고 가정하자. 이 때,

 

\[
b^{*} = S^{*}b = 
\begin{bmatrix}
1 & \frac{1}{3} & -\frac{1}{3} \\
0 & \frac{1}{2} & 0 \\
0 & -\frac{1}{3} & -\frac{1}{3}
\end{bmatrix}
\begin{bmatrix}
4 \\
13 \\
18
\end{bmatrix}
=
\begin{bmatrix}
\frac{7}{3} \\
\frac{13}{2} \\
\frac{5}{3}
\end{bmatrix}
\]

 

그런데, 자세히 보면 $\begin{bmatrix}
\frac{7}{3} & \frac{13}{2} & \frac{5}{3} \\
\end{bmatrix}$는 $\begin{bmatrix}
2 & 6 & 2 \\
\end{bmatrix}$에서 $\begin{bmatrix}
\frac{1}{3} & \frac{1}{2} & \frac{-1}{3} \\
\end{bmatrix}$

만큼 변했음을 알 수 있다. 이 때 변화량은 $S^{*}$의 두번째 열과 동일함을 관찰할 수 있는데, 이는 우변상수 중에서 두 번째 구성요소인 $b_2$가 변했기 때문이다. 이 때 $b_2$의 변화량이 1만큼 변했으므로 $S^{*}$의 두 번째 열은 $b_2$의 단위 변화량 당 기저가능해의 변화량이 된다. 따라서 일반화하여 $\Delta b_2$에 대해 식으로 나타내보면

 

$$\Delta b^{*} = \begin{bmatrix}
2 & 6 & 2 \\
\end{bmatrix} +  \begin{bmatrix}
\frac{1}{3} & \frac{1}{2} & \frac{-1}{3} \\
\end{bmatrix} \Delta b_2$$

로 나타낼 수 있다.

 

다음으로는 목적함수값이 변화하는 정도인 잠재가격을 측정해보자. 동일하게 $b_2$가 12에서 13으로 1만큼 변화한 상황을 가정하겠다. 목적함수 값에 대해서는 $Z^{*} = y^{*} b$ 공식을 활용하면 된다. 그러면 다음과 같이 결과가 나온다.

\[
Z^{*} = y^{*}b = 
\begin{bmatrix}
0 & \frac{3}{2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
4 \\
13 \\
18
\end{bmatrix}
=
37.5
\]

 

이 때, 목적함수값이 36에서 37.5로 1.5만큼 증가하였음을 알 수 있는데, 왜 1.5만큼 증가하였을까? 바로 $y*$에서 두 번째 요소에 해당하는 값이 $\frac{3}{2}$이기 때문이다. 따라서 두 번째 우변상수가 1만큼 변화할 때 목적함수 값은 1.5만큼 증가한다고 말할 수 있다. 식으로 나타내면 다음과 같다.

$$\Delta Z^{*} = \frac{3}{2} \Delta b_2$$

 

<우변상수에 대한 민감도 분석>

 

2) 목적함수 계수가 변하는 경우

두 번째로는 목적함수의 계수가 변하는 상황을 가정해보자. 이번에는 두 번째 목적함수의 계수가 5에서 4로 감소한다고 생각하자. 이번에는 $c = \begin{bmatrix}
3 & 5 \\
\end{bmatrix}$가 $\begin{bmatrix}
3 & 4 \\
\end{bmatrix}$로 변하는 상황이다.

 

1)에서 우변상수가 변할 때는 $y^{*}$가 유지되는 상황이었지만 목적함수 계수가 변할 때는 $c$가 변하므로 최종적으로 $c_B$도 변하게 된다. 이 때 $c_B = \begin{bmatrix}
3 & 4 & 0\\
\end{bmatrix}$이 된다. 이때 $c_B$가 바뀌게 되므로 

\[
y^{*} = c_B S^{*}
\]
가 영향을 받아 바뀌게 된다. $y^{*}$가 바뀌므로 

$$z^{*} - c = y^{*}A - c$$

$$Z^{*} = y^{*}b$$

가 영향을 받아 바뀐다.

 

우선 $z^{*} - c = y^{*}A - c$에 해당하는 부분을 보자. 이는 최종 테이블에서 행 0의 원변수의 계수들이다. 그러나 위 예제에서는 이 변수들이 모두 기저변수에 해당되므로 여전히 0을 유지해야 한다. 직접 계산을 통해 살펴보자. 

 

\[
y^{*} = c_B S^{*} =
\begin{bmatrix}
3 & 4 & 0
\end{bmatrix}
\begin{bmatrix}
1 & \frac{1}{3} & -\frac{1}{3} \\
0 & \frac{1}{2} & 0 \\
0 & -\frac{1}{3} & -\frac{1}{3}
\end{bmatrix}
=
\begin{bmatrix}
0 & 1 & 1
\end{bmatrix}
\] 가 된다. 따라서 이를 이용해 남은 계산을 진행하면, 

 

\[
z^{*} - c = y^{*}A - c =
\begin{bmatrix}
0 & 1 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 \\
0 & 2 \\
3 & 2
\end{bmatrix}
-
\begin{bmatrix}
3 & 4
\end{bmatrix}
=
\begin{bmatrix}
0 & 0
\end{bmatrix}
\]

 

따라서 계산을 통해 기저변수의 계수가 0으로 유지됨을 확인하였다.

 

여기서 한 가지 더 짚고 넘어가자면, 목적함수의 계수가 바뀐다는 것은 기울기가 바뀐다는 것이고 그러면 기울기가 얼마나 변하느냐에 따라 현재해가 최적해가 유지가 될 수 있는 범위가 정해져 있다는 것이다. 그 범위 역시 구할 수 있는데, 바로 비기저변수의 계수가 0이상으로 유지될 조건이다. 비기저변수 중 하나라도 음수가 되어 버리면 그 비기저변수를 진입시켰을 때 더 좋은 최적해가 나올 가능성이 있으므로 직관적으로 해당 조건이 유효하다는 것은 알 수 있다.

 

$c_B$에 해당하는 부분이 $\begin{bmatrix}
0 & \frac{3}{2} & 1\\
\end{bmatrix}$에서 $\begin{bmatrix}
0 & 1 & 1\\
\end{bmatrix}$로 바뀌었는데, 이때 비기저변수 $x_4$에 해당하는 계수가 $\frac{-1}{2}$만큼 변한 것을 볼 수 있는데 왜 그럴까? 바로 $S^{*}$의 두 번째 열에 해당하는 요소 중 두 번째 행의 값인 $S^{*}_{22}$가 $\frac{1}{2}$이기 때문이다. 최종 테이블을 자세히 보면 $S^{*}$의 두 번째 열에 해당하는 비기저변수가 $x_4$이고, 두번째 행에 해당하는 기저변수가 $x_2$인데, 이 두 행과 열이 교차하는 지점의 값이 바로 $x_2$의 계수의 단위 변화량당 $x_4$의 계수 변화량임을 알 수 있다. 위 예시에서는 $x_2$의 계수가 -1만큼 변하므로 $x_4$의 계수도 $\frac{1}{2}$만큼 변한 것이다.

 

따라서 현재해가 최적해가 유지될 조건은 최종 테이블에서 비기저변수인 $x_4, x_5$가 모두 0 이상일 조건이 된다. 그런데 이때 $S^{*}$의 세번째 열의 요소 중 두번째 값은 0이므로 $x_5$의 계수 변화는 없기 때문에 고려할 필요가 없다. 따라서 $x_4$에 대해서만 조건식을 세우면, 

$$\frac{3}{2} + \frac{1}{2} \Delta c_2 \geq 0$$ 

이므로 $\Delta c_2 \geq -3$이라는 결과가 나온다. 따라서 원래 목적함수 계수가 5이므로 현재해가 최적해로 유지되도록 하는 $c_2$의 최솟값이 2라는 결론을 낼 수 있다.

 

마지막으로 $c_2$가 변함에 따라 목적함수 값이 어떻게 변하는지를 살펴보도록 하자. 위에서 $y^{*} = \begin{bmatrix}
0 & 1 & 1\\
\end{bmatrix}$임을 확인하였다.

 

$Z^{*} = y^{*}b$에 대입하면

$$Z^{*} = \begin{bmatrix}
0 & 1 & 1\\
\end{bmatrix}\begin{bmatrix}
4 \\
12 \\
18
\end{bmatrix} = 30$$

의 결과가 나온다. 원래 값이었던 36보다 6만큼 감소한 값이다. -6이라는 변화량이 어떻게 나왔는지 한 번 살펴보자. 위 수식에서 변한 요소를 살펴보면 $y^{*}$의 두 번째 요소밖에 없다. y^{*}에 대한 변화량은 $S^{*}_{22} = \frac{1}{2}$ 임을 이미 확인하였다. 따라서 이 값은 $b$에서 두 번째 우변상수인 12에 곱해져서 계산되므로 

$$36 + b_2 S^{*}_{22} \Delta c_2 = 36 + 12 \times \frac{1}{2} \times (-1) =  30$$

이 됨을 알 수 있다. 

 

<목적함수 계수에 대한 민감도 분석>

 

지금까지가 심플렉스 테이블의 구조를 활용하여 민감도 분석을 하는 방법이었다. 이처럼 테이블의 구조를 이용하면 위 예제보다 더 복잡한 문제에 대해서도 효율적으로 최적해와 목적함수 값의 변화를 계산할 수 있다는 장점이 있다.