1. 문제의 설정
2단계 단체법은 단체법(Simplex Method)을 확장하여 사용하는 방법으로, 주로 슬랙 변수(slack variable)나 초과 변수(surplus variable)를 사용하는 경우에 적용된다. 이러한 경우 초기 기본 해(basic feasible solution)가 주어지지 않을 때, 인공 변수를 도입하여 해결한다. 이때 두 단계로 나누어 문제를 해결하는 것이 특징이다.
2. 1단계: 인공 문제 생성
주어진 선형계획 문제를 아래와 같은 표준형으로 변환한다.
여기서 초기 기본 해를 찾기 위해 인공 변수를 추가하여 다음과 같은 새로운 목적함수를 설정한다.
이때, \mathbf{y}는 인공 변수이다. 이 문제를 해결하기 위해 단체법을 사용하여 1단계에서 인공 변수를 제거하고 초기 해를 얻는다.
3. 1단계의 단체법 적용
1단계에서는 인공 변수를 도입한 문제를 풀기 위해 단체법을 적용한다. 이때, 인공 변수를 포함한 단체 테이블(simplex tableau)을 구성하고, 목적함수를 업데이트하면서 인공 변수를 제거하는 방향으로 계산을 진행한다.
1단계에서의 목적 함수는 다음과 같이 정의된다.
해결 과정에서 모든 인공 변수가 0이 되면, 1단계는 종료되며, 새로운 기본 해가 도출된다. 이 해는 원래 문제에 대한 기본 해로 사용된다.
4. 2단계: 원래 문제로 돌아가기
1단계가 끝나면, 인공 변수가 모두 제거된 상태에서 2단계로 넘어간다. 2단계에서는 원래의 목적 함수
로 돌아가서 단체법을 다시 적용한다. 이때, 1단계에서 구한 기본 해를 초기 해로 사용하며, 단체법을 반복적으로 적용하여 최적 해를 찾는다.
2단계에서는 1단계에서 구한 기본 해를 초기로 하고, 일반 단체법을 적용해 최적 해를 구한다. 2단계에서는 원래 문제의 목적 함수에 따라 피벗팅(pivoting)을 진행하게 된다.
5. 2단계의 단체법 적용
2단계에서는 단체 테이블(simplex tableau)을 원래 문제의 목적 함수에 맞춰서 재구성한다. 1단계에서 도출된 기본 해(basic feasible solution)를 초기 값으로 사용하며, 피벗팅(pivoting) 과정을 통해 최적 해를 찾아가는 과정은 1단계와 유사한다.
5.1 목적 함수의 업데이트
원래 목적 함수 \mathbf{c}^T \mathbf{x}에 따라, 단체 테이블을 업데이트한다. 이때, 새로운 기본 변수들과 대응하는 목적 함수 계수들을 반영하여, 새로운 목적 함수 Z는 다음과 같이 표현된다.
5.2 피벗팅 과정
피벗팅 과정은 기본 변수와 비기본 변수의 교체 과정을 의미한다. 각 단계에서 피벗팅을 통해 다음을 결정한다.
- 들어갈 변수(Entering variable): 이는 현재 해의 개선 방향을 결정하는 변수이다. 가장 큰 양의 계수를 가진 비기본 변수가 들어갈 변수로 선택된다.
- 나갈 변수(Leaving variable): 기본 변수들 중에서 가장 큰 비율을 갖는 변수가 나갈 변수로 선택된다.
이 피벗팅 과정을 통해, 현재 해를 점차 개선해 나간다.
5.3 최적성 조건 확인
최적성을 판단하기 위한 조건은 다음과 같다. 현재의 목적 함수에서 더 이상 개선할 수 없을 때, 즉 모든 비기본 변수의 목적 함수 계수(Coefficients of Objective Function)가 음수일 때 최적 해가 도출되었음을 의미한다.
단체법의 반복 과정은 다음과 같은 단계로 이루어진다.
- 피벗팅을 통해 해를 개선한다.
- 현재 해가 최적인지 확인한다. 만약 최적 해가 아니라면 다시 피벗팅을 진행한다.
- 모든 피벗팅 과정이 종료되면 최적 해를 도출한다.
6. 2단계 종료
모든 비기본 변수의 계수가 음수가 되어 더 이상의 개선이 불가능하면 최적 해가 도출되었음을 의미하며, 2단계 단체법은 종료된다. 이 과정은 원래 문제의 해를 찾기 위해 필요하다.