Материал: Розробка автоматизованої системи оптимального використання заготовок за для розкрою площинних матеріалів

модуль Canvas, потужний інструмент для роботи з двомірної графікою. Він використовує принцип структурування графіки, що, безсумнівно, буде корисно в програмуванні простих двомірних ігор і подібного роду речах. Полотно складається з кількох " елементів ", кожен елемент представлений об'єктом. об'єктів з певними швидкостями по осях ;

модуль Network, що забезпечує підтримку мережі в додатках;

модуль OpenGL, що дозволяє працювати з тривимірною графікою за допомогою бібліотеки OpenGL. Підтримується з версії 2.3.2. ;

модуль SQL, який реалізує доступ до баз даних з додатків Qt. Даний модуль розбитий на три рівні: користувальницький (елементи інтерфейсу ), програмний ( абстрактний доступ до баз даних) і рівень драйверів ;

модуль Table, що надає у ваше розпорядження сітку для відображення табличних даних. Сітка являє собою дуже потужний і гнучкий інтерфейс, працювати з яким - одне задоволення ;

модуль XML, що використовує інтерфейс SAX2 і реалізацію DOM другого рівня.

.2 Розробка блок-схем алгоритмів та їх оптимізація

Пропонується алгоритм послідовного розміщення прямокутників, в основі якого лежать розумні стратегії. Передбачається, що прямокутники впорядковані. Алгоритм ітерації за ітерацій послідовно розміщує один прямокутник за іншим у заданому порядку. Якщо немає можливості розмістити прямокутник, він пропускається і розглядається наступний. Так продовжується до тих пір, поки всі прямокутники не будуть переглянуті.

Алгоритм на початку кожної ітерації формує обмежене число вузлів - точок в області розміщення. Потім намагається розмістити у вузли згідно деякої стратегії черговий прямокутник. Для кожного варіанту розміщення розраховується значення критерію з урахуванням розміщених на попередніх ітераціях об'єктів. З усіх варіантів розміщення вибирається найкращий з точки зору функції мети (формула 4.4). Опишемо детально етапи роботи алгоритму ( рис. 5.1).

Вхідні дані А1 : 1 ) параметри завдання, 2) упорядкована послідовність прямокутників.

Перебрати всі прямокутники в зазначеному порядку. Для кожного прямокутника :

А2 - за допомогою стратегії пошуку вузлів сформувати безліч вузлів для розміщення ;

А3 - кращий вузол не заданий ;

А4 - перебрати всі вузли розміщення. Для кожного вузла:

А5 - зберегти частково побудоване розміщення ;

А6 - помістити прямокутник у вузол згідно стратегії розміщення ;

А7 - перевірити обмеження ( формула 4.1), (формула 4.2). Якщо обмеження порушені - перехід до А11 ;

А8 - розрахувати значення критерію (формула 4.3) ;

А9 - якщо кращий вузол не заданий, то поточний вузол вважати кращим.

А10 - якщо значення критерію кращого вузла менше значення критерію поточного вузла, то поточний вузол вважати кращим ;

А11 - відновити збережене в А5 частково побудоване розміщення і перейти до наступного вузла ;

А12 - якщо кращий вузол знайдений, то помістити прямокутник в кращий вузол згідно стратегії розміщення.

А13 - перейти до наступного прямокутнику.

Рисунок 5.1 - Алгоритм послідовного розміщення

Для пошуку вузлів для розміщення використовуємо базову стратегію пошуку вузлів (рис. 5.2). Вхідні дані В1: 1) параметри завдання, 2) частково побудоване розміщення; 3) розміщений прямокутник Рі.

В2 - список вузлів розміщення порожній;

В3 - додати в список вузлів розміщення точку початку координат;

В4 - перебрати всі розміщені прямокутники в частково побудованому рішенні. Для кожного прямокутника:

В5 - додати в список вузлів розміщення точки (якщо вони раніше не були додані):

В6 - перейти до наступного прямокутнику;

В7 - список вузлів сформований.

Рисунок 5.2 - Алгоритм базової стратегії пошуку вузлів

Базова стратегія легко реалізується і не вимагає значних обчислювальних ресурсів, тому що не потрібно для кожного прямокутника перераховувати заново весь набір вузлів.

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

Вхідні дані С1: 1) параметри завдання, 2) частково побудоване розміщення; 3) поточне безліч вузлів розміщення ; 4) безліч вже розміщених прямокутників  5) розміщується прямокутник  з довжиною xpi та висотою xpj.

Кожному вузлу uk поставимо у відповідність прямокутник wk із розмірами  і координатою лівого верхнього кута в точці (0, 0). Нехай функція  повертає загальну площу перетину двох розміщених на площині прямокутників  та . Тоді запропонований алгоритм виглядає наступним чином:

С2 - перебираються всі вузли . Для кожного вузла обчислюється значення ;

С3 - серед всіх вузлів  вибирається той, для якого значення  мінімально.

Рисунок 5.3 - Алгоритм критерій оцінки якості вузлів розміщення

автоматизована розкрой площинний програмний

Як показує практика, використання техніки розбиття вихідної задачі на підзадачі менших розмірностей дозволяє підвищити якість одержуваних рішень і прискорити роботу алгоритму.

.3 Вибір та обґрунтування апаратного забезпечення проектованої системи

Апаратне забезпечення (англ. hardware) - комплекс технічних засобів, який включає ЕОМ: зовнішні пристрої, термінали, абонентські пункти тощо, які необхідні для функціонування тієї чи іншої системи; фізична частина ЕОМ.

Для роботи з даною програмою користувачу необхідне наступне апаратне забезпечення:

комп’ютер;

монітор;

клавіатура;

миша.

Комп’ютер необхідний для встановлення та запуску програми, монітор - для її відображення користувачу розкрою. За допомогою комп’ютерної миші користувач може запустити програму, та загрузити необхідні дані для розрахунку розкрою. Клавіатура необхідна на той випадок, якщо оператор хоче власноручно корегувати дані.

Особливих вимог до фірми виготовлювача не передбачено. Чим вищі параметри апаратного забезпечення комп’ютера, тим швидше програма буде видавати результат.

.4 Розробка вихідних текстів програмного забезпечення та вибір стандартного програмного забезпечення

Розглянемо файл widget.cpp. Структура widget зберігає у собі список всіх необхідних полів для коректних маніпуляцій програми.

Перелічимо всі основні замінні програми:_arr - масив прямокутників- довжина прямокутника;- ширина прямокутника;

х - координата крайньої точки;

у - координата крайньої точки.

: QWidget(parent)

{= new QGraphicsView;= new QGraphicsScene;= new QMenuBar;= new QToolBar ;= new QStatusBar;_form = new QWidget;_form->setWindowTitle("Загрузить координаты");*load_lay = new QGridLayout;_view = new QListWidget;_load = new QPushButton("Открыть файл...");_submit = new QCommandLinkButton("Подтвердить");_lay->addWidget(do_load);_lay->addWidget(list_view);_lay->addWidget(load_submit);_form->setLayout(load_lay);*paint_btn = new QToolButton;_btn->setText("Построить");>addWidget(paint_btn);*f_menu = new QMenu("Файл");*s_menu = new QMenu("Редактировать");*a_menu = new QMenu("Справка");*open_act = f_menu->addAction("Загрузить");*save_act = f_menu->addAction("Сохранить");_menu->addSeparator();*exit_act = f_menu->addAction("Выход");>addMenu(f_menu);>addMenu(s_menu);>addMenu(a_menu);*lay = new QGridLayout;>setMenuBar(mainmenu);>addWidget(toolbar);>addWidget(viewer);>addWidget(statusbar);(lay);("Squares");(500,400);>setScene(scene);(paint_btn,&QToolButton::clicked,this,&Widget::paint_it);(open_act,&QAction::triggered,load_form,&QWidget::show);(save_act,&QAction::triggered,this,&Widget::save_to_file);(exit_act,SIGNAL(triggered(bool)),qApp,SLOT(quit()));(do_load,&QPushButton::clicked,this,&Widget::load_from_file);(load_submit,&QCommandLinkButton::clicked,load_form,&QWidget::close);

}

Функція необхідна для виводу прямокутників:Widget::paint_it(){*buffer = new QPoint;(int i=point_arr.count()-1;i>0;i--)(int j=0;j<i;j++)(point_arr.at(j)->x()>point_arr.at(j+1)->x() || point_arr.at(j)->x()>point_arr.at(j+1)->x()){>setX(point_arr.at(j)->x());>setY(point_arr.at(j)->y());_arr.at(j)->setX(point_arr.at(j+1)->x());_arr.at(j)->setY(point_arr.at(j+1)->y());_arr.at(j)->setX(buffer->x());_arr.at(j)->setY(buffer->y());

}nx=0, ny=0;(int i=0; i<point_arr.count(); i++){>addRect(nx,ny,point_arr.at(i)->x(),point_arr.at(i)->y());=point_arr.at(i)->x();=point_arr.at(i)->y();

}

}

Функція load_from_file() завантажує файл с координатами прямокутників: Widget::load_from_file(){_view->clear();_arr.clear();lst;fileName = QFileDialog::getOpenFileName(this,tr("Открыть"), "", "Текст (*.txt)");file(fileName);(file.open(QIODevice::ReadOnly |QIODevice::Text)){(!file.atEnd()){.clear();str = file.readLine();_view->addItem(str);= str.split(" ");= new QPoint;->setX(lst.at(0).toInt());->setY(lst.at(1).toInt());_arr.push_back(point1);

}

}

}

Після того як оператор виконав всі розрахунки, та маніпуляції з розкроєм, він може забрести свої результати. Для цього в програмі існує така функція save_to_file: Widget::save_to_file(){image(scene->width(), scene->height(), QImage::Format_ARGB32_Premultiplied);painter(&image);>render(&painter);fileName = QFileDialog::getSaveFileName(this, tr("Save File"),"",tr("Images (*.png)"));.save(fileName);

}

Що стосується стандартного програмного забезпечення, то для роботи з даною системою на комп’ютері користувача мають бути встановлені:

налаштована операційна система Windows, зі всіма необхідними для ПК драйверами;

Встановлений.NET Framework.

При дотриманні вищевказаних вимог, дане програмне забезпечення буде працювати коректно.

5.5 Компіляція та тестування ПО

Для того щоб запустити програму необхідно відкрити файл squares_img.exe. Наступним кроком є відкриття текстового файлу або набір тексту з клавіатури. Для того щоб відкрити файл необхідно натиснути Файл→Відкрити. В програмі встановлений фільтр, а отже користувач зможе відкрити лише файл з форматом *.txt.

В якості вхідних даних завантажуємо текстовий файл з наступним текстом:

20 0

14 0

30 0

10 0

15 0

23 0

20 0

14 0

30 0

10 0

15 0

23 0

20 0

14 0

30 0

10 0

15 0

23 0

Проведемо ряд тестів, для виявлення помилок в проектованій системі.

Тест 1: В даному тесті, поведемо перевірку, оптимального розміщення прямокутників на полотні. Перевіримо працездатність ПЗ оптимізацію, причому проведемо тест 40 разів, засікаючи при цьому час (рис. 5.4)

Рисунок 5.4 - Тест 1

Як видно з даного тесту, всі прямокутники розташовані оптимально на полотні, з мінімальними затратами полотна. Середня обробка програмного забезпечення 1.84 секунди. Тобто, на обробку одного прямокутнику необхідно 0,00283951 секунди часу.

Тест 2: В даному тесті поміняємо місцями в текстовому файлі координати прямокутників, щоб вдостовіритись, що їхнє положення у файлі не міняє результату після оптимізації на полотні(рис 5.5).

Рисунок 5.5 - Тест 2

Як видно з тесту 2, програма знов вистроїла усі прямокутники оптимально, с мінімальними затратами полотна. Алгоритм побудований таким чином, що вся прямокутники спочатку обробляються, а потім вистараються на полотні.

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

. РОЗРОБКА ПРОГРАМНОЇ ДОКУМЕНТАЦІЇ

6.1 Вихідні тексти проектованої системи

Вихідні тексти файлу widget.cpp. Даний файл представляє собою структуру, яка береже в собі список всіх необхідних полів, для коректних маніпуляцій програми.

#include "widget.h"::Widget(QWidget *parent)

: QWidget(parent)

{= new QGraphicsView;= new QGraphicsScene;= new QMenuBar;= new QToolBar ;= new QStatusBar;_form = new QWidget;_form->setWindowTitle("Загрузить координаты");*load_lay = new QGridLayout;_view = new QListWidget;_load = new QPushButton("Открыть файл...");_submit = new QCommandLinkButton("Подтвердить");_lay->addWidget(do_load);_lay->addWidget(list_view);_lay->addWidget(load_submit);_form->setLayout(load_lay);*paint_btn = new QToolButton;_btn->setText("Построить");>addWidget(paint_btn);*f_menu = new QMenu("Файл");*s_menu = new QMenu("Редактировать");*a_menu = new QMenu("Справка");*open_act = f_menu->addAction("Загрузить");*save_act = f_menu->addAction("Сохранить");_menu->addSeparator();*exit_act = f_menu->addAction("Выход");>addMenu(f_menu);>addMenu(s_menu);>addMenu(a_menu);*lay = new QGridLayout;>setMenuBar(mainmenu);>addWidget(toolbar);>addWidget(viewer);>addWidget(statusbar);(lay);("Squares");(500,400);>setScene(scene);(paint_btn,&QToolButton::clicked,this,&Widget::paint_it);(open_act,&QAction::triggered,load_form,&QWidget::show);(save_act,&QAction::triggered,this,&Widget::save_to_file);(exit_act,SIGNAL(triggered(bool)),qApp,SLOT(quit()));(do_load,&QPushButton::clicked,this,&Widget::load_from_file);(load_submit,&QCommandLinkButton::clicked,load_form,&QWidget::close);

}::~Widget()

{

}Widget::paint_it(){*buffer = new QPoint;(int i=point_arr.count()-1;i>0;i--)(int j=0;j<i;j++)(point_arr.at(j)->x()>point_arr.at(j+1)->x() || point_arr.at(j)->x()>point_arr.at(j+1)->x()){>setX(point_arr.at(j)->x());>setY(point_arr.at(j)->y());_arr.at(j)->setX(point_arr.at(j+1)->x());_arr.at(j)->setY(point_arr.at(j+1)->y());_arr.at(j)->setX(buffer->x());_arr.at(j)->setY(buffer->y());

}nx=0, ny=0;(int i=0; i<point_arr.count(); i++){>addRect(nx,ny,point_arr.at(i)->x(),point_arr.at(i)->y());

*if(i>1){(point_arr.at(i)->y()>point_arr.at(i-1)->y()+point_arr.at(i+1)->y()){=point_arr.at(i)->y();

}

}*/=point_arr.at(i)->x();=point_arr.at(i)->y();

}

}Widget::load_from_file(){_view->clear();_arr.clear();lst;fileName = QFileDialog::getOpenFileName(this,tr("Открыть"), "", "Текст (*.txt)");file(fileName);(file.open(QIODevice::ReadOnly |QIODevice::Text)){(!file.atEnd()){.clear();str = file.readLine();_view->addItem(str);= str.split(" ");= new QPoint;->setX(lst.at(0).toInt());->setY(lst.at(1).toInt());_arr.push_back(point1);

}

}

}Widget::save_to_file(){image(scene->width(), scene->height(), QImage::Format_ARGB32_Premultiplied);painter(&image);>render(&painter);fileName = QFileDialog::getSaveFileName(this, tr("Save File"),"",tr("Images (*.png)"));.save(fileName);

}

.2 Опис проектованої системи

Дане програмне забезпечення входить до групи програм «оптимізація положення», а тому дозволить користувачу в лічені секунди оптимізувати розкрій на полотні. Це значним чином скоротить час користувача, адже йому не треба буде самостійно, власноруч розраховувати всі данні, щоб оптимально розложити весь розкрій на полотні, а коли це полотно може бути умовно нескінченним - для користувача це і зовсім не можливо.

Алгоритм проектованої системи побудований на відомому алгоритмі послідовного розміщення, котрий застосовує базову стратегію пошуку вузлів.

Перш за все, дана програма стане у пригоді розробникам текстилю, целюлозно-паперової, металургійної и т.д. індустрії. Завдяки оптимізації розкрою, оператор економить дорогоцінний час, а також, не менш ціні кошти на полотно. Завдяки програмному забеспеченю можна скоротити кількість фахівців до одного оператора, з базовими знаннями комп’ютерної техніки.

Дане програмне забезпечення виведе зображення оптимального розкрою, за короткий час, зможе зберегти результати оптимізації до файлу зображення. Детальніший опис програми представлений в розділі 6ю3 курсової роботи.

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

.3 Інструкції з використання проектованої системи

Для того, щоб почати працювати з даною програмою, необхідно відкрити файл squares_img.exe. Програма складається з чотирьох робочих елементів, рисунок 6.1.

Рисунок 6.1 - Програма squares_img

Перша робоча область представляє собою панель управління. За допомогою цієї панелі, користувач зможе виконувати різноманітні функції.

Друга робоча область, представляє собою графічний вихід розкрою на полотні.

В третій робочій області відображається результат програми. В даній області користувач має можливість переглянути скільки часу знадобиться для оптимізації, так скільки вже пройшло часу.