Все выпуски

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

A mathematical model of competition under conditions of biological invasion, written in the form of a system of nonlinear parabolic equations, is considered. The competition of two closely related species — resident and invader — is studied. The dynamics of populations in a heterogeneous area is determined by local interaction and diffusion. For the invader population, interspecific taxis and directed migration caused by heterogeneity of living conditions are taken into account. In computational experiments, sets of migration parameters corresponding to various invasion scenarios are determined. An analysis of the influence of initial distributions on competitive exclusion and coexistence of species is given.

Рассматривается задача построения вершинного описания выпуклого полиэдра, заданного как множество решений некоторой системы линейных неравенств, коэффициенты которой являются алгебраическими числами. Обратная задача эквивалентна (двойственна) исходной. Предлагаются программные реализации нескольких модификаций хорошо известного метода двойного описания (метода Моцкина-Бургера), решающего поставленную задачу. Рассматривается два случая: 1) элементы системы неравенств - произвольные алгебраические числа, при этом каждое такое число задается минимальным многочленом и локализующим интервалом; 2) элементы системы неравенств принадлежат заданному конечному расширению ${\mathbb Q} (\alpha)$ поля ${\mathbb Q}$, при этом для $\alpha$ задаются минимальный многочлен и локализующий интервал, а все элементы исходной системы, конечные и промежуточные результаты представлены как многочлены от $\alpha$. Как и ожидалось, программная реализация для второго варианта значительно превосходит реализацию для первого варианта по производительности. Для большего ускорения во втором случае предлагается использовать булевы матрицы вместо матриц невязок. Результаты вычислительного эксперимента показывают, что программные реализации вполне пригодны для решения задач умеренных размеров.

We consider the problem of constructing the dual representation of a convex polyhedron defined as a set of solutions to a system of linear inequalities with coefficients which are algebraic numbers. The inverse problem is equivalent (dual) to the initial problem. We propose program implementations of several variations of the well-known double description method (Motzkin-Burger method) solving this problem. The following two cases are considered: 1) the elements of the system of inequalities are arbitrary algebraic numbers, and each such number is represented by its minimal polynomial and a localizing interval; 2) the elements of the system belong to a given extension ${\mathbb Q} (\alpha)$ of ${\mathbb Q}$, and the minimal polynomial and the localizing interval are given only for $\alpha$, all elements of the system, intermediate and final results are represented as polynomials of $\alpha$. As expected, the program implementation for the second case significantly outperforms the implementation for the first one in terms of speed. In the second case, for greater acceleration, we suggest using a Boolean matrix instead of the discrepancy matrix. The results of a computational experiment show that the program is quite suitable for solving medium-scale problems.

На основе известных свойств функции вероятности протекания простой кубической решётки размера L=2 в приближении линейной связи порога протекания бесконечной решётки x_c и среднего значения x_cL конечной решётки введена нескейлинговая функция вероятности протекания для решётки размера L>2. Показано, что на пороге протекания нескейлинговые вероятности для всех ПК решёток одинаковы.
Компьютерные эксперименты на основе метода Монте-Карло согласуются с предлагаемой в работе теорией.

Using known properties of the probability function for passing in a simple cubic lattice with L=2 in approximation of a linear relation between a passing threshold of an infinite lattice x_c and average value x_cL of a finite lattice, we introduce a nonscaling probability function of passing of a lattice with L>2. We show that on the passing threshold nonscaling probabilities for all simple cubic lattices are the same.
Computer experiments based on the Monte-Carlo method are in agreement with the theory proposed.

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

A zero-sum linear-convex differential game with a quality index that estimates a set of deviations of a motion trajectory at given instants of time from given target points is considered. A case when the saddle point condition in a small game, also known as Isaac's condition, does not hold, is studied. The game is formalized in classes of mixed control strategies of players. A numerical method for approximate computation of the game value and optimal strategies is elaborated. The method is based on the recurrent construction of upper convex hulls of auxiliary program functions. The results of numerical experiments in model examples are given.

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

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

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.

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

Issues related to solving the additive problem of sequential traversal of sets with precedence restrictions and cost functions that allow dependence on the list of tasks are considered. The basic method is a broadly understood dynamic programming (DP), supplemented in the case of problems of appreciable dimension by decompositions of the family of tasks and transformation of the parameters of the original problem. Possible applications are related, in particular, to the problem of tool control in figured sheet cutting of parts on CNC machines. In this problem, an important circumstance is taking into account the precedence conditions, which have, in particular, the following meaning: in the case of a part with holes, cutting of each of the internal contours (corresponding to the holes) should precede cutting of the external contour. The quality criterion itself in this problem, as a rule, is additive. Another type of constraints concerns avoiding thermal deformations of parts. When using the approach with penalties for violating the conditions associated with effective heat dissipation during cutting, cost functions arise that allow dependence on the list of tasks completed to date. Note that in another applied problem, namely, in the problem of dismantling radiation hazardous objects, cost functions arise with dependence on the list of tasks that have not been completed at the moment (and, consequently, concern the objects that have not been dismantled). As a result, we arrive at a very general problem with precedence constraints and cost functions with dependence on the list of tasks. The decomposition applied in the case of a noticeable dimensionality with subsequent implementation of the DP requires, on the one hand, the development of clustering methods, and, on the other, the construction of an adequate structure for distributing global precedence conditions among clusters. In the theoretical part of the work, the case of two clusters is discussed, which makes it possible to cover with a single scheme a number of practically interesting problems of a range (in terms of dimensionality) type. An algorithm for constructing a composite solution is indicated, including a stage of clustering training based on a greedy algorithm. This “composite” algorithm is implemented on a PC; a computational experiment was carried out.

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

A minimax routing problem with decomposition elements is considered. In the simplest case, it is supposed that the whole set of tasks is divided into a sum of two subsets (clusters), and execution of tasks from the second subset can be started only after the completion of all tasks from the first subset. For above-mentioned two-cluster problem, an algorithm has been constructed for finding the optimal compositional solution, including a route (permutation of task indices) and a starting point, which is based on the use of a broadly understood dynamic programming. Based on this approach, an algorithm was also constructed to solve the routing problem in the case of an arbitrary ordered finite set of clusters. The algorithm was implemented on a PC, and a computational experiment was carried out. Possible applications may be associated with some logistics tasks in small aviation, when it is necessary to ensure visits to many points by one vehicle (airplane, helicopter) with a limited non-stop flight range.

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

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.

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

In the framework of the methods and equations of the mechanics of multiphase media, a mathematical model is constructed for the formation of gas hydrate during the injection of methane into a reservoir of finite length saturated with methane and ice. The problem under study is reduced to the problem of finding two moving boundaries of phase transitions. Based on the method of catching the front in the node of the spatial grid, numerical solutions of the problem are obtained. The distributions along the spatial coordinate of temperature, pressure, and hydrate saturation are found, and the time evolution of the coordinates of the phase transition boundaries is given. Analysis of the results of computational experiments has shown that the formation of methane gas hydrate can occur both at the frontal boundary and in the extended zone. It has been established that part of the gas hydrate formed in the extended region can be further decomposed into gas and water. In this case, the extended region of hydrate formation will degenerate into the frontal surface.

В работе построен алгоритм повышенного порядка точности на основе WENO схем для моделирования динамики многокомпонентного реагирующего газа с учетом процессов диффузии, теплопроводности и химических реакций. Проведены расчеты для течения газа в проточном реакторе для термического пиролиза этана с внешним обогревом реакционной зоны. В рассматриваемых течениях скорость движения газа много меньше скорости распространения звука в газовой смеси, что обуславливает использование уравнений Навье-Стокса в приближении малых чисел Маха для описания исследуемых процессов. Расчет уравнений химических реакций выделяется в отдельный шаг, где скорость реакции определяется на основе выражений Аррениуса. Для построения модели химической кинетики принята кинетическая схема пиролиза этана, представляющая собой разветвленный радикальный механизм. Проведены расчеты дозвукового течения газа с учетом процессов диффузии, химических реакций и их тепловых эффектов для различных температур нагревательных элементов. Сравнение с экспериментальными данными показало, что $1.97\,\%$-ная конверсия этана в расчетах достигается для $648\,^{\circ}$C на выходе металлического реактора, что близко к экспериментальным значениям, составляющим $2.1\,\%$. Сравнение данных экспериментов по термическому пиролизу этана с данными, полученными в ходе вычислительного эксперимента, показало высокую степень достоверности полученных результатов.

The article considers a high-order accuracy algorithm for modelling the dynamics of multicomponent reactive gas taking into account the processes of diffusion, thermal conductivity and chemical reactions, based on WENO schemes. Computations for gas flow in a flowing reactor for thermal ethane pyrolysis with external heating of the reaction zone are carried out. The velocity of gas motion in explored flows is much less then sound velocity in gas mixture, which motivates using the Navier-Stokes equations in approximation of low Mach numbers for describing the processes under study. Computation of chemical kinetics equations is singled out as a separate step. The velocity of chemical reactions is defined by Arrhenius expressions. The ethane pyrolysis kinetic scheme is used for constructing the model, which is a branched radical mechanism. Computations of subsonic gas flow taking into account the processes of diffusion, chemical reactions and their thermal effects for different temperature of heating elements are carried out. Comparison with experimental data shows that $1.97\,\%$ conversion of ethane is reached at $648\,^{\circ}$C at the outflow of metal reactor. This result is close to $2.1\,\%$, which is obtained by experiment. Comparison of experimental data of thermal ethane pyrolysis with numerical experimental data shows a high level of reliability of the results obtained.