Все выпуски

Рассмотрено применение барицентрического метода для численного решения задач Дирихле и Неймана для уравнения Гельмгольца в ограниченной односвязной области $\Omega\subset\mathbb{R}^2$. Основное допущение в решении заключается в задании границы $\Omega$ в кусочно-линейном представлении. Отличительная особенность барицентрического метода состоит в порядке формирования глобальной системы векторных базисных функций для $\Omega$ через барицентрические координаты. Установлены существование и единственность решения задач Дирихле и Неймана для уравнения Гельмгольца барицентрическим методом и определена оценка скорости сходимости. Уточнены особенности алгоритмической реализации метода.

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

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

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

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

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

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

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

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

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

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