표 형식(Simplex Tableau) - 실험 도서관

Simplex Tableau 개요

Simplex Tableau는 선형계획법의 단체법(Simplex Method)을 해결하기 위해 사용되는 테이블 형식의 배열로, 이 배열은 제약 조건, 목적 함수, 기초 변수의 상태를 종합적으로 표현한다. Tableau는 선형계획 문제를 효율적으로 풀기 위한 정보가 한눈에 보이도록 배열된 테이블로, 각 단계에서 현재의 해를 개선하기 위해 필요한 정보를 제공한다.

기본 구조

Simplex Tableau는 일반적으로 다음과 같은 요소로 구성된다: - 제약 조건의 계수: 선형 제약 조건을 행렬 형태로 나타낸 부분. - 목적 함수 계수: 최적화하려는 목적 함수의 계수들이 포함된다. - 우변 상수: 각 제약 조건의 우변 값. - 기초 변수(Basic Variables): 현재 기준에서 의사 결정 변수가 아닌, 기본적으로 0이 아닌 값이 할당된 변수들. - 잔여 변수(Non-basic Variables): 현재 해에서 0인 변수들. - 계산 결과: 현재 상태의 최적화 값과 각 기초 변수의 값.

각 요소는 Table의 특정 열과 행에 배치되며, 이 테이블을 이용하여 단체법의 반복 과정을 수행한다.

Tableau 행렬 표현

표 형식은 행렬을 이용해 표현할 수 있으며, 이를 수학적으로 다음과 같이 나타낼 수 있다:

$\mathbf{T} = \begin{bmatrix} c_1 & c_2 & \cdots & c_n & \text{RHS} \\ a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \end{bmatrix}$

여기서:

$\mathbf{T}$ 는 Simplex Tableau 행렬을 나타낸다.
$c_1, c_2, \ldots, c_n$ 는 목적 함수의 계수.
$a_{ij}$ 는 제약 조건의 계수 행렬 성분.
$b_1, b_2, \ldots, b_m$ 는 각 제약 조건의 우변 상수이다.

이 행렬의 각 열과 행은 다음과 같은 정보를 포함한다:

첫 번째 행은 목적 함수의 계수와 현재 해의 목적 함수 값.
나머지 행은 제약 조건을 나타내며, 마지막 열에는 각 제약 조건의 우변 값이 포함된다.

기초 변수(Basic Variables)와 잔여 변수(Non-basic Variables)

단체법의 핵심 개념은 각 단계에서 현재 해를 개선하는 방법을 찾는 것이다. 이를 위해 Simplex Tableau는 기초 변수와 잔여 변수를 구분한다.

기초 변수는 현재 해에서 0이 아닌 값을 가지는 변수로, Tableau의 특정 행에 할당된다.
잔여 변수는 현재 해에서 0인 값으로, Tableau의 나머지 열에 할당된다.

기초 변수는 각 단계에서 의사결정 변수가 아니라서 우변에 영향을 미친다. 잔여 변수는 새로운 해를 계산하기 위한 후보로 사용된다.

기본 연산 절차

Simplex Tableau에서 단체법의 연산은 주로 피벗팅(pivoting)을 통해 이루어진다. 피벗팅은 새로운 기초 변수와 잔여 변수를 교환하여 더 나은 해를 찾아가는 과정이다. Tableau를 이용한 단체법의 기본 연산 절차는 다음과 같다:

들어오는 변수(Entering Variable) 결정
Simplex Tableau에서 현재 잔여 변수들 중에서 가장 큰 개선 효과를 기대할 수 있는 변수를 찾는다. 이 변수는 들어오는 변수(Entering Variable)로 불리며, 이는 기초 변수로 포함된다.

들어오는 변수를 결정하기 위해 Tableau의 목적 함수 계수(첫 번째 행)를 살펴본다. 가장 큰 음수인 계수를 가진 변수를 선택하여, 이 변수가 들어오는 변수로 설정된다.

예를 들어, 들어오는 변수는 다음과 같이 선택된다:

$\text{Entering Variable} = \arg \min \left( c_1, c_2, \ldots, c_n \right)$

여기서 $c_i$ 는 잔여 변수들의 계수이다. 음수인 계수는 개선 가능성을 의미하므로, 가장 작은 값을 가지는 변수가 들어오는 변수로 선택된다.

나가는 변수(Leaving Variable) 결정
들어오는 변수를 결정한 후, 다음 단계에서는 나가는 변수를 선택해야 한다. 나가는 변수는 현재 기초 변수들 중에서, 들어오는 변수가 들어옴에 따라 기초 변수를 교체하는 변수이다.

나가는 변수를 결정하기 위해 비율 테스트(Ratio Test)를 사용한다. 이는 Tableau의 우변 상수와 들어오는 변수의 계수 사이의 비율을 계산하여 최소값을 가지는 기초 변수를 나가는 변수로 선택하는 방식이다:

$\text{Leaving Variable} = \arg \min \left( \frac{b_1}{a_{1k}}, \frac{b_2}{a_{2k}}, \ldots, \frac{b_m}{a_{mk}} \right)$

여기서 $a_{ik}$ 는 들어오는 변수에 해당하는 열의 값이고, $b_i$ 는 우변 상수이다.

비율이 양수인 경우만 계산에 사용되며, 음수는 제외한다. 이 비율이 가장 작은 값을 가지는 변수는 나가는 변수로 설정된다.

피벗 연산(Pivot Operation)
들어오는 변수와 나가는 변수가 결정되면, 그다음 단계는 피벗팅(Pivoting)이다. 피벗팅은 Tableau에서 특정 행과 열의 교환을 의미하며, 이를 통해 더 나은 해로 나아가게 된다. 피벗팅은 다음과 같이 수행된다:
나가는 변수가 포함된 행의 피벗팅을 수행하며, 이 행의 피벗팅 요소(pivot element)는 1로 만든다.
나머지 행은 피벗팅 요소를 이용하여 0으로 만들면서, Tableau를 갱신한다.

피벗팅 연산 후, 들어오는 변수는 기초 변수로 바뀌며, 나가는 변수는 잔여 변수가 된다.

해 갱신(Update Solution)
피벗팅이 완료되면 Tableau의 값이 갱신되고, 새로운 기초 해를 구할 수 있게 된다. 이 과정은 새로운 기초 변수가 반영된 새로운 해를 계산하고, 다음 반복을 수행할 준비가 된 상태를 의미한다.
최적성 조건 검사
새로운 Tableau가 만들어지면, 현재 상태가 최적 해인지 확인해야 한다. 최적성 조건은 Tableau의 첫 번째 행(목적 함수 계수)의 값이 모두 0 또는 양수일 때 충족된다. 만약 여전히 음수 값이 존재한다면, 계속해서 피벗 연산을 수행하여 더 나은 해를 찾을 수 있다.

피벗팅 과정의 예시

다음은 피벗팅 과정의 예시이다. 간단한 Tableau에서 피벗팅을 수행하는 과정을 설명한다:

기본 변수	$x_1$	$x_2$	우변
$x_3$	1	2	4
$x_4$	2	1	3
목적 함수	-3	-5	0

들어오는 변수: $x_2$ (가장 작은 값 -5)
나가는 변수: $x_4$ (비율 테스트에서 최소값 $\frac{3}{1} = 3$ )
피벗 연산 후 갱신된 Tableau:

기본 변수	$x_1$	$x_2$	우변
$x_3$	0.5	0	2
$x_2$	2	1	3
목적 함수	-1	0	15

피벗팅 후 새로운 기초 해는 $x_1 = 0, x_2 = 3, x_3 = 2$ 이며, 목적 함수 값은 15로 개선되었다.