УДК 512.25/26
Оценка эффективности использования нуль-матрицы при решении задачи оптимального размещения кругов
А.Д. Григорова, студент 335Б группы
Национальный аэрокосмический университет им. Н.Е.Жуковского «ХАИ»
Задача оптимального размещения геометрических объектов на плоскости имеет широкий спектр практических приложений. Такие задачи достаточно сложны для решения и для их решения зачастую необходимо построение нетривиальной математической модели, описывающей все особенности данной задач. Одной из таких задач, является задача оптимального размещения кругов, в полубесконечной полосе. Эта задача нелинейного программирования с большим количеством локальных экстремумов. Обычно метод глобального поиска для таких задач состоит в многократном решении задачи поиска локального минимума в комбинации с методами направленного перебора таких решений [1]. Поэтому актуальным является задача быстрого нахождения одного локального минимума.
Для поиска минимума был использован метод проекции градиента. Было выполнено две его реализации. Первая — реализация классической форумы Розена с обращением и перемножением матрицы активных ограничений. Во второй программной реализации была использована схема активного набора. Для поиска проекции использовалась так называемая нуль-матрица (матрица, представляющая собой базис подпространства, ортогонального строкам матрице активных ограничений) [2]. Этот второй способ позволил в несколько раз уменьшить время поиска решения. В дальнейшем предполагается еще существенно ускорить вычисление направления движения за счет реализации не полного, а частичного пересчета нуль-матрицы [2].
Список использованных источников:
1. Карташов, А.В. Одна реализация метода последовательно-одиночного размещения для решения задачи оптимального размещения кругов различных радиусов в полосе [Текст] / А. В. Карташов, Н. В. Лученцова; Национальный аэрокосмический университет им. Н. Е. Жуковского "ХАЙ” // Журн. Радіоелектронні і комп'ютерні системи , 2007. — № 2. — С. 90-94.
2. Гилл, Ф. Практическая оптимизация. [Текст] / Ф.Гилл, У. Мюррей, М. Райт / пер. с англ. - М: Мир, 1985 — 478 с.
*Научный руководитель к.ф-м.н доцент каф. 304 А. В. Карташов
Нет похожих статей