파라미터 변동에 따른 해의 안정성 분석

민감도 분석의 개요

파라미터 변동에 따른 해의 안정성 분석은 선형계획법에서 매우 중요한 역할을 한다. 선형계획 문제에서 입력된 파라미터, 즉 목적 함수 계수 또는 제약 조건의 변화가 최적해에 미치는 영향을 분석하는 과정이다. 이러한 분석을 통해 현재 해가 작은 파라미터 변동에도 적절히 유지될 수 있는지, 또는 큰 변화가 발생할 때 새로운 해를 찾아야 하는지 판단할 수 있다.

목적 함수 계수 변화에 대한 안정성 분석

선형계획 문제에서 목적 함수 계수 벡터 $\mathbf{c}$ 가 변동할 때, 최적 해가 안정적으로 유지되는 구간을 찾는 것이 주요 목표이다. 이를 위해 기본해와 기본 계획(Basic Feasible Solution, BFS)을 바탕으로 분석할 수 있다.

먼저 표준형 선형계획 문제는 다음과 같은 형태를 띤다:

$\text{maximize } \mathbf{c}^\top \mathbf{x}$

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

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

기저해의 구조

기본해(BFS)는 주어진 제약 조건을 만족하는 해 중에서 변수가 기저(기준) 상태에 있는 경우를 나타낸다. 기저 변수들의 집합을 $\mathcal{B}$ , 비기저 변수들의 집합을 $\mathcal{N}$ 이라고 정의하면, 기저 상태에서 해를 구하는 문제는 다음과 같은 형태로 표현된다:

$\mathbf{x}_B = \mathbf{B}^{-1} \mathbf{b}, \quad \mathbf{x}_N = 0$

여기서 $\mathbf{B}$ 는 기저 변수들에 해당하는 제약 조건 행렬, $\mathbf{b}$ 는 제약 조건 우변 벡터이다.

기저해 $\mathbf{x}_B$ 가 최적해를 유지하려면 목적 함수의 기저 계수 변화가 해에 미치는 영향을 분석해야 한다.

목적 함수 계수의 민감도 분석 절차

목적 함수 계수 벡터 $\mathbf{c}$ 가 변할 때 해의 안정성을 분석하기 위해서는 다음 절차를 따른다.

단체법(Simplex method)을 이용한 최적 해 도출
초기 목적 함수 계수 $\mathbf{c}$ 를 기준으로 단체법을 적용하여 최적해 $\mathbf{x}^*$ 를 구한다.
최적성 조건 확인
단체법에서 최적성이 유지되기 위해서는 다음 조건이 만족되어야 한다:

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

이때, $\mathbf{c}_B$ 는 기저 변수들의 목적 함수 계수, $\mathbf{c}_N$ 은 비기저 변수들의 목적 함수 계수, $\mathbf{A}_N$ 은 비기저 변수들에 해당하는 제약 행렬이다.

계수 변화 범위 구하기
기저 변수들의 최적성을 유지하기 위해 $\mathbf{c}_B$ 의 변화 범위를 계산한다. 이는 주어진 제약 조건에서 가능한 값의 범위를 나타낸다. $\mathbf{c}_B$ 가 변할 수 있는 범위는 다음과 같이 계산할 수 있다:

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

해석
$\mathbf{c}_B$ 의 변화 범위 내에서 목적 함수가 안정적으로 유지되며, 해가 최적성을 유지한다는 것을 확인한다.

제약 조건 계수 변화에 대한 안정성 분석

제약 조건의 계수, 즉 행렬 $\mathbf{A}$ 또는 우변 벡터 $\mathbf{b}$ 의 변화가 해에 미치는 영향을 분석하는 것도 중요하다. 이러한 변화는 가능한 해 공간을 변화시키므로 최적해가 유지되는 범위를 파악해야 한다.

우변 벡터 $\mathbf{b}$ 의 변화에 따른 안정성 분석

우변 벡터 $\mathbf{b}$ 는 자원 제한이나 기타 제약 조건을 나타낸다. 따라서 우변 벡터가 변할 때, 해 공간과 최적해가 어떻게 변하는지를 분석할 수 있다.

우변 벡터 $\mathbf{b}$ 의 변화에 따른 민감도 분석은 아래와 같은 과정을 따른다:

기본 해의 변화 분석
$\mathbf{b}$ 의 변화가 기저 해에 미치는 영향을 분석하기 위해 기저 행렬 $\mathbf{B}$ 의 역행렬을 활용한다. 주어진 해가 최적성을 유지하기 위해서는 기저 변수 $\mathbf{x}_B$ 가 양수여야 한다. 이는 아래와 같은 형태로 표현할 수 있다:

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

여기서 $\mathbf{B}^{-1}$ 는 기저 행렬의 역행렬이며, $\mathbf{x}_B$ 는 기저 변수의 해이다.

변화 구간 계산
해가 양수 상태를 유지하기 위해서는 다음과 같은 조건을 만족해야 한다:

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

이 부등식을 이용하여 $\mathbf{b}$ 의 가능한 변화 범위를 구할 수 있다. 각 기저 변수 $x_i$ 에 대해 변화 가능 범위는 다음과 같다:

$\frac{b_i}{B_{ii}} \geq 0$

이때, $B_{ii}$ 는 기저 행렬의 대각 원소이며, $b_i$ 는 우변 벡터의 해당 요소이다.

최적성 조건 확인
우변 벡터 $\mathbf{b}$ 가 변할 때, 최적성이 유지되는지를 확인한다. 이때 해 공간이 변하지 않고, 최적해가 그대로 유지되는지 파악해야 한다. 최적성이 유지되기 위해서는 다음 조건이 만족되어야 한다:

$\mathbf{B}^{-1} (\mathbf{b} + \Delta \mathbf{b}) \geq 0$

여기서 $\Delta \mathbf{b}$ 는 우변 벡터의 변화량이다.

제약 조건 행렬 $\mathbf{A}$ 의 변화에 대한 안정성 분석

제약 조건 행렬 $\mathbf{A}$ 가 변할 때도 해가 어떻게 변하는지 분석할 필요가 있다. 이는 주로 특정 제약 조건이 약해지거나 강화되는 경우에 발생한다.

기저 행렬 변화 분석
제약 조건 행렬 $\mathbf{A}$ 가 변하면, 기저 행렬 $\mathbf{B}$ 도 변화할 수 있다. 따라서 기저 해를 구하는 과정에서 기저 행렬의 변화에 따른 영향을 분석해야 한다. 기저 행렬 $\mathbf{B}$ 가 변할 때, 그 역행렬 역시 달라지므로 이를 고려한 분석이 필요하다.
변화 구간 설정
제약 조건 행렬 $\mathbf{A}$ 의 각 요소가 변할 때 해의 안정성이 유지되는 구간을 찾기 위해 다음과 같은 조건을 적용한다:

$\mathbf{A}_B \mathbf{x}_B = \mathbf{b}$

여기서 $\mathbf{A}_B$ 는 기저 변수에 해당하는 제약 조건 행렬이며, $\mathbf{x}_B$ 는 기저 변수의 해이다.

제약 조건 행렬의 변화량 $\Delta \mathbf{A}$ 에 대해 다음과 같은 해석이 가능하다:

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

이를 통해 제약 조건 계수의 변화가 해에 미치는 영향을 분석하고, 안정성이 유지될 수 있는 변동 범위를 도출한다.

파라미터 변동에 따른 해의 안정성 분석: 결합 분석

목적 함수와 제약 조건의 동시 변동

실제 상황에서는 목적 함수 계수 $\mathbf{c}$ 와 제약 조건 우변 $\mathbf{b}$ 가 동시에 변동하는 경우가 발생할 수 있다. 이러한 경우를 분석하기 위해서는 두 파라미터의 상호작용을 고려하여 해의 안정성을 분석해야 한다.

기저 해의 변화
기저 해 $\mathbf{x}_B = \mathbf{B}^{-1} \mathbf{b}$ 는 우변 $\mathbf{b}$ 가 변할 때 달라진다. 동시에 목적 함수 계수 $\mathbf{c}$ 가 변할 때 최적해가 변경될 가능성이 존재한다.

먼저, 기저 해 $\mathbf{x}_B$ 가 양수인 상태를 유지하는 범위를 분석하고, 그 후 $\mathbf{c}$ 의 변동이 최적성 조건을 만족하는지 검토한다.

최적성 조건 및 가능 영역 변화
가능 영역이 제약 조건 우변 $\mathbf{b}$ 의 변동에 따라 달라질 수 있다. 가능 영역의 기하학적 구조는 선형 제약식에 의해 결정되는데, 이는 가능 영역의 다면체(polytop)를 형성한다. 우변 $\mathbf{b}$ 의 변화가 가능 영역을 어떻게 변형시키는지 이해하는 것이 필요하다.

또한, 목적 함수 계수 $\mathbf{c}$ 가 변동하면서 최적성이 유지되려면 다음의 단체법 최적성 조건이 충족되어야 한다:

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

이 조건은 $\mathbf{c}_B$ 의 변화 범위가 기저 변수 해 $\mathbf{x}_B$ 와 양립 가능해야 함을 의미한다.

동시 변동 분석
$\mathbf{c}$ 와 $\mathbf{b}$ 의 동시 변동에 대해 다음과 같은 결합 형태로 해석할 수 있다:

$\mathbf{c}_B^\top (\mathbf{B}^{-1} \mathbf{b} + \Delta \mathbf{b}) = \mathbf{c}_N^\top (\mathbf{A}_N \mathbf{B}^{-1} \mathbf{b} + \Delta \mathbf{b})$

위 식에서 $\Delta \mathbf{b}$ 는 $\mathbf{b}$ 의 변동, $\mathbf{c}_N^\top$ 는 비기저 변수의 목적 함수 계수 변동을 나타낸다.

이를 통해 두 파라미터가 동시에 변할 때 최적해의 안정성이 유지되는 범위를 도출할 수 있다.

다면체 해 공간의 기하학적 분석

선형계획 문제에서 중요한 개념 중 하나는 해 공간을 정의하는 다면체(polytop)이다. 이 다면체는 제약 조건에 의해 형성되며, 최적해는 이 다면체의 꼭짓점에 위치하게 된다.

해 공간의 구조

해 공간은 제약 조건 $\mathbf{A} \mathbf{x} \leq \mathbf{b}$ 에 의해 정의되는 다면체로 표현된다. 우변 $\mathbf{b}$ 가 변할 때, 다면체의 모양과 크기가 변할 수 있다. 이러한 변동이 최적해에 미치는 영향을 분석하기 위해서는 다면체의 기하학적 특성을 파악해야 한다.

극점과 기저 해
선형계획 문제에서 최적해는 가능 영역의 다면체의 극점(vertices)에 존재한다. 극점은 기본 변수들에 의해 결정되며, 기저 해로 표현된다. 기저 해는 다면체의 한 꼭짓점에 해당한다.
다면체의 경계 변화
우변 $\mathbf{b}$ 의 변화는 다면체의 경계를 이동시킬 수 있다. 우변이 증가하거나 감소할 때, 경계가 확장되거나 축소될 수 있으며, 이러한 변화가 최적해의 위치에 영향을 미칠 수 있다.
변동에 따른 가능 영역 분석
$\mathbf{b}$ 의 변화에 따라 다면체가 변형되면 최적해가 새로운 극점으로 이동할 가능성이 있다. 이를 분석하기 위해서는 각 기저 해의 범위를 계산하고, 해당 범위 내에서 우변 변동이 해의 안정성에 미치는 영향을 분석해야 한다.

기하학적 해석을 통한 안정성 확인

우변 벡터 $\mathbf{b}$ 의 변동에 따라 다면체의 구조가 변화할 때, 해가 어떻게 변화하는지 시각적으로 표현하는 것이 유리하다. 이러한 기하학적 분석을 통해 최적해가 변할 수 있는 지점을 예측할 수 있다.