Все выпуски

Изучаются свойства дискретной вариационной задачи динамической аппроксимации в комплексном евклидовом (L + 1)-мерном пространстве E. Она обобщает известные задачи среднеквадратической полиномиальной аппроксимации функций, заданных своими отсчетами в конечном интервале. В рассматриваемой задаче аппроксимация последовательности y = {y_i}_L⁰ отсчетов функции y(t) ∈ L²[0, T], T = Lh на сетке I_h осуществляется решениями однородных линейных дифференциальных или разностных уравнений заданного порядка n с постоянными, но, возможно, неизвестными коэффициентами. Тем самым показано, что в последнем случае задача аппроксимации включает в себя и задачу идентификации. Анализ ее особенностей - основная тема статьи. Ставится задача нахождения вектора коэффициентов  разностного уравнения Σ_n⁰ ŷ_i+k α_i = 0, где k = 0,L − n. Оптимизируются коэффициенты  и начальные условия переходного процесса y этого уравнения. Цель оптимизации - наилучшая аппроксимация исследуемого динамического процесса y ∈ E. Критерий аппроксимации  минимум величины ||y − ŷ||²_E. Показано, что изучаемая вариационная задача сводится к задачам проектирования в E вектора y на ядра разностных операторов с неизвестными коэффициентами α ∈ ω ⊂ S ⊂ Eⁿ⁺¹. Здесь α - направление, S - сфера или гиперплоскость. Показана связь изучаемой задачи с задачами дискретизации и идентифицируемости. Тогда координаты вектора y ∈ E есть точное решение дифференциального уравнения на сетке I_h и y = ŷ. Дано сравнение изучаемой задачи вариационной идентификации с алгебраическими методами идентификации. Показано, что ортогональные дополнения к ядрам разностных операторов всегда имеют теплицев базис. Это приводит к быстрым проекционным алгоритмам вычислений. Показано, что задача нахождения оптимального вектора α сводится к задаче безусловной минимизации функционала идентификации, зависящего от направления  в Eⁿ⁺¹. Предложена итерационная процедура его минимизации на сфере с широкой областью и высокой скоростью сходимости. Изучаемую вариационную задачу можно применять при математическом моделировании в управлении и научных исследованиях. При этом на конечных интервалах может использоваться, в частности, возможность кусочно-линейной динамической аппроксимации сложных динамических процессов разностными и дифференциальными уравнениями указанного типа.

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

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

Этот метод c 2004 года используется А.Г. Ченцовым и его соавторами, но степень экономии ресурсов исследовалось мало. Мы предлагаем подход к решению этой проблемы, основанный на комбинаторном анализе числа подзадач, существенных в смысле условий предшествования. Применяя известные комбинаторные правила сложения и произведения, мы получили результат для важных частных случаев условий предшествования: а) «независимые» наборы условий предшествования; б) «цепь» условий предшествования - когда условия задают линейный порядок; в) случай, когда в графе предшествования нет неориентированных циклов, и исходящая степень любой вершины не превышает единицы. Последний случай представляет собой условия предшествования, встречающихся в практической задаче маршрутизации движений инструмента в машинах листовой резки и соответствует требованию вырезать внутренний контур прежде внешнего.

В связи с более сложной структурой случая в) по сравнению с остальными для него вместо аналитической формулы представлен алгоритм; алгоритм реализован на языке C++, зависимость его вычислительной сложности от числа связанных условиями предшествования объектов имеет не более чем квадратичный порядок. В дальнейшем мы предполагаем расширить область применения нашего подхода до более общих вариантов условий предшествования. Отметим также, что наш подход не зависит от критерия оптимальности, соответственно, может применяться для анализа сложности решения методом динамического программирования в произвольных маршрутных задачах с условиями предшествования.

Изучаются аппроксимирующие конечномерные задачи математического программирования, возникающие в результате кусочно-постоянной дискретизации управления (в рамках техники параметризации управления) при оптимизации распределенных систем достаточно широкого класса. Устанавливается непрерывность по Липшицу градиентов функций аппроксимирующих задач; приводятся соответствующие формулы градиентов, использующие аналитическое решение исходной управляемой системы и сопряженной к ней системы и тем самым обеспечивающие возможность алгоритмического разделения проблемы оптимизации и проблемы решения управляемой начально-краевой задачи. Применение к численному решению задач оптимизации иллюстрируется на примере задачи Коши-Дарбу, управляемой по интегральному критерию. Приводятся результаты численного решения соответствующей аппроксимирующей задачи в системе MatLab с помощью программы fmincon, а также авторской программы, реализующей метод условного градиента. Кроме того, рассматривается задача безусловной минимизации, получаемая из аппроксимирующей задачи с ограничениями методом синус-параметризации. Приводятся результаты численного решения указанной задачи в системе MatLab с помощью программы fminunc, а также авторских программ, реализующих методы наискорейшего спуска и BFGS. Результаты численных экспериментов подробно анализируются.

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

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

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