Previous |  Up |  Next

Article

Keywords:
operations research
Summary:
The main purpose of this article is to provide an exact theory of the dynamic programming on a sufficiently general basis. Let $M$ be a compact topological Hausdorff's space, let $\tilde {T}^M$ be the set of all continuous transformations of the space $M$ into itself. Suppose such a topology is introduced on $\tilde {T}^M$ that $\tilde {T}^M$ is Haousdorff's space and that the transformation $\phi(x,y)=y(x)$ of the product $M \otimes \tilde {T}^M$ into $M$ is continuous with respect to Tichonoff's topology on $M \otimes \tilde {T}^M$. Suppose $\tilde {T}^M$ is a compact subspace of $\tilde {T}^M$ and $\Cal M = M \otimes T^M \otimes \ldots \otimes T^M \otimes \ldots$. We define the transformations $P, N$ and the set $\Cal M^{(x_o)}$ as followe: For each $X=(x_0, y_0, y_1, \ldots)\in \Cal M$ it is: $PX=(y_0(x_0),y_1,\ldots),\ NX=x_0,\ \Cal M^{(x_0)}=\{X; X \in \Cal M, NX= x_0\}$. Suppose $\Psi$ is a continuous function defined on $\Cal M$ and $f(x_0)= max_{x\in \Cal M^{(x_0)}}\ \Psi(X)$. The dynamic programming problem can now be formulated as follows: For all $x\in M$ find the element (or elements) $\bar{X}\in \Cal M^{(x)}$ for which $\Psi(\bar{X})=f(x)$. Existence and uniqueness of the solution of this problem is proved and the method of succesive approximations is used to solve it in case when $\Psi(X)-\Psi(PX)=\Theta(x_0, y_0)$. Further the case $\Psi(X)=\sum^\infty_{i=0}\Theta_i(x_i, y_i)$ is considered and one minor example is solved.
References:
[1] Шрейбep H. А.: Задача динамического планирования и автоматы. Проблемы кибернетики V, Москва, 1961.
[2] Alexandrov P. S.: Úvod do obecné teorie množin a funkcí. Praha 1956.
[3] Бурбаки: Общая топология. Москва, 1961. Zbl 1160.68305
[4] Bellmann R.: Dynamic Programming. Princeton University Press, Princeton, New Jersey, 1957. MR 0090477 | Zbl 0081.36902
[5] Zimmermann K.: O jednom zobecnění úlohy dynamického programování. kandidátská disertační práce, Praha MFF UK, 1968.
Partner of
EuDML logo