Тезисы дипломной работы на тему «Размещение трапеций в полосе с различными переворотами»
ТЕЗИСЫ ДИПЛОМНОЙ РАБОТЫ НА ТЕМУ «РАЗМЕЩЕНИЕ ТРАПЕЦИЙ В ПОЛОСЕ С РАЗЛИЧНЫМИ ПЕРЕВОРОТАМИ»
– автор работы
Научный руководитель – доцент кафедры анализа данных и исследования операций
В данной работе рассматривалась задача размещения трапеций в полосе. Это задача раскроя прямоугольной полосы на заготовки заданных размеров в форме трапеций без отходов. Задача представляет практический интерес. К примеру, при производстве изделий исходный материал часто поступает в виде полос или рулонов, которые в дальнейшем раскраиваются на нужные части.
Задача решалась в трех следующих вариантах:
Трапеции укладываются в полосу без изменений; Трапеции можно поворачивать на 180 градусов; Трапеции можно поворачивать на 180 градусов, а также переворачивать наизнанку.Данная задача рассматривалась как задача теории графов. Трапеции представлялись в
виде ориентированных (в первом варианте) и неориентированных (во втором и третьем вариантах) псевдографов, в которых в дальнейшем строился эйлеров цикл. Порядок, в котором трапеции идут в этом цикле, и есть искомая укладка в полосу. В роли вершин графов выступали разности абсцисс координат боковых сторон, в роли рёбер – сами трапеции.
Алгоритм построения эйлерова цикла был реализован в двух частях. В первой части строился так называемый частичный эйлеров цикл – простой путь, являющийся частью эйлерова цикла, который начинается и заканчивается на вершине графа, соответствующей разности абсцисс координат боковой стороны, равной нулю (т. е. прямому углу). Во второй части алгоритма в «частичную» укладку вставлялись оставшиеся трапеции. В каждом из трех вариантов раскроя были применены различные подходы к алгоритмизации поиска эйлерового цикла.
Для тестирования работы приложения был продуман алгоритм генерации трапеций, которые гарантированно можно уложить в полосу. Полученные данным алгоритмом трапеции удовлетворяли условиям существования эйлерова цикла в графе. Был разработан интерфейс приложения для удобного ввода и вывода данных. Результаты выполнения программы были визуализированы.
Приложение было протестировано на наборах трапеций, как на сгенерированных алгоритмически, так и на тех, что не удовлетворяют условиям существования эйлерова цикла. В первом случае программа всегда выдает верный результат, во втором – сообщает о его невозможности. Были проведены эксперименты по выявлению зависимости времени работы программы от объёма входных данных.
