3.2 동적 계획법의 적용
3.2.1 동적 계획법
일반적인 동적 시스템(dynamic system)은 시간을 나타내는 인덱스를 k 라고 할 때 식 (3.6)에서 알 수 있는 바와 같이 이전 시간대의 상태 (state)와 제어(control) 그리고 외란(disturbance)에 의해 다음 상태가 결 정되는 특성을 가지고 있다. 이는 부터 까지 총 개의 단 계에 대하여 일관되게 적용되는 항목이다. 각 변수의 의미는 표 3.1과 같다.
⋯ (3.6)
이산 시간에 대한 변수
시스템의 상태(state)를 나타내는 변수로서 번째 시간대에서 바라봤을 때 앞으로의 최적화를 위해 필요한
과거의 모든 정보를 포함하고 있는 변수
번째 시간대에서 선택된 제어(control) 또는 결정(decision)을 나타내는 변수
확률과정(probabilistic process)을 따르는 잡음(noise) 혹은 외란(disturbance)을 나타내는 변수
N 제어가 영향을 미치는 시계(time horizon)의 개수로서 시스템이 동작하는 단계(stage)의 수이기도 함 표 3.1 동적 시스템 및 비용함수를 구성하는 변수 설명
이러한 동적 시스템에서 각 단계에서의 비용을 나타내는 함수를
로 나타낼 수 있으며 전 단계에 대한 총 비용은 아래 식 (3.7)과 같다. 여기에서 은 전체 과정의 가장 마지막 단계에서 발 생하는 비용이다. 이 식에서 random parameter 가 존재하므로 총 비 용은 일반적으로 확률변수(random variable)에 의존하는 기댓값으로 표 현할 수 있다. 이것을 수식으로 나타내면 식 (3.8)과 같다.
(3.7)
(3.8)l Principle of Optimality
⋯
이 전체 문제(basic problem)의 최적해(optimal solution)라고 할 때 시간 의 상태 에서 시간 까지의 비용
(3.9)를 최소로 하는 하위 문제(sub-problem)을 고려할 때 전체 문제의 일
부분인
⋯
은 하위 문제의 최적해가 된다. 즉 초기 상태 및 최초의 결정이 어떤 것이었든 나머지 단계의 최적화된 결정은 최 초의 결정으로부터 도출된 상태에 대하여 최적정책을 이루는 것이어야 한다.
l 동적 계획법 알고리즘
초기 상태 에 대해서 전체 문제의 최적해로부터 나온 비용을 의미 하는 는 와 같으며 여기에서 는 시간 에서 시간 까 지 거꾸로(backward) 진행하는 알고리즘의 마지막 단계에서 구해진다.
알고리즘은 다음 식 (3.10)과 같다.
min
⋯ (3.10)
어떻게 제어를 해야 하는지를 의미하는 변수인 가 위의 식을 최소화한다면 정책(policy)
⋯
가 최적이 된다.는 번째 단계에서 시작했을 때의 최적의 기댓값이다.
동적 계획법 알고리즘은 마지막 단계에 대한 최소의 비용을 찾는 것 으로부터 시작된다. 알고리즘은 의 계산 결과를 이용하여
를 계산하는 방향, 즉 시간의 진행에 비추어 거꾸로 반복된다. 이 반복된 계산을 0번째 단계까지 반복한다. 이 과정에서 최적의 정책인
는 최초의 결정이 무엇이었는지에 관계없이 각 단계에서 동 적 계획법 알고리즘이 요구하는 최소화 문제를 만족시킨다 [9].
본 연구의 4장에서는 각 단계에서 최적의 결정을 수행하는 동적 계획 법을 적용하여 발전사업자 입장에서 기대수익을 최대화하는 양수발전기 입찰 전략을 찾고자 한다.