단체법의 기본 개념 - 실험 도서관

선형계획 문제의 수학적 표현

단체법(Simplex Method)은 선형계획법에서 가장 널리 사용되는 알고리즘으로, 선형계획 문제를 해결하는 방법 중 하나이다. 선형계획 문제는 다음과 같이 정의된다:

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

$\text{Subject to } \mathbf{A} \mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq 0$

여기서: - $\mathbf{c} \in \mathbb{R}^n$ 은 목표 함수의 계수 벡터, - $\mathbf{x} \in \mathbb{R}^n$ 은 결정 변수 벡터, - $\mathbf{A} \in \mathbb{R}^{m \times n}$ 은 제약 조건의 계수 행렬, - $\mathbf{b} \in \mathbb{R}^m$ 은 제약 조건의 우변 벡터이다.

단체법은 이 선형계획 문제의 해를 구하기 위한 효율적인 알고리즘으로, 기본적으로 두 가지 과정을 반복한다: 1. 기저해 찾기 2. 기저해 개선

기저해 (Basic Feasible Solution)

기본적으로 선형계획 문제는 다차원의 해 공간에서 해를 찾는 문제로 해석할 수 있다. 이 해 공간의 각 꼭짓점(vertex)은 선형 제약 조건을 만족하는 기저해에 해당한다. 단체법은 이 기저해들 중에서 최적해를 찾기 위해 탐색한다.

기저해를 구하려면 다음과 같이 문제를 표준형으로 변환해야 한다:

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

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

여기서 제약 조건이 등식 형태로 주어지기 때문에, 기저해는 행렬 $\mathbf{A}$ 의 열 중에서 $m$ 개의 독립적인 열을 선택하여 이를 통해 해를 구성할 수 있다.

단체법의 탐색 과정

단체법은 기저해들 사이를 이동하면서 목표 함수 $\mathbf{c}^\top \mathbf{x}$ 의 값을 점진적으로 개선해 나간다. 이 과정에서 두 가지 중요한 단계가 이루어진다:

1. 기저 변수 선택

기저해를 개선하기 위해서는 현재 기저에 포함된 변수를 변경해야 한다. 이때 기저에 포함된 변수를 선택하는 기준은 목표 함수의 기울기에 따라 결정된다. 목표 함수의 계수 벡터 $\mathbf{c}$ 의 각 성분이 해에 미치는 영향도를 고려하여 가장 큰 개선이 가능한 방향으로 이동하게 된다.

2. 피봇팅(pivoting)

피봇팅은 새로운 기저를 찾기 위한 과정이다. 선택된 변수를 새롭게 기저에 포함시키고, 다른 변수를 제외함으로써 새로운 기저해를 구하게 된다. 이때 기저해가 유효성을 유지하기 위해서는 제약 조건을 만족해야 한다. 피봇팅은 제약 조건 행렬 $\mathbf{A}$ 와 목표 함수의 변화율을 이용하여 계산된다.

단체법의 핵심은 이러한 기저 변수의 교체를 통해 목표 함수의 값을 지속적으로 개선해 나가는 것이다.

기저 변수의 교체 규칙

단체법에서 기저 변수를 교체하는 과정은 두 가지 중요한 개념에 의존한다: 들어오는 변수(entering variable)와 나가는 변수(leaving variable)이다.

들어오는 변수 (Entering Variable)

들어오는 변수는 목표 함수의 값을 가장 크게 개선할 수 있는 변수로 선택된다. 이는 목표 함수의 기울기, 즉 $\mathbf{c}$ 벡터의 값들에 따라 결정된다. 만약 현재 기저해가 최적해가 아니라면, 어떤 변수 $x_j$ 를 증가시키는 것이 목표 함수 $\mathbf{c}^\top \mathbf{x}$ 의 값을 더 크게 만들 수 있다. 이때, 기저에 포함되지 않은 변수들 중에서 목표 함수의 값을 가장 크게 개선할 수 있는 변수를 들어오는 변수로 선택한다.

나가는 변수 (Leaving Variable)

들어오는 변수를 추가하면 기존의 기저에 포함된 변수 중 하나는 기저에서 제외되어야 한다. 이는 제약 조건을 만족하면서 해를 유지하기 위해 필수적이다. 나가는 변수는 제약 조건을 위반하지 않는 범위 내에서 결정된다. 즉, 들어오는 변수가 증가함에 따라 제약 조건을 먼저 위반하게 되는 변수가 나가는 변수로 선택된다.

나가는 변수를 결정하는 공식은 다음과 같다. 만약 들어오는 변수가 $x_j$ 이고, 현재 기저에 속하는 변수들이 $x_B$ 라면, 들어오는 변수의 값에 따라 제약 조건을 위반하는 변수를 찾아야 한다.

먼저 제약 조건 행렬 $\mathbf{A}$ 에서 들어오는 변수 $x_j$ 의 열을 선택하고, 그 열을 사용하여 각 기저 변수의 변화를 계산한다. 이때 들어오는 변수가 증가할 수 있는 최대치는 다음과 같이 계산된다:

$\theta = \min \left\{ \frac{b_i}{a_{ij}} \mid a_{ij} > 0 \right\}$

여기서 $b_i$ 는 제약 조건의 우변 값이고, $a_{ij}$ 는 $\mathbf{A}$ 행렬에서 $x_j$ 에 해당하는 열의 값이다. 이때 $\theta$ 는 들어오는 변수가 증가할 수 있는 최대량을 의미하며, 이 양을 넘어가면 제약 조건이 위반된다. 따라서 $\theta$ 에 해당하는 변수는 나가는 변수가 된다.

피봇팅 과정

들어오는 변수와 나가는 변수가 결정되면, 이를 사용하여 새로운 기저해를 계산하는 과정이 필요하다. 이 과정은 피봇팅(pivoting) 이라고 불리며, 다음과 같은 단계를 따른다.

나가는 변수와 들어오는 변수를 교체하여 새로운 기저를 형성한다.
새로운 기저에서 목표 함수의 값을 재계산한다.
새로운 기저해가 최적해인지 확인한다. 만약 최적해가 아니라면, 다시 들어오는 변수와 나가는 변수를 선택하여 반복한다.

피봇팅 과정은 제약 조건을 만족하면서 목표 함수의 값을 지속적으로 개선하기 위한 필수적인 단계이다. 피봇팅이 종료되면, 단체법은 최적해에 도달하게 된다.

표(Simplex Tableau)의 사용

단체법의 계산 과정을 쉽게 처리하기 위해 표(Simplex Tableau)를 사용한다. 이 표는 제약 조건과 목표 함수를 모두 하나의 행렬로 정리하여 피봇팅 과정을 직관적으로 처리할 수 있게 해 준다. 표는 다음과 같은 형태로 구성된다:

$\begin{array}{c|cccc|c} & x_1 & x_2 & \cdots & x_n & RHS \\ \hline x_{B_1} & a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ x_{B_2} & a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ x_{B_m} & a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \\ \hline Z & c_1 & c_2 & \cdots & c_n & z_0 \end{array}$

여기서: - 각 행은 제약 조건을 나타내며, 기저 변수들 $x_{B_1}, x_{B_2}, \dots, x_{B_m}$ 의 계수를 포함한다. - 마지막 행은 목표 함수 $Z = \mathbf{c}^\top \mathbf{x}$ 의 계수와 현재의 최적 값을 나타낸다.

단체법의 피봇팅 과정은 이 표를 이용하여 빠르고 효율적으로 처리할 수 있다.

단체법의 반복 과정

단체법은 다음과 같은 반복 과정에 따라 최적해를 찾아간다:

표에서 개선할 수 있는 변수 선택 (Entering Variable Selection) 표에서 최종 행인 $Z$ -행에 있는 목표 함수 계수를 확인하여, 가장 크게 개선될 수 있는 변수, 즉 음의 값 중 절대값이 가장 큰 $c_j$ 에 해당하는 변수를 들어오는 변수로 선택한다. 이 변수는 목표 함수의 값 $Z$ 를 개선할 수 있는 방향을 제시한다.
피봇 열 선택 (Pivot Column Selection) 들어오는 변수를 선택한 후, 이 변수에 대응하는 열을 피봇 열로 설정한다. 이 열은 피봇팅에 사용되며, 해당 변수의 기저에서 나가는 변수를 찾는 기준이 된다.
피봇 행 선택 (Pivot Row Selection) 다음 단계는 피봇 열에서 나가는 변수를 선택하는 것이다. 각 제약 조건의 우변 값 $b_i$ 와 피봇 열의 값 $a_{ij}$ 을 비교하여 들어오는 변수를 가장 크게 증가시키면서 제약 조건을 위반하지 않는 범위 내에서 나가는 변수를 결정한다.

나가는 변수는 다음 공식을 사용하여 선택된다:

$\theta = \min \left\{ \frac{b_i}{a_{ij}} \mid a_{ij} > 0 \right\}$

여기서 $a_{ij}$ 는 피봇 열에서의 값이고, $b_i$ 는 제약 조건의 우변이다. 가장 작은 $\theta$ 값을 가지는 변수는 더 이상 기저에서 유지될 수 없으므로 나가는 변수로 선택된다.

피봇팅 (Pivoting) 나가는 변수가 결정되면, 해당 행과 열을 기준으로 피봇팅을 수행한다. 피봇팅은 표의 값을 업데이트하는 과정을 포함하며, 이를 통해 새로운 기저해를 구할 수 있다.

피봇팅 과정은 선택된 피봇 요소(즉, 피봇 행과 열의 교차점에 있는 값)를 1로 만들고, 그 주변의 값을 적절히 변환하여 새로운 기저 행렬을 생성하는 과정이다. 새로운 기저가 계산되면, 목표 함수의 값도 업데이트된다.

최적성 조건 확인 피봇팅 후, 최종 행 $Z$ -행의 목표 함수 계수들을 확인하여 모두 양수이면 최적해에 도달한 것이다. 만약 음수 계수가 남아있다면, 반복 과정을 계속 진행한다.

종결 조건

단체법은 다음 두 가지 조건 중 하나에 도달할 때 종료된다:

최적해 도달 표의 마지막 행, 즉 $Z$ -행에 있는 모든 목표 함수 계수들이 양수로 변환되면, 현재의 기저해가 최적해임을 의미한다. 이때 들어오는 변수나 나가는 변수를 선택할 필요가 없으며, 알고리즘은 종료된다.
불가능성 또는 무한 해 만약 표의 모든 가능한 나가는 변수 후보가 없거나, 피봇팅을 통해 해가 개선되지 않고 무한히 반복되는 경우, 문제는 불가능하거나 무한 해를 가짐을 의미한다. 이러한 경우 단체법은 적절한 종결 조건을 통해 종료된다.

단체법의 기본 개념은 이러한 반복적인 기저 탐색과 피봇팅을 통해 이루어지며, 이를 통해 최적해를 찾아가게 된다. 이 과정은 기저해가 다차원 공간에서 꼭짓점들 사이를 이동하며 목표 함수의 값을 개선하는 과정으로 직관적으로 이해할 수 있다.