Dynamic Programming (Multi-Stage Programming)

Presentation on theme: "Dynamic Programming (Multi-Stage Programming)"— Presentation transcript:

1 Dynamic Programming (Multi-Stage Programming)

2 Dynamic Programming이란?
의사결정 문제를 해결하기 위한 수학적 기법 전체 문제를 몇 단계의 부분문제(Sub-problem)로 나누어 해결 마지막 단계부터 차례로 각 단계의 문제를 첫 단계까지 거꾸로 처리함(Recursive Process) 각 단계의 결정 간의 상호 관계를 고려하여 부분문제를 해결 각 단계의 문제를 푼 후 다시 마지막 단계로 해를 역추적함 1957년 R. Bellman에 의하여 소개 된 이후 수많은 문제에 적용되고 있음

3 DP 예제1(Pricing Problem)
Djsm 회사의 사장은 향후 5년간 신제품에 대한 가격을 결정하려고 한다 그가 고려하고 있는 가격은 $5, $6, $7, $8 네 가지이다. 그러나 가격의 변동은 $1 이내로 제한된다. 가격에 따라 발생하는 이익은 각 해마다 달라진다.

4 DP 예제1(계속) 가격에 따른 이윤은 다음과 같다. 이윤을 최대화 하기 위한 가격 정책은?

5 DP 예제1(계속) 문제의 단계는 년도에 따라 5단계로 구성되며 각 단계에서 취할 수 있는 부분 해는 다음과 같이 계산 된다.

6 DP 예제1(계속) 1차년도까지의 부분 해를 구하면 다음과 같다

7 DP 예제1(계속) 다시 최대의 이윤 경로를 5차년도까지 구하면 다음과 같다
즉, $8-$8-$7-$8-$7의 가격 정책이 최적이다.

8 Principle of Optimality
최적성의 원리 다단계 결정과정에 대한 최적정책을 결정하는데 핵심적인 의미를 가지고 있음 처음의 상태와 처음의 결정이 무엇이든 간에 목표에 도달하는 나머지 과정은 이때까지의 결정의 결과로서 나타난 상태에 관하여 최적정책을 구성하여야 함 “An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first step” – R.E.Bellman(1957) The principle of optimality allows one to devide the total problem and solve the last decision stage, work backward and solve thw second-to-last decision, etc., until the first decision is solved

9 DP 예제2 (An Inventory-Production Problem)
한 회사는 다음과 같은 향후 4년간의 제품 수요에 대한 공급을 하여야 함 제품의 생산 단가는 $1이며 $3의 Setup Cost(고정비용)이 수반되며 한 주기 당 6개 이상을 생산 할 수 는 없음. 따라서 생산 비용은 다음과 같음. 다음 주기까지 재고를 유지하기 위한 비용은 unit 당 $0.5임 수요를 충족하는 최소 비용 정책은? 각 주기 별 생산량을 결정

10 DP 예제2(계속) 다음과 같이 DP문제로 정의 할 수 있음 각 주기 간의 재고량(Inventory)의 연결식은 다음과 같음
각 주기의 비용식은 다음과 같음

11 DP 예제2(계속) fn(In)을 n주기 부터 마지막까지의 최적(최소)비용식이라 하자 fn(In)은 주어진 In값에 따라 최소비용을 가져오는 결정변수 Xn 에 따라 달라짐. 결국 f1(I1)을 구하는 문제임! (I1 =0)

12 DP 예제2(계속) 4주기부터 문제를 시작함. 마지막 단계이므로 재고량이 Zero이므로 쉽게 해결할 수 있음

13 Summary for Period 3

14

15 Optimal Solution