Wykład 4
IV. Decyzje wielostopniowe, programowanie dynamiczne
Problem alokacji zasobów. Algorytm Bellmana.
Podstawy programowania dynamicznego opracowane zostały przez Richarda Bellmana i opublikowane w podstawowej pracy z tego zakresu badań Dynamic Programing /New Jersey 1957r/. Autor omówił w niej zasady podejmowania decyzji optymalnych w procesach wieloetapowych.
Charakterystyczną cechą tych procesów jest to, że składają się one z ciągu przedsięwzięć, w których efekty osiągnięte w poprzednim przedsięwzięciu wykorzystywane są do sterowania przebiegiem przedsięwzięć następnych.
Teoria programowania dynamicznego przedstawiona przez R. Bellmana daje rozwiązania decyzyjnych modeli tak deterministycznych jak i stochastycznych, także wtedy gdy analizowany proces jest procesem ciągłym, oraz gdy jest procesem dyskretnym.
Podstawą teorii jest zasada optymalności Bellmana - „polityka optymalna ma tę własność, że niezależnie od początkowego stanu i początkowej decyzji, pozostałe decyzje muszą stanowić politykę optymalną ze względu na stan wynikający z pierwszej decyzji”.
Zasada sformułowana przez R. Bellmana prowadzi do definicji równań funkcyjnych, tworzących układ równań rekurencyjnych, które stanowią model /obraz/ ciągu przedsięwzięć o których mowa powyżej.
Idea metody programowania dynamicznego sprowadza się do wyznaczenia optimum funkcji wielu zmiennych przez wielokrotne wyznaczenie optimum funkcji jednej zmiennej. Funkcje jednej zmiennej o których mowa są definiowane w szczególny sposób, w jaki?, przeanalizujmy przykład.
Inwestor dysponuje kapitałem K, który może zainwestować w n różnych przedsięwzięć. Na podstawie przeprowadzonych analiz, wynikających z oczekiwań związanych ze zwrotem poniesionych nakładów inwestycyjnych, oszacowano ciąg funkcji zwrotu nakładów
; gdzie
, i=1,…n, oznacza wartość zwrotu nakładów poniesionych na inwestycje w i - te przedsięwzięcie, zaś
wielkość poniesionych nakładów w i przedsięwzięcie.
Inwestor chce znać odpowiedź na następujące pytania:
Jak podzielić nakłady finansowe /kwotę K/ pomiędzy n przedsięwzięć, by łączny zwrot z tytułu poniesionych nakładów był maksymalny,
Jak duży będzie to zwrot nakładów, czy konieczna jest cała kwota nakładu by oczekiwany maksymalny zwrot uzyskać.
Rozwiązanie:
Niech
oznacza funkcję zwrotu nakładów. Oczekujemy takich decyzji, które określą nieujemne wartości
, i=1,…n, tak, że funkcja
przyjmie wartość maksymalną przy założeniu
K.
Postać analityczna funkcji nie jest zdefiniowana, należy zatem rozwiązać kwestię definicji tej funkcji jak?.
Etap I:
, oznacza zwrot nakładów poniesionych w całej kwocie nakładów K, tylko w przedsięwzięcie pierwsze,
K,
Etap II: Niech
, gdzie:
K, funkcja
pozwala wyznaczyć maximum zwrotu nakładów w pierwsze i drugie przedsięwzięcie łącznie.
Etap III:
, gdzie
K, funkcja
określa maximum zwrotu nakładów w przedsięwzięcie pierwsze, drugie i trzecie.
…………………………………………………………………………………
Etap n-1:
, gdzie
K, funkcja
wyznacza maximum zwrotu nakładów w przedsięwzięcie od pierwszego do n-1.
Etap n:
, gdzie
K.
Funkcja
, teza ta wynika z definicji funkcji
. Oznacza to, że po realizacji n etapów, w których definiujemy funkcje zwrotu nakładów w kolejno dołączane przedsięwzięcia otrzymujemy odpowiedź na sformułowane na wstępie pytania o wartość zwrotu łącznego oraz odpowiedź na pytanie o alokację nakładów.
Przykład: Zarząd pewnej firmy zamierza zainwestować w budowę sieci sklepów w trzech miejscowościach. Dysponuje kwotą 30 mln PLN, dział analiz opracował dane dotyczące zwrotu nakładów przy nakładach na poziomie 10, 20 i 30 mln PLN.
Nakłady |
Zwrot w miejsc. A |
Zwrot w miejsc. B |
Zwrot w miejsc. C
|
0 |
0 |
0 |
0 |
10 |
0,26 |
0,24 |
0,27 |
20 |
0,55 |
0,56 |
0,54 |
30 |
0,62 |
0,63 |
0,65 |
Dokonać takiej alokacji nakładów by łączny zwrot nakładów był maksymalny.
Etap I:
= 0,62. Gdyby Inwestor podjął decyzje o inwestycji tylko w miejscowości A, wówczas spodziewany zwrot nakładów wyniósłby 0,62 mln PLN.
Etap II:
, rozkład {0,0},
, {10,0},
,
, {0,20},
, {10,20}.
Etap III:
, rozkład {0,0,0},
, {0,0,10},
,
, {0,20,0},
, rozkład {0,20,10}.
Spodziewany maksymalny zwrot z inwestycji sięga 0,83 mln PLN. Wynik ten można osiągnąć inwestując 20 mln PLN w miejscowości B, dalsze 10 mln PLN należy zainwestować w miejscowości C, inwestycji w miejscowości A nie należy brać pod uwagę.
Powyższy wynik otrzymano przy założeniu iż zwrot nakładów został oszacowano w przestrzeni dyskretnej co oznacza, że oszacowano zwrot przy nakładach na poziomie 10,20 i 30 mln PLN. Niewątpliwie bardziej interesujący wynik otrzymalibyśmy zakładając, że zwrot nakładów ma charakter ciągły, co osiągniemy opisując zwrot nakładów za pomocą funkcji ciągłych.
Niech
,
,…,
są funkcjami ciągłymi aproksymującymi zwrot nakładów odpowiednio w miejscowości A1,A2 ,…, An, nakłady inwestycyjne na poziomie K. Określić tak zmienne
,…
, by łączny efekt
osiągnął wartość maksymalną, przy założeniu, że:
K oraz
.
Rozwiązanie:
Niech
,
,
……………………………………………………………………….
.
Przykład: Oszacowano parametry funkcji ciągłych, definiujących zwrot nakładów w trzy produkty finansowe:
,
,
, gdzie
, nakład inwestycyjny K=10 mln PLN.
Oszacować tak zmienne decyzyjne
/oznaczają wielkość nakładów odpowiednio w produkt pierwszy, drugi i trzeci/ aby łączny efekt;
osiągnął wartość maksymalną, przy założeniu, że:
oraz
.
Rozwiązanie:
Etap I: Oznaczamy taką wartość
dla której
, jest to tzw. punkt krytyczny funkcji
, gdzie
Warunek
jest spełniony dla
oraz
.
Wartość
, oraz
,
. Porównując te trzy wartości otrzymamy:
oraz
, zatem
dla
, gdzie
Etap II: Rozwiązujemy równanie
, gdzie:
,
tzn.
, stąd
.
Wartość
, oraz
,
.
Zatem w punkcie
realizuje się największa wartość funkcji
w przedziale [0;10]. Stąd
,
.
, tzn., że funkcja
osiąga maximum dla
,
,
, które wynosi 28.19mln PLN.