Geodesic
On the Dynamic Programming Algorithm under the Assumption of Monotonicity
Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences, Tome 134 (2014) no. 1, pp. 186-191

Voir la notice de l'article provenant de la source Math-Net.Ru

We formulate a discrete optimal control problem, which has not been considered earlier, which arises in the design of oil and gas networks. For this problem we set four theorems so that you can have a process, the optimal process and the optimum value. Necessary and sufficient conditions we give in Theorem 1. Under these conditions, by Theorem 1, we get not empty attainability intervals. For each interval, we choose the grid—a subset of its points, where by an arbitrary point of interval, we find the nearest point on the left. By means of such approximations, we define the Bellman functions on the grids. Using Bellman functions in Theorem 2 we give the process and we evaluate its deviation from the optimal process. In Theorem 2, we guarantee, that the given process is optimal when the attainability intervals and their grids coincide. In other cases, to get the optimal process, we use Theorem 3 and Theorem 4. In Theorem 3 we set that the process given in Theorem 2, is minimal in the lexicographical order which we introduce using Bellman functions. In Theorem 3 we give procedure that builds, if possible, in this order, the next process, skipping only the processes that are not optimal. We find the optimal process and the optimal value by Theorem 4, starting from the process given in Theorem 2, using one or more calls of the procedure given in Theorem 3.
Keywords: dynamic programming, Bellman functions, procedures, algorithms. 
V. G. Ovchinnikov. On the Dynamic Programming Algorithm under the Assumption of Monotonicity. Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences, Tome 134 (2014) no. 1, pp. 186-191. http://geodesic.mathdoc.fr/item/VSGTU_2014_134_1_a15/
@article{VSGTU_2014_134_1_a15,
     author = {V. G. Ovchinnikov},
     title = {On the {Dynamic} {Programming} {Algorithm} under the {Assumption} of {Monotonicity}},
     journal = {Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences},
     pages = {186--191},
     year = {2014},
     volume = {134},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSGTU_2014_134_1_a15/}
}
TY  - JOUR
AU  - V. G. Ovchinnikov
TI  - On the Dynamic Programming Algorithm under the Assumption of Monotonicity
JO  - Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences
PY  - 2014
SP  - 186
EP  - 191
VL  - 134
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VSGTU_2014_134_1_a15/
LA  - ru
ID  - VSGTU_2014_134_1_a15
ER  - 
%0 Journal Article
%A V. G. Ovchinnikov
%T On the Dynamic Programming Algorithm under the Assumption of Monotonicity
%J Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences
%D 2014
%P 186-191
%V 134
%N 1
%U http://geodesic.mathdoc.fr/item/VSGTU_2014_134_1_a15/
%G ru
%F VSGTU_2014_134_1_a15

[1] V. A. Emelichev, V. G. Ovchinnikov, “Application of the method of constructing successive plans to the problem of oil field equipping”, Dokl. Akad. Nauk BSSR, 26:4 (1982), 344–347 (In Russian) | Zbl

[2] V. G. Ovchinnikov, “Algorithms of dynamic programming for optimal and similar processes”, Proceedings of the Fifth All-Russian Scientific Conference with international participation (29–31 May 2008). Part 4, Matem. Mod. Kraev. Zadachi, Samara State Technical Univ., Samara, 2008, 107–112 (In Russian)

[3] V. G. Ovchinnikov, “On the algorithms of dynamic programming for optimal processes”, Vestn. Samar. Gos. Tekhn. Univ. Ser. Fiz.-Mat. Nauki, 2012, no. 3(28), 215–218 | DOI | Zbl