Все выпуски

В статье рассматривается экстремальная задача маршрутизации с ограничениями. В общей формулировке предполагается, что объектами посещения являются любые непустые конечные множества — мегаполисы. Основной прикладной задачей, рассматриваемой в данном исследовании, является задача оптимизации траектории движения инструмента для станков листовой резки с ЧПУ, известная как проблема пути резания. Эта проблема возникает на этапе разработки управляющих программ для станков с ЧПУ. Возможны и другие приложения. В частности, результаты исследования могут быть использованы в задаче минимизация дозы облучения при демонтаже системы радиационно-опасных элементов после аварий на АЭС и в транспортных проблемах. В качестве ограничений исследуются ограничения предшествования. Они могут быть использованы для уменьшения вычислительной сложности. В качестве основного метода исследования использовалось широко понимаемое динамическое программирование. Предлагаемая реализация метода учитывает ограничения предшествования и зависимость целевых функций от списка задач. Последняя относится к классу очень сложных состояний, которые определяют допустимость маршрута на каждом шаге маршрутизации, в зависимости от уже выполненных или, наоборот, еще не завершенных задач. Применительно к задаче резки зависимость целевой функции от списка задач позволяет уменьшать термические деформации материала при резке. В работе математическая формализация экстремальной задачи маршрутизации с дополнительными ограничениями, описание метода и полученный с его помощью точный алгоритм. Оптимизации подлежат порядок выполнения задач, конкретная траектория процесса, и его начальная точка.

The paper deals with an extremal routing problem with constraints. In the general formulation, it is assumed that the objects of visiting are any non-empty finite sets — megalopolises. The main applied problem considered in this study is the tool path optimization problem for CNC sheet-cutting machines, known as the Cutting Path Problem. This problem arises at the stage of developing control programs for CNC machines. Other applications are also possible. In particular, the results obtained in the chapter can be used in the problem of minimizing the radiation dose when dismantling a system of radiation-hazardous elements after accidents at nuclear power plants and in transport problems. Among tasks constraints, the precedence constraints are investigated. These constraints can be used to reduce computational complexity. As the main method, the study used broadly understood dynamic programming. The offered realization of the method takes into account the precedence constraints and the dependence of the objective functions on the task list. This dependence belongs to the class of very complex conditions that determine the route admissibility at each routing step, depending on the tasks already completed or, on the contrary, not yet completed. As applied to the Cutting Path Problem, the dependence of the objective function on the task list makes it possible to reduce thermal deformations of the material during cutting. The chapter provides a mathematical formalization of an extremal routing problem with additional constraints, a description of the method, and the exact algorithm obtained with its help. The order of task execution, the specific trajectory of the process, and the starting point are optimized.

Рассматривается плоская модель курсового движения автомобиля, с двумя степенями свободы (боковое перемещение центра тяжести и курсовой угол). Управление осуществляется поворотом управляемых колес. Система рассматривается как замкнутая система автоматического регулирования. В статье рассматривается нахождение «оптимальной» передаточной характеристики, наилучшей в некотором определенном смысле для замкнутой системы. Анализируются возможные критерии оптимизации. Показано, что наиболее подходящим критерием для осуществления управления данным объектом является минимум функционала от отклонения от заданной траектории направляющей точки (точки, расположенной на продольной оси автомобиля впереди по направлению движения) и угла поворота управляемых колес.

A flat model of the motor car’s directional motion with two degrees of freedom (lateral motion of the center of gravity and relative bearing) is considered. The control is performed by turning steering wheels. The system is regarded as a closed automatic control system. The paper discusses finding an optimal transfer characteristic which in some definite sense is the best for the closed system. Possible criteria of optimization are analyzed. It is shown that the minimum of the functional from the off-path jogging of the guiding point (the point located on the longitudinal axis of a motor car ahead in the direction of motion) and the turning angle of the steering wheels is the most appropriate criterion for controlling this object.

В данной работе изучены сечения производящего ряда для решений линейного многомерного разностного уравнения с постоянными коэффициентами и найдены рекуррентные соотношения, связывающие такие сечения. Как следствие, доказан многомерный аналог теоремы Муавра о рациональности сечений производящего ряда в зависимости от вида начальных данных задачи Коши для многомерного разностного уравнения. Для задач о числе путей на целочисленной решетке показано, что при подходящем выборе шагов сечения их производящего ряда представляют известные последовательности многочленов (Фибоначчи, Пелля и др.).

In this paper, we study the sections of the generating series for solutions to a linear multidimensional difference equation with constant coefficients and find recurrent relations for these sections. As a consequence, a multidimensional analogue of Moivre's theorem on the rationality of sections of the generating series depending on the form of the initial data of the Cauchy problem for a multidimensional difference equation is proved. For problems on the number of paths on an integer lattice, it is shown that the sections of their generating series represent the well-known sequences of polynomials (Fibonacci, Pell, etc.) with a suitable choice of steps.

Рассмотрены новые свойства криволинейного интеграла Римана-Стилтьеса. Доказано, что криволинейный интеграл Римана-Стилтьеса не зависит от пути интегрирования, если интегрируемая и интегрирующая функции зависят только от одной переменной. Найдено новое необходимое условие функциональной зависимости функций двух переменных. Предлагается новый подход к определению двойного интеграла Римана-Стилтьеса, который содержит не одну, а две интегрирующие функции. Рассмотрены общие свойства двойного интеграла Римана-Стилтьеса. Приведены способы вычисления двойного интеграла для случая гладких или кусочно-гладких интегрирующих функций. Получена одна формула для преобразования двойного интеграла Римана-Стилтьеса в повторный интеграл.

The article deals with the new properties of the Riemann-Stieltjes curvilinear integral. It is proved that the Riemann-Stieltjes curvilinear integral is independent of path of integration if an integrable and an integrating functions depend only on one variable. A new necessary condition of the functional dependence of functions of two variables is found. The author proposes a new approach to the definition of the Riemann-Stieltjes double integral, which contains not one but two integrating functions. General properties of the Riemann-Stieltjes double integral are discussed. Methods for calculating the double integral for the case of smooth or piecewise-smooth integrating functions are presented. A formula for the conversion of the Riemann-Stieltjes double integral into an iterated integral is obtained.

В настоящее время в рамках управления воздушным движением крайне важной является задача формирования оптимального безопасного расписания прибытия самолетов в точку слияния воздушных трасс. Безопасность результирующей очереди обеспечивается наличием безопасного временнóго интервала между соседними прибытиями в точку слияния. Изменение момента прибытия может обеспечиваться изменением скорости движения самолета и/или использованием схем, удлиняющих или укорачивающих его траекторию. Оптимальность результирующей очереди рассматривается с точки зрения дополнительных требований: минимизации отклонения назначенных моментов прибытия от номинальных, минимизации количества изменений порядка самолетов в очереди, минимизации расхода топлива и т.д. Минимизируемый критерий оптимальности, отражающий эти требования, часто выбирается как сумма индивидуальных штрафов каждому судну за отклонение назначенного момента прибытия от номинального. Функция индивидуального штрафа почти во всех статьях рассматривается либо как модуль отклонения, либо как функция, похожая на модуль, но с различными наклонами ветвей, что приводит к разному штрафу за задержку и ускорение. В целом, задача может быть разделена на две: одна связана с поиском оптимального порядка прибытия судов, вторая — с выбором оптимальных моментов прибытия при заданном порядке. Последняя подзадача достаточно просто решается, поскольку чаще всего может быть формализована как задача линейного программирования. Однако первая решается значительно сложнее, для ее решения применяются разнообразные методы — от эвристических и генетических процедур до подходов смешанного целочисленного линейного программирования. В статье предлагаются условия на параметры задачи, достаточные для того, чтобы порядок оптимальных моментов прибытия самолетов в точку слияния совпадал с порядком номинальных моментов. Это позволяет исключить первую подзадачу из решения всей задачи.

Nowadays, the problem of creating an optimal safe schedule for arrival of aircraft coming in several flows to a checkpoint, where these flows join into one, is very important for air-traffic management. Safety of the resultant queue is present if there is a safe interval between neighbor arrivals to the merge point. Change of an arrival instant of an aircraft is provided by changing its velocity and/or usage of fragments of the air-routes scheme, which elongate or shorten the aircraft path. Optimality of the resultant queue is considered from the point of some additional demands: minimization of the deviation of the actual aircraft arrival instant from the nominal one, minimization of order changes in the resultant queue in comparison with the original one, minimization of fuel expenditures, etc. The optimality criterion to be minimized, which reflects these demands, is often taken as a sum of penalties for deviations of the assigned arrival instants from the nominal ones. Each individual penalty is considered in almost all papers as either the absolute value of the difference between the assigned and nominal arrival instants or a similar function with asymmetric branches (which punishes delays and accelerations of an aircraft in different ways). The problem can be divided into two subproblems: one is a search for an optimal order of aircraft in the resultant queue, and the other is a search for optimal arrival instants for a given order. The second problem is quite simple since it can be formalized in the framework of linear programming and solved quite efficiently. However, the first one is very difficult and now is solved by various methods. The paper suggests sufficient conditions for the problem, which guarantee that the order of the optimal assigned instants is the same as the order of the nominal ones and, therefore, exclude the first subproblem.

Рассматривается «аддитивная» задача последовательного обхода мегаполисов (непустых конечных множеств), при посещении которых выполняются некоторые работы; перемещения и выполняемые работы оцениваются функциями стоимости, допускающими зависимость от списка заданий. Имеются ограничения различных типов, среди которых выделяются условия предшествования, используемые «в положительном направлении» (в интересах снижения сложности вычислений). Кроме того, в постановке присутствуют динамические ограничения, формирующиеся по мере выполнения заданий. Исследуемая постановка ориентирована на инженерные приложения, связанные с листовой резкой на машинах с ЧПУ. Исследуется подход к построению оптимальных решений на основе нестандартной версии динамического программирования (ДП). В рамках данного подхода учитываются ограничения различных типов, включая динамические ограничения, естественно возникающие при листовой резке деталей (в частности учитываются тепловые допуски, связанные с надежным отводом тепла из окрестностей точек врезки). При этом допускается комбинация «прямых» запретов на перемещения и выполнение врезки, а также системы штрафов. В последнем случае типично возникают функции стоимости с зависимостью от списка заданий. Применяемый вариант ДП позволяет оптимизировать точку старта, маршрут, отождествляемый с перестановкой индексов, и трассу (траекторию), согласованную с данным маршрутом. На этапе построения функции Беллмана используется экономичный вариант ДП, при котором весь массив значений этой функции не насчитывается, а определяется только система ее слоев (при условиях предшествования, типичных для задачи, связанной с листовой резкой, это приводит к существенному снижению вычислительных затрат). На основе ДП построен оптимальный алгоритм, реализованный на ПЭВМ; приведены результаты вычислительного эксперимента.

The “additive” problem of sequentially visiting megalopolises (nonempty finite sets) is considered; some tasks are executed as the megalopolises are visited. Permutations and operations are evaluated by cost functions that admit a dependence on the list of tasks. There are restrictions of different types, which include precedence conditions used in the “positive direction” (to reduce the complexity of calculations). In addition, this conception involves dynamical restrictions that are formed in the process of task execution. This conception is oriented to engineering applications associated with sheet cutting on CNC machines. An approach to constructing optimal solutions based on a nonstandard version of dynamic programming (DP) is investigated. This approach takes into account restrictions of different types, including dynamic constraints which naturally arise in sheet cutting applications (in particular, it takes into account heat tolerances related to diffusion of heat in the vicinities of tie-in points). In this regard, a combination of “direct” interdictions of movements and cutting and a system of penalties is allowed; in the latter case, cost functions with a dependence on the list of tasks arise. The variant of DP that is used allows one to optimize the selection of a starting point, the route, which is identified with a permutation of the indexes, and the trajectory corresponding to the above-mentioned route. An economical variant of DP is used at the stage of construction of the Bellman function. This conception allows avoiding calculation of the whole array of values of this function; instead, only the system of its layers is defined (in the case of using the precedence conditions, which are typical of the problem of sheet cutting, this conception results in a considerable reduction of calculation costs). An optimal DP-based algorithm is constructed and realized on PC, and the results of the computational experiment are presented.

Работа посвящена исследованию процессов распределения ресурсов в динамических ресурсных сетях, т.е. сетях, пропускные способности дуг которых зависят от времени. Распределение ресурса в сети происходит в дискретном времени, при этом ресурс каждой вершины распределяется только между смежными с ней вершинами по некоторым правилам. Проведено исследование процессов перераспределения ресурса в таких сетях. Основной задачей является разработка методов нахождения предельного состояния (распределения) ресурса в динамической ресурсной сети. Показано, что подход, основанный на построении вспомогательной сети, применим для сведения задачи о распределении ресурса в динамической сети к аналогичной задаче для вспомогательной сети. Для сильно регулярных периодических динамических сетей доказаны теоремы о существовании предельного состояния на вспомогательном графе. Для его нахождения можно использовать подходы, разработанные для решения задачи о кратчайшем пути в динамических сетях.

This paper is devoted to studying the processes of resource allocation in dynamic resource networks. In such networks, the capacities of the arcs depend on time. Resource allocation in the network occurs in discrete time. The resource of each vertex is distributed only between adjacent vertices according to some rules. The study of the processes of resource redistribution in such networks is carried out. The main goal is to develop methods for finding the limit state (distribution) of a resource in a dynamic resource network. It is shown that the approach based on the construction of an auxiliary network is also applicable to reduce the problem of resource allocation in a dynamic network to a similar problem in an auxiliary network. Theorems on the existence of a limit state on an auxiliary graph are proved for strongly regular periodic dynamical networks. To find the limit states, one can use the approaches which are developed for the shortest path problem in dynamic networks.

Рассматривается задача о конфликтном взаимодействии одного убегающего и группы преследователей. Все игроки обладают равными динамическими возможностями. Движение каждого из них описывается дифференциальным уравнением четвертого порядка. Убегающий обладает полной информацией, а преследователи знают только координаты всех игроков. Поимка понимается как совпадение ускорений, скоростей и координат игроков. Предполагается, что начальное положение, скорость и ускорение убегающего принадлежат заданному конусу. Кроме того, предполагается, что третья производная функции, задающей траекторию движения убегающего, в начальный момент времени также принадлежит этому конусу. Доказано, что если число преследователей меньше размерности пространства, то в игре можно избежать «мягкой поимки».

A problem of conflict interaction of one evader with a group of pursuers is considered. All players have equal dynamic capabilities. The motion of each player is defined by a fourth order differential equation. An evader has full information, and pursuers know positions of all players only. A capture is defined as equality of accelerations, velocities and positions of players. It is assumed that initial position, velocity and acceleration of an evader are inside of the given cone. It is also assumed that a third order derivative, defining evader's path, is initially inside of this cone too. It is proved that if the number of pursuers is less than the space dimension, then runaway occurs.

Проблема согласования семантики данных, представленных в рамках различных моделей, остается актуальной значительный промежуток времени. Прежде всего, это связано с удобством работы пользователей, которые привыкли к определенным инструментальным средствам, например, к электронным таблицам. Подготовленные в этих средах данные нуждаются в загрузке в централизованную базу данных, что позволяет избавиться от дублирования и противоречивости данных. Препятствием на этом пути является проблема согласования данных. Редактирование данных непосредственно в базе данных является сложной задачей для пользователей непрограммистов. Традиционным способом решения этой проблемы является разработка специальных приложений, которые имеют ограниченный функционал. В данной работе предлагается технология, которая позволяет редактировать данные в базе данных с использованием электронных таблиц, делая доступным их богатый функционал. Основным отличием от аналогичных подходов является использование модели «Трансформация», которая делает представление данных удобным для восприятия человеком. Поскольку модель данных «Трансформация» существенно отличается от реляционной модели, появляется необходимость согласования данных между базой данных и электронными таблицами. Для решения аналогичных проблем Л.А. Калиниченко предложил методику коммутативных преобразований в базах данных. В данной работе эта методика, с некоторыми изменениями, используется в алгоритмах передачи данных из базы данных в «Трансформацию» и обратно. В статье представлен обзор работ по проблеме согласования данных в различных источниках, представлено описание модели данных «Трансформация», в том числе: описание схемы таблицы, условий существования экземпляра таблицы и операций редактирования данных. В работе приводится описание алгоритма загрузки данных в таблицу из базы данных и алгоритма преобразования данных в базе данных в соответствии с изменениями в таблице, определены условия коммутативности преобразований, представлено доказательство корректности преобразований.

The problem of coordinating the semantics of data presented within different models has remained relevant for a significant period of time. First of all, this is related to the convenience of work for users who are accustomed to certain tools, for example, spreadsheets. The data prepared in these environments needs to be loaded into a centralized database, which makes it possible to get rid of duplication and inconsistency of data. An obstacle to this path is the problem of data reconciliation. Editing data directly in the database is a difficult task for non-programmer users. The traditional way to solve this problem is to develop special applications that have limited functionality. This paper proposes a technology that allows editing data in a database using spreadsheets, making their rich functionality available. The main difference from similar approaches is the use of the “Transformation” model, which makes the presentation of data convenient for human perception. Since the “Transformation” data model differs significantly from the relational model, there is a need to reconcile data between the database and spreadsheets. To solve similar problems, L.A. Kalinichenko proposed a method of commutative transformations in databases. In this paper, this technique, with some modifications, is used in algorithms for transferring data from a database to “Transformation” and back. The article presents an overview of works on the problem of data matching in various sources, a description of the data model “Transformation”, including: a description of the table schema, conditions for the existence of a table instance and data editing operations. The paper describes an algorithm for loading data into a table from a database and the algorithm for transforming data in a database in accordance with changes in the table, defines the conditions for the commutativity of the transformations, and presents a proof of the correctness of the transformations.

Рассмотрена задача оптимального управления движением космического аппарата при коррекции его положения в инерциальной системе координат за счет управляющих моментов, получаемых от ускорений инерционных маховиков бесплатформенной инерциальной навигационной системы. Полученное оптимальное управление обеспечивает плавное изменение ориентации космического аппарата, которое рассматривается как движение по кратчайшей траектории в конфигурационном пространстве специальной ортогональной группы $SO(3)$. Алгоритм управления реализуется с использованием оригинальной процедуры нелинейной сферической интерполяции кватернионов. Основными исполнительными органами ориентации динамического контура управления бесплатформенной инерциальной навигационной системой при решении задачи оптимального управления были выбраны четыре инерционных маховика (три - по осям космического аппарата, четвертый - по биссектрисе). Результаты моделирования верифицируются путем создания анимации корректирующего движения космического аппарата.

We consider the optimal control problem for spacecraft motion during correction of its position in an inertial coordinate system by means of control torques. Control torques arise from the acceleration of inertial flywheels of a strapdown inertial navigation system. We investigate optimal control, which ensures a smooth change in the spacecraft orientation. This smooth corrective motion is described as the motion along the shortest path in the configuration space of a special orthogonal group $SO(3)$. The shortest path coincides with the large circle arc of the unit hypersphere $S^3$. We also consider a control algorithm using the original procedure of nonlinear spherical interpolation of quaternions. Four inertial flywheels are used as the main executive bodies for orientation of the dynamic control loop of the strapdown inertial navigation system when solving the optimal control problem. Three flywheels are oriented along the axes of the spacecraft. The fourth flywheel is oriented along the bisector. The simulation results are presented. We consider examples for corrective motion in which the spacecraft has zero velocity and acceleration at the beginning and end of the maneuver. We give an animation of the corrective movement of the spacecraft. The proposed formalism can be extended to control the spacecraft motion at an initial angular velocity different from zero, as well as in the orbital coordinate system.