Все выпуски

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

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

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.

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

Control theory is a section of modern mathematics being actively developed at present time. The class of problems investigated within the framework of this theory is quite extensive and includes issues related to the existence of solutions as well as issues related to the effective methods for constructing controls. One of the approaches to solving control problems under lack of information was suggested by Yu.S. Osipov in the fundamental paper published in the Russian Mathematical Surveys in 2006. Later, this approach, called the method of program packages, was developed, in particular, in the articles cited in this paper. This approach is based on a suitable modification of the method of non-anticipatory strategies (quasi-strategies) for solving control problems with unknown initial states. As is known, quasi-strategies reflecting the Volterra properties of program realizations of closed-loop controls in corresponding program disturbances are oriented to the investigation of problems with known initial states under the presence of unknown dynamical disturbances. Such disturbances are usually absent in standard control problems with incomplete information and incompleteness of information is due to a lack of information about the initial state of the system. So, program packages became an analogue of the properties of nonanticipativeness for problems with unknown initial states. It should be noted that in all previous works related to the method of program packages, the guidance problems to one single target set were considered. In the present paper the guaranteed guidance problem to a collection of target sets under incomplete information about the initial state is considered for a linear autonomous control dynamical system. The criterion for the solvability of that problem is established. It is based on the method of program packages. An illustrative example is given.

Метод малого параметра Пуанкаре активно применяется в небесной механике, а также в теории дифференциальных уравнений и в ее важном разделе — оптимальном управлении. В предлагаемой статье данный метод используется для построения явного вида равновесия по Нэшу и Бержу в дифференциальной позиционной игре с малым влиянием одного из игроков на скорость изменения фазового вектора.

The Poincaré small parameter method is actively used in celestial mechanics, as well as in the theory of differential equations and in its important section called optimal control. In this paper, the mentioned method is used to construct an explicit form of Nash and Berge equilibrium in a differential positional game with a small influence of one of the players on the rate of change of the state vector.

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

The paper studies the existence of two new classes of polynomial solutions to differential equations related to the problem of the gyrostat motion with a fixed point in the magnetic field, taking into account the Barnett–London effect. A common feature of the structure of these classes is that the functions that set the invariance relations for the unit vector components of the symmetry axis of the active force fields are either rational functions of the first component of the specified vector or of the auxiliary variable. Three new particular solutions to the polynomial classes under consideration are constructed. These solutions are described by the functions obtained by the inversion of hyperelliptic integrals. It has been proved that another constructed solution of the polynomial structures under study, for which the movement of the gyrostat has the property of precession, is a particular case of a known solution.

Рассмотрены проблемы и условия, связанные с формированием конструктивных механизмов построения ИТ-сферы.

Problems and conditions connected with the forming of the conctructive mechanisms of IT-spheres are discussed.