Применение симплекс-метода при решении оптимизационных задач размещения геометрических объектов

( 0 Votes ) 
Категория: ИКТМ 2013 Просмотров: 485

УДК 512.25/26


Применение симплекс-метода при решении
оптимизационных задач размещения
геометрических объектов
А.Ю. Шахов, студент 3556 группы
Национальный аэрокосмический университет им. НЕ.Жуковского «ХАИ»


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