Введение
1. Постановка задачи исследования и анализ некото рых методов ее решения 15
1.1. Характерные признаки и неформальная постановка задач размещения геометрических объектов 15
1.2. Формальная постановка математической модели основ ной задачи исследования 27
1.4. Анализ существующих методов решения основной задачи 31
1.4.1. Метод последовательного одиночного размещения -основной метод локальной оптимизации 32
1.4.2. Методы оптимизации в пространстве перестановок. 34
ВЫВОДЫ 38
2. Построение условий взаимных непересечений многоугольников с использованием структур линейных неравенств 39
2.1. Структуры неравенств, операции над ними и эквивалентные преобразования 40
2.2. Соответствие между структурами линейных неравенств и логическими формулами 48
2.3. Метод исключения неизвестных при решении структур линейных неравенств 55
2.4. Построение условий взаимных непересечений с использованием метода исключения неизвестных 64
Выводы 77
3. Математическая модель задачи оптимального размещения ^-многоугольников в полубесконеч ной полосе 78
3.1. Построение области допустимых решений и постановка задачи 78
3.2. Особенности формирования области допустимых решений 88
3.3. Свойства дерева решений задачи 92
Выводы 95
4. Точные методы решения задачи размещения у -многоугольников в полосе 97
4.1. Решение задачи оптимального размещения у-много угольников 97
4.1.1. Применение метода исключения неизвестных 98
4.1.2. Поиск оптимального решения методом ветвей и границ 100
4.2. Использование метода ветвей и границ для оптимального размещения прямоугольников 104
4.3. Поиск локальных экстремумов задачи с использованием методов линейного программирования 123
Выводы 133
Заключение 135
Литература
