기저 해와 극점 - 실험 도서관

선형계획법의 기본 개념

선형계획법에서 "기저 해"와 "극점"은 매우 중요한 개념이다. 이는 선형계획 문제의 해를 찾는 과정에서 반드시 다루어야 할 수학적 구조와 연관되어 있다.

기저 해

기저 해는 주어진 선형계획 문제에서 가능한 해의 일종으로, 일반적으로 다음과 같은 수학적 정의를 따른다.

선형계획 문제는 다음과 같이 일반적인 형태로 표현될 수 있다.

$\text{maximize} \quad \mathbf{c}^\top \mathbf{x}$

$\text{subject to} \quad \mathbf{A} \mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq 0$

여기서:

$\mathbf{A} \in \mathbb{R}^{m \times n}$ : 제약 조건을 나타내는 행렬
$\mathbf{b} \in \mathbb{R}^m$ : 제약 조건의 상수 벡터
$\mathbf{c} \in \mathbb{R}^n$ : 목적 함수의 계수 벡터
$\mathbf{x} \in \mathbb{R}^n$ : 변수 벡터

기저 해는 $\mathbf{A} \mathbf{x} = \mathbf{b}$ 라는 제약 조건을 만족시키는 해 중에서 $n$ 개의 변수 중 최대 $m$ 개의 변수를 선택하여 $\mathbf{x}$ 의 값을 결정하는 방식이다. 이때 선택되지 않은 나머지 변수는 0이 된다. 이를 기저 변수라 하며, 그 수는 문제의 구조에 따라 다를 수 있다.

기저 행렬

선형계획 문제에서 기저 해를 구하려면, 행렬 $\mathbf{A}$ 에서 $m \times m$ 크기의 부분 행렬을 선택해야 한다. 이 행렬을 기저 행렬이라고 하며, 이를 통해 기저 해를 계산할 수 있다. 기저 행렬은 풀랭크(Full Rank)이어야 한다. 즉, 이 행렬은 역행렬이 존재해야 한다.

기저 행렬을 $\mathbf{B}$ 라고 하면, 기저 해는 다음과 같이 주어진다:

$\mathbf{x}_B = \mathbf{B}^{-1} \mathbf{b}$

여기서:

$\mathbf{x}_B$ : 기저 변수 벡터
$\mathbf{B}^{-1}$ : 기저 행렬의 역행렬

기저 행렬 $\mathbf{B}$ 가 풀랭크이고 $\mathbf{B}^{-1}\mathbf{b} \geq 0$ 을 만족할 때, 기저 해는 유효하다(feasible)고 할 수 있다.

극점

극점은 기저 해와 밀접한 관련이 있다. 선형계획 문제의 해 공간에서, 기저 해는 일반적으로 해 공간의 극점에 해당한다. 극점은 선형계획 문제의 제약 조건을 만족시키는 모든 가능한 해 중에서, 목적 함수가 최댓값을 가질 수 있는 위치를 의미한다.

기하학적으로, 극점은 다면체(polytopes)의 꼭짓점에 해당한다. 이는 선형계획 문제의 제약 조건을 다면체 형태로 표현할 때, 기저 해가 그 다면체의 꼭짓점 중 하나에 대응된다는 것을 의미한다. Simplex 알고리즘은 이러한 극점을 탐색하며 최적 해를 찾는 방법이다.

해의 기본 구조

기저 해는 보통 $n$ 차원의 공간에서 $m$ 개의 제약 조건을 만족하는 해 중에서, 적어도 $n - m$ 개의 변수가 0이 되는 해를 의미한다. 이를 통해 최적 해를 찾는 과정에서 불필요한 변수를 제거하거나 특정 변수의 값을 고정함으로써 계산량을 줄일 수 있다.

기저 해가 존재하지 않거나 불능(unbounded)한 경우도 있으며, 이는 문제의 특성에 따라 다르다. 이 경우에는 특별한 처리를 통해 문제를 해결해야 한다.

기저 해의 성질

기저 해는 다음과 같은 몇 가지 중요한 성질을 가지고 있다.

기저 해의 유일성: 특정한 선형계획 문제에서 기저 해는 항상 유일하지 않을 수 있다. 하나 이상의 기저 해가 존재할 수 있으며, 이러한 기저 해들은 다면체의 서로 다른 극점에 해당한다. 다만, 목적 함수가 특정 방향으로 단조롭게 증가하는 경우에는 최적 기저 해는 하나로 결정될 수 있다.
해의 기본 성질: 기저 해는 선형계획 문제의 제약 조건을 만족하는 최소 개수의 변수 집합으로 이루어진다. 이를 통해 계산 복잡성을 줄이고 해를 보다 효율적으로 찾을 수 있다.
기저 해와 최적 해: 모든 최적 해가 기저 해는 아니지만, 모든 기저 해는 반드시 어떤 극점에 대응되므로 최적 해에 도달할 가능성이 높다. 이는 Simplex 알고리즘이 기저 해에서 시작하여 기저 해를 이동하면서 최적 해를 찾는 원리와도 일치한다.
선형 독립성: 기저 행렬 $\mathbf{B}$ 는 풀랭크(Full Rank)를 가져야 하므로, 선택된 $m$ 개의 변수는 선형 독립성을 가져야 한다. 이를 만족하지 않으면 기저 해가 될 수 없고, 역행렬을 계산할 수 없게 된다.
기저 해의 유효성 (Feasibility): 기저 해는 $\mathbf{A} \mathbf{x} = \mathbf{b}$ 를 만족시키며, $\mathbf{x} \geq 0$ 조건을 만족해야 한다. 기저 해가 이러한 조건을 만족하지 않으면 유효하지 않은 해로 간주된다.

기저 해 구하는 과정

기저 해를 구하기 위해서는 선형계획 문제의 제약 조건 행렬 $\mathbf{A}$ 에서 풀랭크를 가지는 $m \times m$ 부분 행렬 $\mathbf{B}$ 를 선택하여 그 해를 계산한다. 이를 단계별로 요약하면 다음과 같다.

제약 조건 행렬 $\mathbf{A}$ 에서 $m$ 개의 열을 선택하여 $m \times m$ 행렬 $\mathbf{B}$ 를 구성한다.
선택된 열에 대응하는 변수들을 기저 변수로 설정하고, 나머지 변수들을 비기저 변수로 설정한다.
$\mathbf{B}^{-1} \mathbf{b}$ 를 계산하여 기저 변수의 값을 구한다.
구한 기저 변수가 $\mathbf{x} \geq 0$ 조건을 만족하는지 확인한다. 만족하지 않으면 다른 열을 선택하여 과정을 반복한다.

예시

제약 조건이 다음과 같은 선형계획 문제를 고려해 보자:

$\mathbf{A} = \begin{pmatrix} 1 & 2 & 1 \\ 2 & 1 & 0 \end{pmatrix}, \quad \mathbf{b} = \begin{pmatrix} 4 \\ 3 \end{pmatrix}$

이 문제에서 $\mathbf{A}$ 의 일부 열을 선택하여 기저 행렬 $\mathbf{B}$ 를 구성한다. 예를 들어, 첫 번째와 두 번째 열을 선택하면 기저 행렬은 다음과 같이 된다:

$\mathbf{B} = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$

기저 행렬 $\mathbf{B}$ 의 역행렬을 구한 후, 기저 해는 다음과 같이 계산된다:

$\mathbf{x}_B = \mathbf{B}^{-1} \mathbf{b}$

역행렬 $\mathbf{B}^{-1}$ 을 계산하면:

$\mathbf{B}^{-1} = \begin{pmatrix} -1 & 2 \\ 2 & -1 \end{pmatrix}$

따라서 기저 해는:

$\mathbf{x}_B = \begin{pmatrix} -1 & 2 \\ 2 & -1 \end{pmatrix} \begin{pmatrix} 4 \\ 3 \end{pmatrix} = \begin{pmatrix} 2 \\ 5 \end{pmatrix}$

이 경우 $\mathbf{x}_B \geq 0$ 조건을 만족하므로, 이 기저 해는 유효하다.

기저 해의 기하학적 의미

기저 해는 기하학적으로 다면체의 꼭짓점에 해당한다. 선형계획 문제의 해 공간은 다면체 형태로 나타나며, 기저 해는 이 다면체의 극점, 즉 꼭짓점에서 나타난다. 기저 해가 존재한다면, 이는 다면체의 하나의 꼭짓점에서 발생한다.

다면체와 기저 해의 관계

다면체는 선형계획 문제의 제약 조건에 의해 형성되는 해 공간으로, 각 제약 조건은 다면체의 면을 나타낸다. 기저 해는 다음과 같은 조건을 만족하는 경우 다면체의 꼭짓점에서 위치한다:

차원: 기저 해는 $n$ -차원 공간에서 $m$ 개의 제약 조건을 만족해야 한다. 즉, 다면체의 각 면은 하나의 제약 조건에 의해 형성된다.
극점: 다면체의 극점은 기저 해가 위치할 수 있는 위치로, 이는 Simplex 알고리즘이 극점을 탐색하며 최적 해를 찾는 원리와 밀접하게 연관된다.

다음 그림은 다면체의 꼭짓점을 기저 해로 나타낸다.

graph LR A[기저 해 1] --> B[기저 해 2] B --> C[기저 해 3] B --> D[기저 해 4] C --> E[기저 해 5] D --> F[기저 해 6]

Simplex 알고리즘과 기저 해

Simplex 알고리즘은 기저 해에서 시작하여 다른 기저 해로 이동하면서 최적 해를 찾아가는 방식으로 작동한다. 기저 해가 다면체의 꼭짓점에 위치하므로, Simplex 알고리즘은 이러한 극점을 따라 이동하며 해를 구한다.

이 과정에서 다음과 같은 절차가 반복된다:

기저 해를 선택하여 이를 현재 해로 설정한다.
목적 함수의 값을 개선할 수 있는 다른 기저 해로 이동한다.
이동이 더 이상 불가능할 때, 최적 해에 도달하게 된다.

기저 해와 비기저 해

기저 해와 달리, 비기저 해는 $\mathbf{A} \mathbf{x} = \mathbf{b}$ 조건을 만족하지 않는 해이다. 비기저 해는 일반적으로 중간 과정에서 발생하는 해로, 최종적으로 기저 해에 도달해야 문제를 해결할 수 있다. 기저 해는 항상 제약 조건을 만족하며, 이 과정에서 비기저 해를 거치지 않도록 하는 것이 목표이다.

기저 해의 계산 사례

이제 기저 해의 계산을 실제로 다뤄 보자. 예를 들어, 다음과 같은 선형계획 문제를 생각해 보자:

$\text{maximize} \quad 3x_1 + 5x_2$

$\text{subject to} \quad \begin{aligned} x_1 + 2x_2 &\leq 6 \\ 4x_1 + x_2 &\leq 8 \\ x_1, x_2 &\geq 0 \end{aligned}$

이 문제에서 제약 조건을 만족시키는 기저 해를 구하는 과정은 다음과 같다:

제약 조건을 등식으로 변환:

$x_1 + 2x_2 = 6 \quad (슬랙 변수 도입)$

$4x_1 + x_2 = 8$

기저 행렬 $\mathbf{B}$ 를 선택:

$\mathbf{B} = \begin{pmatrix} 1 & 2 \\ 4 & 1 \end{pmatrix}$

이 경우, 기저 행렬의 역행렬을 계산하여 기저 해를 구할 수 있다.

계산 과정을 계속 진행하면 기저 해의 위치와 값을 확인할 수 있으며, 이러한 기저 해는 다면체의 꼭짓점에서 발생한다.

기저 해 계산 과정의 자세한 설명

이제 앞서 설명한 문제의 기저 해 계산 과정을 자세히 살펴보자.

문제 재구성

주어진 선형계획 문제를 다시 한 번 정리해 보자:

$\text{maximize} \quad 3x_1 + 5x_2$

$\text{subject to} \quad \begin{aligned} x_1 + 2x_2 &\leq 6 \\ 4x_1 + x_2 &\leq 8 \\ x_1, x_2 &\geq 0 \end{aligned}$

이 문제를 표준형으로 변환하기 위해, 각 제약 조건에 슬랙 변수를 도입하여 등식 형태로 바꾸어 준다:

$\begin{aligned} x_1 + 2x_2 + s_1 &= 6 \\ 4x_1 + x_2 + s_2 &= 8 \end{aligned}$

여기서 $s_1$ 과 $s_2$ 는 슬랙 변수로, 각각 첫 번째와 두 번째 제약 조건의 남는 여유를 나타낸다.

따라서, 이제 새로운 선형계획 문제는 다음과 같다:

$\text{maximize} \quad 3x_1 + 5x_2$

$\text{subject to} \quad \begin{aligned} x_1 + 2x_2 + s_1 &= 6 \\ 4x_1 + x_2 + s_2 &= 8 \\ x_1, x_2, s_1, s_2 &\geq 0 \end{aligned}$

기저 변수와 비기저 변수 선택

이 문제에서 기저 변수는 $x_1$ , $x_2$ , $s_1$ , $s_2$ 중에서 두 개를 선택해야 한다. 일반적으로, 변수 중에서 슬랙 변수를 기저 변수로 먼저 선택하고, 나머지 변수를 비기저 변수로 두는 방식으로 초기 기저 해를 구할 수 있다.

여기서 $s_1$ 과 $s_2$ 를 기저 변수로 선택하면, 기저 행렬 $\mathbf{B}$ 는 다음과 같이 구성된다:

$\mathbf{B} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$

기저 변수인 $s_1$ 과 $s_2$ 의 값을 계산하면 다음과 같다:

$s_1 = 6 - (x_1 + 2x_2), \quad s_2 = 8 - (4x_1 + x_2)$

비기저 변수의 값 결정

처음에는 $x_1 = 0$ 과 $x_2 = 0$ 으로 설정할 수 있다. 그러면 $s_1 = 6$ , $s_2 = 8$ 이 되어, 이 초기 기저 해는 유효하다. 이 상태에서 Simplex 알고리즘은 목적 함수를 개선하기 위해 다른 기저 해로 이동하는 과정을 수행한다.

기저 해 이동

기저 해는 Simplex 알고리즘에 의해 다면체의 한 꼭짓점에서 다른 꼭짓점으로 이동하면서 최적 해를 찾아가게 된다. 각 단계에서 기저 변수를 교체하여 새로운 기저 해를 계산하고, 이때 목적 함수의 값이 개선되는지 확인한다.

현재 기저 해는 $(x_1 = 0, x_2 = 0, s_1 = 6, s_2 = 8)$ 인데, 이 상태에서 $x_1$ 또는 $x_2$ 를 기저 변수로 교체하여 목적 함수 $3x_1 + 5x_2$ 를 증가시킬 수 있다. 이를 위해 다음 단계를 진행하게 된다.

Simplex 알고리즘의 기저 해 갱신

이 과정을 반복하면서 새로운 기저 해를 구하고, 최적 해에 도달하게 된다. Simplex 알고리즘은 각 기저 해에서 다음 기저 해로 이동할 때, 목적 함수의 값을 증가시키는 방향으로 이동한다. 이렇게 최종적으로 최적 기저 해에 도달하면, 그 해는 선형계획 문제의 최적 해가 된다.

기저 해의 이동 과정을 요약하면 다음과 같다:

현재 기저 해에서 목적 함수를 개선할 수 있는 변수(즉, 비기저 변수)를 선택한다.
선택된 변수를 기저 변수로 교체하고, 새로운 기저 해를 계산한다.
새로운 기저 해가 유효한지 확인하고, 유효하다면 목적 함수 값을 계산하여 개선 여부를 확인한다.
목적 함수 값이 더 이상 개선되지 않으면, 최적 해에 도달한 것으로 간주한다.

이로써 기저 해와 극점의 기하학적 관계, 기저 해의 구하는 과정, 그리고 Simplex 알고리즘의 기저 해 갱신 과정을 모두 살펴보았다.