Методы решения экстремальных задач размещения многоугольных геометрических объектов в полосе

• Автор: Магас, Сергей Леонидович
• Шифр специальности: 08.00.13
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Харьков
• Количество страниц: 156 c. : ил

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

1. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ И АНАЛИЗ НЕКОТОРЫХ МЕТОДОВ ЕЕ РЕШЕНИЯ

1.1. Характерные признаки и неформальная постановка

задач размещения геометрических объектов

1.2. Формальная постановка математической модели основной задачи исследования

1.4. Анализ существующих методов решения основной задачи

1.4.1. Метод последовательного одиночного размещения основной метод локальной оптимизации.

1.4.2. Методы оптимизации в пространстве перестановок. .

ВЫВОДЫ

2. ПОСТРОЕНИЕ УСЛОВИЙ ВЗАИМНЫХ НЕПЕРЕСЕЧЕНИЙ

уМНОГОУГОЛЬНИКОВ С ИСПОЛЬЗОВАНИЕМ СТРУКТУР ЛИНЕЙНЫХ НЕРАВЕНСТВ
2.1. Структуры неравенств, операции над ними и эквивалентные преобразования
2.2. Соответствие между структурами линейных неравенств
и логическими формулами
2.3. Метод исключения неизвестных при решении структур линейных неравенств
2.4. Построение условий взаимных непересечений с использованием метода исключения неизвестных. .
ВЫВОДЫ
стр.
3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ уМНОГОУГОЛЬНИКОВ В ПОЛУБЕСКОНЕЧ
НОЙ ПОЛОСЕ ....
3.1. Построение области допустимых решений и постановка задачи.
3.2. Особенности формирования области допустимых решений
3.3. Свойства дерева решений задачи.
ВЫВОДЫ.
4. ТОЧНЫЕ МЕТОДЫ РИНЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ
у МНОГОУГОЛЬНИКОВ В ПОЛОСЕ.
4.1. Решение задачи оптимального размещения многоугольников.
4.1.1. Применение метода исключения неизвестных.
4.1.2. Поиск оптимального решения методом ветвей и границ .
4.2. Использование метода ветвей и границ для оптимального размещения прямоугольников
4.3. Поиск локальных экстремумов задачи с использованием
методов линейного программирования
ВЫВОДЫ
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Поэтому очевидна необходимость совершенствования имеющихся приближенных методов, а также разработки новых методов с оценками близости получаемого решения к глобальному или локальным экстремумам задачи. Кроме этого, принципиально важным является создание методов точного решения для тех задач размещения, размерность которых позволяет получить такое решение. Диссертационная работа является продолжением исследований, проводимых в Институте проблем машиностроения АН УССР под руководством профессора Ю. ЭТИХ методов, , . Диссертационная работа выполнялась в период с г. Разработка математических методов размещеш Президиума АН УССР 4 от . Разработка методов и алгоритмов решения компоновочных задач при проектировании промышленных зданий от ГР 5, ин. ВНТИЦ . ГР 5. Методы и алгоритмы, предложенные в диссертационной работе, реализованы на подмножестве языка Фортран для ЭВМ БЭСМ6 и ЕС ЭВМ и предназначены для автоматизации процесса построения планов раскроя материалов в различных отраслях машиностроения, легкой промышленности, а также для решения задач оптимального распределения ресурсов, которые могут быть сведены к задачам размещения геометрических объектов. Годовой экономический эффект от внедрения результатов работы в производство составляет тыс. Канев, ка Всесоюзном научнопрактическом семинаре Прикладные аспекты управления сложными системами Кемерово, на Ш Всесоюзной конференции Автоматизация поискового конструирования и подготовка инженерных кадров Иваново, на постоянно действующих семинарах Методы поисковой оптимизации и размещения геометрических объектов Харьков, , Прикладные методы математики и кибернетики Харьков, , Математические методы геометрического проектирования Харьков, III2 при Научном совете по проблеме Кибернетика АН УССР. Материалы диссертации являются частью работы Смелякова С. В., Яковлева С. В., Винарского В. Я., Магаса . I. Туранова И. Н. Разработка и внедрение в народное хозяйство моделей, методов и алгоритмов решения оптимизационных задач геометрического проектирования, отмеченной Премией ЦК ЛКСИ Украины и Украинского республиканского совета НТО молодым ученым, специалистам и производственникам членам НТО за лучшие разработки в области науки и техники года. Основные результаты диссертации опубликованы в работах , , , , , , , , , . Диссертация состоит из введения, четырех глав, заключения, списка литературы и прилохсения. Первая глава Постановка задачи исследования и анализ некоторых методов ее решения посвящена построению формальной математической модели задачи оптимального размещения геометрических объектов, анализу особенностей этой задачи и существующих методов ее решения. Задача оптимального размещения уэобъектов поставлена в виде общей задачи математического программирования. Исследованы свойства этой задачи, показана ее многоэкстремальность. Проанализированы существующие методы ее решения, показан их приближенный характер. Вторая глава Построение условий взаимных иепересечений у многоугольников с использованием структур линейных неравенств посвящена разработке математического аппарата структур линейных неравенств и использованию его для аналитического построения геометрических ограничений на взаимное положение объектов условий взаимных иепересечений. Исследованы конструктивные свойства структур линейных неравенств в плане описания невыпуклых многогранных множеств, множеств, лежащих в пересечении и объединении таких множеств, а также в плане аналитического построения ортогональных проекций невыпуклых многогранных множеств на подпространства меньшей размерности. Третья глава Математическая модель задачи оптимального размещения у многоугольников в полубесконечной полосе посвящена постановке и исследованию особенностей задачи оптимального размещения конечного числа ориентированных у Задача ставится в форме минимизации линейной функции цели на некотором невыпуклом многогранном множестве, заданном структурой линейных неравенств. Исследованы свойства этого множества. Показана возможность выделения из него выпуклых многогранных множеств и предложена схема усеченного перебора этих множеств.