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

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

Інформаційне забезпечення в проектованій системі складається із трьох основних частин:

• вхідна інформація;
• проміжна інформація;
• вихідна інформація.

Далі будемо називати цю інформацію, як інформаційний потік. Інформаційний потік – це кількість інформації, яка проходить крізь перетин каналу зв’язку за одиницю часу. Також інформаційний потік можна визначити як визначений напрям переміщення інформації у просторі та часі; мірна величина, яка вимірюється як швидкість передачі інформації.

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

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

Дані проектованої системи можуть бути класифіковані за ступенем їх зміни у процесі роботи системи.

Вхідні дані. Верстак передає програмі інформацію про розмір полотна, розміри полотна можуть бути тільки позитивними - 2 змінні типу float = 128 біт (16 байт).

Оператор має можливість : ввести масив координат фігури , завантажити з зовнішнього пристрою або передати по локальній мережі. Кожен прямокутник має два параметри : довжина і ширина . Один прямокутник , що складається з двох параметрів мають тип float , займає 128 біт ( 16 байт) . Для зберігання п прямокутників необхідно 16 * n байт.

Проміжні дані . При частковому побудові розміщення прямокутників на площині крім параметрів прямокутника використовуються координати вершини кожного прямокутника . Параметри прямокутника - 2 параметра типу float займають 16 байт. Координати вершини - 2 параметра типу float займають 16 байт.

Для часткового побудови розміщення n прямокутників необхідно 32 * n байт пам'яті.

 Вихідні  дані. В якості вихідних даних - масив прямокутників з параметрами  довжини і ширини, а так само  координатами їх вершини типу  float (16 байт + 16 байт).

 Для візуального  виведення n прямокутників необхідно 32 * n байт пам'яті.

 

 

Рисунок 4.1 – Схема інформаційних потоків

 

5 РОЗРОБКА ТА ОПТИМІЗАЦІЯ АЛГОРИТМІЧНОГО ЗАБЕЗПЕЧЕННЯ ПРОЕКТУ

5.1 Вибір і обґрунтування  інструментальних засобів

 

Qt - це кроссплатформенна бібліотека , метою якої є витіснення нативних API з програм . Зараз Qt - це величезний об'єктно-орієнтована система , в більшості випадків дозволяє обійтися без залучення будь-яких інших бібліотек . У першу чергу Qt - відмінний засіб для створення графічного інтерфейсу користувача (GUI) . До складу Qt входить дизайнер , що дозволяє легко створювати графічні інтерфейси для програми.

Файл збірки можна буде створити одним викликом утиліти qmake (природно , під керуванням цільової платформи). Від себе додам , що іноді цей файл доводиться правити руками (а як же). Про значимість даної бібліотеки говорить хоча б те , що вона використовується в таких успішних проектах , як Borland C++ Builder 6 і Opera.

Перелічимо основні гідності ядра бібліотеки Qt :

• вбудована підтримка Unicode і локалізації (дуже добре і дуже правильно реалізованої , смію зауважити ) . У Qt4 обіцяють новий механізм рендеринга шрифтів , що підтримує Unicode ;
• потужні події і фільтри подій (подія - це щось подібне універсального сигналу , який можна посилати будь-кому віджету , розпізнавати і відповідним чином обробляти за допомогою фільтрів. Наприклад натискання різних клавіш) ;
• багатофункціональні керовані інтервалами таймери які роблять можливим просто і швидко вставляти багато різних завдань в керований подіями ГПИ ;
• ієрархічні і настроюються об'єктні дерева , що організують приналежність об'єктів природним чином ;
• захищені покажчики QGuardedPtr , які автоматично приймають значення NULL при знищенні відповідного об'єкта , на відміну від звичайних покажчиків в C , які в цьому випадку стають " невизначеними покажчиками ";
• Зручна документація , доступна і російською мовою ( посилання на жаль не знаю , але можу з задоволенням вислати за заявкою ) . До складу ядра бібліотеки входять як класи для побудови GUI (наприклад: мітка , поле введення , кнопка тощо) , так і класи , призначені для організації різних структур зберігання даних (наприклад , списковий ), роботи з файлами , мережевої взаємодії і багато чого іншого. Деякі з цих можливостей реалізовані у вигляді додаткових модулів;
• модуль Canvas , потужний інструмент для роботи з двомірної графікою. Він використовує принцип структурування графіки , що , безсумнівно , буде корисно в програмуванні простих двомірних ігор і подібного роду речах. Полотно складається з кількох " елементів " , кожен елемент представлений об'єктом . об'єктів з певними швидкостями по осях ;
• модуль Network , що забезпечує підтримку мережі в додатках;
• модуль OpenGL , що дозволяє працювати з тривимірною графікою за допомогою бібліотеки OpenGL . Підтримується з версії 2.3.2 . ;
• модуль SQL , який реалізує доступ до баз даних з додатків Qt. Даний модуль розбитий на три рівні: користувальницький (елементи інтерфейсу ) , програмний ( абстрактний доступ до баз даних) і рівень драйверів ;
• модуль Table , що надає у ваше розпорядження сітку для відображення табличних даних. Сітка являє собою дуже потужний і гнучкий інтерфейс , працювати з яким - одне задоволення ;
• модуль XML , що використовує інтерфейс SAX2 і реалізацію DOM другого рівня.

 

5.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 – Алгоритм критерій оцінки якості вузлів розміщення

 

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

 

 

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

 

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

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

• комп’ютер;
• монітор;
• клавіатура;
• миша.

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

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

 

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

 

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

Перелічимо всі основні замінні програми:

• point_arr – масив прямокутників
• nx – довжина прямокутника;
• ny – ширина прямокутника;
• х – координата крайньої точки;
• у – координата крайньої точки.

 

Нижче представлений код програми з описом до нього:

Widget::Widget(QWidget *parent)

    : QWidget(parent)

{

    viewer = new QGraphicsView;

    scene = new QGraphicsScene;

    mainmenu = new QMenuBar;

    toolbar = new QToolBar ;

    statusbar = new QStatusBar;

    load_form = new QWidget;

    load_form->setWindowTitle("Загрузить координаты");

    QGridLayout *load_lay = new QGridLayout;

    list_view = new QListWidget;

    do_load = new QPushButton("Открыть файл...");

    load_submit = new QCommandLinkButton("Подтвердить");

    load_lay->addWidget(do_load);

    load_lay->addWidget(list_view);

    load_lay->addWidget(load_submit);

    load_form->setLayout(load_lay);

    QToolButton *paint_btn = new QToolButton;

    paint_btn->setText("Построить");

    toolbar->addWidget(paint_btn);

    QMenu *f_menu = new QMenu("Файл");

    QMenu *s_menu = new QMenu("Редактировать");

    QMenu *a_menu = new QMenu("Справка");

    QAction *open_act = f_menu->addAction("Загрузить");

    QAction *save_act = f_menu->addAction("Сохранить");

    f_menu->addSeparator();

    QAction *exit_act = f_menu->addAction("Выход");

    mainmenu->addMenu(f_menu);

    mainmenu->addMenu(s_menu);

    mainmenu->addMenu(a_menu);

    QGridLayout *lay = new QGridLayout;

    lay->setMenuBar(mainmenu);

    lay->addWidget(toolbar);

    lay->addWidget(viewer);

    lay->addWidget(statusbar);

    setLayout(lay);

    setWindowTitle("Squares");

    resize(500,400);

    viewer->setScene(scene);

    connect(paint_btn,&QToolButton::clicked,this,&Widget::paint_it);

    connect(open_act,&QAction::triggered,load_form,&QWidget::show);

    connect(save_act,&QAction::triggered,this,&Widget::save_to_file);

    connect(exit_act,SIGNAL(triggered(bool)),qApp,SLOT(quit()));

    connect(do_load,&QPushButton::clicked,this,&Widget::load_from_file);

    connect(load_submit,&QCommandLinkButton::clicked,load_form,&QWidget::close);

}

 

Функція необхідна для виводу прямокутників:

void Widget::paint_it(){

    QPoint *buffer = new QPoint;

    for(int i=point_arr.count()-1;i>0;i--)

        for(int j=0;j<i;j++)

            if(point_arr.at(j)->x()>point_arr.at(j+1)->x() || point_arr.at(j)->x()>point_arr.at(j+1)->x()){

                buffer->setX(point_arr.at(j)->x());

                buffer->setY(point_arr.at(j)->y());

                point_arr.at(j)->setX(point_arr.at(j+1)->x());

                point_arr.at(j)->setY(point_arr.at(j+1)->y());

                point_arr.at(j)->setX(buffer->x());

                point_arr.at(j)->setY(buffer->y());