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

1. 초기 기본 feasible 해 찾기

단체법(Simplex Method)은 선형 계획법에서 기본 feasible 해(basic feasible solution)를 찾아 그 해를 개선해 나가는 방법이다. 먼저, 선형 계획 문제를 표준형으로 변환한 후 초기 기본 feasible 해를 찾아야 한다.

표준형 선형 계획 문제는 다음과 같다.

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

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

여기서,

$\mathbf{c}$ 는 목적 함수의 계수 벡터,
$\mathbf{x}$ 는 결정 변수 벡터,
$\mathbf{A}$ 는 제약 조건의 계수 행렬,
$\mathbf{b}$ 는 제약 조건의 우변 값 벡터이다.

단체법에서는 초기 feasible 해가 중요하다. 초기 feasible 해는 주어진 제약 조건 하에서 모든 $x_i \geq 0$ 을 만족하는 해이다. 이때, $\mathbf{A} \mathbf{x} = \mathbf{b}$ 의 해를 구해야 하므로, 기본 변수(basic variables)와 비기본 변수(non-basic variables)를 나누어 초기 해를 설정한다.

기본 변수는 행렬 $\mathbf{A}$ 의 열 중 선형 독립인 열에 해당하는 변수들이며, 비기본 변수는 나머지 변수들이다. 초기 기본 feasible 해는 비기본 변수를 0으로 두고 기본 변수의 값을 제약 조건에 따라 결정하는 방식으로 찾을 수 있다.

2. 목적 함수의 개선 방향 결정

초기 feasible 해를 찾은 후, 목적 함수를 개선할 수 있는 방향을 결정해야 한다. 이를 위해 비기본 변수 중에서 목적 함수를 가장 크게 개선할 수 있는 변수를 선택하게 된다. 이를 들어올리는 변수(incoming variable)라고 한다.

먼저, 목적 함수의 개선 정도를 평가하기 위해 목적 함수의 기울기(gradient)를 계산한다. 선형 계획 문제에서 기울기는 $\mathbf{c}$ 벡터로 주어진다. 기본 feasible 해에서 기울기가 비기본 변수 방향으로 어떻게 변하는지를 조사하여 개선 방향을 결정한다.

개선할 수 있는 변수는 다음과 같이 결정된다:

비기본 변수 $x_j$ 의 목적 함수 계수 $c_j$ 가 음수라면, 그 변수를 증가시킴으로써 목적 함수 값을 증가시킬 수 있다. 이때, $c_j$ 가 가장 작은 비기본 변수를 선택하여 그 변수를 증가시키는 방향으로 이동한다.

$\Delta z = c_j$

여기서, $\Delta z$ 는 목적 함수의 증가량, $c_j$ 는 선택된 비기본 변수의 계수이다.

3. 들어올리는 변수에 따른 이동

비기본 변수를 선택한 후, 그 변수를 증가시키면서 목적 함수 값을 개선하는 방향으로 이동하게 된다. 그러나 모든 제약 조건을 만족시키기 위해, 들어올리는 변수의 값은 제한된다. 이 제한은 기본 변수 중 하나가 0으로 변할 때까지 들어올리는 변수의 값을 증가시킬 수 있음을 의미한다.

이를 위해, 제한 조건을 다음과 같이 설정한다:

$\mathbf{A} \mathbf{x} = \mathbf{b}$

비기본 변수를 증가시키면, 기본 변수의 값도 변화하게 된다. 이때 들어올리는 변수의 증가량을 $\theta$ 라고 하면, 제약 조건의 균형을 맞추기 위해 기본 변수의 변화량은 다음과 같이 계산된다:

$\mathbf{x}_{\text{basic}} = \mathbf{b} - \mathbf{A}_{\text{non-basic}} \mathbf{x}_{\text{non-basic}}$

여기서, $\mathbf{A}_{\text{non-basic}}$ 는 비기본 변수에 대응하는 $\mathbf{A}$ 의 열이다.

들어올리는 변수를 증가시키는 동안 기본 변수 중 하나가 0으로 변할 때, 그 기본 변수를 outgoing variable이라 한다. 이 변수는 더 이상 기본 변수가 아니며, 비기본 변수로 변환된다. 즉, 이번 단계에서는 들어올리는 변수와 나가는 변수를 교환하는 것이다.

이 과정을 진행할 때, 나가는 변수는 다음과 같은 기준으로 결정된다:

$\theta = \min \left( \frac{x_i}{a_{ij}} \right), \, \text{where } a_{ij} > 0$

여기서, $x_i$ 는 기본 변수의 현재 값이며, $a_{ij}$ 는 해당 기본 변수의 제약 조건 계수이다. 이 식을 통해 $\theta$ 를 계산하면, 나가는 변수를 결정할 수 있다.

4. 기본 feasible 해의 갱신

나가는 변수가 결정되면, 새로운 기본 feasible 해를 계산한다. 새롭게 들어온 변수는 기본 변수로 변환되고, 나간 변수는 비기본 변수로 변환된다. 이로 인해 새로운 해를 얻게 된다. 새로운 해는 다음과 같이 표현된다:

$\mathbf{x}_{\text{new}} = \mathbf{x}_{\text{old}} + \theta \mathbf{d}$

여기서, $\mathbf{d}$ 는 이동 방향 벡터이며, $\theta$ 는 이동량이다.

이 과정을 통해 목적 함수의 값을 개선할 수 있으며, 새로운 기본 feasible 해를 얻게 된다. 이때, 만약 더 이상 개선할 수 없다면(즉, 모든 비기본 변수의 계수가 양수일 경우), 최적해에 도달하게 된다.

5. 반복 과정

단체법은 기본 feasible 해를 반복적으로 개선하는 방식으로 최적해에 도달한다. 반복 과정은 다음 단계들로 구성된다:

들어올리는 변수 선택: 비기본 변수 중에서 목적 함수 값을 개선할 수 있는 변수를 선택한다. 이는 목적 함수 계수 벡터 $\mathbf{c}$ 에서 음수인 계수를 가진 변수를 선택하는 방식으로 이루어진다.
나가는 변수 결정: 선택된 들어올리는 변수를 증가시키면서 나가는 변수를 결정한다. 나가는 변수는 기본 변수 중에서 가장 먼저 0이 되는 변수로, 이는 제약 조건을 만족시키기 위한 제한 값 $\theta$ 를 계산하여 선택된다.
기본 feasible 해 갱신: 나가는 변수를 비기본 변수로, 들어올리는 변수를 기본 변수로 변환하고 새로운 기본 feasible 해를 계산한다.

이 과정은 최적해에 도달할 때까지 반복된다. 최적해에 도달하는 조건은 다음과 같다:

비기본 변수 중에서 목적 함수의 계수 벡터 $\mathbf{c}$ 가 모두 양수일 경우, 더 이상 개선할 수 없으므로 최적해에 도달하게 된다.

만약 반복 과정 중에 특정 상황에서 목적 함수가 개선되지 않는 경우가 발생할 수 있다. 이를 퇴행 현상(degeneracy)이라고 하며, 이는 특정 기본 변수의 값이 0일 때 발생할 수 있다. 이러한 현상이 발생하면, 동일한 해를 반복적으로 구할 수 있으므로 이를 방지하기 위한 특별한 처리 방식이 필요하다.

6. 최적해 확인

최적해는 비기본 변수의 계수가 모두 양수이거나 0일 때 도달하게 된다. 최적해에 도달한 후, 이 해가 전체 문제에 대한 최적해인지를 확인하는 과정이 필요하다.

만약, 들어올리는 변수를 선택할 수 없다면 현재의 기본 feasible 해가 최적해가 된다.
기본 feasible 해를 확인하고, 목적 함수의 값을 계산하여 최종적으로 얻어진 최적해가 문제를 만족시키는지 검토한다.

7. 단체법의 종료

최적해에 도달하거나 더 이상 개선할 수 없는 경우, 단체법은 종료된다. 이때, 얻어진 기본 feasible 해는 최적해로 간주되며, 목적 함수의 최종 값과 함께 출력된다.

이것이 단체법의 전체 절차이며, 단체법의 핵심은 초기 feasible 해를 시작으로 목적 함수 값을 반복적으로 개선하여 최적해에 도달하는 과정에 있다. 각각의 단계는 기본 feasible 해를 계산하고 목적 함수의 개선 방향을 찾아가며 반복된다.