Authors

The variational problems in linear structures routing

Dynamic programming in applications of a special kind

This article discusses applied problems, for the solution of which the dynamic programming method developed by R. Bellman in the middle of the last century was previously proposed. This method, based on the use of the optimality principle and the recurrence equations resulting from it, made it possible to reduce the solution of many complex applied problems to the solution of a sequence of simpler problems of the same type. To date, with the help of dynamic programming, many practically important problems have been solved. However, when solving problems of large dimension, especially when developing systems in which the dynamic programming algorithm is built into a repeatedly repeated calculation cycle, the calculation time is unacceptably long even when using modern computers. The problem of increasing the efficiency of dynamic programming continues to be relevant. This is the purpose of this paper. It is established that various implementations of dynamic programming are possible when solving the same applied problems. Authors analyze the possibilities of increasing the efficiency of using dynamic programming with a detailed consideration of the specific features of applied problems, some of which allow obtaining recurrence formulas for calculating the optimal trajectory based on the optimality principle of R. Bellman without enumerating options. It is shown that many applied problems, for the solution of which a dynamic programming method was proposed with the rejection of options for paths leading to a specific state, also allows the rejection of hopeless states in the process of counting. This dramatically increases the effectiveness of dynamic programming both in terms of the used memory size and in terms of counting time. This statement is based on the us of specially designed experimental programs for calculations in order to evaluate the effectiveness of the new algorithm as applied to solving practical problems of both single-criterion and two-criterion ones. Examples of such problems and the corresponding algorithm for solving them are given. Read more...

Spline-approximation as the basis of computer technology design of linear structures routes

This article is a continuation of the article published in Journal of Applied Informatics nо.1 in 2019 [1]. In it, the problems of computer design of routes of various linear structures (new and reconstructed railways and highways, pipelines for various purposes, canals, etc.) are considered from a unified standpoint, as problems of approximating a sequence of points on plane of a smooth curve consisting of elements of a given type, i.e. spline. The fundamental difference from other approximation problems considered in the theory of splines and its applications is that the boundaries of the elements of the spline and even their number are unknown. Therefore, a two-stage scheme for finding a solution has been proposed. At the first stage, the number of spline elements and their parameters are determined using dynamic programming. For some tasks, this stage is the only one. In more complex cases, the result of the first stage is used as an initial approximation to optimize the spline parameters using nonlinear programming. Another complicating factor is the presence of numerous restrictions on the spline parameters, which take into account design standards and conditions for the construction and subsequent operation of the structure. The article discusses the features of mathematical models of the corresponding design problems. For a spline consisting of arcs of circles, mated by line segments, used in the design of the longitudinal profile of both new and reconstructed railways and highways and pipelines, a mathematical model is built and a new algorithm for solving a nonlinear programming problem is proposed, taking into account the structural features of the constraint system. In contrast to standard nonlinear programming algorithms, a basis is constructed in the zero-space of the matrix of active constraints and its modification is used when the set of active constraints changes. At the same time, to find the direction of descent at each iteration, no solution of auxiliary systems of equations is required at all. Two options for organizing the iterative optimization process are considered: descent through groups of variables in the presence of sections for independent construction of the descent direction and the traditional change of all variables in one iteration. Experimentally, no significant advantage of one of these options has been revealed. Read more...