인공 변수와 초기 기본 해 - 소프트웨어 융합

인공 변수 도입

선형계획법에서 단체법(Simplex Method)을 사용하기 위해서는 초기 기본 해가 필요하다. 하지만 어떤 경우에는 문제의 제약 조건으로 인해 초기 기본 해를 쉽게 구할 수 없는 경우가 있다. 이때 인공 변수(artificial variables)를 도입하여 문제를 해결할 수 있다.

인공 변수는 제약 조건을 만족하는 초기 기본 해를 만들기 위해 추가되는 변수이다. 특히, 균등성이 없는 문제에서 유용하다. 예를 들어, 제약 조건이 부등식 형태로 주어진 경우에 인공 변수를 추가하여 부등식을 등식으로 변환하고, 이를 통해 초기 기본 해를 도출할 수 있다.

인공 변수는 단체법을 시작할 때만 사용되며, 목적 함수의 최적화를 통해 이후에 제거된다.

초기 기본 해 설정

단체법을 시작하기 위해서는 초기 기본 해를 구해야 한다. 이를 위해 인공 변수를 도입한 뒤, 2단계 단체법의 첫 번째 단계에서 초기 기본 해를 설정하는 방법은 다음과 같다:

문제의 형태를 표준형으로 변환
먼저 선형계획 문제는 표준형으로 변환되어야 한다. 표준형은 일반적으로 다음과 같은 형태로 주어진다:

$\text{최대화} \quad \mathbf{c}^\top \mathbf{x}$

$\text{제약 조건} \quad \mathbf{A} \mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq 0$

여기서, $\mathbf{A}$ 는 계수 행렬, $\mathbf{b}$ 는 상수 벡터, $\mathbf{x}$ 는 변수 벡터, $\mathbf{c}$ 는 목적 함수의 계수 벡터이다.

인공 변수 추가
제약 조건 중에서 부등식이 포함된 제약 조건이 있을 경우, 인공 변수를 추가한다. 부등식을 등식으로 변환하는 과정에서 여유 변수 또는 잉여 변수를 추가하고, 추가적으로 초기 기본 해를 찾기 위해 인공 변수를 도입한다. 예를 들어, 다음과 같은 부등식이 있다고 가정할 수 있다:

$\mathbf{A}_1 \mathbf{x} \geq \mathbf{b}_1$

이때, 부등식 좌변에 인공 변수 $\mathbf{y}$ 를 추가하여 다음과 같이 변환할 수 있다:

$\mathbf{A}_1 \mathbf{x} - \mathbf{y} = \mathbf{b}_1$

여기서 $\mathbf{y}$ 는 인공 변수이며, $\mathbf{y} \geq 0$ 을 만족한다.

단체법 테이블 설정
인공 변수를 도입한 후, 초기 단체법 테이블을 설정한다. 이때 인공 변수가 포함된 제약 조건을 기본 해로 사용하여 초기 해를 도출한다.
초기 기본 해 도출
인공 변수를 포함한 제약 조건을 기준으로 초기 기본 해를 구한다. 초기 기본 해는 단체법 알고리즘의 시작점이 된다. 만약 인공 변수가 포함된 제약 조건을 만족하지 않는다면, 추가적인 단계가 필요할 수 있다.

인공 변수로부터의 목적 함수 설정

인공 변수를 도입한 후, 초기 기본 해를 설정하는 과정에서 인공 변수들이 단체법에서 계속 남아 있으면 최적해가 될 수 없다. 이를 해결하기 위해 2단계 단체법에서는 목적 함수에 인공 변수를 포함시켜서 인공 변수를 제거하는 과정을 진행한다. 이때 인공 변수의 목적 함수 기여도는 최대한 낮춰야 한다.

목적 함수의 변환
인공 변수를 포함한 제약 조건에 따라 새로운 목적 함수를 설정한다. 예를 들어, 다음과 같은 문제에서 인공 변수 $\mathbf{y}$ 를 도입한 목적 함수는 다음과 같이 표현된다:

$\text{최소화} \quad Z = \mathbf{c}^\top \mathbf{x} + M \mathbf{y}^\top \mathbf{1}$

여기서 $M$ 은 매우 큰 상수로, 인공 변수 $\mathbf{y}$ 의 값이 최대한 0에 가까워지도록 유도하는 역할을 한다. 즉, 단체법의 과정에서 인공 변수의 영향을 최소화하여 최종 해에서 제거될 수 있도록 한다.

2단계 단체법의 첫 번째 단계
첫 번째 단계는 인공 변수들을 제거하는 과정이다. 인공 변수가 목적 함수에 영향을 주지 않도록, 이들을 제거한 새로운 기본 해를 찾기 위한 계산을 진행한다. 이 과정은 단체법 테이블에서 인공 변수를 제거하고 나머지 변수를 중심으로 기본 해를 계산하는 형태로 진행된다.
기본 해 갱신
단체법의 반복 과정을 통해 인공 변수가 포함된 해를 계속해서 갱신한다. 인공 변수의 값을 0으로 만드는 것이 목표이다. 만약 인공 변수를 포함한 제약 조건에서 인공 변수가 사라지지 않는다면 해당 제약 조건을 제거하거나 새로운 기본 해를 설정해야 한다.

초기 기본 해의 종료 조건

2단계 단체법에서 초기 기본 해 설정 과정이 완료되는 조건은 인공 변수가 모두 0이 되고, 기본 해가 유효해진 순간이다. 이때 단체법 테이블에서 인공 변수가 완전히 제거되고, 나머지 변수들로 최적화 문제를 해결할 수 있다. 1단계에서 인공 변수를 제거한 후, 다음과 같은 최종 형태의 기본 해가 도출된다:

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

이 기본 해를 바탕으로 2단계에서 실제 단체법 알고리즘을 적용하여 최적해를 찾는 과정이 시작된다.