Changeset 1090 for applications/dual/SIDP/text/ch1.tex
- Timestamp:
- 06/13/10 17:27:15 (14 years ago)
- Files:
-
- 1 modified
Legend:
- Unmodified
- Added
- Removed
-
applications/dual/SIDP/text/ch1.tex
r919 r1090 1 1 DEFINICNI OBORY 2 2 \section{Formulace � stochastick� �� 3 �t�m pojmem v teorii ��e \emph{syst�. Syst�je �t sv�, kterou chceme poznat ��. Budeme-li p�kl�t diskr��ovahu �u, stav syst� v �ov� 3 �t�m pojmem v teorii ��e \emph{syst�. Syst�je �t sv�, kterou chceme poznat ��. Budeme-li p�kl�t diskr��ovahu �u, stav syst� v �ov�okam�iku $t$ pod��� horizontu d�y $N$ popisuje syst�rovnic 4 4 \begin{equation} 5 5 \label{sys} … … 10 10 V � ��� v�dy p�sanou ztr�vou (resp. �vou) funkci 11 11 \begin{equation} 12 g(x_{ 0:N},u_{0:N-1},w_{0:N-1}).12 g(x_{1:N},u_{0:N-1}). 13 13 \end{equation} 14 14 15 Ozna� $U(x_t)$ mno�inu p�tn�d�ch z�h� syst�ve stavu $x_t$. P osloupnost��c� strategi�\pi=\mu_{0:N-1}$ budeme rozum�posloupnost zobrazen�\begin{equation}15 Ozna� $U(x_t)$ mno�inu p�tn�d�ch z�h� syst�ve stavu $x_t$. P�tnou ��trategi�\pi=\mu_{0:N-1}$ budeme rozum�posloupnost zobrazen�\begin{equation} 16 16 \label{con} 17 17 \mu_t(x_t)=u_t \, \qquad t=0,1,\ldots,N-1, … … 22 22 \begin{equation} 23 23 \label{los} 24 J_\pi(x_0)=\E_{w_{0:N-1}}\left\{g(x_{ 0:N},\mu_{0:N-1}(x_{0:N-1}),w_{0:N-1})\right\}.24 J_\pi(x_0)=\E_{w_{0:N-1}}\left\{g(x_{1:N},\mu_{0:N-1}(x_{0:N-1}))\right\}. 25 25 \end{equation} 26 26 27 27 �ohou je potom naj�takovou $\pi^*$, pro kterou plat�\begin{equation} 28 J_{\pi^*}(x_0)=\min_{\pi \in \Pi}J_\pi(x_0) .28 J_{\pi^*}(x_0)=\min_{\pi \in \Pi}J_\pi(x_0), 29 29 \end{equation} 30 kde $\Pi$ zna�mno�inu v�ech p�tn�d�ch strategi� 30 31 31 32 Celkov�e tedy jedn� optimaliza� � nal� takovou posloupnost funkc�eqref{con}, kter�inimalizuje o��nou ztr�vu \eqref{los} za podm�k \eqref{sys}. 32 33 33 34 \section{Pou�it�ynamick� programov� p��en�lohy stochastick� �� aditivn�tr�u} 34 �ohu stochastick� ��ak, jak byla definov� v p�oz��i, nelze obecn�e�it. Je tedy pot�� n�k bl� specifikovat. V tomto sm� je mo�n�mezit se na n�k�i��var ztr�v�unkce \eqref{los}. Jako vhodn�e �en�eukazuje uva�ovat tzv. aditivn�var ztr�v�unkce, tedy �e existuj�unkce $g_t$ takov��e m� ps�35 �ohu stochastick� ��ak, jak byla definov� v p�oz��i, nelze obecn�e�it. Je tedy pot�� n�k bl� specifikovat. V tomto sm� je mo�n�mezit se na n�k�i��var ztr�v�unkce \eqref{los}. Jako vhodn�e ukazuje uva�ovat tzv. aditivn�var ztr�v�unkce, tedy �e existuj�unkce $g_t$ takov��e m� ps� 35 36 \begin{equation} 36 37 \label{adi} 37 g(x_{ 0:N},u_{0:N-1},w_{0:N-1})=g_N(x_N)+\sum_{t=0}^{N-1}g_t(x_t,u_t,w_t)38 g(x_{1:N},u_{0:N-1})=\sum_{t=1}^{N-1}g_t(x_{t+1},u_t). 38 39 \end{equation} 39 40 40 41 O��nou ztr� \eqref{los} potom m� p�t do tvaru 41 42 \begin{equation} 42 J_\pi(x_0)=\E_{w_{0:N-1}}\left\{ g_N(x_N)+\sum_{t=0}^{N-1}g_t(x_t,\mu_t(x_t),w_t)\right\}43 J_\pi(x_0)=\E_{w_{0:N-1}}\left\{\sum_{t=0}^{N-1}g_t(x_{t+1},\mu_t(x_t))\right\}. 43 44 \end{equation} 44 45 45 Takto specifikovan�loha se d�e�it pou�it�dynamick� programov� []. Dynamick�rogramov� je p�p k ��ptimaliza�ch � na kter�e m� d�t jako na posloupnost rozhodnut�pro kter�lat�zv. princip optimality. Ten � �e optim��osloupnost rozhodnut��u vlastnost, �e pro libovoln�te� stav a rozhudnut�us��chna n�eduj� rozhodnut�ptim��zhledem k v��zhodnut�rvn�. D� �e pro ztr� tvaru \eqref{adi} plat�rincip optimality je snadn�e ho nal� nap�d v [ref].46 Takto specifikovan�loha se d�e�it pou�it�dynamick� programov� \cite{bellman1957dynamic}. Dynamick�rogramov� je p�p k ��ptimaliza�ch � na kter�e m� d�t jako na posloupnost rozhodnut�pro kter�lat�zv. princip optimality. Ten � �e optim��osloupnost rozhodnut��u vlastnost, �e pro libovoln�te� stav a rozhudnut�us��chna n�eduj� rozhodnut�ptim��zhledem k v��zhodnut�rvn�. D� �e pro ztr� tvaru \eqref{adi} plat�rincip optimality je snadn�e ho nal� nap�d v \cite{bertsekas1995dynamic}. 46 47 47 48 P��en�lohy stochastick� �� aditivn�tr�u je tedy mo�n�ostupovat, jak je u ���moc�ynamick� programov� zvykem. Minim��odnotu st� ztr� od okam�iku $t$ do $N$ v z�slosti na $x_t$ ozna�e $J_t(x_t)$. M� pro ni ps� 48 49 \begin{gather} 49 J_N(x_N)= g_N(x_N)\\50 J_t(x_t)=\min_{u_t \in U(x_t)}\E_{w_t}\left\{g_k(x_ t,u_t,w_t)+J_{t+1}(f_t(x_t,u_t,w_t))\right\} \qquad t=0,\ldots,N-150 J_N(x_N)=0\\ 51 J_t(x_t)=\min_{u_t \in U(x_t)}\E_{w_t}\left\{g_k(x_{t+1},u_t)+J_{t+1}(x_{t+1})\right\} \qquad t=0,\ldots,N-1. 51 52 \end{gather} 52 53 53 P��en�udeme postupovat od konce �� horizontu a postupn�ledat $J_t(x_t)$. Potom libovoln�\pi=\{\mu_0,\ldots,\mu_{N-1}\}$, kter�pl� syst�rovnic 54 P��en�udeme postupovat od konce �� horizontu a postupn�ledat $J_t(x_t)$. Pro v� $x_{t+1}$ se pou�ije rovnice \eqref{sys}. 55 Libovolnou ��trategii $\pi=\{\mu_0,\ldots,\mu_{N-1}\}$, kter�pl� syst�rovnic 54 56 \begin{equation} 55 57 \label{impl} 56 58 J_t(x_t)=\E_{w_t}\left\{g_k(x_t,\mu_t(x_t),w_t)+J_{t+1}(f_t(x_t,\mu_t(x_t),w_t))\right\} \qquad t=0,\ldots,N-1 57 59 \end{equation} 58 je optim��osloupnost rozhodnut�60 pak nazveme optim��osloupnost�ozhodnut�