📂최적화이론

기저가용해의 유일성 증명

정리 ¹

$$\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}$ 에 대해 선형계획문제가 위와 같이 방정식 폼으로 나타난다고 할 때, 그 기저가용해는 기저 $B$ 에 따라 유일하게 결정된다.

---

• $\mathbf{c}^{T}$ 는 전치를 의미한다.
• 가용해란 최적화와 관계 없이 일단 제약 조건을 만족시키는 해를 말한다.
• $[n] = \left\{ 1, \cdots , n \right\}$ 은 $1$ 부터 $n$ 까지의 자연수의 집합이다.
• $A_{B}$ 는 행렬 $A$ 에서 집합 $B$ 에 나열된 열만을 취한 정방행렬이다.
• 가용해 $\mathbf{x} \in \mathbb{R}^{n}$ 에 대해 기수가 $m$ 인 집합 $B \subseteq [n]$ 이 존재해서 $\exists A_{B}^{-1}$ 이고 $x_{j} = 0 \forall j \notin B$ 인 $\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ 를 기저가용해라 한다. 이 집합 $B$ 를 기저라 부른다.

증명

가용해의 정의에 따라 $\mathbf{x}$ 에 대해 $A \mathbf{x} = \mathbf{b}$ 은 만족한다고 하자. 여기서 기저가 아닌 인덱스의 집합 $N := [n] \setminus B$ 을 정의함으로써 $A \mathbf{x}$ 를 다음과 같이 나타낼 수 있다. $$A \mathbf{x} = A_{B} \mathbf{x}_{B} + A_{N} \mathbf{x}_{N}$$ 기저 $B$ 의 조건 (ii)에 따라 $\mathbf{x}_{N}$ 의 모든 성분은 $0$ 이고, $\mathbf{x}_{N} = \mathbf{0}_{n-m}$ 이 되어 $$\mathbf{b} = A \mathbf{x} = A_{B} \mathbf{x}_{B}$$ 이다. 벡터 $\mathbf{x}_{B}$ 는 $A_{B} \mathbf{x}_{B} = \mathbf{b}$ 를 만족시키는데, 기저 $B$ 의 조건 (i)에서 $A_{B}^{-1}$ 가 존재하므로 방정식 $A_{B} \mathbf{x}_{B} = \mathbf{b}$ 는 유일한 해만을 가진다.

• 만약 그 유일한 해의 모든 성분이 $0$ 보다 크거나 같다면 $B$ 에 따른 정확히 하나의 기저가용해를 가진 것이다.
• 그 외의 경우, 그 해는 $\mathbf{x} \ge 0$ 를 만족하지 못한다.

결론적으로, 주어진 선형계획문제와 기저 $B$ 에 따른 기저가용해는 존재하지 않거나 존재하더라도 하나의 유일한 해만을 가진다.

설명

정리에서 기저는 하나의 기저가용해만을 결정하는 것을 확인했지만, 하나의 기저가용해는 여러가지 다른 기저에서 각각 얻을 수도 있다.

같이보기

선형계획법의 기본정리

이 정리는 선형계획법의 기본정리 증명에 사용된다.