📂최적화이론

선형 계획 문제의 기저가용해

정의 ¹

$$ \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}$ 에 대해 선형계획문제가 위와 같이 방정식 폼으로 나타난다고 할 때, 그 가용해 $\mathbf{x} \in \mathbb{R}^{n}$ 에 대해 기수가 $m$ 인 집합 $B \subseteq [n]$ 이 존재해서 다음 두 조건을 만족시키면 $\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ 를 기저가용해^{basic Feasible solution}라 한다.

• (i): $\exists A_{B}^{-1}$
• (ii): $x_{j} = 0 \forall j \notin B$

이 때 $x_{j}$ 를 기저변수^{basic variable}, 집합 $B$ 를 기저^basis라 부른다. 기저가용해인 가용해는 형용사형을 사용해 가용해가 베이직^basic하다고 말할 수 있다.

---

• $\mathbf{c}^{T}$ 는 전치를 의미한다.
• [가용해]란 최적화와 관계 없이 일단 제약 조건을 만족시키는 해를 말한다.
• $[n] = \left\{ 1, \cdots , n \right\}$ 은 $1$ 부터 $n$ 까지의 자연수의 집합이다.
• $A_{B}$ 는 행렬 $A$ 에서 집합 $B$ 에 나열된 열만을 취한 정방행렬이다.

설명

정의에 말이 좀 길어서 어려워보이는데 사실 별것 아니니 겁먹지 말자.

기저가용해는 뭐가 어찌되든 가용해에 대한 논의일 뿐이니 $\mathbf{c} \in \mathbb{R}^{n}$ 는 전혀 신경쓰지 않는다.

예시

$$ \begin{align*} A =& \begin{bmatrix} 1 & 5 & 3 & 4 & 6 \\ 0 & 1 & 3 & 5 & 6 \end{bmatrix} \\ \mathbf{b} =& \begin{bmatrix} 14 \\ 7 \end{bmatrix} \end{align*} $$ 이라고 할 때, $\mathbf{x} = (0,2,0,1,0)$ 은 방정식 폼에서 두 제약 $$ \begin{align*} 1 x_{1} + 5 x_{2} + 3 x_{3} + 4 x_{4} + 6 x_{5} =& 14 \\ 0 x_{1} + 1 x_{2} + 3 x_{3} + 5 x_{4} + 6 x_{5} =& 7 \end{align*} $$ 을 만족시키는 가용해다. 여기서 $\mathbf{x}$ 의 성분으로는 $x_{2}, x_{4}$ 만이 사용되었고^{조건 (ii)}, $B = \left\{ 2, 4 \right\}$ 에 대해 $$ A_{B} = \begin{bmatrix} 5 & 4 \\ 1 & 5 \end{bmatrix} $$ 가 넌싱귤러^nonsingular하므로^{조건 (i)} 가용해 $\mathbf{x}$ 는 기저가용해다.

기하적 설명

$A \in \mathbb{R}^{1 \times 3}$ 인 경우, 그러니까 제약이 $m=1$ 개고 해공간의 차원이 $n = 3$ 인 선형 계획 문제를 생각해보자.

탁 깨놓고 말해서 기저가용해란 위 그림의 삼각뿔에서 $\mathbf{0}$ 이 아닌 꼭짓점^vertex들을 말한다. 물론 지금은 최적해가 아닌 가용해만 고려하고 있긴한데, 상식적으로 생각해봐도 설마 최적해가 뜬금없이 모서리^edge 한 가운데에 있겠는가? 목적 함수가 비선형으로 휘어있는 것도 아니니 최적해가 존재한다면 저 셋 중에 있을 것이고, 이를 추상화하고 일반화한 것이 바로 기저가용해의 개념이다.

한편 이 해공간은 다름아닌 심플렉스고, 여기에서 심플렉스 메소드의 아이디어로 이어지게 된다.

대수적 설명

$A_{B} \in \mathbb{R}^{m \times m}$ 의 역행렬 $A_{B}^{-1}$ 이 존재한다는 것은 정방행렬 $A_{B}$ 의 열벡터들이 선형독립이라는 것이고, 이는 $n$ 가지의 모든 변수가 아닌 정확히 필요한 $m \le n$ 가지의 변수만을 생각해도 충분하다는 것이다. 위 단락에서 기하적으로 보았을 때 세 꼭짓점을 표현하기 위해 각각 단 하나의 차원만을 필요했던 것을 생각해보면 그 의미가 딱 맞아 떨어진다.