Реализация глобального поиска для задачи оптимального размещения многоугольников

Реализация глобального поиска для задачи оптимального размещения многоугольников

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

. АНАЛИТИЧЕСКИЙ ОБЗОР ПРОБЛЕМЫ РАЗМЕЩЕНИЯ МНОГОУГОЛЬНИКОВ

.1            Обзор литературы

.2            Формализация предметной области

.3            Постановка задачи

Выводы по разделу 1

. ПОСТРОЕНИЕ И АНАЛИЗ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ РАЗМЕЩЕНИЯ МНОГОУГОЛЬНИКОВ

.1            Представление области допустимых решений с помощью Ф-функции

.2            Предикатное представление условий непересечения многоугольников

.3            Построение условий попадания в полосу

.4            Математическая модель

.5            Анализ математической модели. Обоснование выбора метода решения

Выводы по разделу 2

. МЕТОД РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ. ОСОБЕННОСТИ АЛГОРИТМИЧЕСКОЙ РЕАЛИЗАЦИИ

.1            Построение дерева решений

.2            Построение набора правил отсечения

.3            Алгоритм непересечения многоугольников

.4            Алгоритм непересечения многоугольника и полосы

.5            Построение интерактивной оболочки

.7            Решение систем линейных алгебраических уравнений

Выводы по разделу 3

. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ. ОПИСАНИЕ ПРОГРАММНОГО ПРОДУКТА

.1            Теоретические сведения о языке UML

.2            Варианты использования

.3            Диаграммы взаимодействия

.4            Диаграмма классов

4.5           Диаграмма состояния

4.6           Системные требования

.7            Руководство пользователя

.8            Пример работы

Выводы по разделу 4

. ОХРАНА ТРУДА

.1            Характеристика производственного помещения

.2            Выявление опасных и вредных факторов, действующих на пользователей ПК

.3            Мероприятия по снижению влияния опасных и вредных факторов действующих на пользователей ПК

Выводы к разделу 5

. ЭКОНОМИЧЕСКАЯ ЧАСТЬ

.1            Описание программного продукта

.2            Оценка рынка сбыта

.4            Расчет обобщенных показателей качества

Выводы к разделу 6

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Приложение А - Листинг программы

ВВЕДЕНИЕ

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

Интенсивные исследования в данной области были начаты в пятидесятых годах. В настоящее время изучение задач осуществляется по двум взаимосвязанным направлениям. С одной стороны, создание формального математического аппарата и выявление особенностей задач на основе единого подхода к их описанию. С другой стороны, использование специфики каждой конкретной задачи, что позволяет свести ее к соответствующему классу задач математического проектирования.

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

Исследование R-функций показало их принципиальную возможность применения для математической постановки задач геометрического проектирования. Однако непосредственное использование этой теории на практике возможно лишь в сравнительно простых случаях. Дело в том, что необходимость многократной проверки условий, накладываемых на взаимоотношение располагаемых объектов, приводит к значительным затратам машинного времени, объема памяти и других ресурсов ЭВМ.

Преодолеть эти трудности стало возможно благодаря многочисленным работам Стояна Ю.Г. и его учеников. Вначале был создан математический аппарат, основанный на использовании функции плотного размещения и её годографа, что позволило преобразовать информацию о размещаемых объектах в информацию об их возможных плотных размещениях. На этой основе была разработана методология последовательно-одиночного размещения. Это позволило осуществить разработку автоматической (без участия человека) системы решения задач размещения достаточно большого набора объектов нерегулярной формы. Получаемые результаты давали хорошие приближения к локальному, а иногда и к глобальному минимуму. Большое количество экстремумов задачи вызвало необходимость перебора приближений полученных решений к локальным экстремумам.

В дальнейшем получила должное развитие методология построения точной математической модели и основанных на ней методов решения исследуемой задачи. Было введено понятие Ф-функции, формализующей геометрические отношения непересечения геометрических объектов и являющиеся качественной мерой выполнения этих отношений. После появилась теория, обосновывающая построение структур линейных неравенств для построения условий непересечения. Понятие структуры линейных неравенств, задающей в евклидовом пространстве некоторое точечное множество, тесно связано с предикатным описанием этого множества. Оно использует неравенства в качестве элементарных предикатов и обычные логические операции, заданные на бинарных множествах (дизъюнкции, конъюнкции и т.д.).

Применение для задания условий непересечения размещаемых объектов этих двух способов позволило сформулировать поставленную задачу как задачу математического программирования.

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

Постановка задачи: на полубесконечной полосе необходимо оптимальным образом разместить при соблюдении условий непересечения n произвольных ориентированных в общем случае невыпуклых многоугольников.

Для решения этой задачи с помощью ЭВМ необходимо построить адекватную математическую модель, создать и развить вычислительные методы её решения.

Целью исследования является создание программного продукта, который позволяет решить поставленную задачу, применив метод последовательного анализа вариантов.

Объект исследования: задача размещения многоугольников в полубесконечной полосе.

Предмет исследования: метод последовательного анализа вариантов.

Задача, рассматриваемая в работе, относится к классу задач оптимального размещения.

Интерес к множеству задач размещения вызван, с одной стороны, их сложностью и нетривиальностью математических моделей, необходимых для адекватного описания, а с другой стороны - широким спектром практических приложений.

Наиболее изученным является класс задач размещения прямоугольников (прямоугольных параллелепипедов) в прямоугольной области для которых разработаны эффективные эвристические методы.

Анализ работ позволяет сделать следующие выводы. Если статья посвящена описанию точной математической модели задачи размещения в терминах классического математического программирования, то отсутствует описание алгоритма и его реализации, построенных на основании математической модели. С другой стороны, если в работе говорится о численных результатах и приводятся примеры решенных задач, то методология решения основана на эвристиках и нет доказательства оптимальности полученного решения. Кроме того, математические модели, которые рассматриваются в указанных работах, не позволяют говорить даже о локальном экстремуме.

В нашей стране одной из первых фундаментальных работ, посвященных изучению методов размещения геометрических тел с учетом их формы и размеров, является монография Л.В. Канторовича и В.А. Залгаллера [1]. В ней для построения оптимальных планов раскроя плоских материалов на прямоугольные заготовки используется метод разрешающих индексов, предложенный Л.В. Канторовичем.

Для задач размещения объектов более сложной формы непосредственное применение указанных методов, однако, оказалось невозможным и для решения практических задач такого рода широко использовались различные эвристические приемы.

Важным шагом вперед, позволившим аналитически описывать объекты сложной геометрической формы и использовать математический аппарат классического анализа для их исследования, было создание В.Л Рвачевым теории R-функций [2]. Однако непосредственное применение R-функций при решении задач нерегулярного размещения геометрических объектов сложной формы для описания условий их взаимного непересечения оказалось излишне громоздким и требующим значительных вычислительных затрат.

Универсальный конструктивный математический аппарат, позволяющий строить аналитическое описание условий взаимного расположения объектов с учетом любых технологических ограничений, был разработан в работах научной школы, возглавляемой Ю.Г. Стояном.

Первым шагом в этом направлении было создание функции плотного размещения, её годографа, и построение на этой основе методологии последовательно-одиночного размещения [3,4]. Это позволило осуществить разработку автоматической (без участия человека) системы решения задач размещения достаточно большого набора объектов нерегулярной формы. Получаемые результаты давали хорошие приближения к локальному, а иногда и к глобальному минимуму. Большое количество экстремумов задачи вызвало необходимость перебора приближений полученных решений к локальным экстремумам.

В дальнейшем методология построения точной математической модели и методов решения исследуемой задачи получила должное развитие в работе Стояна Ю.Г. [5], введено понятие Ф-функции, формализующей геометрические отношения непересечения геометрических объектов и являющиеся качественной мерой выполнения этих отношений.

После появилась теория, обосновывающая построение структур линейных неравенств, для условий непересечения. Понятие структуры линейных неравенств, задающей в евклидовом пространстве некоторое точечное множество, тесно связано с предикатным описанием этого множества. Оно использует неравенства в качестве элементарных предикатов и обычные логические операции, заданные на бинарных множествах (дизъюнкции, конъюнкции и т.д.)

На сегодняшний день задача размещения объектов произвольной формы продолжает оставаться актуальной во многих отраслях промышленной деятельности. Поэтому необходимо удовлетворять условиям непересечения объектов. Для построения этих условий будем использовать Ф-функции и их предикатное представление. Неотрицательная область Ф-функции может быть описана несколькими способами:

с помощью предикатного описания [6];

с помощью R-функций [2];

с помощью структур линейных неравенств [7].

R-функции позволяют представить Ф-функции с помощью дифференцируемой функции, которая, однако, оказывается нелинейной. В работе для описания Ф-функции выбран предикатный метод описания, т.к. он первичный для R-функций и структур линейных неравенств.

1.2 Формализация предметной области

В работе дана полубесконечная полоса с фиксированной шириной, на которой необходимо оптимально разместить заданное количество ориентированных многоугольников, так чтобы они не пересекались.

Для описания полосы введем следующие обозначения:

 - полубесконечная полоса;

b - ширина полосы;

 - длина полосы.

Рисунок 1.1 - Полубесконечная полоса

С каждым многоугольником, помещённым в полосу, свяжем собственную систему координат. Центры этих систем называются полюсами многоугольников. Координаты полюсов будем задавать относительно неподвижной системы координат полосы.

Введем обозначения (рис. 1.2):

- многоугольник, размещаемый в полосе;

- набор размещаемых многоугольников;

 - количество вершин (сторон) i-ого многоугольника;

- координаты полюса i-го многоугольника в неподвижной системе координат;

 - r-я вершина i-го многоугольника, где ;

 - координаты r-й вершины i-го многоугольника в собственной системе координат (СК);

 - r-й отрезок границы i-го многоугольника, где . Здесь и далее будем полагать, что .

Набор координат всех полюсов относительно неподвижной СК и будет составлять размещение в полосе.

Рисунок 1.2 -