RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Editorial staff Guidelines for authors License agreement Editorial policy Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Vestn. Samar. Gos. Tekhn. Univ., Ser. Fiz.-Mat. Nauki [J. Samara State Tech. Univ., Ser. Phys. Math. Sci.]: Year: Volume: Issue: Page: Find

 Vestn. Samar. Gos. Tekhn. Univ., Ser. Fiz.-Mat. Nauki [J. Samara State Tech. Univ., Ser. Phys. Math. Sci.], 2014, Issue 1(34), Pages 186–191 (Mi vsgtu1257)

Computer Science

On the Dynamic Programming Algorithm under the Assumption of Monotonicity

V. G. Ovchinnikov

Samara State Technical University, Samara, 443100, Russian Federation

Abstract: 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

DOI: https://doi.org/10.14498/vsgtu1257

Full text: PDF file (563 kB) (published under the terms of the Creative Commons Attribution 4.0 International License)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.7
MSC: Primary 90B10; Secondary 90C90, 65K05
Original article submitted 01/IX/2013
revision submitted – 13/XII/2013

Citation: V. G. Ovchinnikov, “On the Dynamic Programming Algorithm under the Assumption of Monotonicity”, Vestn. Samar. Gos. Tekhn. Univ., Ser. Fiz.-Mat. Nauki [J. Samara State Tech. Univ., Ser. Phys. Math. Sci.], 1(34) (2014), 186–191

Citation in format AMSBIB
\Bibitem{Ovc14} \by V.~G.~Ovchinnikov \paper On the Dynamic Programming Algorithm under the Assumption of Monotonicity \jour Vestn. Samar. Gos. Tekhn. Univ., Ser. Fiz.-Mat. Nauki [J. Samara State Tech. Univ., Ser. Phys. Math. Sci.] \yr 2014 \vol 1(34) \pages 186--191 \mathnet{http://mi.mathnet.ru/vsgtu1257} \crossref{https://doi.org/10.14498/vsgtu1257} \zmath{https://zbmath.org/?q=an:06968835} \elib{http://elibrary.ru/item.asp?id=22813970} 

• http://mi.mathnet.ru/eng/vsgtu1257
• http://mi.mathnet.ru/eng/vsgtu/v134/p186

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. V. G. Ovchinnikov, “K dinamicheskomu programmirovaniyu po leksikograficheski uporyadochennym znacheniyam pri predpolozheniyakh monotonnosti”, Svyaz teorii i praktiki nauchnykh issledovanii, Sbornik statei Mezhdunarodnoi nauchno-prakticheskoi konferentsii, Ufa, 2016, 4–10
•  Number of views: This page: 168 Full text: 79 References: 50