선형계획법에서의 딕셔너리와 태블로
노테이션
$$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$
행렬 $A \in \mathbb{R}^{m \times n}$ 과 $\mathbf{b} \in \mathbb{R}^{m \times 1}$ 와 $\mathbf{c} \in \mathbb{R}^{n}$ 에 대해 선형계획문제가 위와 같이 방정식 폼으로 나타난다고 하고, 그 성분들을 다음과 같이 적도록 하자. $$ \begin{align*} A =& \left( a_{ij} \right) \\ \mathbf{b} =& \left( b_{1} , \cdots , b_{m} \right) \\ \mathbf{c} =& \left( c_{1} , \cdots , c_{n} \right) \\ \mathbf{x} =& \left( x_{1} , \cdots , x_{n} \right) \end{align*} $$
딕셔너리 1
$i = 1 , \cdots , m$ 에 대해서 다음과 같은 꼴의 연립방정식을 딕셔너리dictionary라 한다. $$ \begin{align*} \zeta &=& & & \sum_{j=1}^{n} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j=1}^{n} a_{ij} x_{j} \end{align*} $$
$\zeta$ 를 제외한 좌변의 변수들을 기저변수basic variable, 우변의 변수들을 비기저변수nonbasic variable라 한다. 일단 이들의 인덱스를 $$ \begin{align*} \mathcal{B} :=& \left\{ n+1 , n+2 , \cdots , n+m \right\} \\ \mathcal{N} :=& \left\{ 1 , 2 , \cdots , n \right\} \end{align*} $$ 와 같이 나타낸다. 다만 이는 가장 처음에 주어진 선형계획문제를 그대로 옮겨 쓴 것이고, 풀이가 진행됨에 따라 변하는 계수 위에 바bar를 두어서 다음과 같이 표현한다. $$ \begin{align*} \zeta &=& \bar{\zeta} &+& \sum_{j \in \mathcal{N}} \bar{c}_{j} x_{j} \\ x_{n+i} &=& \bar{b}_{i} &-& \sum_{j \in \mathcal{N}} \bar{a}_{ij} x_{j} \end{align*} $$ 여기서 $i \in \mathcal{B}$ 이며, 표기에도 알 수 있듯 $\mathcal{N}$ 과 $\mathcal{B}$ 은 고정된 집합들이 아니라 역시 풀이가 진행됨에 따라 변하게 된다.
태블로 2
가용 기저 $B$ 에 의해 결정되는 심플렉스 태블로tableau $\mathcal{T}(B)$ 란, 주어진 선형계획문제 $A \mathbf{x} = \mathbf{b}, z = \mathbf{c}^{T} \mathbf{x}$ 와 같은 해의 집합을 가지는 $m+1$차 연립선형방정식을 말한다. $N := \left\{ 1 , \cdots , n + m \right\} \setminus B$ 에 대해 $\mathbf{x}_{B}$ 를 기저변수들의 벡터, $\mathbf{x}_{N}$ 을 비기저변수들의 벡터라 하면 어떤 두 벡터 $\mathbf{p} \in \mathbb{R}^{m}$, $\mathbf{r} \in \mathbb{R}^{n-m}$ 와 행렬 $Q \in \mathbb{R}^{m \times (n-m)}$ 에 대해 다음과 같이 나타낸다. $$ \begin{align*} \mathbf{x}_{B} &=& \mathbf{p} &+& Q \mathbf{x}_{N} \\ z &=& z_{0} &+& \mathbf{r}^{T} \mathbf{x}_{N} \end{align*} $$
설명
까놓고 말해서 딕셔너리와 태블로는 같은 것이고, 인용을 보면 알 수 있듯 저자마다 선호하는 표현의 차이에 불과하다. 당연하지만 개념적으로 $B = \mathcal{B}$ 이며 $N = \mathcal{N}$ 이고, 그냥 변수를 그대로 썼느냐 행렬 표기를 썼느냐가 달라보일뿐이다.
포스팅을 위해 선형계획법의 많은 교재를 찾아보았지만 딕셔너리가 되었든 태블로가 되었든 이들에 대해 자세하게 설명하고 싶어하는 저자는 없었다. 애초에 ‘연립방정식’부터가 그렇지만, 고도의 추상화에 익숙해진 수학도들은 ‘다음과 같은 꼴’이나 ‘알고리즘에 따라 변하는’ 등의 모호한 표현에 대해 극도의 불안감, 혐오감을 느낀다. 그 심정은 이해하지만 저자들 역시 단지 노테이션에 목을 매기보다는 선형계획법 그 자체에 대한 논의로 빨리 넘어가고 싶어 보였고, 진정으로 선형계획법에 흥미를 가진다면 독자 역시 적당히 하고 넘어가길 추천한다.