제약 조건의 변화

선형계획 문제에서 제약 조건은 해 공간을 정의하는 중요한 요소 중 하나이다. 제약 조건이 변할 때, 최적 해는 달라질 수 있으며 이러한 변화를 분석하는 것이 민감도 분석의 중요한 부분이다. 특히 제약 조건의 우변 값이 변화할 때의 민감도를 고려하는데, 이를 통해 문제의 구조적인 변화를 이해할 수 있다.

제약 조건의 기본 형식

선형계획법에서 일반적인 제약 조건의 형태는 다음과 같이 표현된다:

$\mathbf{A} \mathbf{x} \leq \mathbf{b}$

여기서:

$\mathbf{A}$ 는 제약 조건 계수 행렬이다.
$\mathbf{x}$ 는 결정 변수 벡터이다.
$\mathbf{b}$ 는 제약 조건 우변 값을 나타내는 벡터이다.

이때, 제약 조건의 우변 $\mathbf{b}$ 의 각 요소가 변화할 때 최적 해가 어떻게 변하는지를 분석하는 것이 목적이다.

제약 조건 우변의 변화

제약 조건의 우변 $\mathbf{b}$ 가 변화한다고 가정해봅시다. 특히, $\mathbf{b}$ 의 특정 요소 $b_i$ 가 변화할 때, 최적 해와 목적 함수 값에 미치는 영향을 분석한다. 이 경우, 그림자 가격(Shadow Price) 개념이 도입된다.

$\Delta \mathbf{b}_i \quad \Rightarrow \quad \Delta \mathbf{x}^*$

그림자 가격은 제약 조건 우변 값이 1단위 증가할 때, 목적 함수 값이 얼마나 변하는지를 나타낸다. 예를 들어, 만약 제약 조건이 자원 사용량과 관련이 있다면, 자원이 추가로 1단위 제공될 때, 이익이 얼마나 증가하는지를 알 수 있다.

제약 조건의 경계 범위

제약 조건의 우변 $b_i$ 는 특정 범위 내에서 변화할 수 있으며, 이 범위 내에서 최적 해가 변하지 않는 허용 범위(Feasible Range)를 찾을 수 있다. 만약 $b_i$ 가 허용 범위를 벗어나면, 새로운 최적 해가 필요할 수 있다.

이때, $\mathbf{b}_i$ 의 허용 범위를 결정하는 수학적 과정은 단체법(Simplex Method)의 기본 해석 과정에서 나온다. 특히, 기본 해의 기저 행렬과 관련된 계산을 통해 $b_i$ 의 허용 범위를 결정할 수 있다.

허용 범위 계산

제약 조건 우변 $b_i$ 의 허용 범위를 계산하는 방법은 다음과 같이 요약된다. 먼저, 단체법에서 현재 기본 해를 나타내는 기저 행렬 $\mathbf{B}$ 를 이용한다. 기저 행렬은 기본 변수들에 해당하는 제약 조건 행렬의 일부로 구성되며, 이를 통해 최적 해를 결정할 수 있다.

기본 변수는 $\mathbf{B}^{-1} \mathbf{b}$ 로 표현되며, 제약 조건 우변 $\mathbf{b}$ 의 변화에 따라 해의 변화가 결정된다.

$\mathbf{x}_B = \mathbf{B}^{-1} \mathbf{b}$

이때, $\mathbf{b}$ 가 변화할 수 있는 허용 범위는 다음의 부등식을 만족해야 한다:

$\mathbf{B}^{-1} \mathbf{b} \geq 0$

이 부등식이 의미하는 바는, 제약 조건의 우변이 변할 때에도 기본 해가 여전히 유효해야 한다는 것이다. 만약 이 부등식이 성립하지 않는다면, 해가 허용 가능 영역을 벗어나기 때문에 새로운 기본 해를 찾아야 한다.

그림자 가격(Shadow Price)

제약 조건의 우변 값이 변화할 때, 목적 함수 값에 미치는 영향을 그림자 가격으로 나타낸다. 예를 들어, $b_i$ 가 1단위 증가할 때, 목적 함수 값이 얼마나 변하는지를 나타내는 값이 바로 그림자 가격이다. 이 값은 다음과 같이 계산된다.

$\lambda_i = \mathbf{c}_B^\top \mathbf{B}^{-1} \mathbf{a}_i$

여기서:

$\lambda_i$ 는 제약 조건 $i$ 의 그림자 가격이다.
$\mathbf{c}_B$ 는 기본 변수에 대응하는 목적 함수 계수이다.
$\mathbf{B}^{-1}$ 는 기저 행렬의 역행렬이다.
$\mathbf{a}_i$ 는 제약 조건 행렬 $\mathbf{A}$ 의 $i$ -번째 열이다.

이 수식은 $b_i$ 가 1단위 증가할 때, 목적 함수 값이 $\lambda_i$ 만큼 변한다는 것을 의미한다. 만약 $\lambda_i > 0$ 이면, 제약 조건이 완화될 때 목적 함수 값이 증가하고, $\lambda_i < 0$ 이면 목적 함수 값이 감소하게 된다.

민감도 분석을 위한 해석

우변 벡터 $\mathbf{b}$ 가 작은 범위 내에서 변할 때, 최적 해가 어떻게 변화하는지 분석하는 것이 민감도 분석의 주요 목표이다. 특히, $\mathbf{b}$ 의 특정 값에서 허용 가능한 범위 내에서 해가 변화하지 않는지를 분석함으로써, 제약 조건 변화에 따른 최적 해의 안정성을 평가할 수 있다.

제약 조건 변화는 종종 자원 할당 문제에서 발생하며, 새로운 자원이 추가되거나 제거될 때 최적 해가 어떻게 달라질지 분석하는 데 사용된다. 예를 들어, 특정 생산량을 제한하는 제약 조건이 완화될 경우, 이 변화가 총 이익에 미치는 영향을 계산할 수 있다.

다이어그램으로 기본 구조 표현

graph TD A[제약 조건 우변의 변화] B[그림자 가격 계산] C[허용 범위 계산] D[기본 해 분석] E[최적 해의 변화] A --> B B --> C C --> D D --> E

이 분석 절차는 제약 조건의 변화에 따른 최적 해의 민감도를 평가하는 데 필수적이다.