쌍대 단체법의 절차 - 실험 도서관

쌍대 문제와 표준형 문제 설정

쌍대 단체법을 적용하기 위해서는 우선적으로 원래의 선형계획 문제(Primal Problem)와 이에 대응하는 쌍대 문제(Dual Problem)를 설정해야 한다. 원래 문제는 일반적으로 표준형으로 주어진다:

$\text{Minimize} \quad \mathbf{c}^T \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$ 이다.

이에 대응하는 쌍대 문제는 다음과 같이 정의된다:

$\text{Maximize} \quad \mathbf{b}^T \mathbf{y}$

$\text{subject to} \quad \mathbf{A}^T \mathbf{y} \leq \mathbf{c}, \quad \mathbf{y} \geq 0$

여기서, $\mathbf{y} \in \mathbb{R}^m$ 는 쌍대 변수이다.

초기 해 선택

쌍대 단체법을 수행하기 위해서는 우선 쌍대 문제의 초기 기본 해를 선택해야 한다. 이는 원래 문제의 경우와 마찬가지로, 기저 해가 정해져야 한다. 초기 해는 원래 문제의 비기본 변수와 관련이 있으며, 일반적으로 인공 변수를 사용하여 초기 해를 설정할 수 있다. 이 과정은 다음과 같은 조건을 만족해야 한다:

$\mathbf{A}^T \mathbf{y} = \mathbf{c}$
$\mathbf{y} \geq 0$

이후 각 변수의 기저 상태를 확인하고, 기저 해가 유효한지 검사한다.

표 형식 설정 (Dual Simplex Tableau)

단체법과 유사하게 쌍대 단체법에서도 표 형식(Dual Simplex Tableau)을 사용하여 문제를 풀어나간다. 표 형식의 각 열은 기저 변수와 비기저 변수를 나타내며, 이를 통해 현재 해의 상태를 추적할 수 있다.

표 형식의 예시는 다음과 같다:

$\begin{array}{c|c} \mathbf{y} & \mathbf{c} - \mathbf{A}^T \mathbf{y} \\ \hline \text{기저 변수들} & \text{잔여 조건들} \end{array}$

각 단계에서는 이 표 형식을 업데이트하며, 쌍대 문제의 개선된 해를 구하게 된다.

축소 비용 벡터 계산

표 형식을 기반으로 축소 비용 벡터(Reduced Cost Vector)를 계산하여 개선할 수 있는 방향을 설정한다. 축소 비용 벡터는 다음과 같이 정의된다:

$\mathbf{r} = \mathbf{c} - \mathbf{A}^T \mathbf{y}$

여기서 $\mathbf{r}$ 이 음수인 경우, 해당 열에 대응하는 비기저 변수를 기저 변수로 교체하는 피봇팅(Pivoting)을 통해 개선된 해를 구할 수 있다.

피봇팅(Pivoting)

쌍대 단체법에서는 피봇팅 과정이 원래 단체법과 유사하게 이루어진다. 축소 비용 벡터 $\mathbf{r} = \mathbf{c} - \mathbf{A}^T \mathbf{y}$ 에서 음수인 값이 있는 열을 선택하고, 그 열에 대응하는 변수를 기저 변수로 포함시킨다. 이때 피봇팅할 열은 다음과 같은 기준에 따라 선택된다:

$\mathbf{r}_j < 0$ 인 $j$ 를 선택
그 열을 따라 가능한 행을 선택하여 교환

피봇팅 과정은 다음과 같은 단계로 나뉜다:

들어오는 변수 선택: 축소 비용 벡터에서 음수인 항목을 찾아 그에 대응하는 변수를 기저에 포함시킨다.
나가는 변수 선택: 들여온 변수와 함께 기저에서 제외할 변수를 선택한다. 이를 위해서는 가능 영역 내에서 최소한의 값을 유지하는 방향을 결정하는 과정이 필요하다.

피봇팅 행렬은 다음과 같은 방식으로 갱신된다:

$\mathbf{A}_{new} = \mathbf{A}_{old} - \frac{1}{\text{피봇 행의 피봇 열 값}} \times (\text{피봇 행})$

이 과정에서 들어오는 변수는 기저 변수가 되고, 나가는 변수는 비기저 변수가 된다.

해 갱신

피봇팅 과정을 통해 새로운 기저 해를 계산한 후, 해당 해가 최적해인지 판단하는 과정이 필요하다. 쌍대 단체법의 경우, 새롭게 얻어진 해가 최적해가 되는 기준은 다음과 같다:

$\mathbf{r} \geq 0$ 일 때, 더 이상 개선할 수 없는 최적해에 도달했음을 의미한다.
$\mathbf{y} \geq 0$ 조건을 만족하는지 확인한다.

해를 갱신한 후에는 다시 축소 비용 벡터를 계산하여 추가적인 피봇팅이 필요한지 확인한다. 이 과정이 반복되면서 점진적으로 최적해에 접근하게 된다.

종료 조건

쌍대 단체법에서의 종료 조건은 원래 단체법과 마찬가지로 두 가지 조건을 만족할 때 이루어진다:

축소 비용 벡터 $\mathbf{r}$ 의 모든 값이 0 이상일 때
기저 해가 유효하고, 가능한 영역 내에 있을 때

이때, 최적해에 도달했음을 확인할 수 있다.