Все выпуски

Для произвольной игровой задачи наведения на множество предложен метод преобразования к задаче наведения «в момент».

The method of transformation of the guidance problem for the conict-controlled system into the problem of guidance "into the moment" is suggested. The transformation is realized by changing the dynamic function.

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

The paper is concerned with the randomized Nash equilibrium for a nonzero-sum deterministic differential game of two players. We assume that each player is informed about the control of the partner realized up to the current moment. Therefore, the game is formalized in the class of randomized non-anticipative strategies. The main result of the paper is the characterization of a set of Nash values considered as pairs of expected players' outcomes. The characterization involves the value functions of the auxiliary zero-sum games. As a corollary we get that the set of Nash values in the case when the players use randomized strategies is a convex hull of the set of Nash values in the class of deterministic strategies. Additionally, we present an example showing that the randomized strategies can enhance the outcome of the players.

Рассматривается модель хаотического движения пластинки в вязкой жидкости, описываемая колебательной системой трех обыкновенных дифференциальных уравнений с квадратичной нелинейностью. В ходе бифуркационного исследования особых точек системы построены карты типов особых точек и найдено уравнение поверхности в пространстве параметров диссипации и циркуляции, на которой происходит бифуркация Андронова-Хопфа рождения предельного цикла. При дальнейшем изменении параметров вблизи поверхности Андронова-Хопфа найдены каскады бифуркаций удвоения периода цикла Фейгенбаума и субгармонические каскады Шарковского, заканчивающиеся рождением цикла периода три. Получены выражения для седловых чисел седлоузла и двух седлофокусов и построены их графики в пространстве параметров. Показано, что в системе реализуются гомоклинические каскады бифуркаций при разрушении гомоклинических траекторий седлофокусов. Существование гомоклинических траекторий седлофокусов доказано численно-аналитическим методом. Графики старшего показателя Ляпунова и бифуркационные диаграммы показывают, что при изменении коэффициентов диссипации система в несколько этапов переходит к хаосу.

We consider the model of chaotic motion of a plate in a viscous fluid, described by an oscillatory system of three ordinary differential equations with a quadratic nonlinearity. In the course of the bifurcation study of singular points of the system, maps of the types of singular points are constructed and a surface equation is found in the space of dissipation and circulation parameters on which the Andronov-Hopf bifurcation of the limit cycle creation takes place. With a further change in the parameters near the Andronov-Hopf surface, cascades of the period doubling doubling of the Feigenbaum cycle and the Sharkovsky subharmonic cascades, ending with the creation of a cycle of period three, are found. Expressions are obtained for saddle numbers of the saddle-node and two saddle-foci and their plots are plotted in the parameter space. It is shown that homoclinic cascades of bifurcations are realized in the system with the destruction of homoclinic trajectories of saddle-foci. The existence of homoclinic trajectories of saddle-foci is proved by a numerical-analytical method. The graphs of the largest Lyapunov exponent and the bifurcation diagrams show that when the dissipation coefficients change, the system switches to chaos in several stages.

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

This paper presents a novel approach to interpreting logical formulas for synthesizing algorithms and programs. The proposed method combines features of Kleene realizability and Gödel's “dialectica” interpretation but does not rely on them directly. A simple version of positive predicate logic without functions is considered, including conjunction, disjunction, implication, and universal and existential quantifiers. A new realizability semantics for formulas and sequents is described, which considers not just a realization of a formula, but a realization with additional support. The realization roughly corresponds to Kleene realizability. The support provides additional data in favor of the correctness of the realization. The support must confirm that the realization works correctly for the formula under any valid conditions of application. A proof language is presented for which a correctness theorem is proved showing that any derivable sequent has a realization and support confirming that this realization works correctly for this formula under any valid conditions with a suitable interpreter for the programs used.

Для данного уравнения рассмотрена периодическая краевая задача. У задачи существует счетное число периодических по временной переменной плоских волн. Исследован вопрос об их устойчивости и бифуркациях. Все результаты получены аналитически и основаны на асимптотических методах нелинейной динамики.

Periodic boundary value problem the name of which is given in the title of this article is considered in this work. There is a countable number of plane waves which are periodic on according to time variable. The question of their stability and bifurcation has been examined. Each of them turned out to bifurcate invariant tors of 2,3,4 dimensions, including asymptotically stable ones. Features which make them different from the analogous problem when the number of space variables equals 1 or 2 are also shown. In particular we have shown parameter ranges when precritic bifurcation of saddle tors is possible and revealed the cases of realization of stable regimes with sharpening the latter is illustrated by figures. All these results have been obtained analytically and are based on asymptotic methods of nonlinear dynamic.

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

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 controlled parabolic system that describes the heating of a given number of rods is considered. The density functions of the internal heat sources of the rods are not known exactly, and only the segments of their change are given. At the ends of the rods there are controlled heat sources and disturbances. The goal of the choice of control is to lead the vector of average temperatures of the rods at a fixed time to a given compact for any admissible functions of the density of internal heat sources and any admissible realizations of disturbances. After replacing variables, the problem of controlling a system of ordinary differential equations in the presence of uncertainty is obtained. Using a numerical method, a solvability set is constructed for this problem. Model calculations are carried out.

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

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

The article is concerned with the procedure of insertion of optimizable fragments of route solutions into the global solutions of the «big» problem defined by heuristic algorithms. Setting of the route problem takes into account some singularities of the engineering problem about the sequential cutting of details each having one exterior and probably several interior contours. The latter ones must be subjected to cutting previously in comparison with the exterior contour, which leads to a great number of given preceding conditions. These conditions are actively used to decrease the computational complexity. Nevertheless, the problem dimensionality remains sufficiently large that does not permit to use “global’’ dynamic programming and forces heuristic algorithms to be used (the problem under investigation is a hard-solvable problem in the traditional sense). Therefore, it is interesting to develop the methods for correction of solutions based on the above-mentioned algorithms. In the present investigation, such correction is realized by the replacement of fragments (of the above-mentioned solutions) having a moderate dimensionality by optimal “blocks’’ constructed by dynamic programming with local preceding conditions which are compatible with the constraints of the initial “big’’ problem. The proposed replacement does not deteriorate, but, in typical cases, improves the quality of the initial heuristic solution. This is verified by the computing experiment on multi-core computer.

The proposed algorithm is realized in the iterated regime: the solution (in the form of “route-trace’’) obtained after the first insertion on the basis of dynamic programming is taken as an initial solution for which the insertion is constructed again. In addition, the beginning of the new insertion is chosen randomly in the bounds defined by the possibilities of formation of a sliding “window’’ of the appreciable dimensionality which is in fact sufficient for the employment of the economical version of dynamic programming. Further, the procedure is repeated. The operation of the iterated algorithm is illustrated by solution of model problems including the versions with sufficiently dense “packing’’ of parts on a sheet, which is typical for the engineering production.

Рассматривается новое конструктивное понимание логических формул, согласованное с интуицией и с традиционными средствами конструктивного логического вывода. Новое понимание логически проще традиционной реализуемости (в смысле кванторной глубины), но является также естественным с точки зрения алгоритмического решения задач. Это понимание, кроме свидетельства (реализации, подтверждения) понимаемой формулы, привлекает понятия теста (противодействия, препятствия) этой реализации на данной формуле. Для понимания формулы $A$ рассматриваются предложения вида $a:A:b.$ Это предложение означает, что объект $a$ (выдвигаемый в подтверждение формулы $A$) выигрывает у объекта $b$ (который противодействует выполнению формулы $A$) формулу $A$ в процессе осуществления специальной процедуры сопоставления этих объектов друг с другом и с данной формулой. Данная процедура может считаться некоторой процедурой арбитража для вынесения необходимого решения. Базис процедуры арбитража для атомарных формул задается интерпретацией языка. Процедура для сложных предложений задается специальными правилами определения смысла логических связок. При наиболее естественном определении процедура арбитража имеет полиномиальную временную сложность. Формула $A$ считается истинной в новом смысле этого слова, если имеется подтверждение, выигрывающее ее у всех возможных противодействий. Рассматривается логический язык без отрицаний. Доказана теорема о корректности в новом смысле традиционных интуиционистских аксиом и правил вывода. При этом рассматривается секвенциальное логическое исчисление, ориентированное на обратный метод поиска вывода.

A new constructive understanding of logical formulas is considered. This understanding corresponds to intuition and traditional means of constructive logical inference. The new understanding is logically simpler than traditional realizability (in the sense of quantifier depth), but it also natural with respect to algorithmic solution of tasks. This understanding uses not only witness (realization) of the formula to understand but it also uses notion of test (counteraction) of this realization at the given formula. The main form of a sentence to understand a formula $A$ is $a:A:b$, that means that “the witness $a$ wins the obstacle $b$ while trying to approve the formula $A$”. This procedure can be regarded as a procedure of arbitration for making the necessary solution. The basis of the arbitration procedure for atomic formulas is defined by the interpretation of the language. The procedure for complex sentences is given by special rules determining the meaning of logical connectives. In the most natural definition of the arbitration procedure it has polynomial time complexity. A formula $A$ is considered to be true in the new sense if there is a witness of the formula that wins all possible obstacles at the formula. A language without negation is considered. A theorem of correctness of traditional intuitionistic axioms and inference rules is proved. The system of logical inference is formulated in sequent form. It is oriented to the inverse method of logical inference search.

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

One of the versions of the generalized variational Ginzburg-Landau equation is considered, supplemented by periodic boundary conditions. For such a boundary value problem, the question of existence, stability, and local bifurcations of single-mode equilibrium states is studied. It is shown that in the case of a nearly critical threefold zero eigenvalue, in the problem of stability of single-mode spatially inhomogeneous equilibrium states, subcritical bifurcations of two-dimensional invariant tori filled with spatially inhomogeneous equilibrium states are realized. The analysis of the stated problem is based on such methods of the theory of infinite-dimensional dynamical systems as the theory of invariant manifolds and the apparatus of normal forms. Asymptotic formulas are obtained for the solutions that form invariant tori.