민감도 분석의 개요 - 실험 도서관

선형계획법에서의 민감도 분석

선형계획법에서 민감도 분석은 최적해가 주어진 상태에서, 목적 함수의 계수 또는 제약 조건이 변화할 때 최적해가 어떻게 변하는지를 분석하는 방법이다. 즉, 민감도 분석을 통해 우리는 현재의 최적해가 얼마나 안정적인지를 평가할 수 있다. 이는 실제 상황에서 입력값이 변동될 가능성이 있기 때문에, 최적해의 안정성을 평가하는 것이 매우 중요하다.

민감도 분석의 주요 목표

최적해의 유지 가능성: 특정 파라미터가 변했을 때, 여전히 현재의 해가 최적해로 남는지 여부를 분석한다.
최적해의 변화 탐색: 파라미터가 특정 범위를 넘어설 때 새로운 최적해가 나타나는지를 평가한다.
비용 분석: 목적 함수의 계수가 변화할 때, 최적의 목적 함수 값이 어떻게 변화하는지를 확인한다.

목적 함수 계수 변화에 대한 민감도 분석

선형계획법 문제에서 목적 함수의 계수가 변화할 때, 최적해가 변할 수 있다. 이를 분석하기 위해 목적 함수의 계수를 아래와 같이 설정하자.

$\text{maximize } z = \mathbf{c}^{T} \mathbf{x}$

$\text{subject to } \mathbf{A} \mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq 0$

여기서, $\mathbf{c}$ 는 목적 함수 계수 벡터이고, $\mathbf{x}$ 는 결정 변수 벡터이다. $\mathbf{A}$ 는 제약 조건 행렬, $\mathbf{b}$ 는 제약 조건의 우변 벡터이다.

민감도 분석에서의 주요 질문은 다음과 같다.

$c_i$ 가 변할 때 최적해는 어떻게 변하는가?
$c_i$ 가 변해도 여전히 현재의 $\mathbf{x}$ 가 최적해로 남는가?

이러한 질문에 답하기 위해 우리는 목적 함수 계수의 변화가 가능한 범위를 구해야 한다. 일반적으로 이 범위는 비기저 변수와 기저 변수에 따라 달라진다.

기저 해(Basic Feasible Solution, BFS)와 민감도 분석의 관계

기저 해는 단체법에서 중요한 개념으로, 현재의 최적해가 기저 해에 속할 경우 민감도 분석을 통해 최적해가 유지되는 범위를 계산할 수 있다. 이를 위해 기저 변수와 비기저 변수의 변화를 고려하게 된다.

기저 변수 $\mathbf{B}$ 와 비기저 변수 $\mathbf{N}$ 를 사용하여, 최적해의 변화가 없을 때의 조건을 다음과 같이 설정할 수 있다.

$\mathbf{B} \mathbf{x}_B + \mathbf{N} \mathbf{x}_N = \mathbf{b}$

여기서, $\mathbf{x}_B$ 는 기저 변수의 값, $\mathbf{x}_N$ 은 비기저 변수의 값이다. 기저 해를 유지하기 위해 $\mathbf{x}_B$ 와 $\mathbf{x}_N$ 이 만족해야 할 조건을 계산할 수 있다.

제약 조건 변화에 대한 민감도 분석

제약 조건이 변화할 때도 최적해가 영향을 받을 수 있다. 이를 분석하기 위해 제약 조건의 우변 $\mathbf{b}$ 에 변화를 주어, 해당 변화가 최적해에 미치는 영향을 평가할 수 있다.

제약 조건이 $\mathbf{A} \mathbf{x} = \mathbf{b}$ 로 주어졌을 때, $\mathbf{b}$ 가 변할 수 있는 범위를 다음과 같이 계산할 수 있다.

$\mathbf{b} \rightarrow \mathbf{b} + \Delta \mathbf{b}$

이때, $\Delta \mathbf{b}$ 의 변화가 허용 가능한 범위 내에서 최적해가 유지될 수 있는지 여부를 분석하는 것이 목적이다.

목적 함수 계수의 변화 범위

민감도 분석에서 목적 함수 계수의 변화는 주로 기저 변수와 비기저 변수에 대한 민감도를 평가함으로써 이루어진다. 현재의 최적 기저 해가 계속 최적해로 유지되기 위한 목적 함수 계수의 허용 범위는 아래와 같이 계산할 수 있다.

목적 함수 계수 벡터 $\mathbf{c}$ 는 기저 변수에 대해서 다음과 같은 관계식을 만족해야 한다.

$\mathbf{c}_B = \mathbf{c}_N \mathbf{A}_N \mathbf{A}_B^{-1}$

여기서 $\mathbf{c}_B$ 는 기저 변수에 대응하는 목적 함수 계수이고, $\mathbf{c}_N$ 은 비기저 변수에 대응하는 목적 함수 계수이다. 이 관계식을 이용하여, 기저 변수를 유지하기 위한 $\mathbf{c}_B$ 의 허용 범위를 구할 수 있다.

이때, 기저 해가 변하지 않으면서 목적 함수의 계수가 변할 수 있는 최대 변화 범위를 계산하려면, 아래 조건을 충족해야 한다.

기저 변수에 대한 민감도: 현재 선택된 기저 해에서 목적 함수 계수의 변화가 기저 변수에 대한 값의 변화를 초래하지 않도록 해야 한다. 이를 위해서는 목적 함수 계수의 변화가 일정 범위 내에서 발생해야 한다.
비기저 변수에 대한 민감도: 비기저 변수에 대한 목적 함수 계수의 변화가 최적해에 영향을 미치는지 평가해야 한다. 이는 비기저 변수의 최적화 범위를 계산하여 해당 변수에 대한 민감도를 분석하는 과정이다.

이 과정을 통해 우리는 기저 해가 최적해로 유지되는 목적 함수 계수의 변화 범위를 구할 수 있다. 이러한 범위를 계산함으로써, 현재의 최적해가 어느 정도의 파라미터 변화까지 유지될 수 있는지를 평가할 수 있다.

제약 조건의 변화에 따른 민감도 분석

제약 조건의 우변 $\mathbf{b}$ 가 변화할 때, 최적해가 유지될 수 있는 범위를 계산하는 것도 민감도 분석의 중요한 부분이다. 제약 조건 $\mathbf{A} \mathbf{x} \leq \mathbf{b}$ 에서 $\mathbf{b}$ 의 변화가 허용 범위 내에 있는지 여부는 아래와 같은 방식으로 분석할 수 있다.

우선, 제약 조건이 $\mathbf{A} \mathbf{x} = \mathbf{b}$ 인 경우, $\mathbf{b}$ 가 변화하여도 기저 해가 최적해로 남기 위한 조건을 계산한다.

$\mathbf{b} \rightarrow \mathbf{b} + \Delta \mathbf{b}$

이때 $\Delta \mathbf{b}$ 는 제약 조건 우변의 변화량을 나타낸다. 기저 해가 유지되기 위해서는 $\Delta \mathbf{b}$ 의 변화 범위가 특정 값 이하로 제한되어야 한다.

이를 계산하기 위해서는 기저 행렬 $\mathbf{A}_B$ 의 역행렬을 사용하여, 제약 조건의 변동에 따른 해의 변화 정도를 분석해야 한다.

$\mathbf{x}_B = \mathbf{A}_B^{-1} (\mathbf{b} + \Delta \mathbf{b})$

이 수식을 통해 $\Delta \mathbf{b}$ 의 변화에 따라 기저 해가 어떻게 변하는지, 그리고 그 변화가 최적해에 어떤 영향을 미치는지를 평가할 수 있다. 이때 $\Delta \mathbf{b}$ 의 범위를 제한함으로써 최적해가 유지될 수 있는 조건을 구할 수 있다.

민감도 분석의 해석 방법

민감도 분석을 통해 구한 결과는 다양한 방식으로 해석될 수 있다. 일반적으로 목적 함수 계수나 제약 조건의 우변 값이 변화할 때, 최적해와 그에 따른 목적 함수 값이 어떻게 변화하는지 평가하는 데 중점을 둔다.

1. 목적 함수 계수의 변화 해석

목적 함수 계수의 변화 범위를 구한 후, 그 범위 내에서 목적 함수 계수가 변화할 경우 현재의 최적해가 그대로 유지될 수 있는지 해석할 수 있다. 예를 들어, $c_i$ 가 특정 범위 내에서 변할 때, 기저 해는 유지되며 최적해 역시 변하지 않는다.

이때, 목적 함수 값의 변화는 다음과 같은 방식으로 분석할 수 있다.

현재의 기저 해가 최적해로 남을 때: 목적 함수 계수의 변화가 $c_i$ 의 허용 범위 내에 있을 경우, 최적해는 변하지 않으며 목적 함수 값은 변화한다.
기저 해가 변할 때: 목적 함수 계수가 특정 범위를 넘어설 경우, 새로운 기저 해가 나타나며, 그에 따라 최적해 역시 달라지게 된다. 이 경우에는 새로운 기저 해에서 최적해를 다시 계산해야 한다.

2. 제약 조건의 변화 해석

제약 조건의 우변 값 $\mathbf{b}$ 가 변할 때, 기저 해가 유지될 수 있는 조건을 바탕으로 변화 범위를 계산한다. 일반적으로 우변 값이 변화하면 가능 영역(Feasible Region)이 변하게 되고, 그에 따라 최적해도 달라질 수 있다.

가능 영역의 변화: 제약 조건의 우변 값이 변하면, 선형계획 문제의 가능 영역이 확장되거나 축소될 수 있다. 가능 영역이 축소될 경우, 일부 기저 해가 가능 영역 밖으로 벗어날 수 있으며, 이로 인해 새로운 기저 해가 나타날 가능성이 생긴다.
최적해의 변화: 제약 조건의 우변 값이 변하여 가능 영역이 변하더라도, 현재의 최적해가 여전히 가능 영역 내에 남아 있을 수 있다. 이 경우, 최적해는 변하지 않으며, 그에 따른 목적 함수 값만 변화하게 된다.

3. 기저 해의 민감도 분석

기저 해의 민감도는 현재 선택된 기저 해가 변화하는 파라미터에 얼마나 민감한지에 대한 평가를 의미한다. 즉, 기저 해의 민감도는 현재의 최적 기저 해가 유지될 수 있는 파라미터의 허용 범위를 분석하는 것이다.

기저 해가 민감한 경우: 파라미터가 약간만 변해도 최적해가 크게 달라지는 경우, 해당 기저 해는 매우 민감하다고 할 수 있다. 이때, 민감도 분석을 통해 파라미터의 변화를 제한하는 것이 중요하다.
기저 해가 민감하지 않은 경우: 파라미터가 크게 변해도 현재의 기저 해가 유지되는 경우, 해당 기저 해는 비교적 안정적이라고 할 수 있다. 이 경우, 파라미터의 변화에 따른 위험이 낮다.

민감도 분석의 기법

민감도 분석을 수행하는 다양한 기법이 있으며, 대표적으로는 다음과 같은 방법들이 있다.

1. 그림을 이용한 기하학적 방법

작은 차원의 문제에 대해서는 기하학적 방법을 통해 직관적으로 민감도 분석을 할 수 있다. 예를 들어, 이차원 문제에서 목적 함수의 기울기나 제약 조건이 변화할 때 최적해가 어떻게 변하는지를 시각적으로 확인할 수 있다.

graph TD; A[해 공간] --> B(기저 해); B --> C(최적해); B --> D(변화된 최적해); C --> D;

2. 단체법 기반의 민감도 분석

단체법을 통해 최적해를 구한 후, Simplex Tableau를 이용하여 민감도 분석을 수행할 수 있다. Tableau 상에서 목적 함수 계수나 제약 조건의 변화가 허용 범위 내에 있는지 여부를 확인하는 것이 이 방법의 핵심이다.

Simplex Tableau를 이용한 민감도 분석 절차:
현재의 Simplex Tableau를 기반으로 목적 함수 계수 또는 제약 조건의 변화를 설정한다.
현재의 기저 해가 유지되는지를 평가한다.
변화가 허용 범위 내에 있는 경우, 최적해는 그대로 유지되며, 목적 함수 값만 변화한다.
허용 범위를 넘어설 경우, 새로운 기저 해를 찾아야 한다.