목적 함수 계수의 변화

민감도 분석에서 목적 함수 계수의 변화

선형계획법의 민감도 분석에서 중요한 부분 중 하나는 목적 함수 계수의 변화에 대한 영향을 분석하는 것이다. 선형계획 문제에서 목적 함수는 다음과 같이 표현된다:

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

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

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

계수 변화가 최적 해에 미치는 영향

목적 함수의 계수 $c_i$ 중 하나가 변할 때, 최적 해가 어떻게 변하는지 분석하는 것이 목적이다. 예를 들어, 특정 계수 $c_i$ 를 $c_i' = c_i + \Delta c_i$ 로 변화시켰을 때, 최적 해가 여전히 기존의 해가 될 수 있는지를 알아본다.

변화된 목적 함수는 다음과 같이 표현될 수 있다:

$z' = \mathbf{c'}^T \mathbf{x} = \left( \mathbf{c} + \Delta \mathbf{c} \right)^T \mathbf{x}$

이때, 계수 $\mathbf{c}$ 의 변동이 최적 해를 유지하는지, 혹은 새로운 해를 도출해야 하는지를 판단하려면 현재 기저 해의 변동 가능성을 분석해야 한다. 이를 위해, 단체법에서 기저 해를 사용해 민감도 분석을 수행한다.

최적 기저 해의 유지 조건

기저 해가 변하지 않는 경우는 목적 함수 계수의 변화가 현재 기저 해의 최적성을 유지할 때이다. 이를 분석하기 위해, 단체법에서 사용된 표 형식(Simplex Tableau)의 목적 함수 계수 부분을 살펴봐야 한다.

단체법에서 목적 함수는 단체 테이블의 마지막 행에 나타난다. 이때, 기저 변수가 포함되지 않은 비기저 변수들에 대한 계수는 아래와 같이 나타낼 수 있다:

$z_j = c_j - \mathbf{c_B}^T \mathbf{B}^{-1} \mathbf{A_j}$

여기서,
- $z_j$ 는 비기저 변수 $x_j$ 에 대한 감소 비용,
- $c_j$ 는 목적 함수의 원래 계수,
- $\mathbf{c_B}$ 는 기저 변수에 대응하는 목적 함수의 계수 벡터,
- $\mathbf{B}$ 는 기저 변수에 해당하는 제약 조건의 계수 행렬,
- $\mathbf{A_j}$ 는 비기저 변수 $x_j$ 에 대응하는 제약 조건의 열 벡터이다.

기저 해가 최적성을 유지하려면 모든 비기저 변수에 대해 $z_j \geq 0$ 이어야 한다. 그러므로, $c_j$ 가 변화한 후에도 이 조건을 만족하는지 확인해야 한다. 목적 함수 계수의 변화가 기저 해를 유지하는지를 판단하기 위한 조건은 다음과 같다:

$c_j' - \mathbf{c_B}^T \mathbf{B}^{-1} \mathbf{A_j} \geq 0$

여기서 $c_j' = c_j + \Delta c_j$ 로 대체하면, 새로운 조건은 다음과 같이 표현된다:

$(c_j + \Delta c_j) - \mathbf{c_B}^T \mathbf{B}^{-1} \mathbf{A_j} \geq 0$

즉, $\Delta c_j$ 의 변화가 일정 범위 내에 있어야 기저 해가 변하지 않고 유지될 수 있다는 것이다. 이 범위는 현재 기저 해의 비기저 변수들에 대한 감소 비용에 따라 결정된다.

변화 가능한 범위 계산

목적 함수 계수 $c_j$ 가 변할 수 있는 범위를 계산하기 위해, 위 조건을 재정리하면 다음과 같다:

$\Delta c_j \geq - (c_j - \mathbf{c_B}^T \mathbf{B}^{-1} \mathbf{A_j})$

이는 $c_j$ 가 변화할 수 있는 하한선을 나타낸다. 동일한 방식으로 상한선을 계산하면, $\Delta c_j$ 는 다음 범위 내에서 변화할 수 있다:

$- (c_j - \mathbf{c_B}^T \mathbf{B}^{-1} \mathbf{A_j}) \leq \Delta c_j \leq \text{상한선}$

이 범위 내에서 $\Delta c_j$ 가 유지되면, 최적 기저 해는 변경되지 않는다. 상한선은 문제의 특성에 따라 계산이 달라질 수 있다.

상한선 계산

목적 함수 계수의 변화에 대한 상한선은 각 비기저 변수에 대한 감소 비용 조건에 따라 다르다. 비기저 변수 $x_j$ 의 감소 비용 $z_j$ 가 최적성을 유지하기 위해서는 비기저 변수의 값이 양수로 변하지 않아야 한다. 이를 위해, 아래 조건을 만족해야 한다:

$z_j' = c_j' - \mathbf{c_B}^T \mathbf{B}^{-1} \mathbf{A_j} \geq 0$

이때 $c_j' = c_j + \Delta c_j$ 이므로, 변형된 식은 다음과 같다:

$(c_j + \Delta c_j) - \mathbf{c_B}^T \mathbf{B}^{-1} \mathbf{A_j} \geq 0$

이를 정리하면:

$\Delta c_j \geq - (c_j - \mathbf{c_B}^T \mathbf{B}^{-1} \mathbf{A_j})$

이 식은 $\Delta c_j$ 가 변화할 수 있는 하한선을 나타낸다. 상한선 역시 비슷한 방식으로 계산할 수 있으며, 기저 해를 유지하는 범위 내에서 $c_j$ 가 변화할 수 있는 상한선은 다음과 같이 정의된다:

$\Delta c_j \leq \text{상한선}$

이때 상한선은 기저 해에 영향을 주지 않는 한계까지의 값으로 설정되며, 문제에 따라 달라질 수 있다. 이러한 범위 내에서 목적 함수 계수가 변화하면 최적 기저 해는 유지될 수 있다.

기저 해가 변하는 경우

목적 함수 계수 $c_j$ 의 변화가 일정 범위를 벗어나면, 기저 해는 변할 수 있다. 이 경우 새로운 기저 해를 찾기 위한 단체법 절차를 다시 수행해야 한다. 새로운 기저 해가 도출되면, 그에 따라 새로운 해를 구하고 최적 해를 확인하는 과정이 필요하다.

기저 해가 변경될 경우, 표 형식에서 $z_j$ 의 값이 음수가 되어 비기저 변수가 기저 변수로 변경될 가능성이 있다. 이러한 경우, 해당 변수를 기저 변수로 변환하고 새로운 기저 해를 찾는 단계를 거친다.