단체법의 수리적 기초 - 소프트웨어 융합

1. 선형계획법의 표준형(Standard Form)

선형계획 문제는 다음과 같은 형태로 표현될 수 있다.

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

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

여기서, - $\mathbf{c} \in \mathbb{R}^n$ : 비용 벡터 (objective function의 계수) - $\mathbf{x} \in \mathbb{R}^n$ : 결정 변수 벡터 - $\mathbf{A} \in \mathbb{R}^{m \times n}$ : 제약식의 계수 행렬 - $\mathbf{b} \in \mathbb{R}^m$ : 제약식의 우변 값 벡터

이 문제는 목적 함수를 최대화하려는 문제이며, 제약 조건은 결정 변수 $\mathbf{x}$ 가 0 이상이어야 하고, 제약식 $\mathbf{A} \mathbf{x} = \mathbf{b}$ 을 만족해야 한다.

2. 기본 해(Basic Solution)

단체법의 핵심 아이디어는 선형계획 문제에서 가능한 해 중에서 기본 해(basic solution)를 탐색하는 것이다. 이를 위해서는 행렬 $\mathbf{A}$ 에서 $m$ 개의 선형 독립인 열을 선택하여 기저 행렬(basis matrix) $\mathbf{B}$ 를 형성한다.

기본 해는 다음과 같이 정의된다:

$\mathbf{x} = \begin{pmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{pmatrix}$

여기서, - $\mathbf{x}_B \in \mathbb{R}^m$ : 기저 변수 (basis variables) - $\mathbf{x}_N \in \mathbb{R}^{n-m}$ : 비기저 변수 (non-basis variables)

기저 변수 $\mathbf{x}_B$ 는 $\mathbf{B} \mathbf{x}_B = \mathbf{b}$ 를 만족하며, 비기저 변수 $\mathbf{x}_N = 0$ 로 설정된다.

3. 목적 함수의 기저 표현

목적 함수를 기저 변수를 이용해 다시 표현할 수 있다. 이를 위해, 전체 비용 벡터 $\mathbf{c}$ 를 기저 변수와 비기저 변수로 나누어 생각한다:

$\mathbf{c}^\top \mathbf{x} = \mathbf{c}_B^\top \mathbf{x}_B + \mathbf{c}_N^\top \mathbf{x}_N$

비기저 변수가 0으로 설정되므로, 목적 함수는 단순히 $\mathbf{c}_B^\top \mathbf{x}_B$ 로 축소된다. 따라서, 단체법은 기본적으로 $\mathbf{x}_B$ 에 의한 목적 함수의 변화를 추적한다.

4. 단체법의 단계

단체법의 주요 단계는 다음과 같다: 1. 초기 해 설정: 기본 해를 설정한다. 이때 기저 행렬 $\mathbf{B}$ 가 역행렬이 가능한 상태로 선택되어야 한다. 2. 변수 선택: 목적 함수를 개선하기 위해 비기저 변수 중 하나를 선택한다. 3. 피봇팅: 기저 변수를 업데이트하여 새로운 해를 계산한다.

5. 피봇팅 과정

단체법에서 피봇팅은 기저 변수를 교체하는 과정이다. 새로운 기저 변수는 목적 함수를 개선하는 방향으로 선택되며, 이를 위해 다음과 같은 계산이 필요하다.

기저 해에서 목적 함수의 변화율을 계산하기 위해 $\mathbf{A}_N$ 과 $\mathbf{A}_B^{-1}$ 를 이용하여 새로운 목적 함수 계수를 구할 수 있다:

$\mathbf{c}_N^\prime = \mathbf{c}_N - \mathbf{A}_N^\top \mathbf{A}_B^{-1} \mathbf{c}_B$

여기서, $\mathbf{c}_N^\prime$ 는 비기저 변수에 대한 새로운 목적 함수 계수이다. 이 계수들이 양수라면 목적 함수를 개선할 수 있다.

6. 피봇팅 규칙(Pivoting Rule)

비기저 변수 중에서 목적 함수를 개선할 수 있는 변수를 선택하는 과정에서, 다음과 같은 조건을 고려해야 한다:

들어오는 변수(Incoming Variable): 비기저 변수 $\mathbf{x}_N$ 중에서, 목적 함수 계수 $\mathbf{c}_N^\prime$ 이 양수인 변수를 선택한다. 이는 해당 변수를 증가시켰을 때 목적 함수가 개선된다는 것을 의미한다.
나가는 변수(Outgoing Variable): 들어오는 변수에 대응하는 기저 변수 중에서, 새로운 제약을 만족하기 위해 최소값 조건을 만족하는 변수를 나가는 변수로 선택한다. 이를 비율 테스트(Ratio Test)라고 한다. 나가는 변수는 다음과 같이 계산된다:

$\theta = \min \left\{ \frac{\mathbf{x}_B}{\mathbf{A}_B^{-1} \mathbf{A}_N} \right\}$

여기서, $\theta$ 는 나가는 변수에 해당하는 최소 비율이다. 이 과정에서 기저 행렬 $\mathbf{B}$ 를 갱신한다.

7. 갱신된 기저 해

피봇팅이 완료되면, 새로운 기저 해는 다음과 같이 계산된다:

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

비기저 변수는 여전히 $\mathbf{x}_N = 0$ 로 유지된다. 새로운 기저 행렬 $\mathbf{B}$ 와 기저 변수에 대한 정보를 이용하여 해를 갱신하고, 목적 함수를 계산한다.

8. 단체법의 종료 조건

단체법은 다음 두 가지 조건 중 하나가 충족될 때 종료된다:

최적성 조건: 더 이상 개선할 수 있는 비기저 변수가 없을 때, 즉 모든 $\mathbf{c}_N^\prime \leq 0$ 일 때 알고리즘이 종료된다. 이때 현재 기저 해가 최적 해이다.
무한 해: 만약 비율 테스트에서 $\theta$ 가 무한대라면, 이는 문제에 무한한 해가 존재함을 의미하며, 단체법은 종료된다.

9. 단체법의 시간 복잡도

단체법의 시간 복잡도는 문제의 크기에 따라 달라지며, 일반적으로 $O(mn)$ 의 복잡도를 갖는다. 여기서 $m$ 은 제약식의 수, $n$ 은 변수의 수이다. 단체법은 이론적으로는 다항 시간 알고리즘이 아니지만, 실무에서는 대부분의 경우 매우 효율적으로 작동한다.

10. 단체법의 기하학적 해석

단체법은 기하학적으로 선형계획 문제의 해를 다각형(또는 단체)의 꼭짓점에서 찾아내는 과정으로 볼 수 있다. 제약 조건이 정의하는 다각형의 각 꼭짓점에서 목적 함수를 평가하며, 이를 통해 최적 해를 찾아낸다. 각 꼭짓점은 하나의 기본 해에 해당하며, 피봇팅 과정은 한 꼭짓점에서 인접한 꼭짓점으로 이동하는 과정으로 해석될 수 있다.