Wykład 4

IV. Decyzje wielostopniowe, programowanie dynamiczne

1. 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:

1. Jak podzielić nakłady finansowe /kwotę K/ pomiędzy n przedsięwzięć, by łączny zwrot z tytułu poniesionych nakładów był maksymalny,

2. 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 A₁,A₂ ,…, A_n, 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.