다단계 선형계획법은 의사결정이 시간에 따라 여러 단계로 나뉘어 진행되는 문제를 다루는 방법론이다. 일반적으로 이러한 문제는 한 번에 모든 결정을 내리는 것이 아니라, 각각의 단계에서 의사결정이 이루어지며, 이후의 결정을 통해 전체적인 목표를 최적화한다. 다단계 문제에서는 각 단계에서의 결정이 다음 단계의 문제에 영향을 미치기 때문에 상호 의존적인 구조를 가지며, 이는 수학적으로 표현하여 최적화 문제로 다룰 수 있다.

다단계 의사결정의 구조

다단계 의사결정 문제는 주어진 시간 $\{ t_1, t_2, \dots, t_n \}$에서 각각의 단계에서 결정이 이루어지며, 각 단계의 결정은 이전 단계의 결과에 의존한다. 이 구조는 아래와 같은 수학적 형태로 정의될 수 있다.

의사결정 변수 $\mathbf{x}_i$는 각 단계 $i$에서 선택되는 결정 변수이다. 즉, $i$번째 단계에서 의사결정자가 선택하는 값이다. 각 단계에서의 목적 함수는 다음과 같이 정의될 수 있다.

여기서 $f_i(\mathbf{x}_i, \mathbf{u}_i)$는 $i$번째 단계에서의 목적 함수이며, $\mathbf{u}_i$는 이전 단계의 결정으로부터 전달된 상태 변수이다. 상태 변수 $\mathbf{u}_i$는 다음과 같은 관계식을 만족한다.

이때, $g_i$는 $i$번째 단계에서 결정 변수 $\mathbf{x}_i$와 상태 변수 $\mathbf{u}_i$ 간의 변화를 나타내는 함수이다. 각 단계에서 가능한 결정은 제약 조건에 의해 제한되며, 이러한 제약 조건은 일반적으로 다음과 같은 형태를 갖는다.

여기서 $A_i$는 $i$번째 단계의 제약 조건을 나타내는 행렬이고, $\mathbf{b}_i$는 제약 조건에 따라 결정 변수가 가져야 할 상수 벡터이다.

단계별 최적화 문제

다단계 의사결정 문제는 각 단계에서 최적화를 수행하는 방식으로 해결될 수 있으며, 이를 수학적으로 풀어내기 위해서는 각 단계에서의 목적 함수와 제약 조건을 종합적으로 고려해야 한다. 특히, 각 단계에서의 결정이 이후 단계에 미치는 영향을 고려하여 전체 시스템의 최적화를 달성해야 한다.

다단계 의사결정 문제를 해결하기 위해 사용되는 방법은 크게 두 가지로 나눌 수 있다: 선제적 방법(forward approach)과 후향적 방법(backward approach)이다. 선제적 방법은 현재 단계에서 이후 단계를 미리 고려하여 최적 결정을 내리는 방식이며, 후향적 방법은 최종 단계부터 거슬러 올라가면서 최적의 결정을 찾아나가는 방식이다.

선제적 방법 (Forward Approach)

선제적 방법에서는 첫 번째 단계부터 시작하여 각 단계에서 다음 단계를 고려한 결정을 내린다. 이를 동적 계획법(Dynamic Programming)으로 설명할 수 있다. 동적 계획법에서는 다음 단계의 상태 변수 $\mathbf{u}_{i+1}$가 현재 단계의 의사결정 변수 $\mathbf{x}_i$에 어떻게 영향을 미치는지 계산하여, 현재 단계에서 최적의 결정을 내린다.

다단계 선형계획법에서 선제적 방법을 사용할 때는 각 단계에서의 문제를 풀기 위해 다음과 같은 과정이 반복된다.

1. 현재 상태에서의 목적 함수 계산: 현재 단계 $i$에서 목적 함수 $f_i(\mathbf{x}_i, \mathbf{u}_i)$를 계산한다.
2. 다음 단계로 전달될 상태 변수 계산: 상태 변수 $\mathbf{u}_{i+1}$를 $g_i(\mathbf{x}_i, \mathbf{u}_i)$에 의해 계산하여, 다음 단계로 전달될 상태를 정의한다.
3. 다음 단계에서의 최적화를 고려: 다음 단계에서의 목적 함수 $f_{i+1}(\mathbf{x}_{i+1}, \mathbf{u}_{i+1})$가 최적화될 수 있도록 현재 단계의 결정을 내린다.

이 과정에서 현재 단계의 결정이 최종 단계에 미치는 영향을 고려하여, 전체 최적화 문제를 해결할 수 있다. 선제적 방법의 주요 장점은 실시간 의사결정에 적합하다는 것이다. 즉, 시간이 진행되면서 결정이 점진적으로 이루어지는 문제에서 유리하게 작동한다.

후향적 방법 (Backward Approach)

후향적 방법은 마지막 단계부터 거꾸로 문제를 풀어나가는 방식이다. 이 방법은 마지막 단계에서 최적의 결정을 내린 후, 그 이전 단계에서 그 결정을 고려한 최적화를 수행하는 방식이다. 후향적 방법은 주로 벨만 방정식(Bellman Equation)을 기반으로 설명된다.

후향적 방법에서는 다음과 같은 절차를 따른다.

1. 최종 단계에서 최적화 수행: 최종 단계 $n$에서의 목적 함수 $f_n(\mathbf{x}_n, \mathbf{u}_n)$를 최적화한다.
2. 이전 단계로 거슬러 올라가며 최적화 수행: 단계 $i$에서 최적화를 수행할 때, 단계 $i+1$에서 최적화된 결과를 고려하여 최적의 $\mathbf{x}_i$를 선택한다.
3. 반복: 이 과정을 반복하여 첫 번째 단계까지 최적화를 완료한다.

후향적 방법은 특히 미래의 불확실성이 적거나, 문제의 규모가 크지 않은 경우에 적합한다. 이 방법은 미리 모든 단계의 결과를 예측한 후에야 결정을 내릴 수 있다는 점에서, 선제적 방법과는 대조적이다.

예시: 다단계 문제의 수학적 모델링

다음은 두 단계의 다단계 의사결정 문제를 예시로 다룬 간단한 모델이다.

1단계에서의 목적 함수는 다음과 같다.

제약 조건은 다음과 같다.

이때, $\mathbf{u}_2$는 $g_1(\mathbf{x}_1, \mathbf{u}_1)$로 결정된다. 2단계에서의 목적 함수는 다음과 같다.

제약 조건은 다음과 같다.

후향적 방법을 사용한다면, 2단계에서 먼저 최적의 $\mathbf{x}_2$를 계산한 후, 그 결과를 바탕으로 1단계에서의 최적화 문제를 풀이한다.

선형계획법에서의 다단계 의사결정 문제의 해결 방식

다단계 선형계획 문제는 복잡한 시스템에서 중요한 역할을 하며, 각 단계의 결정이 이후에 미치는 영향을 정량적으로 분석하는 것이 핵심이다. 이를 해결하는 주요 방법으로는 단순한 선형계획법을 적용하는 것 외에도 동적 계획법과 같은 방법이 자주 사용된다. 다단계 문제의 특성상, 각 단계에서의 최적화는 일반적인 선형계획법의 문제와 비교하여 더 복잡해질 수 있지만, 효과적인 방법론을 통해 최적화할 수 있다.