+7 (495) 987 43 74 ext. 3304
Join us -              
Рус   |   Eng

Authors

Struchenkov V.

Degree
Dr. Sci. (Eng.), Professor, Senior Researcher, General Informatics Department, Russian Technological University (MIREA)
E-mail
str1942@mail.ru
Location
Moscow, Russia
Articles

The variational problems in linear structures routing

In linear structures routing we have the following problem: find the extremal of given functional, i.e 2D or 3D curve, which must consist of a special type elements. The parameters of elements are limited and their number is unknown. At first we must determine number of elements and after this we can find their optimal parameters.In the case of 2D extremal we shall consider a broken line and parabolic spline. The broken line is used as a longitudinal profile of railways and the parabolic spline is used as a longitudinal profile of roads. Initial problem was solved as multi-stage process using the methods of dynamic and nonlinear programming. On each stage we consider the different mathematical models of unknown extremal line: 1. A broken line with short elements similar to longitudinal profile of ground. This model allow us to find the initial approximation of unknown line using nonlinear programming. 2. The result of first stage give us opportunity to find number of elements using dynamic programming. 3. We use a special algorithm of nonlinear programming for solving initial problem with fixed number of elements and the result of second stage as initial approximation. In this article our purpose is to give a new algorithm for transformation a broken line to another line, which is the following spline: straight, clotoida, circle, clotoida, straight and so on.This algorithm is one of the implementations of dynamic programming. It can be used both in the design of new roads and in their reconstruction, as well as in the design of trenches for pipelines of various purposes.
Read more...

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...