선형계획법에서 단체법(Simplex Method)을 확장한 2단계 단체법은 시작점 선택 문제를 해결하는 중요한 방법 중 하나이다. 2단계 단체법에서는 기본적으로 인공 변수를 도입하여 가능한 기본해를 찾은 후, 본격적인 단체법 절차로 들어가게 된다. 이 과정에서 첫 번째로 해결해야 할 문제는, 적절한 시작점을 어떻게 선택할 것인가이다. 시작점 선택 문제는 초기 기본 feasible solution을 찾는 과정에서 결정적 역할을 한다.
1. 문제 정의
일반적인 선형계획 문제는 다음과 같이 주어진다:
여기서:
- \mathbf{c}는 비용 벡터 (objective function의 계수),
- \mathbf{A}는 제약 조건 행렬,
- \mathbf{b}는 제약 조건 우변의 상수 벡터,
- \mathbf{x}는 결정 변수 벡터이다.
단체법은 기본적으로 가능한 기본 feasible solution을 찾아서 그 점에서 출발하여 최적해로 이동하는 방식이다. 하지만, 만약 주어진 문제에 feasible solution이 처음부터 주어지지 않는다면, 이를 찾는 것이 중요한 단계가 된다.
2. 인공 변수 도입
초기 feasible solution이 없는 경우, 2단계 단체법에서는 인공 변수를 도입하여 문제를 해결한다. 인공 변수는 주어진 문제에 추가로 더해지며, 추가된 인공 변수를 통해 새로운 문제를 설정하고 이를 해결함으로써 feasible solution을 찾는 과정을 진행한다. 이때, 원래의 선형계획 문제는 다음과 같이 변형된다:
여기서 \mathbf{I}는 단위 행렬이고, \mathbf{w}는 인공 변수이다. 이 새로운 문제에서 인공 변수를 최소화하는 것이 목적이 된다.
이 과정을 통해, 원래 문제에서 feasible solution을 찾고, 그 solution을 기반으로 다시 단체법을 적용하여 최적해로 이동하게 된다. 시작점 선택 문제는 이 인공 변수의 도입을 어떻게 효과적으로 할 것인지와 밀접하게 관련되어 있다.
3. 인공 변수 최소화
1단계에서 인공 변수를 포함한 새로운 목적 함수를 최소화하는 작업을 수행한다. 이때, 목적 함수는 다음과 같이 변형된다:
이때 w_i는 인공 변수이고, 이 인공 변수들이 모두 0이 되는 feasible solution을 찾는 것이 목표이다.
4. 인공 변수의 제거
1단계에서 인공 변수를 최소화한 후, 인공 변수들이 모두 0이 되면 원래의 문제로 돌아갈 수 있다. 즉, 인공 변수를 제거하고, 찾은 feasible solution을 바탕으로 원래의 목적 함수 \mathbf{c}^\top \mathbf{x}를 최소화하는 2단계 단체법의 절차로 넘어간다.
이때 중요한 점은, 인공 변수를 모두 제거할 수 없는 경우, 즉 모든 인공 변수가 0이 될 수 없는 경우에는 원래 문제에 feasible solution이 없다는 것을 의미한다. 이는 문제 자체가 해결 불가능한 경우임을 나타내며, 최적해를 찾을 수 없게 된다.
5. 초기 기본 feasible solution의 중요성
시작점 선택 문제의 핵심은 초기 feasible solution을 어떻게 찾는가이다. 만약 초기 feasible solution이 주어지지 않는다면, 인공 변수를 도입하여 가능한 해를 찾는 것이 필수적이다. 2단계 단체법에서는 이 과정을 통해 feasible solution을 얻고, 이를 바탕으로 최적해를 구하는 단계를 수행하게 된다.
이렇게 얻어진 시작점은 이후 단체법 절차를 진행하는 데 있어 매우 중요한 역할을 하며, 시작점이 적절하지 않다면 최적해로 빠르게 수렴하지 못할 가능성이 높다.
6. 대안적인 시작점 선택 방법
특정 경우에는 인공 변수를 도입하지 않고도 시작점을 선택할 수 있는 방법들이 존재한다. 이 경우에는 문제의 특성에 따라, 다양한 휴리스틱 또는 초기 해를 추정하는 방법들이 사용될 수 있다. 그러나 2단계 단체법에서는 일반적으로 인공 변수를 도입하여 시작점을 선택하는 것이 가장 보편적인 방법으로 알려져 있다.
인공 변수를 도입한 1단계의 절차가 종료되면, 이 시작점을 기반으로 원래의 목적 함수를 최소화하는 본격적인 단체법 과정이 시작된다.