[공학]동적 계획법(Dynamic Programming)

목차

동적 계획법(Dynamic Programming)
1. 동적 계획법 기본개념
2. 분할과 연쇄적 의사결정
3. 후진접근법
4. 동적 계획법의 기본형태
5. 동적 계획법의 구조

본문내용

1. 동적 계획법 기본개념
지금까지 살펴본 많은 경영과학기법들은 주어진 제약조건하에서 최적해를 구하고 대부분 한 단계로 제한된 의사결정문제의 해결을 위한 것이었다. 다시 말하면 문제해결을 위해 변수들이 동시 또는 집합적으로 사용되어야 한다. 그러나 많은 실제 상황문제들은 복잡하고 여러 가지 다양한 조건들의 분석을 통한 연쇄적인 의사결정이 요구되기 때문에 기존의 경영과학기법들을 적용하는데 다소 문제가 있었다. 이 장에서 소개되는 동적계획법(dynamic programming)은 이러한 연쇄적인 의사결정상황에 사용되는 방법으로 다단계(multistage) 의사결정과정이라고도 불리 운다. 동적계획법의 기본 접근방법은 연쇄적(sequential) 의사결정에 관한 문제를 분해 또는 분할을 통하여 문제의 규모를 줄여가면서 해결해 나가는 것이다.
동적계획법의 선구자는 리차드 벨만(Richard Bellman)으로 그는 1940년대 후반부터 꾸준한 연구를 하여 1957년에 Dynamic Programming이라는 저서를 처음으로 발표하였다. 그 이후 동적 계획법의 실제 적용과 방법론적 관점에 중점을 둔 많은 연구들이 발표되어 왔다. 동적 계획법에는 선형계획법의 심플렉스법과 같이 해법이 따로 없고 단지 여러 단계의 문제를 풀 수 있는 제 방법들을 활용할 따름이다. 이러한 동적 계획법의 유연성 때문에 생산계획, 판매 및 마케팅. 전략계획, 재고관리, 장비유지 및 교체, 투자계획과 인력계획 등 여러 분야의 연쇄적인 다단계 의사결정문제에 널리 적용되고 있다.

2. 분할과 연쇄적 의사결정
동적 계획법은 의사결정문제가 여러 개의 작은 부속문제들로 분할(segmentation)되는 것에서 출발한다. 이때 각각의 부속문제를 단계(stage) 또는 의사결정점(decision point)이라고 한다. 특히 각 단계들은 상호연관성, 즉 다음 단계 부속문제의 해결에 영향을 미치므로 각 단계의 상호연관성이 항상 고려되어야 한다. 이러한 경우 특정 단계에서의 의사결정은 다음 단계의 의사결정에 영향을 주게 되므로 동적 계획법에서의 의사결정은 다단계적 또는 연쇄적이라고 할 수 있다. 예를 들어, 3년에 걸친 투자에 대한 의사결정시 투자에 따른 이익의 최대화를 위하여 매년 얼마의 자금을 어디에 투자해야 할 것인가를 결정해야 하는데 이를 단계적인 의사결정과정으로 나타내면

참고자료

· 경영과학 (출)민영사 박순달 저
· 신경영과학 (출)형설 이상문 저
· OR/MS 원론 (출)형성 이상용 저