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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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)  

This article is cited in 1 scientific paper (total in 1 paper)

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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  mathscinet  elib
  • Вестник Самарского государственного технического университета. Серия: Физико-математические науки
    Number of views:
    This page:168
    Full text:79
    References:50

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019