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

지금까지 심플렉스 방법을 소개하면서 대수적 형태와 표의 형태로 설명하였다. 심플렉스 방법을 행렬형으로 검토하면 더 깊은 통찰을 얻을 수 있다. 다음은 앞서 다뤘던 예제 문제이다.

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

 

이 표준형 예제를 행렬형으로 표기하면 다음과 같다.

\[
\begin{aligned}
\text{Maximize} \quad & Z = cx \\
\text{Subject to} \quad & Ax \leq b \\
                        & x \geq 0
\end{aligned}
\]

 

여기서 c는 $[c_1, c_2, \cdots, c_n]$ 와 같은 행벡터이고,

$x, b, 0$은 다음과 같은 열벡터이고,

\[
x = \begin{bmatrix}
 x_1\\
 x_2\\
 \vdots \\
 x_n \\
\end{bmatrix}, \quad
b = \begin{bmatrix}
 b_1\\
 b_2\\
 \vdots \\
 b_m \\
\end{bmatrix}, \quad
0 = \begin{bmatrix}
 0\\
 0\\
 \vdots \\
 0 \\
\end{bmatrix}
\]

 

A는 다음과 같은 행렬이다.

 \begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots &  & \vdots  \\
a_{m1} & a_{m2} & \cdots & a_{mn} \\
\end{bmatrix}

 

여기에 확장형 모형에 사용되는 여유변수의 열벡터를 도입한다.

\[
x_s = \begin{bmatrix}
 x_{n+1}\\
 x_{n+2}\\
 \vdots \\
 x_{n+m} \\
\end{bmatrix}
\]

 

그러면 제약식들은 다음과 같이 된다.

$$[A, I] \begin{bmatrix}
x \\
x_s
\end{bmatrix}$$

 

이때 다음 벡터 $ \begin{bmatrix}
x \\
x_s
\end{bmatrix}$중에서 $n$개의 비기저변수들은 0으로 놓는다.

이런 $n$개의 변수들을 0으로 고정하여 제거함으로서 $m$개의 미지수들과 $m$개의 등식들을 가진 집합이 남는다. 이는 다음과 같이 표현된다.

$$Bx_B = b$$

여기서 $x_B$는 기저변수들로 이루어진 열벡터이고, \[
\begin{bmatrix}
x \\
x_s
\end{bmatrix}
\]
 벡터의 비기저변수를 제거함으로써 얻을 수 있다. 

 

다음으로, 기저행렬 $B$는

\begin{bmatrix}
B_{11} & B_{12} & \cdots & B_{1m}\\
B_{21} & B_{22} & \cdots & B_{2m} \\
\vdots & \vdots &  & \vdots  \\
B_{m1} & B_{m2} & \cdots & B_{mm} \\
\end{bmatrix}

이며, $[A,  I]$의 비기저변수들의 계수에 해당하는 열들을 제거함으로써 얻을 수 있다. 기저행렬 $B$는 심플렉스 반복 단계마다 기저변수가 테이블 상에 놓이는 순서가 바뀌므로 $B$들의 열의 순서는 그에 맞춰서 매번 다른 순서로 구성이 될 것이다.

 

심플렉스 방법이 해를 갖는 전제조건은 $B$가 가역일 때다. 따라서 $B^{-1}$은 항상 존재한다. 그러므로 $Bx_B = b$를 풀면,

$$x_B = B^{-1}b$$로 풀 수 있다. 

또한, $c_B$를 $x_B$의 해당요소들에 대해 그 요소가 목적함수계수들인 벡터를 나타낸다. 그러면 기저해에 대한 목적함수 값은 다음과 같다.

$$Z = c_Bx_B = c_BB^{-1}b$$

 

이제 위 예제를 행렬 문제로 나타내보자. 이 경우,

\[
c = \begin{bmatrix}
3 & 5
\end{bmatrix}, \quad

[A,  I] = \begin{bmatrix}
1 & 0 & 1 & 0 & 0 \\
0 & 2 & 0 & 1 & 0 \\
3 & 2 & 0 & 0 & 1
\end{bmatrix}, \quad

b = \begin{bmatrix}
4 \\
12 \\
18
\end{bmatrix}
\]

\[
x = \begin{bmatrix}
x_1 \\
x_2
\end{bmatrix}, \quad

x_s = \begin{bmatrix}
x_3 \\
x_4 \\
x_5
\end{bmatrix}
\]

 

[반복 0] : 기저변수 : $[x_3, x_4, x_5]$

\[
x_B = \begin{bmatrix}
x_3 \\
x_4 \\
x_5
\end{bmatrix}, \quad

B = \begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix} = B^{-1}
\]

$$x_B = \begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix} \begin{bmatrix}
4 \\
12 \\
18
\end{bmatrix} = \begin{bmatrix}
4 \\
12 \\
18
\end{bmatrix}$$

 

$$c_B = \begin{bmatrix}
0 & 0 &0  \\
\end{bmatrix}, \quad Z = \begin{bmatrix}
0 & 0 &0  \\
\end{bmatrix} \begin{bmatrix}
4 \\
12 \\
18
\end{bmatrix} = 0$$

 

[반복 1] : 기저변수 : $[x_3, x_2, x_5]$

\[
x_B = \begin{bmatrix}
x_3 \\
x_2 \\
x_5
\end{bmatrix}, \quad

B = \begin{bmatrix}
1 & 0 & 0 \\
0 & 2 & 0 \\
0 & 2 & 1
\end{bmatrix}, \quad

B^{-1} = \begin{bmatrix}
1 & 0 & 0 \\
0 & \frac{1}{2} & 0 \\
0 & -1 & 1
\end{bmatrix}
\]

\[
x_B = B^{-1} b = 
\begin{bmatrix}
1 & 0 & 0 \\
0 & \frac{1}{2} & 0 \\
0 & -1 & 1
\end{bmatrix}
\begin{bmatrix}
4 \\
12 \\
18
\end{bmatrix}
=
\begin{bmatrix}
4 \\
6 \\
6
\end{bmatrix}
\]

\[
c_B = \begin{bmatrix}
0 & 5 & 0
\end{bmatrix}, \quad
Z = c_B x_B = 
\begin{bmatrix}
0 & 5 & 0
\end{bmatrix}
\begin{bmatrix}
4 \\
6 \\
6
\end{bmatrix}
= 30
\]

 

[반복 2] : 기저변수 =  $[x_3, x_2, x_1]$

\[
x_B = \begin{bmatrix}
x_3 \\
x_2 \\
x_1
\end{bmatrix}, \quad

B = \begin{bmatrix}
1 & 0 & 1 \\
0 & 2 & 0 \\
0 & 2 & 3
\end{bmatrix}, \quad

B^{-1} = \begin{bmatrix}
1 & \frac{1}{3} & -\frac{1}{3} \\
0 & \frac{1}{2} & 0 \\
0 & -\frac{1}{3} & -\frac{1}{3}
\end{bmatrix}
\]

\[
x_B = B^{-1} 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 \\
12 \\
18
\end{bmatrix}
=
\begin{bmatrix}
2 \\
6 \\
2
\end{bmatrix}
\]

\[
c_B = \begin{bmatrix}
0 & 5 & 3
\end{bmatrix}, \quad
Z = c_B x_B = 
\begin{bmatrix}
0 & 5 & 3
\end{bmatrix}
\begin{bmatrix}
2 \\
6 \\
2
\end{bmatrix}
= 36
\]

 

현재 식들 집합 행렬형

심플렉스 방법의 행렬형의 초기 형태는 다음과 같다.

$$\begin{bmatrix}
1 & -c & 0 \\
0 & A & I  \\
\end{bmatrix}
\begin{bmatrix}
Z \\
x \\
x_s
\end{bmatrix} = \begin{bmatrix}
0 \\
b
\end{bmatrix}$$

 

이를 심플렉스 테이블에 표기하면 다음과 같다.

 

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

반복			기저변수	방정식	계수						우변
					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$

 

위의 테이블을 아래 예제 테이블에 대응시켜서 생각해보면 더 이해가 잘 될 것이다.

 

반복			기저변수	방정식	계수						우변
					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	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

 

 

이번에는 관련 예제 문제를 하나 살펴보자. 다음과 같이 어느 최대화 표준형 문제의 초기 테이블과 최종 테이블이 주어졌다고 하자.

 

반복			기저변수	방정식	계수						우변
					Z	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
0			$Z$	(0)	1	a	b	0	0	0	0
			$x_3$	(1)	0	0	0	1	0	0	4
			$x_4$	(2)	0	0	2	0	1	0	12
			$x_5$	(3)	0	5	2	0	0	1	18
최종			$Z$	(0)	1	0	0	0	4.1	0.4	c
			$x_3$	(1)	0	0	0	1	0	0	4
			$x_2$	(2)	0	0	1	0	0.5	0	6
			$x_1$	(3)	0	1	0	0	-0.2	0.2	1.2

 

심플렉스 테이블의 행렬형 구조를 이용해면 테이블의 역추적해서 위 a,b,c,d,e에 들어갈 값을 찾아낼 수 있다. 

 

1) 우선 원문제의 목적함수의 계수에 해당하는 값인 a,b를 구해보자.

 

최종 테이블의 기저변수를 보면 $x_B = \begin{bmatrix}
x_3 & x_2  &  x_1 \\
\end{bmatrix}$ 임을 알 수 있다.

 

따라서 $c_B$는 $x_B$에 해당하는 요소들의 목적함수 계수로 구성된 벡터이므로

$c_B =\begin{bmatrix}
0 & -b & -a \\
\end{bmatrix}$ 임을 알 수 있다. (초기 테이블의 $x_3, x_2, x_1$에서 $Z$행에 대응되는 값)

 

그런데, 테이블의 행렬 구조를 살펴보면 최종 테이블에서 $c_BB^{-1} = \begin{bmatrix}
0 & 4.1 & 0.4 \\
\end{bmatrix} $로 주어졌음이 확인된다. 

 

따라서 $c_BB^{-1}B = c_B$를 이용하면 $c_B$를 구할 수 있을 것이다. 그렇다면 이제 남은 $B$를 찾는 것이다. $B$는 기저행렬이므로 초기 테이블에서 $x_B$의 순서에 따라 순서대로 열을 구성하면 된다. 초기 테이블을 보면 $x_3$, $x_2, x_1$에 해당하는 열벡터가 각각 \[
\begin{array}{ccc}
\begin{bmatrix}
1 \\
0 \\
0
\end{bmatrix}
&
\begin{bmatrix}
0 \\
2 \\
2
\end{bmatrix}
&
\begin{bmatrix}
0 \\
0 \\
5
\end{bmatrix}
\end{array}
\] 이므로 $B = \begin{bmatrix}
1 & 0 & 0 \\
0 & 2 & 0 \\
0 & 2 & 5 \\
\end{bmatrix}$로 나타내진다.

 

\[ ∴ 
c_B = c_B B^{-1} B = 
\begin{bmatrix}
0 & 4.1 & 0.4
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 2 & 0 \\
0 & 2 & 5
\end{bmatrix}
= 
\begin{bmatrix}
0 & 9 & 2
\end{bmatrix}
\]

 

2) 이제는 최종 테이블에서의 목적함수 값인 $c$를 구해보자. 

최종 테이블에서 $c = c_BB^{-1}b$로 표현된다. 우리는 이미\[
c_B B^{-1} =
\begin{bmatrix}
0 & 4.1 & 0.4
\end{bmatrix}
\]
 임을 알고 있다. 따라서 b만 알면 되는데 이는 초기 테이블에서 우변상수에 해당하는 벡터이다. 따라서 둘을 단순히 곱해주면 그만이다.

 

\[ ∴ 
c = c_B B^{-1}b = 
\begin{bmatrix}
0 & 4.1 & 0.4
\end{bmatrix}
\begin{bmatrix}
4 \\
12 \\
18
\end{bmatrix}
= 
0 \times 4 + 4.1 \times 12 + 0.4 \times 18 = 56.4
\] 로 구해진다.

 

또 하나의 방법은 행렬은 결합법칙이 성립하므로 \[
c = (c_B B^{-1})b = c_B (B^{-1}b) \] 로도 구할 수 있다. 1)에서 $c_B$를 구했고 "<심플렉스 테이블의 행렬형 구조>"로 돌아가보면 $ B^{-1}b$는 임의의 반복 단계 테이블에서 우변상수 벡터임을 확인할 수 있다. 따라서 

\[
\therefore\ 
c = 
\begin{bmatrix}
0 & 9 & 2
\end{bmatrix}
\begin{bmatrix}
4 \\
6 \\
1.2
\end{bmatrix}
=
0 \times 4 + 9 \times 6 + 2 \times 1.2 = 56.4
\]
로 동일하게 구해짐이 확인된다.

 

추가로 몇 가지 더 특징들을 발견할 수 있는데, 행렬 $B$의 역행렬을 취하면  \[
\begin{bmatrix}
1 & 0 & 0 \\
0 & 0.5 & 0 \\
0 & -0.2 & 0.2
\end{bmatrix}
\]
로써 구해지는데, 이는 최종 테이블에서 여유변수 열에 해당하는 열벡터들로 이루어진 행렬로써 존재함을 볼 수 있다. 이렇듯 특정 반복단계 (반복 $i$)에서의 기저변수에 해당하는 기저행렬의 역행렬은 $i$번째 테이블에서, 여유변수 열에 해당하는 부분의 행렬임을 알 수 있다. (테이블에서 파란색으로 표시하였다) 따라서 $B$와 $B^{-1}$중 하나를 모르더라도 테이블에서 바로 해당 부분을 찾아 계산할 수도 있다는 것이다. 

 

또한, $B^{-1}$와 제약식들의 계수로 이루어진 행렬인 $A$를 곱하면 $B^{-1}A$로 나타낼 수 있고, 이는 "<심플렉스 테이블의 행렬형 구조>"에서 원 변수 (결정변수) 열에 해당하는 부분의 행렬로 구해짐을 알 수 있다. (테이블에서 붉은색으로 표시하였다)

실제로 $B^{-1}A$를 계산해보면 \[
\begin{bmatrix}
0 & 0 \\
0 & 1 \\
1 & 0
\end{bmatrix}
\]이 나옴이 확인된다. 

 

마지막으로, 초기 테이블이 주어졌을 경우 특정 반복단계에서의 기저변수들이 무엇인지만 알면 최종 테이블을 바로 구할 수 있는데, 바로 초기 테이블에 \[
\begin{bmatrix}
1 & \begin{bmatrix} c_BB^{-1} \end{bmatrix} \\
0 & \begin{bmatrix} B^{-1} \end{bmatrix}
\end{bmatrix}
\]을 곱해주는 것이다. 

 

1), 2)에서 보였듯이, $c_B$와 $B$ 모두 $x_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]
\]

 

 

이상으로 심플렉스 테이블을 행렬형으로 일반화시키는 내용이었다. 이와 같은 방법은 실제로 계산의 효율을 상당히 늘릴 수 있다. 각 단계의 해를 구하기 위해 불필요한 반복 작업을 생략해도 되기 때문이다. 이 방법은 따라서 앞선 포스팅에서 다룬 사후 분석이나 민감도 분석에 유용하게 사용된다. 이전 포스팅에서 민감도 분석은 그래프를 이용하였는데, 이 방법은 결정변수가 2개 이하일 때만 유용하다는 한계가 있다. 하지만 심플렉스 테이블을 이용하면 변수가 많은 상황에서도 효율적인 민감도 분석을 할 수 있다. 

 

이 부분은 이후 포스팅에서 다루도록 하겠다.