Елементи технології вибору методів та формування алгоритмів розв’язання задач АСУ

Мета і задачі дослідження. Мета роботи полягає в розробці методології створення бази алгоритмів (БА) та системи керування нею (СКБА), як підсистем системи підтримки прийняття рішень (СППР), а також створенні, з використанням розробленої методології, СКБА і БА системи підтримки прийняття рішень з планування і управління виробництвом, для яких характерні лінійні багатокритеріальні оптимізаційні задачі.

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

вибір системи для автоматизації прийняття управлінських рішень;

вибір методів прийняття рішень;

розробка методології створення СКБА та БА як підсистем СППР;

декомпозиція алгоритмів прийняття рішень на незалежні модулі;

визначення загальних і специфічних модулів алгоритмів розв'язання лінійних багатокритеріальних задач та формування на їх основі БА;

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

Наукова новизна отриманих результатів. Наукова новизна полягає в розробці підсистем адаптивної СППР. В рамках цього:

розроблена методологія до створення СКБА і БА системи підтримки прийняття рішень, яка дозволяє адаптувати алгоритм вирішення задачі відповідно типу дотаткової інформації, якою володіє ОПР;

створені БА і СКБА на основі розробленої методології для класу лінійних багатокритеріальних оптимізаційних задач;

здійснена модифікація алгоритмів цільового програмування та системної оптимізації.

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

Апробація результатів дисертації. Всі положення, винесені на захист, знайшли відображення в доповідях, що доповідались і обговорювались на 1 та 3 Міжнародних молодіжних форумах “Радіоелектроніка і молодь у XXI сторіччі” (Харків, 1997 та 1999 р.), а також на міжнародних конференціях "Теорія і техніка передачі, прийому й обробки інформації" (Туапсе, 1995, 1996 р., Харків 1997, 1998 р.). Отримані результати дисертації знайшли використання на ДП “Завод ім. Малишева”, що підтверджується відповідним актом про впровадження, при вирішенні задачі формування виробничої програми об'єднання.

Публікації. Результати дисертації опубліковані у трьох статтях, 1 доповіді, 7 тезах доповідей.

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

Особистий внесок здобувача. В праці [1] автором дисертації особисто досліджено уточнення загальної моделі задачі прийняття рішень в оперативному управлінні виробництвом, обрані та частково програмно реалізовані алгоритми розв'язання згаданих задач. В праці [2] для запропонованої моделі розроблено алгоритм розв'язання задачі системної оптимізації. У праці [5] проведена деталізація інтерактивного процесу формування та вибору рішення для методів цільового програмування та системної оптимізації. У працях [6] та [7] проведені додаткові дослідження методів цільового програмування та системної оптимізації. У праці [11] розроблена процедура, яка дозволяє будувати алгоритм цільового програмування відповідно додатковій інформації, якою володіє ОПР. У праці [9] здійснена узагальнена типізація модулів алгоритмів прийняття рішень в оперативному управлінні виробництвом. У праці [8] така типізація, але вже більш детальна, зроблена для багатокритеріальних оптимізаційних задач. У праці [10] описані вище модулі розглядаються як компоненти бази алгоритмів системи підтримки прийняття рішень.

Структура дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, висновку і додатка. Повний обсяг роботи 162 сторінки, у тому числі: додаток - 2 сторінки, 15 малюнків - 15 сторінок, 3 таблиці - 3 сторінки. Список використаних літературних джерел містить 101 найменування - 11 сторінок.

Основний зміст

У першому розділі проаналізовані існуючі системи автоматизації прийняття рішень, виділені галузі їх застосування. Визначено, що для автоматизації розв'язання розглянутих задач найбільш відповідною системою є система підтримки прийняття рішень, оскільки системи саме цього класу призначені для розв'язання слабкоструктурованих, погано формалізованих задач, якими є задачі планування і керування виробництвом. У зв'язку з цим проаналізовані методи створення СППР: аналізу рішень, розрахунку рішень, дослідження рішень, процесу впровадження. Відзначені характеристики, на які акцентують увагу різні методи. У результаті підібране сполучення методів, що дозволить створити СППР, яка відповідатиме вимогам розв'язуваних задач, - використаються елементи перших трьох методів, при чому домінувати буде метод розрахунку рішень. Проведений аналіз характеристик багатокритеріальних задач планування і управління виробництвом дозволив стверджувати: найбільшу увагу викликають багатокритеріальні оптимізаційні задачі, які найчастіше виникають в процесах планування і управління виробництвом. Аналіз методів розв'язання багатокритеріальних задач, які базуются на ідеї зведення до однокритеріальної оптимізації, дозволив відокремити найбільш розроблені з них: метод послідовних обмежень, метод вагових коефіцієнтів, метод цільового програмування та метод системної оптимізації. Надалі, при розробці системи управління базою алгоритмів автор обмежувався набором алгоритмів саме цих методів. Кожний з наведених методів використовує різну додаткову інформацію від ОПР для усунення невизначеності, пов'язаної з багатокритеріальним характером рішення, що приймається. Для кожного методу використовується свій тип додаткової інформації. Якщо тип додаткової інформації, якою володіє ОПР, відповідає методу, що використовується для вирішення задачі, то використання методу проходить успішно, що дозволяє достатньо ефективно вирішувати зведену задачу. Однак, якщо тип додаткової інформації не відповідає методу, що використовується, ефективність його використання різко падає. Оскільки при вирішенні навіть однієї і тієї ж задачі в різні проміжки часу ОПР володіє різною додатковою інформацією, то виникає проблема її ефективного використання. Для вирішення цих проблем з урахуванням проведеного аналізу висунуті наведені вище задачі дослідження.

У другому розділі на основі результатів досліджень попередників щодо структури СППР (Левикіна В.М., Стопченка Г.І., Ситніка В.Ф., Мешалкіна Е.А., Кокушкіна В.А., Дударева Г.І. та ін.), сформовано структуру СППР згідно вимогам, що висуваються до них на сьогоднішній день (рис. 1). Пунктиром визначені підсистеми, розробці яких присвячено роботу.

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

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

Рисунок 1 Структура СППР

модулі, що використовуються декількома (хоча б двома) алгоритмами, а специфічні, як говорить сама назва, - це ті модулі, що використовуються лише одним алгоритмом. Такий розподіл дозволяє скоротити час на доробку системи. Отримані в результаті декомпозиції модулі складуть базу алгоритмів. Запропоновано створити окрему систему з елементами знань, яка буде відстежувати події і викликати процедури (модулі), що їх обробляють. Це і буде система керування базою алгоритмів (рис. 2). Іншими словами, перед створенням СКБА необхідно проаналізувати алгоритми, що передбачається використовувати при вирішенні задач, і виділити множину подій , що можуть виникнути в процесі вирішення. Декомпозиція алгоритмів на незалежні модулі дозволить створити множину обробних процедур і функцій . Множину у загальному випадку повинно складатися з двох підмножин і . - множина макроподій, що впливають на вибір методу вирішення задачі. - множина мікроподій, що впливають на склад тіла алгоритму вирішення. Крім безлічі , для обробки подій буде використовуватися безліч проміжних дій , що містить у собі елементарні математичні дії, дії переприсвоєння і т.і. СКБА створюється на базі множин , використовуючи продукционні правила (або інший відповідний спосіб представлення знань), у вигляді направленого графа, що охоплює всі можливі шляхи розвитку подій. Гілка графа буде мати вигляд

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

Рисунок 2 Система керування базою алгоритмів

Якщо , то [послідовність з елементів множин і .

Розглянута також взаємодія БА і СКБА, у разі використання запропонованої методології, з іншими підсистемами СППР під час вирішення задачі. Схема взаємодії підсистем СППР наведена на рис. 3.

У третьому та четвертому розділах запропонована методологія реалізована при створенні БА та СУБА, як підсистем СППР для класу лінійних багатокритеріальних оптимізаційних задач.

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

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

Рисунок 3 Взаємодія БА та СКБА з іншими підсистемами під час розв'язання задачі.

(1)

де - багатокритеріальна цільова функція;

- набір локальних критеріїв оптимізації багатокритеріальної цільової функції, , де - матриця коефіцієнтів багатокритеріальної цільової функції (, );

- додаткова інформація суб'єктивного характеру, якою володіє ОПР;

- матриця коефіцієнтів системи функціональних обмежень задачі (, );

- вектор змінних, відносно яких йде вирішення задачі ();

- вектор вільних членів системи функціональних обмежень задачі ();

- кількість локальних критеріїв задачі;

- кількість змінних задачі;

- кількість функціональних обмежень задачі.

Параметр неможливо формалізувати до початку вирішення задачі. Це пов'язано з тим, що у різних обставинах ОПР має різну додаткову інформацію про вирішувану задачу. У дисертації розглядаються наступні випадки:

ОПР може упорядкувати за важливістю локальні критерії задачі та, в процесі вирішення, визначає можливі погіршення досягнутих значень одних локальних критеріїв для поліпшення значень інших. У цьому випадку , де - інформація про упорядкування локальних критеріїв за важливістю, - поступки від досягнутих в процесі вирішення значень локальних критеріїв ();

ОПР може визначити вагу локальних критеріїв задачі: , (). У цьому випадку ;

ОПР може диапазонно визначити бажані значення локальних критеріїв: , де та - відповідно найгірше та найліпше з бажанних значень -го локального критерія (). У цьому випадку , де , ().

ОПР може точково визначити бажаємі значення локальних критеріїв: , де - бажане значення -го локального критерія (). У цьому випадку .

ОПР окрім інформації у вигляді або , () може визначити можливі ресурси змінення функціональних обмежень: та , де - ресурс змінення -го коефіцієнта у -му функціональному обмеженні, - ресурс змінення значення вільного члена у -му функціональному обмеженні. У цьому випадку або відповідно.

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

Загальні модулі:

Модуль загальний 1 (процедура). Введення початкової інформації та формування на її основі задачі багатокритеріальної оптимізації.

Містить у собі такі наступні операції:

1. Введення параметрів: ,

де - початкова кількість змінних;

- кількість критеріїв;

- початкова кількість обмежень;

- початкова матриця коефіцієнтів багатокритеріальної цільової функції, , ;

- початкова матриця коефіцієнтів системи обмежень, , ;

- початкова матриця вільних коефіцієнтів системи обмежень, ;

- матриця видів оптимізації локальних критеріїв цільової функції, ;

- матриця знаків обмежень, ;

- багатокритеріальна цільова функція, ;

- матриця змінних, відносно яких йде розв'язання задачі, ;

2. Формування багатокритеріальної цільової функції

; (2)

3. Формування обмежень задачі

(3)

Таким чином вхідна інформація відсутня.

Вихідна інформація: ;

(Аналогічним чином описані всі інші модулі.)

Модуль загальний 2 (процедура). Приведення задачі з загальної до канонічної форми;

Модуль загальний 3 (функція). Перевірка на сумісність системи обмежень;

Модуль загальний 4 (процедура). Розрахунок точок екстремумів локальних критеріїв багатокритеріальної цільової функції на заданій області;

Модуль загальний 5 (процедура). Розрахунок опорних точок пошуку для пошукових процедур;

Модуль загальний 6 (процедура). Вибір метрики міри близькості в критеріальному просторі;

Модуль загальний 7 (процедура). Задання цілі у критеріальному просторі або точкою, або областю;

Модуль загальний 8 (процедура). Розрахунок значень екстремумів локальних критеріїв багатокритеріальної цільової функції;

Модуль загальний 9 (процедура). Приведення локальних критеріїв до діапазону змінення від 0 до 1;

Модуль загальний 10 (процедура). Перехід від початкової постановки задачі до постановки задачі загального вигляду;

Модуль загальний 11 (процедура). Переведення з розмірності початкової постановки задачі до розмірності задачі загального виду;

Модуль загальний 12 (процедура). Процедура пошуку рішення з ОПЗ найближчого, з точки зору обраної метрики, до бажаного;

Модуль загальний 13 (процедура). Процедура пошуку рішення з ОПЗ найближчого, з точки зору обраної метрики, до бажаної області;

Модуль загальний 14 (процедура). Реалізація симплекс метода;

Модуль загальний 15 (процедура). Повернення до початкової розмірності;

Модуль загальний 16 (процедура). Виведення проміжкового рішення;

Модуль загальний 17 (процедура). Виведення кінцевого рішення.

Размещено на Allbest.ru