균형 상태와 비균형 상태

1. 균형 상태

균형 상태는 선형계획법에서 제약 조건의 양쪽(자원과 요구)이 정확히 일치하는 상황을 말한다. 이는 특히 공급망 문제에서 자주 나타나는 경우로, 공급량과 수요량이 동일할 때를 의미한다.

선형 계획의 일반적인 형태는 다음과 같다:

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

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

여기서: - $\mathbf{A}$ 는 제약 조건의 계수 행렬이며, $m \times n$ 차원의 행렬이다. - $\mathbf{x}$ 는 $n$ -차원의 변수 벡터이다. - $\mathbf{b}$ 는 $m$ -차원의 자원 벡터로, 각 제약 조건의 우변 값이다. - $\mathbf{c}$ 는 목적 함수의 계수 벡터이다.

2. 균형 상태의 예시

균형 상태는 공급과 수요가 일치하는 경우에 나타난다. 예를 들어, 한 도시에 여러 공장에서 물품을 공급하고 여러 상점에서 그 물품을 수령할 때, 각 공장에서 공급되는 총 물량과 각 상점에서 요구하는 물량이 동일하다면, 이 문제는 균형 상태에 있다고 할 수 있다.

이때 균형 상태의 선형 계획 문제는 다음과 같이 나타낼 수 있다.

$\sum_{i=1}^{n} x_{i} = \sum_{j=1}^{m} d_j$

여기서: - $x_i$ 는 각 공급지 $i$ 에서 공급되는 물량 - $d_j$ 는 각 수요지 $j$ 에서 요구하는 물량

3. 비균형 상태

비균형 상태는 공급과 수요가 일치하지 않는 경우를 의미한다. 즉, 공급되는 자원의 양이 수요보다 많거나 적을 때 비균형 상태가 발생한다. 이 경우는 추가적인 가상 변수를 도입하여 균형 문제로 변환할 수 있다.

비균형 상태의 일반적인 예는 공급이 수요보다 많거나 적을 때이다. 이를 해결하기 위해 '더미' 변수, 또는 추가적인 변수를 도입하여 균형 문제로 재구성할 수 있다. 예를 들어, 공급이 수요보다 많을 때, 여분의 공급을 처리하기 위한 가상 수요지를 도입할 수 있다.

4. 비균형 상태의 처리 방법

비균형 문제를 해결하기 위한 방법은 다음과 같다:

가상 변수 도입: 공급이 수요보다 많을 경우, 여분의 공급을 가상 수요지에 배정하여 균형을 맞춘다. 이는 추가적인 제약 조건을 통해 처리된다.
문제의 재구성: 문제를 재구성하여 기존의 제약 조건에 가상 변수를 더함으로써 균형 문제로 변환한다. 예를 들어, 공급이 $S$ 이고 수요가 $D$ 인 경우, $S > D$ 라면, 여분의 $S - D$ 만큼을 가상 수요로 처리한다.

제약 조건은 다음과 같이 변경될 수 있다:

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

여기서: - $\mathbf{d}$ 는 가상 변수로, 공급과 수요의 차이를 보정한다.

5. 비균형 상태의 예시

비균형 상태를 다루기 위해 가상 변수를 추가하는 예를 살펴보겠다. 공급량이 수요량보다 많은 경우를 가정해 보자. 예를 들어, 두 개의 공급지 $S_1, S_2$ 가 있고 세 개의 수요지 $D_1, D_2, D_3$ 가 있다고 할 때, 공급량과 수요량이 다음과 같이 주어진다:

$S_1 = 100, \quad S_2 = 150$

$D_1 = 50, \quad D_2 = 80, \quad D_3 = 70$

총 공급량은 $250$ 이고, 총 수요량은 $200$ 이다. 이때 50만큼의 여분 공급량이 존재한다. 이 문제를 균형 상태로 만들기 위해 가상 수요지 $D_4$ 를 추가하고, 이를 통해 50만큼의 여분 공급량을 할당한다.

수식을 다시 작성하면:

$S_1 + S_2 = D_1 + D_2 + D_3 + D_4$

여기서 $D_4 = 50$ 이다. 가상 수요지의 도입으로 비균형 문제는 균형 문제로 변환되었다.

6. 균형 및 비균형 상태의 수학적 표현

균형 상태에서 선형 계획 문제는 다음과 같이 표현된다:

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

비균형 상태에서는 다음과 같이 가상 변수를 도입하여 수정된 제약 조건을 포함한다:

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

이때, $\mathbf{d}$ 는 가상 변수로, 공급과 수요의 차이를 나타내며, 이를 통해 문제를 균형 상태로 전환한다.

7. 비균형 문제의 해결 알고리즘

비균형 문제의 해결은 단순히 가상 변수를 추가하는 것뿐만 아니라, 다음과 같은 단계를 포함한다:

초기 가상 변수 설정: 공급량과 수요량의 차이를 계산하여 가상 수요지를 추가한다.
변환된 문제 해결: 변환된 균형 문제에 대해 기존의 선형 계획법 알고리즘(예: 단체법)을 사용하여 해를 구한다.
가상 변수 처리: 해가 도출된 후, 가상 변수에 할당된 값은 실제 자원 흐름과 무관하므로 제거한다.

이 과정을 통해 비균형 문제를 해결할 수 있으며, 실세계 응용에서 이러한 기법은 특히 물류 및 공급망 관리에서 중요한 역할을 한다.