Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

• ВВЕДЕНИЕ
• 1. АНАЛИТИЧЕСКИЙ ОБЗОР ПРОБЛЕМЫ РАЗМЕЩЕНИЯ МНОГОУГОЛЬНИКОВ
• 1.1 Обзор литературы
• 1.2 Формализация предметной области
• 1.3 Постановка задачи
• Выводы по разделу 1
• 2. ПОСТРОЕНИЕ И АНАЛИЗ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ РАЗМЕЩЕНИЯ МНОГОУГОЛЬНИКОВ
• 2.1 Представление области допустимых решений с помощью Ф-функции
• 2.2 Предикатное представление условий непересечения многоугольников
• 2.3 Построение условий попадания в полосу
• 2.4 Математическая модель
• 2.5 Анализ математической модели. Обоснование выбора метода решения
• Выводы по разделу 2
• 3. МЕТОД РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ. ОСОБЕННОСТИ АЛГОРИТМИЧЕСКОЙ РЕАЛИЗАЦИИ
• 3.1 Построение дерева решений
• 3.2 Построение набора правил отсечения
• 3.3 Алгоритм непересечения многоугольников
• 3.4 Алгоритм непересечения многоугольника и полосы
• 3.5 Построение интерактивной оболочки
• 3.6 Определение направления обхода вершин многоугольника
• 3.7 Решение систем линейных алгебраических уравнений
• Выводы по разделу 3
• 4. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ. ОПИСАНИЕ ПРОГРАММНОГО ПРОДУКТА
• 4.1 Теоретические сведения о языке UML
• 4.2 Варианты использования
• 4.3 Диаграммы взаимодействия
• 4.4 Диаграмма классов
• 4.5 Диаграмма состояния
• 4.6 Системные требования
• 4.7 Руководство пользователя
• 4.8 Пример работы
• Выводы по разделу 4
• 5. ОХРАНА ТРУДА
• 5.1 Характеристика производственного помещения
• 5.2 Выявление опасных и вредных факторов, действующих на пользователей ПК
• 5.3 Мероприятия по снижению влияния опасных и вредных факторов действующих на пользователей ПК
• Выводы к разделу 5
• 6. ЭКОНОМИЧЕСКАЯ ЧАСТЬ
• 6.1 Описание программного продукта
• 6.2 Оценка рынка сбыта
• 6.3 Расчет себестоимости и цены программного продукта
• 6.4 Расчет обобщенных показателей качества
• Выводы к разделу 6
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
• Приложение А - Листинг программы
• ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С полосой свяжем неподвижную систему координат с началом в левом нижнем углу (рис. 1.1).

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

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

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

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

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

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

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

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

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

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

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

Рисунок 1.2 - Размещение многоугольников в полосе

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

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

 (1.1)

Т.е. ставится задача о нахождении размещения полюсов () в . На размещения накладываются ограничения непересечения и попадание в полосу.

Необходимо построить область допустимых решений .

где - многоугольник, зависящий от положения полюса.

Условие (1.2) описывает попадания в область i-го многоугольника, а (1.3) - их попарное непересечение.

Поэтому задачу можно сформулировать так:

,

(1.4)

Для использования эффективных методов при решении этой задачи необходимо представить (1.2, 1.3) в виде ограничений переменных задачи в линейном пространстве . Этому будет посвящена следующая глава.

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

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

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

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

Для формализации условий непересечения был применен аппарат Ф-функций.

Ф-функции вводят для каждой пары (i,j) размещаемых объектов. При определении и описании их свойств необходимо учесть особенности нашей задачи. Зависимость объекта от значения вектора переменных соответствующей геометрической информации [5] будем выражать в виде -. Информацию о двух объектах представим в виде вектора ,.

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

, если (2.1)

, если

(2.2)

, если (2.3)

- замыкание множества .

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

Теперь условия (1.2),(1.3) можно записать в виде Ф-функций. Запишем условие (1.2) в виде Ф-функции:где - дополнение.

Преобразуем полученное выражение, получим:

(2.4)

Условие (1.3) соответствует неравенству

(2.5)

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

(2.6)

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

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



Рисунок 2.1 - Размещение многоугольников в полосе

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

(2.7)

Каждая пара соседних вершин определяет одно из неравенств вида (2.7). Коэффициенты этих неравенств определяются по формулам [10] (обход вершин происходит против часовой стрелки):

(2.8)

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

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

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

Условие равносильно выражению , а это означает, что

(2.9)

Теперь из всех k выберем ближайшую точку и обозначим её . Получим:

(2.10)

Аналогично можно показать, что условие равносильно выражению

Разобьем каждый i-ый многоугольник на выпуклых многоугольников.

Обозначим через , количество вершин в -м и -м выпуклых многоугольниках.

(2.11)

Пусть , тогда преобразуем полученное выражение (2.11):

(2.12)

Таким образом, для представлений условий непересечения с помощью предикатов получаем неравенство (2.12) эквивалентное (1.3).

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

Выше было показано предикатное представление Ф-функции для условий непересечения объектов в области D. Теперь изобразим такое же представление для условия (1.2). Для этого построим рисунок 2.2.

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



Рисунок 2.2 - Построение условий попадания в полосу

Из построенного рисунка видно, что объект попадает в область , если его полюс попадает в . Опишем это условие. Введем обозначения:

- расстояние от левой границы полосы до .

- расстояние от левой границы полосы до .

Полуплоскость справа от левой границы можно задать так:

или . (2.13)

Полуплоскость слева от правой границы:

или (2.14)

Нижние и верхние ограничения будут выглядеть следующим образом:

или (2.15)

или (2.16)

Объединяя для всех многоугольников ограничения, получим:

(2.17)

Таким образом, получено описание -функции с помощью предикатов.

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

Таким образом, математическая модель имеет вид , где , , а описание области допустимых решений D получается объединением ограничений на попадания объектов в полосу (2.12) и их непересечения (2.17):

(2.18)

Проведем анализ полученной области.

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

Свойства области D:

1. Если множество D не пусто, то оно ограниченно.

2. Область .

3. Область D при невыпуклая и в общем случае несвязная.

4. Функция цели линейная.

5. Все условия, составляющие ограничения на размещения - линейные неравенства, поэтому полученная область имеет форму многогранника.

6. Экстремум лежит в крайней точке области - вершине, т. к. функция цели линейна.

7. Все крайние точки определяются комбинациями уравнений из набора, построенного по формулам (2.10), (2.13)-(2.16).

Следуя методу разбиения области допустимых решений на выпуклые подмножества, можно привести такую верхнюю оценку числа систем уравнений:

(2.19)

где - оценка числа выпуклых подмножеств области D;

, - количество условий непересечения объектов;

- размерность системы неравенств, определяющих каждое из таких подмножеств;

- верхняя оценка числа вершин каждой выпуклой подобласти области D.

Разрешимость задачи определяется только выполнением условий размещения в полосе по переменным .

Задача является многоэкстремальной.

Так как системы уравнений, полученные из набора неравенств (2.11) и (2.17) определяют не только вершины области допустимых решений, но и внутренние и внешние точки, то следует бесперспективные решения сразу отбрасывать, не решая систему уравнений.

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

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

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

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

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

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

- перебор вершин области допустимых решений;

- перебор выпуклых подмножеств области допустимых решений.

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

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

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

Согласно свойству 7 области D, функция цели Z задачи (1.4) достигает своего глобального минимума в вершинах области D.

В разделе 2 было отмечено, что не все точки области D, задаваемые линейно независимыми системами уравнений, являются вершинами. Рассматриваемое множество точек включает в себя точки вне области, внутренние точки области и т. д.

Отметим, что экстремум функции цели Z может достигаться не только в вершине X, но и на некоторой q-грани R произвольной размерности, вплоть до размерности (2n-1). Очевидно, q-грани L будет необходимо принадлежать и вершина области D, поэтому в дальнейших рассуждениях ограничимся анализом множества вершин области D.

Следуя методу разбиения области допустимых решений на выпуклые подмножества, можно привести такую верхнюю оценку числа систем уравнений:

 , (3.1)

где - оценка числа выпуклых подмножеств области D;

, - количество условий непересечения объектов;

- размерность системы неравенств, определяющих каждое из таких подмножеств;

- верхняя оценка числа вершин каждой выпуклой подобласти области D.

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

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

Процесс построения некоторой вершины области D можно представить себе как процедуру последовательного выделения гиперплоскостей, уравнения которых входят в систему Fx=b, определяющую некоторую точку .

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

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

На последнем уровне дерева вершины его соответствуют некоторой точке . Точки Х получены как пересечение некоторого линейного многообразия и гиперплоскости, уравнение которой содержит независимую переменную Z с ненулевым коэффициентом. Каждая вершина (m-1)-ого уровня имеет n потомков, так как независимая переменная Z с ненулевым коэффициентом входит всего в n уравнений.

Итак, дерево решение имеет m=2n+1 уровней - по числу независимых переменных задачи. Оценка числа систем уравнений построенных на m-ом уровне - . Дерево решений позволяет получить все системы уравнений, соответствующие неравенствам из (2.18) и тем самым описать все вершины области. Для сокращений числа систем уравнений, подлежащих решению на последнем уровне дерева, путем исключения из множества всех систем уравнений, заведомо не определяющих вершину области D, необходимо построить достаточно эффективный набор правил отсечения бесперспективных вершин дерева решений.

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

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

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

Стратегия выбора на каждом шаге кандидатов - частичных решений, подлежащих развитию, такова: выбор кандидата на (k+1)-м шаге алгоритма осуществляется из множества частичных решений, присоединенных к списку на предыдущем шаге, и только тогда, когда не содержит частичных решений, необходимо обратиться ко всему списку.

Итак, на m-м уровне дерева решений возможны следующие ситуации:

1. Построенная система уравнений Fx=b является линейно зависимой.

2. Построенная система является несовместной.

3. Система Fx=b определяет вершину области, в которой значение функции цели не является оптимальным.

4. Полученная система определяет точку вне области.

5. Система Fx=b ранга m определяет точку на границе области D, но не вершину.

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

7. Сформированная система Fx=b определяет внутреннюю точку области допустимых решений.

8. В полученной вершине пересекаются более m гиперплоскостей.

Правило отсечения 1. В системе m уравнений, определяющих точку , обязательно присутствует уравнения вида:

(3.2)

В общем случае .

Правило отсечения 2. Если на первых g уровнях дерева в систему Fx=b включены уравнения вида , то на m-м уровне эти уравнения в формировании системы Fx=b не участвуют и соответствующие вершины дерева не рассматриваются.

Правило отсечения 3. Если в системе уравнений Fx=b, соответствующей вершине дерева присутствует уравнение вида

то вершина дерева решений является концевой.

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

Правило отсечения 4. Пусть в текущей вершине дерева решений к составленной на предыдущих уровнях дерева систем уравнений добавляется уравнение

Алгоритм.

Шаг 1. Положить

Шаг 2. Вычислить относительно уравнения

Шаг 3. Положить k=k+1,l=0.

Шаг 4. Если k>n, закончить анализ; иначе идти к шагу 5.

Шаг 5. Положить l=l+1.

Шаг 6. Вычислить относительно уравнения .

Шаг 7. Для объектов и проверить условия взаимного непересечения.

Шаг 8. Если перейти к шагу 3; иначе идти к шагу 6.

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

Правило отсечения 5. Пусть на g-ом уровне дерева выбрана вершина такая, что определяет одну из четырех систем уравнений с уравнениями вида:

(3.3)

Тогда, если не выполнены условия взаимного непересечения - ого - ого объектов, рассматриваемого вершина является концевой.

Правило отсечения 6. Пусть вершина дерева решений определяет систему Fx=b, содержащую подсистему вида:

(3.4)

Положим и вычислим значение :

(3.5)

Тогда, если и или , то вершина является концевой.

Правило отсечения 6. Отметим, что биекция на системе уравнений Fx=b может задаваться конечным числом способов. Для отсечения вершин дерева решений, которые порождают системы уравнений, отличающиеся только способом задания , предлагается следующее правило отсечения.

Если на k-ом уровне (k-нечетное) выбрана вершина дерева , то на (k+1)-ом уровне выбирается вершина , причем .

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

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

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

Имеется набор из n неориентированных многоугольников. Для того, чтобы многоугольники не покрывали друг друга, достаточно их попарного не пересечения. Рассмотрим рисунок 3.1:

Рисунок 3.1 - Условие пересечения мноугольников

Воспользуемся утверждением (1): если хотя бы одна вершина одного многоугольника принадлежит другому многоугольнику или наоборот, то такие многоугольники пересекаются.

Действительно на рисунке 3.1 видим, что объекту принадлежит вершина , а объекту - соответственно вершина .

Для реализации алгоритма, основанного на утверждении (1), необходимо знать принадлежит та или иная точка многоугольнику. Рассмотрим рисунок 3.2:



Рисунок 3.2 - Принадлежность точки многоугольнику

Дополнительные обозначения:

- многоугольник,

- точка на плоскости,

- точки пересечения,

- горизонтальная прямая, проходящая через точку Х.

Требуется ответить на вопрос - принадлежит точка X многоугольнику .

Алгоритм, позволяющий определить принадлежность точки многоугольнику:

Шаг 1. Проводим горизонтальную прямую .

Шаг 2. Двигаемся слева направо от оси ординат вдоль прямой .

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

Шаг 4. Если число пересечений нечетно, то точка Х принадлежит многоугольнику , если четно - то точка Х не принадлежит многоугольнику.

Дополнительно рассматривается условие прохождения прямой через вершину многоугольника.

На рисунке 3.2 видим, что точка . Действительно число пересечений нечетно.

Такой алгоритм можно использовать и в случае, когда прямая проводится вертикально. Выбор именно горизонтального (вертикального) направления обусловлен более простым математическим описанием прямой.

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

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

Дано:

- набор многоугольников;

- размеры полосы (ширина и длина). Так как стоит реальная задача, то требуется привести полубесконечную полосу к конечной. Для чего и вводится дополнительный параметр - длина.

Требуется определить принадлежность многоугольника к полосе.

Рассмотрим рисунок 3.3:



Рисунок 3.3 - Принадлежность многоугольника полосе

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

Описание алгоритма:

Шаг 1. Присвоить значение абсциссы первой вершины многоугольника .

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

Шаг 3. Взять следующую вершину .

Шаг 4. Если абсцисса вершины , то .

Если абсцисса вершины , то .

Если ордината вершины , то .

Если абсцисса вершины , то .

Шаг 5. Если все вершины не перебрали, то перейти на шаг 3.

Шаг 6. Строим прямоугольник по полученной диагонали .

Шаг 7. Определяем принадлежность прямоугольника полосе.

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

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

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

Операции над геометрическими объектами:

- перемещение в любом направлении;

- поворот вокруг произвольной точки.

Режимы работы:

- режим перемещения;

- режим поворота;

- режим добавления многоугольника;

- режим удаления многоугольника;

- режим редактирования многоугольника (перемещение его вершин);

- режим добавления новой вершины;

- режим удаления вершины.

Элементы управления:

- манипулятор - мышь. Все операции, производимые над геометрическими объектами осуществляются исключительно мышью;

- клавиатура. Настроечные параметры вводятся вручную с клавиатуры.

Настроечные параметры:

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

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

- направление вращения.

Требуемые элементы интерфейса:

- меню, которое должно включать в себя: работу с файлами данных, задание настроечных параметров, выбор выполнимой задачи;

- кнопки, позволяющие выбирать режимы работы;

- панель инструментов;

- статусная строка.

Более подробная реализация каждого из элементов интерактивной оболочки приводится ниже.

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

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

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

3.6 Определение направления обхода вершин многоугольника

Для построения условий непересечения многоугольников требуется находить коэффициенты прямых по формуле (2.8). Было отмечено, что обход вершин многоугольника необходимо осуществлять против часовой стрелки. Ниже представлен алгоритм, определяющий направление обхода.

Найдем какую-нибудь внутреннюю точку A(x,y) выпуклого многоугольника, например, центр масс трех последовательных точек на контуре: A(x,y)=((x1+x2+x3)/3;(y1+y2+y3)/3).

На контуре выберем произвольно две последовательные вершины L1 и L2 и вычислим углы, которые образуют отрезки (A,L1) и (A,L2) с осью OX. Если первый угол меньше второго, то обход против часовой стрелки, иначе - по часовой.

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

В качестве метода решения СЛАУ был выбран метод SVD-разложения.

Для случая, когда система N линейных уравнений с N неизвестными Ax = b имеет одно и только одно решение, разработано большое число способов разрешения системы. Тем не менее, на практике иногда приходится решать системы уравнений, имеющие бесконечное число решений - в такой ситуации большинство методов откажутся работать, сообщив об ошибке.

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

Для решения используется сингулярное разложение матрицы A, т.е. её представление в виде A = U*W*V, где U имеет размер MxN (а также ортонормированные или нулевые столбцы), W - диагональная с неотрицательными элементами на главной диагонали (сингулярными значениями), V - ортонормированная размером NxN. Матрица A приводится к указанной форме, а после приведения такая система уравнений легко решается, если использовать указанные свойства матриц.

В случае, если определитель матрицы W не ноль, существует единственное точное решение, которое записывается в виде .

Если определитель ноль, то решение (или наилучшее приближение к нему) не единственно, вместо матрицы в произведении участвует диагональная матрица D, в которой , если не ноль, или , если ноль или близко к нолю.

Таким образом, получается частное решение.

Замечание 1.

Алгоритм SVD-разложения работает медленнее метода Гаусса, но обладает большей функциональностью и более устойчив при решении систем уравнений с плохо обусловленной матрицей.

Замечание 2.

На практике обычно сингулярные значения оказываются близки к 0, но ненулевые. Это происходит из-за погрешностей численных расчетов. Исходя из свойств SVD-разложения, можно ввести универсальную меру "близости к нолю" сингулярного значения для любой исходной матрицы A - если отношение исследуемого значения к максимальному из значений близко к машинной точности epsilon, то алгоритм считает это значение равным нулю и не использует его в расчетах.

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

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

Также были рассмотрены особенности алгоритмической реализации поставленной задачи, а именно:

- непересечения мноугольников;

- попадание многоугольников в полосу;

- алгоритмы работы интерактивной оболочки;

- направление обхода вершин многоугольника;

- алгоритм решения СЛАУ.

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

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

Часто при создании проекта трудно предусмотреть все аспекты его деятельности и его использования. Поэтому для создания объемных проектов используют моделирование. Моделирование - это устоявшаяся и повсеместно принятая инженерная методика, а модель - схема системы или чертеж.

Моделирование позволяет решить четыре различных задачи [8]:

- визуализировать систему в ее текущем или желательном для пользователя состоянии;

- определить структуру или поведение системы;

- получить шаблон, позволяющий затем сконструировать систему;

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

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

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

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

Первичные цели при создании UML (Unified Modelling Language) были следующими:

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

- предоставить механизмы расширения и специализации, для расширения заложенных концепций;

- быть независимым от определенного языка программирования и процесса разработки;

- предоставить формальную базу для понимания языка моделирования;

- интегрировать лучший практический опыт разработок.

UML должен и может поддерживать все приемлемые языки программирования. Он также должен и может поддерживать различные методы и процессы построения моделей.

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

Rational Rose, в отличие от подобных средств проектирования, способна проектировать системы любой сложности. CASE Rational Rose являясь объектно-ориентированным инструментом моделирования. Rose базируется на UML, который был разработан компанией Rational именно с целью создания наиболее оптимального и универсального языка для описания как предметной области, так и конкретной задачи в программировании. Любая задача программируется при помощи определенных диаграмм. В терминах представления модели UML определяет следующие графические диаграммы [9]:

- диаграммы вариантов использования (use case diagram) ,

- диаграммы классов (class diagram) ;

- диаграммы описания поведения включают:

§ диаграммы состояния (statechart diagram) ,

§ диаграммы активности (activity diagram) ;

- диаграммы взаимодействия включают:

§ диаграммы последовательности (sequence diagram),

§ диаграммы кооперации (collaboration diagram);

- диаграммы реализации включают:

§ диаграммы компонентов (component diagram),

§ диаграммы топологии, развертывания (deployment diagram).

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

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

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

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

Варианты использования - это то, что пользователь ожидает от системы. Рассмотрим каждый фрагмент этого определения по отдельности.

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

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

Рисунок 4.1 - Диаграмма вариантов использования

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

Диаграммы взаимодействия (interaction diagrams) являются моделями, описывающими поведение взаимодействующих групп объектов. Как правило, диаграмма взаимодействия охватывает поведение объектов в рамках только одного варианта использования. На такой диаграмме отображается ряд объектов и те сообщения, которыми они обмениваются между собой.

Сообщение (message) - средство, с помощью которого объект-отправитель запрашивает у объекта получателя выполнение одной из его операций.

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

Диаграмма последовательности соответствующая варианту использования «Ввод данных о геометрических объектах» представлена на рисунке 4.2:

Рисунок 4.2 - Диаграмма последовательности «Ввод данных о геометрических объектах»

Инженер может запросить объект «Главное окно» о вводе данных о многоугольниках вручную или из файла. В свою очередь «Главное окно» уведомляет объект-алгоритм о вводе данных.

На рисунке 4.3 видим последовательность ввода параметров размещения:



Рисунок 4.3 - Диаграмма последовательности «Ввод параметров размещения»

Ввод параметров размещения аналогичен вводу данных о многоугольниках.

На рисунке 4.4 представлен процесс получение решения:

Рисунок 4.4 - Диаграмма последовательности «Получение решения»

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

На рисунке 4.5 видим последовательность сохранения полученных результатов:

Рисунок 4.5 - Диаграмма последовательности «Сохранение результатов работы»

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

Вторым видом диаграммы взаимодействия является кооперативная диаграмма.

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

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

4.4 Диаграмма классов

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

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

Разработчики используют диаграммы классов для реального создания классов. Такие CASE-средства, как Rational Rose, могут генерировать основу кода классов, которую затем программисты заполняют деталями на выбранном ими языке. С помощью этих диаграмм аналитики могут показать детали системы, а архитекторы системы -- понять ее проект. Если, например, какой-либо класс несет слишком большую функциональную нагрузку, это будет видно на диаграмме классов, и архитектор сможет перераспределить ее между другими классами. Если между сообщающимися классами не определено никаких связей, это также будет видно на диаграмме. Диаграммы классов следует создавать, чтобы показать взаимодействующие классы в каждом варианте использования, можно создавать также более общие диаграммы, охватывающие все системы или подсистемы целиком.

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

Существуют три различных точки зрения на построение диаграмм классов:

* концептуальная точка зрения. Если диаграммы классов рассматриваются с концептуальной точки зрения, то они будут отображать понятия изучаемой предметной области (моделируемой организации). Эти понятия, естественно, будут соответствовать реализующим их классам, однако такое прямое соответствие зачастую отсутствует. На самом деле, концептуальная модель может иметь весьма слабое отношение или вообще не иметь никакого отношения к реализующему ее программному обеспечению, поэтому ее можно рассматривать как независимую от средств реализации (языка программирования);

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

* точка зрения реализации. В этом случае модель действительно определяет реализацию классов ПО. Эта точка зрения является наиболее распространенной среди программистов.

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

При построении диаграммы точка зрения должна быть ясной и единственной. При чтении диаграммы следует выяснить, с какой точки зрения она строилась. Если нужно интерпретировать эту диаграмму правильным образом, то без такого знания не обойтись.

Точка зрения на диаграммы классов не является собственно формальной частью UML, однако при построении и анализе моделей она является крайне важной. Конструкции UML можно использовать с любой из трех точек зрения. Большинство опытных разработчиков-программистов предпочитают точку зрения реализации. С другой стороны, очевидно, что построение диаграмм классов на стадии формирования требований к ПО должно выполняться с концептуальной точки зрения.