All issues

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

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

A direct algorithm for solving a linear programming problem (LP), given in canonical form, is considered. The algorithm consists of two successive stages, in which the following LP problems are solved by a direct method: a non-degenerate auxiliary problem at the first stage and some problem equivalent to the original one at the second. The construction of the auxiliary problem is based on a multiplicative version of the Gaussian exclusion method, in the very structure of which there are possibilities: identification of incompatibility and linear dependence of constraints; identification of variables whose optimal values are obviously zero; the actual exclusion of direct variables and the reduction of the dimension of the space in which the solution of the original problem is determined. In the process of actual exclusion of variables, the algorithm generates a sequence of multipliers, the main rows of which form a matrix of constraints of the auxiliary problem, and the possibility of minimizing the filling of the main rows of multipliers is inherent in the very structure of direct methods. At the same time, there is no need to transfer information (basis, plan and optimal value of the objective function) to the second stage of the algorithm and apply one of the ways to eliminate looping to guarantee final convergence.

Two variants of the algorithm for solving the auxiliary problem in conjugate canonical form are presented. The first one is based on its solution by a direct algorithm in terms of the simplex method, and the second one is based on solving a problem dual to it by the simplex method. It is shown that both variants of the algorithm for the same initial data (inputs) generate the same sequence of points: the basic solution and the current dual solution of the vector of row estimates. Hence, it is concluded that the direct algorithm is an algorithm of the simplex method type. It is also shown that the comparison of numerical schemes leads to the conclusion that the direct algorithm allows to reduce, according to the cubic law, the number of arithmetic operations necessary to solve the auxiliary problem, compared with the simplex method. An estimate of the number of iterations is given.

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

The work investigates the search for inefficient edges in the model of stable dynamics by Nestrov – de Palma (2003). For this purpose, we prove several general theorems about equilibrium properties, including the condition of equal costs for all used routes that can be extended to all paths involving edges from equilibrium routes. The study demonstrates that the standard problem formulation of finding edges whose removal reduces the cost of travel for all participants has no practical significance because the same edge can be both efficient and inefficient depending on the network’s load. In the work, we introduce the concept of an inefficient edge based on the sensitivity of total driver costs to the costs on the edge. The paper provides an algorithm for finding inefficient edges and presents the results of numerical experiments for the transportation network of the city of Anaheim.

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

An important role in the construction of mathematical models of dynamic systems is played by inverse problems, which in particular include the problem of parametric identification. Unlike classical models that operate with point values, interval models give upper and lower boundaries on the quantities under study. The paper considers an interpolation approach to solving interval problems of parametric identification of dynamic systems for the case when experimental data are represented by external interval estimates. The purpose of the proposed approach is to find such an interval estimate of the model parameters, in which the external interval estimate of the solution of the direct modeling problem would contain experimental data or minimize the deviation from them. The approach is based on the adaptive interpolation algorithm for modeling dynamic systems with interval uncertainties, which makes it possible to explicitly obtain the dependence of phase variables on system parameters. The task of minimizing the distance between the experimental data and the model solution in the space of interval boundaries of the model parameters is formulated. An expression for the gradient of the objectivet function is obtained. On a representative set of tasks, the effectiveness of the proposed approach is demonstrated.

Разработан и протестирован новый метод формирования тестовых сигналов для корреляционной идентификации нелинейных динамических систем методом Ли–Шетцена. Для коррекции моментных функций тестовых сигналов применен численный алгоритм оптимизации Гаусса–Ньютона. В экспериментах получены тестовые воздействия длиной до 40 000 точек, позволяющие определять ядра Винера 2-го порядка с линейным разрешением до 32 точек, ядра Винера 3-го порядка с линейным разрешением до 12 точек, ядра Винера 4-го порядка с линейным разрешением до 8 точек.

Тhe new test-signals forming method for correlation identification of a nonlinear system based on Lee–Shetzen cross-correlation approach is developed and tested. Numerical Gauss–Newton algorithm is applied to correct autocorrelation functions of test signals. The achieved test-signals have length less than 40 000 points and allow to measure the 2nd order Wiener kernels with a linear resolution up to 32 points, the 3rd order Wiener kernels with a linear resolution up to 12 points and the 4th order Wiener kernels with a linear resolution up to 8 points.

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

An algorithm is proposed to identify parameters of a 2D vortex structure used on information about the flow velocity at a finite (small) set of reference points. The approach is based on using a set of point vortices as a model system and minimizing a functional that compares the model and known sets of velocity vectors in the space of model parameters. For numerical implementation, the method of gradient descent with step size control, approximation of derivatives by finite differences, and the analytical expression of the velocity field induced by the point vortex model are used. An experimental analysis of the operation of the algorithm on test flows is carried out: one and a system of several point vortices, a Rankine vortex, and a Lamb dipole. According to the velocity fields of test flows, the velocity vectors utilized for identification were arranged in a randomly distributed set of reference points (from 3 to 200 pieces). Using the computations, it was determined that: the algorithm converges to the minimum from a wide range of initial approximations; the algorithm converges in all cases when the reference points are located in areas where the streamlines of the test and model systems are topologically equivalent; if the streamlines of the systems are not topologically equivalent, then the percentage of successful calculations decreases, but convergence can also take place; when the method converges, the coordinates of the vortices of the model system are close to the centers of the vortices of the test configurations, and in many cases, the values of their circulations also; con-vergence depends more on location than on the number of vectors used for identification. The results of the study allow us to recommend the proposed algorithm for identifying 2D vortex structures whose streamlines are topologically close to systems of point vortices.

Исследуются динамические теоретико-игровые модели инновационного развития корпорации. Предлагаемые модели основаны на согласовании частных и общественных интересов агентов. Предполагается, что структура интересов каждого агента включает как частную (личные интересы), так и общественную (интересы компании в целом, в первую очередь отражающие необходимость ее инновационного развития) составляющие. Агенты могут делить персональные ресурсы между этими направлениями. Динамика системы описывается не дифференциальным, а разностным уравнением. При исследовании предложенной модели инновационного развития используются имитация и метод перебора областей допустимых управлений субъектов с некоторым шагом. Основной вклад работы — сравнительный анализ эффективности методов иерархического управления для информационных регламентов Штакельберга/Гермейера при принуждении/побуждении (четыре регламента) с помощью индексов системной согласованности. Предлагаемая модель носит универсальный характер и может быть использована для научно обоснованной поддержки ПИР компаний всех отраслей экономики. Специфика конкретной компании учитывается в ходе идентификации модели (определения конкретных классов ис- пользуемых в модели функций и числовых значений параметров), которая представляет собой отдельную сложную задачу и предполагает анализ системы официальной отчетности компании и применение экспертных оценок ее специалистов. Приняты следующие предположения относительно информационного регламента иерархической игры: все игроки используют программные стратегии; ведущий выбирает и сообщает ведомым экономические управления либо административные управления, которые могут быть только функциями времени (игры Штакельберга) либо зависеть также от управлений ведомых (игры Гермейера); при известных стратегиях ведущего ведомые одновременно и независимо выбирают свои стратегии, что приводит к равновесию Нэша в игре ведомых. За конечное число итераций предложенный алгоритм имитационного моделирования позволяет построить приближенное решение модели или сделать вывод, что равновесия не существует. Достоверность и эффективность предложенного алгоритма следуют из свойств методов сценариев и прямого упорядоченного перебора с постоянным шагом. Получен ряд содержательных выводов относительно сравнительной эффективности методов иерархического управления инновациями.

Dynamic game theoretic models of the corporative innovative development are investigated. The proposed models are based on concordance of private and public interests of agents. It is supposed that the structure of interests of each agent includes both private (personal interests) and public (interests of the whole company connected with its innovative development first) components. The agents allocate their personal resources between these two directions. The system dynamics is described by a difference (not differential) equation. The proposed model of innovative development is studied by simulation and the method of enumeration of the domains of feasible controls with a constant step. The main contribution of the paper consists in comparative analysis of efficiency of the methods of hierarchical control (compulsion or impulsion) for information structures of Stackelberg or Germeier (four structures) by means of the indices of system compatibility. The proposed model is a universal one and can be used for a scientifically grounded support of the programs of innovative development of any economic firm. The features of a specific company are considered in the process of model identification (a determination of the specific classes of model functions and numerical values of its parameters) which forms a separate complex problem and requires an analysis of the statistical data and expert estimations. The following assumptions about information rules of the hierarchical game are accepted: all players use open-loop strategies; the leader chooses and reports to the followers some values of administrative (compulsion) or economic (impulsion) control variables which can be only functions of time (Stackelberg games) or depend also on the followers’ controls (Germeier games); given the leader’s strategies all followers simultaneously and independently choose their strategies that gives a Nash equilibrium in the followers’ game. For a finite number of iterations the proposed algorithm of simulation modeling allows to build an approximate solution of the model or to conclude that it doesn’t exist. A reliability and efficiency of the proposed algorithm follow from the properties of the scenario method and the method of a direct ordered enumeration with a constant step. Some comprehensive conclusions about the comparative efficiency of methods of hierarchical control of innovations are received.

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

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

В ходе исследования проанализированы различные режимы подачи субстрата в метантенк, температурные среды и виды сырья. Показано, что скорость образования биогаза при непрерывном режиме подачи сырья в 1.4–1.9 раза выше в мезофильной среде (в 1.9–3.2 — в термофильной среде), чем при периодическом режиме за период полной ферментации, что связано с большей скоростью подачи субстрата и большей концентрацией питательных веществ в субстрате. Однако выход биогаза за период полной ферментации при периодическом режиме вдвое выше выхода за период полной смены субстрата в метантенке при непрерывном режиме, что означает неполную переработку субстрата во втором случае. Скорость образования биогаза для термофильной среды при непрерывном режиме и оптимальной скорости подачи сырья втрое выше, чем для мезофильной среды. Сравнение выхода биогаза для различных типов сырья показывает, что наибольший выход биогаза наблюдается для отходов птицефабрик, наименьший — для отходов ферм КРС, что связано с содержанием питательных веществ в единице субстрата каждого вида.

The paper presents a mathematical model that describes the process of obtaining biogas from livestock waste. This model describes the processes occurring in a biogas plant for mesophilic and thermophilic media, as well as for continuous and periodic modes of substrate inflow. The values of the coefficients of this model found earlier for the periodic mode, obtained by solving the problem of model identification from experimental data using a genetic algorithm, are given.

For the model of methanogenesis, an optimal control problem is formulated in the form of a Lagrange problem, whose criterial functionality is the output of biogas over a certain period of time. The controlling parameter of the task is the rate of substrate entry into the biogas plant. An algorithm for solving this problem is proposed, based on the numerical implementation of the Pontryagin maximum principle. In this case, a hybrid genetic algorithm with an additional search in the vicinity of the best solution using the method of conjugate gradients was used as an optimization method. This numerical method for solving an optimal control problem is universal and applicable to a wide class of mathematical models.

In the course of the study, various modes of submission of the substrate to the digesters, temperature environments and types of raw materials were analyzed. It is shown that the rate of biogas production in the continuous feed mode is 1.4–1.9 times higher in the mesophilic medium (1.9–3.2 in the thermophilic medium) than in the periodic mode over the period of complete fermentation, which is associated with a higher feed rate of the substrate and a greater concentration of nutrients in the substrate. However, the yield of biogas during the period of complete fermentation with a periodic mode is twice as high as the output over the period of a complete change of the substrate in the methane tank at a continuous mode, which means incomplete processing of the substrate in the second case. The rate of biogas formation for a thermophilic medium in continuous mode and the optimal rate of supply of raw materials is three times higher than for a mesophilic medium. Comparison of biogas output for various types of raw materials shows that the highest biogas output is observed for waste poultry farms, the least — for cattle farms waste, which is associated with the nutrient content in a unit of substrate of each type.