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

!, 1 ФЕЗ ^^ М1НЮТЕРСТВ0 ОСВГГИ УКРА1НИ

ХАРЮВСЬКИЙ ДЕРЖАВНИЙ ТЕХН1ЧНИЙ УНИВЕРСИТЕТ ----------РАДЮЕЛЕКТРОНЖИ

М1ХАСВИЧ Олексш 1горович

УДК 519.81

ЕЛЕМЕНТИ ТЕХНОЛОГИ ВИБОРУ МЕТОД1В ТА ФОРМУВАННЯ АЛГОРИТМ1В РОЗВ'ЯЗАННЯ ЗАДАЧ АСУ.

Спешальшсть 05.13.06 — Автоматизоваш системи управлшня та прогресивш шформацшш технологи

АВТОРЕФЕРАТ

дисертацп на здобуття паукового ступеня кандидата техшчних наук

Харюв - 2000

Дисертащею е рукопис

Робота виконана на кафедр! шформацшних управляючих систем Харювського державного техшчного ушверситету радюелектрошки.

Науковий кер1вник: доктор техшчних наук, професор,

Офшийш опоненти:

доктор техшчних наук, професор, завщуючий кафедрою системотехшки Харювського державного техшчного ушверситету радюелектрошки Петров Едуард Георгшович;

кандидат техшчних наук, доцент кафедри шформацшних систем 1 технологш в д1яльност1 ОВС Харювського университету внутршшх справ МВС УкраУни Танянський Серий Станиславович.

Провщна установа -

Нацюнальний техшчний ушверситет "Кшвський пол1техшчний шститут", кафедра техшчноУ юбернетики.

Захиствщбудеться " «¿У " /ЬРОТСП^О_2000 р. о_годи!п

на засщанш спещагнзованоТ вченоТ ради, шифр Д 64.052.01, по присудженню наукового ступеня кандидата техшчних наук у Харювському державному техтчному ушверситет1 радюелектрошки за адресою: 61166, м. Харк1в, пр. Ленша, 14, факс: (0572) 43-30-53.

3 дисертащею можна ознайомитися у б1блютещ Харювського державного техничного университету радюелектрошки за адресою: 61166, м. Харю в, пр. Ленша, 14.

Автореферат роз1слано " X! " СУ УУЬ-?_2000 р.

Вчений секретар

завщуючий кафедрою ¡нформащйних управляючих систем Харювського державного техшчного ушверситету радюелектрошки Левикш Вжтор Макарович

спещал13овано1 вчено1 ради, доктор техшчних наук

В.П. Авраменко

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальность теми. На сьогодниинш день в УкраУш ¡нтенсивно

провадяться роботи з комп'ютеризаци управлшня виробництвом, яю включають розробку та вдосконалення традищйних автоматизованих систем управлшня виробництвом на баз! великих ЕОМ, реал!зашю нових ¡нформацшних технололй, засиованих на використанш персонально! обчислговальноТ техшки. розподшеноУ (децентршизованоУ) обробки ¡нформацн. економжо-математичних метод1в в с\купност1 з методами штучного ¡нтелекту.

Автоматизащя е дшовим ¡нструментом удосконалювання управлшня, планувания, проектування тощо, 1 сприяе широкому розповсюдженню автоматизованих систем в уах сферах д!яльност1 людини, розширенню п фупкщй, можливосп розв'язання все бшьш складних задач. Сучасний стан засоб^в обчислювапьноТ техшки, теори прийняття ршень, штучного штелекту вщкривае нов1 можливост1 для розв'язування складних задач (оптим1зацшних, ¡мгацшних, багатокритер!'альних та шших). Проте ефективжсть Ух використання в процесах прийняття ршень значною м>рою залежить Н1д opraHi3au.ii взаемоди людини з ЕОМ, досв1ду, щтуУци та практичних навичок користувача, а також вщ можливостей засоб!в обчислювальноТ техшки.

Розширення сфер використання ЕОМ та усютаднення автоматизованих систем зумовили залучення до процесу безпосередиъоУ взасмод1У з ЕОМ широкого кола користувачш i створення для концевого користувача (не ир01рам1ста за фахом) засоб1в сшлкування, то дають змогу задовольняти гид час взаемоди з обчислювальною системою своУ ¡нформацшн! потреби.

Автоматизоване управлшня тдприемством здшсшоеться за допомогою рвннх функцюналышх пшсистем АСУ, серед яких знание мюце иалежить шдсистем! техшко-економ1чного управлшня, що здшенюе виршення залач оилшу, контролю I ана!шу, доагпдження 1 прогнозування стану виробиицтва, формування керуючих вгипдав. Для розв'язання задач техшко-економ1чного управлшня викорисювуються модели у вигляд1 виробничих функцш ! норматива! (оптим1зацшш) модели Рехизацш таких моделей пов'язана з подоланням р!зного роду невизначеностей, якт призводять до некоректност1 основних задач моделювання 1 опттпзашУ \ до того, що практично вс1 огпимнашГпп задач! АСУ формулюються як багатокритер'юльш.

Таким чином, ¡стотш трудноии в управлшш сучасним виробництвом пов'язаж з необхщш'стго подолання протпртч М1Ж бажаною простотою опису об'екту керування \ потребою врахування широкого спектру виробничих характеристик цього об'екту керування, а також протир!ч М1Ж вимогою оперативност1 формування управлшського ршення \ глибиною його пророб1тки. Додатков! трудноии пов'язаш з наявшетю пapaмeтpiв задач, як! принципово неможливо фор.магпзувати на час прийняття ршень, та яю можуть

змшювати своУ характеристики як ш'д задач! до задач!, так 1 у процеа вирпиенпя одшеТ задач!. Використання ж спрощених (неадекватних) моделей та алгоритипв розв'язання задач призводить до отримання ршень ¡з заздалепдь пршою ефектившстю.

В цих умовах вважаеться актуальним створення для автоматизацп виршення багатокритер!алышх задач з планування та управлшня виробництвом тако'1 системи керування базою алгоритм!в (СКБА), яка б допомагала особ1, що приймае ршення (ОПР), вибирати метод та формувати алгоритм розв'язання задач! вщповщно типу додатковоТ шформацп, якою вш волод1е. Цю СКБА необхщно створювати, як пщсистему тдтримки прийняття ршень.

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана в рамках держбюджетноТ науково-дослщно'! роботи № 010 «Разработка методологии, методов и средств проектирования распределенных систем управления с требуемыми параметрами».

Мета I задач! дослщження. Мета роботи полягае в розробщ методологи створення бази алгоритм ¡в (БА) та системи керування нею (СКБА), як тдсистем системи тдтримки прийняття рнпень (СППР), а також створены!, з використанням розроблено'1 методолоп\', СКБА 1 БА системи тдтримки прийняття ршень з планування I управления виробництвом, для яких характерш лшшш багатокритер!альш отттащйн! задач!.

Для досягнення поставлено'/ мети у робот! вирщуються так! задач!:

- виб!р системи для автоматизащТ прийняття управлшських р!шень;

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

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

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

- визначення загальних 1 специф!чних модул!в алгоритм!в розв'язання лшшних багатокритер!альних задач та формування на Ух основ! БА;

- створення системи керування базою алгоршшв, як узагальненого алгоритму пошуку р!шення лшшно? багатокритер!альноУ оптимвацшноТ задач!.

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

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

- створеш БА ! СКБА на основ! розроблено'1 методологи для класу лшшних багатокритер!альних опттнзацшних задач;

- здшснена модиф!кац!я алгоритм ¡в цшьового програмування та системно!" оптим!заци.

Практнчне значения отриманих результате. В результат! дисертац!йних дослщжень отриман! практичн! результата, як! дозволяють

шдвищити ефективтсть управлшських ршень. Створеш nporpaMHi засоби шдтримки прийняття piiueHb з фомування виробничоУ программ об'еднання, як! знайшли використання на ДП «Завод im. Малишева», що пщтверджуеться в^шовщним актом про впровадження.

Апробация результате дисертацп. Bei положения, винесеш на захист, знайшли вщображення в доповщях, що доновиались i обговорювались на 1 та 3 1УПжнародних молод!жних форумах «Радюелектронжа i молодь у XXI CTopiMHi» (Харюв, 1997 та 1999 р.), а також на м1жнародних конференциях "Теория i техшка передач!, прнйому й обробки шформаш'Г (Туапсе, 1995, 1996 р., Харюв 1997, 1998 р.). Отримаш результат!! дисерташТ знайшли використання на ДП «Завод ¡м. Малишева», що шдтверджуеться вщповщним актом про впровадження, при виршенш задач! формування виробничоТ програми об'еднання.

Публ1кацп. Результати дисертацн опублжоваш у трьох статгях, 1 доиов1Д!, 7 тезах доповщей.

ГТовний список праць здобувача, опублжованих за темою дисертащУ, приведено нижче.

Особистий внесок здобувача. В пращ [1] автором дисертацн особисто дослщжено уточнения загальноТ модел! задач! прийняття ршень в оперативному управлнип виробництвом, o6pani та частково програмно

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

Структура дисерташУ. Дисертациша робота складасться з вступу. чотирьох роздшв, висиовку i додатка. Повний обсяг роботи 162 сторшки, у тому чиелк додаток - 2 стор1нки. 15 малюнкш - 15 сторшок, 3 таблиц! - 3 сторшки. Список використаних л^тературних джерел MiCTüTb ¡01 найменування — 11 cTOpiHOK.

ОСНОВНИЙ ЗМ1СТ

У першому роздш1 проанагнзоваш !снуюч! системи автоматизаци прийнятгя ршень, видшеш галуз! Тх застосування. Визначено, що для автоматизаци розв'язання розглянутих задач найбшып вщповщною системою е система шдтримки прийнятгя ршень, оскшьки системи саме цього класу призначеш для розв'язання слабкоструктурованих, погано формалвованих задач, якими е задач! планування 1 керування виробництвом. У зв'язку з цим проанал1Эован1 методи створення СППР: аналЬу ршень, розрахунку ршень, дослщження ршень, процесу впровадження. Вщзначеш характеристики, на яю акцешують увагу р!зш методи. У результат! пдабране сполучення метод1в, що дозволить створити СППР, яка вщповщатиме вимогам розв'язуваних задач, -використаються елементи перших трьох метод1в, при чому домшувати буде метод розрахунку ршень. Проведений анал13 характеристик багатокритер!альних задач планування ! управлшня виробництвом дозволив стверджувати: найбшьшу увагу викликають багатокритер1альш оптжпзацШш задач^ як1 найчаспше виникають в процесах планування 1 управлшня виробництвом. Анализ метод!в розв'язання багатокритер!альних задач, яш базуются на ¡деТ зведення до однокритер'1альноТ оптим!зацн, дозволив вщокремити найбшып розроблеш з них: метод послщовних обмежень, метод вагових коефщ!ент1в, метод цшьового програмування та метод системно! оптимпацп. Надал"1, при розробщ системи управлшня базою алгоритм1в автор обмежувався набором алгоритм!в саме цих метод1в. Кожний з наведених метод1в використовуе р!зну додаткову ¡нформащю вщ ОПР для усунення невизначеност!, пов'язано!" з багатокритер1альним характером ршення, що приймаеться. Для кожного методу використовуеться свШ тип додатковоУ шформащТ. Якщо тип додатково! ¡нформаци, якою волод!е ОПР, вщповщае методу, що використовуеться для виршення задач!, то використання методу проходить усп!шно, що дозволяе достатньо ефекгивно вир!шувати зведену задачу, Однак, яюцо тип додатковоТ ¿нформацп не вщиовщае методу, що використовуеться, ефективн!сть його використання р!зко падае. Оскшьки при вир!шенш навггь одша \ та! ж задач! в р!зш промгжки часу ОПР волод1е р!зною додатковою ¡нформащею, то виникае проблема и ефективного використання. Для виршення цих проблем з урахуванням проведеного аналЬу висунут! наведен! вище задач! дослщження.

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

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

Наступним кроком запропонована методология до створення СКБЛ як шдсистеми СППР, яка базусться на подшному програмуванш. У випадку, що розглядаеться, подыми визначено наявнють або вщсутшсть Т1еУ або ииноУ додатковоТ ¡цформащ1 в ОПР. додатково ввели подш подш на макропод!'! 1 м1кроподи. Макроподп це поди, що визначають групу метод1в, яка найбшьше шдходить для розв'язання конкретно! задачи Мжроподи це поди, що визначають уже безпосередньо т1ло алгоритму розв'язання задач!. Для створення аналога процедур, що обробляють поди, запропоноваио декомпозувати ввдбраш алгоритми вир1шення на незалежш модул! (процедур» та функци), з подальшим Тх розподшом на загальш 1 специф!чш. Загальш - це модул!, що використовуються дек!лькома (хоча б двома) алгоритмами, а специф!чн!, як говорить сама назва, - це т! модул!, що використовуються лише одним алгоритмом. Такий розпод!л дозволяе скоротити час на доробк\ системи. Отримаш в результат! декомпозицп модул1 складуть базу алгоритмов. Запропоноваио створити окрему систему з елементами знань, яка буде в!дстежувати под!! ! викликати процедури (модул!), що Ух обробляють. Це ! буде система керування базою алгортшв (рис. 2). 1ншими словами, перед створенням СКБА необхщно проанагизувати алгоритми, що передбачаеться використовувати при виршенш задач,! видшити множину подш 5, що можуть

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

виникнути в процес! виршення. Декомпозищя алгоритмш на незалежш модул1 дозволить створити множину обробних процедур 1 фуНКЦШ Р. Множину 5 у загальному випадку повинно складатися з двох шдмножин 5] 1 5 2 ■ -множина макролодж, що впливають на вибф методу виршення задач!. -множима мжроподж, що впливають на склад тша алгоритму виршення. Кр1м безл1ч'| Р, для обробки подж буде використовуватися безл'ш пром1ЖНих Д1Й РБ, що мютить у соб1 елементарш математичш ди переприсвоення \ тл. СКБА створюеться на баз! множим Р, РВ, використовуючи продукционш правила (або шший вщповщний споЫб представления знань), у випвдп направленого графа, що охоплюе вс1 можлив1 шляхи розвитку подш. Плка графа буде мати вигляд

Якщо , то [послшовнють з елемеьтв миожин Р 1 РО]

Розглянута також взаемод1Я БА \ СКБА, у раз! використання запропоновансм методологи, з ¡ншими гндсистемами СППР гид час виршення задач!. Схема взаемодГ! подсистем СППР наведена на рис. 3.

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

задач!.

У третьему та четвертому роздйлах запропонована методология

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

Розглядаеться вир!шення лппйноТ багатокритер!ально1 оптим!защйноТ задач!, яка формулюеться в такому вгляд!:

АХ <Ь,

х} > о, ]-17".

де Ф - багатокритер!альна ц!льова функшя; Р'(Х) = {/¡(Х)} - наб!р локальних

(1)

критернв оптимвацп

п

багатокритер1ально1 ц'|льово1 функци, /, = Y-Ci,jxj > Де С = - матриця

У=1

коефаденпв багатокритер1альноТцшьовоТфункци (/' = 1 ,к, j = 1,и);

/ - додаткова шформащя суб'ективного характеру, якою волод1е ОПР; /1 = {«/у} - матриця коефвденпв системи функцюнальних обмежень

задач! (/ = !,«, j = 1, п);

ЛГ = {ху} - вектор змшних, вщносно яких йде виршення задач! (у = 1,и); b-{bi} - вектор вшьних член!в системи функц!ональних обмежень задач! (/ = 1 ,т);

к - KLTbKicTb локапьних критернв задач!; п - кшькють змшних задач!; т - юлькють функц!ональних обмежень задач!.

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

1. ОПР може упорядкувати за важлив!стю локальш критерн задач! та, в процесс виршення, визначае можлив! попршення досягнутих значень одних локальних критернв для пол!пшення значень шших. У цьому випадку

I = Fus де 1\ - шформащя про упорядкування локальних критернв за

важливютю, Fus = [f"s} - поступки вщ досягнутих в процес! вир!шення значень локальних критерйв (/ = 1, к);

2. ОПР може визначити вагу локальних критернв задач!: Л = {Яу},

к _

=1, О <Л,- <1 (г = 1,к). У цьому випадку 1 = Л;

(=1

3. ОПР може диапазонно визначити бажаш значения локальних

_r* min . - , ч ,* шах r* min ,* max . • „ .

критернв: fi < /, (х) < fi , де ft та fi - вщповщно наипрше та

найл!пше з бажанних значень г-го локального критер!я (/ = 1,к). У цьому

випадку 7 = (F*min,F*max),fle F*min ={f*min}, F*^={f*max} =

4. ОПР може точково визначити бажаенй значения локальних критернв: * * * —

F ~{fi }, де fj - бажане значения г-го локального критер'1я (i—\,k). У *

цьому випадку I = F .

5. ОПР окр1м ¡нформаш у вигляд! F ={/*} або F*min = {/,• min}, т-'* max , г* max, : г,

F ~xfi } = може визначити можлив! ресурси змшення

функцюнальних обмежень: Д^ = {Да/у} та Д6 = {Д6/}, де Да/ у - ресурс змшення у-го коефщкнта у 1-му функщональному обмеженш, ДА/- ресурс

змшення значения выьного члена у / -му функциональному обмеженш. У цьому - - випадку I = ('У, ДА,ЛЬ) ибо /_= ( £*тт, /•'*шах , АЛ, Д^ виновино.

У третьему розли™ алгоритми послшовних обмежень, вагових коефшглгпв, шльового програмування та системно!" оптим!зацп декомпозовано на незалежш модуль загальною юльмстю амдесят чотири. ГПсля анал1зу цих модушв було встановлено, що вони певною м1рою дублюються, були визначсш та тишзоваш (ушверсашзоваш) амнадцять загальних та п'ятнадцять специф^чних модул)в, як11 склали базу алгоритм1в. Загальш модул!:

- Модуль загальний 1 (процедура). Введения початковоТ ¡нформашУ та формування на УУ основ! задач! багатокритер:'алы101 опти\шацп. Мштить у соб1 так1 наступи! операцп:

1. Введения параметр|в: п" ,к,т" ,СН, Ан,Ьп,ОРТ, ,

д ел" - початкова кшьюсть зм!нних ; к - кшькють критернв ;

т" - початкова кшыНсть обмежень :

С" = {с"у} - початкова матриця коефщ1ент1в багатокритер1алыюТ

шльовоУ функци, / = 1 ,к, ] - 1, пн ;

А" - {а" } - початкова матриця коефнйент1в систем» обмежень,

/ = !,,„" , у =!,»";

Ь" = {Ь'¡} - початкова матриця в!льних коефщ1ент1в системи обмежень,

I 1 »

1 ~ \,т ;

ОРТ = {ор1(} - матриця вид1в оптмпзащУ локальних критер1Ув шльовоУ функц!У, 1 = 1 ,к ;

2М-{:щ} - матриця знак1в обмежень, / = \,т" ; Р(-Ю = {// (^0) - багатокритер1альна щльова фуикщя. г = 1, к ; X - {хJ} - матриця змшних, вщносно яких йде розв'язгишя задач!,

7 = 1 ,п";

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

^ = хХ-+ОРТ; (2)

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

Анххть}', (3)

>0, у = 1, ин.

Таким чином вхщна шформац1я вщсутня.

Вихщна шформащя: п" ,к,т" ,С", А" ,ЬН, ОРТ, ;

(Аналопчним чином описан! вс1 шип модуль)

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

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

- Модуль загальний 4 (процедура). Розрахунок точок екстремум^в локальних критерЛ'в багатокритер1альноУ щльовоУ функци на задашй облает!;

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

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

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

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

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

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

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

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

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

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

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

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

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

Специф!чш модули

- Модуль специф!чний 1 (процедура). Введения вагових коефшенпв;

- Модуль специф^чний 2 (процедура). Визначення номеру

найважлившого локального критерто на h -ому крош для методу послщовних обмежень;

- Модуль специф1чняй 3 (процедура). Створення узагальненого критерно пошуку Ф для методу вагових косфщкнта;

- Модуль специфнший 4 (процедура): Формування области пошуку р'ииення на /;-му Kpoui для методу послщовних обмежень;

- Модуль специф^чний 5 (процедура). Створення узагальненого критерто пошуку Ф для методу послщовних обмежень;

- Модуль спеииф1-чний 6 (процедура). Додавання змшних для методу 1Нльового програмування;

- Модуль специ(]нчний 7 (процедура). Створення узагальненого кригер1'ю пошуку Ф для метод}' щльового програмування;

- Модуль специф!чний 8 (процед\ра). Формування облает! пошуку ранения для методу щльового програмування;

- Модуль специф^чний 9 (процедура). Розширення ОПЗ для методу системно!' оптим!зацп;

- Модуль специф1чний 10 (процедура). Анал1з р!шення для методу вагових коефщент;

- Модуль специфнший 11 (процедура). Анализ ршення для методу послщовних обмежень;

- Модуль специф1чний 12 (процедура). Введения усеченого значения

fyc

J для методу послщовних оомежень;

'IV

- Модуль сиециф!чний 13 (процедура). АналЬ р1шення для методу щльового програмування з абсолютною метрикою;

- Модуль специф1чний 14 (процедура). Анагйз ршення для узагальненого методу щльового програмування;

- Модуль специфншиЛ 15 (процедура). Анал1з ргшення для методу системно!'оптимвацн.

Bei inuii дй", що зустр1чаються у алгоритмах, можна визначити, як пром!жковг Це елементарш математичт ди, чи дп, що узгоджують д!яльшсть блою'в. тцо ви.щлеш вище. Всього отримано тридцять два модуля проти первинноГ KÜTbicocTi в сшдесят один модуль, шо дозволяе скоротпти обсяг бази алгоритм1в бшьше шж удвое.

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

У четвертому роздЫ розроблена технолопя вибору методу роз'язання задач!, для чого було зроблено упорядкування тишв додатково! шформацп,

якою може волод^ти ОПР, за складтстю. Запит наявност! у ОПР додатковоУ шформацп починаеться з самоТ складноТ, що дозволить застосувати найбшьш складний алгоритм на самш першш стад!) розв'язання задач!, а значить отримати бшьш ефективне радения за менший час. Дал1 була побудована система керування базою алгоритм ¡в, яка складаеться з двох частин: вибору групи алгоритм1в (рис. 4) 1 побудови алгоритму групи. Для опису другоУ частини СКБА запропонований дещо змшений ор!ентований граф, де вершинами виступають модул!, що були описан! вище; праворуч чи зверху В1Д ребер описуються пром!жков! д1У, якщо вони потр^бш; л1воруч чи знизу вщ ребер позначаються умови за яких розвиток алгоритму гиде саме в цьому напрямку. Наприклад, алгоритм цшьового програмування, якщо опустите промгжков! дц, у такому засоб! опису отримав вигляд рис. 5.

Також в четвертому роздш запропоноваш рекомендаци щодо побудови процедури пошуку р!шення найближчого до бажаного, на баз'1 методу покоординатного спуску; процедури пошуку решения найближчого до облает! бажаних ршень, на баз! методу покоординатного спуску; процедури розширен ня облает! припустимих ршень для методу системно!' оптим!заци. Перш! дв! процедури не претендують на оптимальн!сть за часом та точшетю пошуку, але допомагають зрозумки як адаптувати пошуков! метода для пошуку в облает! припустимих значень р!шення найближчого, з точки зору обраноУ метрики, до бажаного чи найближчого до облает! бажаних значень. Запропонована процедура розширення облаеи припустимих р'илень для методу системно'! оптим!зац11 дозволяе в д!алоговому режим!, зрозумшо для ОПР, зм!нювати область припустимих значень з метою полшшення ртення. Розглянуто приклад практичного використання отриманих результат!в.

висновки

1. У запропонованш дисертац!йн1й робот! автором проанал!зоваш ¡снуюч! системи автоматизаци, метода створення СППР, методи виршення багатокритер!альних оптим!зац!йних задач, внаслщок чого визначено, що для автоматизаци ршення розглянутих задач найбьльш в!дпов!дною системою е система шдтримки прийняття р!шень, визначено сполучення метод1в створення СППР, яке вщповщае вир'ипуваним задачам та В1д'1бран! методи виршення багатокритер!альних задач для використання при розробщ БА та СКБА.

2. Створена структура СППР, яка вщповщае сучасним вимогам, що висуваються до систем цього класу на сьогодтшнш день.

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

Рисунок 4. - Перша частина СКБА - виб]р методу вирндення задач!

Metod=4 ^

Загальний 2

С

Загальний 3

Система |

сунпсна —*

© i

(Т^Загалышй

Система не сужена

^ л ; ; и ь ] : и й

:на_——i_______ ,—. ----

Загальний 7 -(б) V--_

Загальний 15

^ Загальний 4 i.

С^^З^альний!^^-^

СТ^^ЗагальнийЗ^Т^1

Загальний 15

Метрика не абсолютна, або щль визначена ( А лиалазонно

Юль визначена диапазонно

Рисунок 5 - Управляючий граф для групи цшьового програмування

4. Розроблено структуру СКБА для випадку використання розробленоУ методологи, яка вщображае особливост1 побудови та функщонування тако'1 систем«.

5. Запропоновано схему взаемодй" БА та СКБА, створених з використанням розробленоУ методологи, з шшими шдсистемами СППР гид час виршення задач i, яка вщображае особливосп процесу прийняття ршень, пов'язан! з використанням можливостей ОПР.

6. 3 використанням розробленоУ методологи, створена БА, для класу лпнйних багатокритер1альних оптим1зацшних задач. Реалвоваш алгоритми: послщовних обмежень, вагових коеф1щент1в, шльового програмування та системно! опттизащУ. Використання розробленоУ методологи дозволило приблизно удвое зкоротити обсяг БА.

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

8. Розглянута можлив!Сть адаптаци пошукових метод1в для вир1шення задач шльового програмування та системноУ оптим1зашУ, що дозволяе використовувати в цих задачах метрику м!ри близькосл вщмпшу вщ абсолютно!' та прашовати з бажанними значениями локапьних критерпв. як1 иизначеж диапазоно.

9. Створена процедура розширення облает! припустимих значень для методу системноУ отттащУ, яка дозволяе вносити змши до системи функшональних обмежень задаш' у зрозумшй для ОПР формг

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

СПИСОК ОПУБЛ1КОВАНИХ ПРАЦЬ ЗДОБУВАЧА ЗА ТЕМОЮ ДИСЕРТАЦН

1. Стопченко Г.И., Райков В.М., Михаевич А.И. Модели принятия решений в оперативном управлении производством.// АСУ и приборы автоматики. - Харьков: ХТУРЭ, 1998 г., вып. № 108. - С. 159 - 165.

2. Михаевич А.И., Айдаров A.B. Модель та алгоритм виршення одного окремого випадку системноУ оптим1зацп.// Вестник Харьковского государственного политехнического университета. - Харьков: ХГПУ, 1999 г., выпуск №58.-С.25-27.

3. Михаевич А.И. Подход к построению СУБА СППР.// 1нформацшно керуюч) системи на зашзничному транспорта - Харкт: ХДАЗТ, 1999 г., выпуск № 3. - С. 56 - 60.

4. Михаевич А.И. Система управлшня базою алгоршмв виршення багатокритер1альних задач. 3-й Мшнародний форум "Радюелектрошка i молодь у XXI ст." доповцп/ ХТУРЕ. -Харкт, 1999 р. у 2 частинах. Частина 2. -С. 117-120.

5. Стопченко Г.И., Райков В.М., Михаевич А.И. Моделирование процессов поиска многокритерильных решений в интеллектуальных системах. Тез. докл. Межд. конф. "Теория и техника передачи, приема и обработки информации" Туапсе: ХТУРЭ. 1995.-С. 144.

6. Стопченко Г.И., Райков В.М., Михаевич А.И. Адаптивные диалоговые методы и процедуры принятия решений. Тез. докл. Межд. конф. "Теория и техника передачи, приема и обработки информации". Туапсе: ХТУРЭ. 1996. -С. 104.

7. Пивнев А.Д., Райков В.М., Михаевич А.И. Диалоговая система принятия решений в оперативном управлении производством. Тез. докл. Межд. конф. "Теория и техника передачи, приема и обработки информации". Туапсе: ХТУРЭ. 1996.-С. 138.

8. Михаевич А.И., Данько В.Е. Типизация базы алгоритмов системы поддержки принятие решений в управлении производством. Тез . докл. 1 -й Межд. молодежи, форум "Электроника и молодежь в XXI веке". Харьков: ХТУРЭ, 1997.-С. 233.

9. Стопченко Г.И., Райков В.М., Михаевич А.И. Типизация и проектирование базы диалоговых процедур системы поддержки принятия решений. Тез. докл. Межд. конф. "Теория и техника передачи, приема и обработки информации". Харьков-Туапсе: ХТУРЭ. 1997. - С. 268.

Ю.Левыкин В.М., Айдаров A.B., Михаевич А.И. Выбор методов в интеллектуальных системах поддержки принятия решений. Тез. докл. Межд. конф. "Теория и техника передачи, приема и обработки информации" ХТУРЭ, Туапсе. 1997.-С. 270.

11.Стопченко Г.И., Фурсенко А.К., Михаевич А.И. Технология и методы целевого программирования в задачах принятия многокритериальных решений. Сборник научных трудов по материалам 4-й Межд. конф. "Теория и техника передачи, приема и обработки информации" ("Новые информационные технологии") Харьков: ХТУРЭ. 1998. - С. 286.

MixaeBH4 O.I. Елементи технологи вибору метод1в та формування алгоритм1в розв'язання задач АСУ. — Рукопис.

Дисертащя на здобутгя наукового ступеня кандидата техшчних наук за спещальшстю 05.13.06 - автоматизоваш системи управлшня та прогресивш

¡нформацшш технологи'. - Харктський державний техшчний университет радюелектрошки, Харюв, 1999.

Дисертащя присвячена питаниям автоматизацн процес1в прийнятгя рппень. У po6oT¡ розроблено методологйо, що дозволяе створювати систему керування базою алгормшв, яка здшснюе вийр методу i формування алгоритму виршення задач i вщповщно додатковоУ шформаци про и конкретш поточи! характеристики, яка е у особи, що приймае ршхення. Методолопя використовуе поняття подншого програмування з вшповцншми доробками, розглянутими в дисертацй'. 3 використанням запропонованоУ методолопУ створена система керування базою алгоритмов, як тдсистема системи шдтримки прийняття ршень по плануванню i управлпшю виробництвом, для класу лшшних багатокритер1альних оптим1защйних задач. Ochobhî результата роботи були впроваджеш на ДП "Завод ím. Малишева" для вир^шення задач формування виробничоУ програми об'еднання.

Ключо1м слова: автоматизация, система П1дтримки прийняття piuieiib, база алгоритм1в, система керування базою алгоритм1в, багатокритер1альна задача, оптим1зац!я, алгоритма П1дтримки прийняття р1шення.

Mikhaevitch A.I. Methods choosing technology Elements and tasks decision algorithms forming to ASD. — Manuscript.

Thesis for a candidate's degree by speciality 05.13.06 - automated control systems and progressive information technologies. - Kharkov state technical university of radioelecfronics, Kharkov, 1999.

Dissertation sacred to decisions acceptance processes automation questions. In work is worked up approach, permissive to create a control system of basis of algorithms, which carries out a method choosing and forming of task decision algorithm in accordance with that supplementary information about her concrete current descriptions, which has by person, making decision. Approach uses notions of event programming with proper revisions, considered in dissertation. With using of offered approach is created a control system of basis of algorithms, how decisions acceptance backing system subsystem on planning and to management by production, for class of linear multicriteria tasks of optimization. The Basic job perfomance were inculcated on State enterprise "Завод им. Малышева" for decision of forming tasks of production unification program.

Key words: automation, decisions support system, basis of algorithms, control system of basis of algorithms, multicriteria tasks, optimization, decision support algorithms.

Михаевич А.И. Элементы технологии выбора методов и формирования алгоритмов решения задач АСУ. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - автоматизированные системы управления и

прогрессивные информационные технологии. - Харьковский государственный технический университет радиоэлектроники, Харьков, 1999

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

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

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

созданию базы алгоритмов (БА) и СУБА системы поддержки принятия решений, который основывается на событийном программировании. На основе указанного подхода создана структура системы управления базой алгоритмов СППР. Рассмотрена схема взаимодействия БА и СКБА с другими подсистемами СППР в процессе поиска решения.

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

В рамках четвертого раздела разработаны элементы технологии выбора метода и формирования алгоритма решения задачи, построена система управления базой алгоритмов, которая состоит из двух частей: управление выбором метода решения задачи и управление формированием алгоритма группы (для описания второй части СУБА предложен несколько измененный ориентированный граф). Приведены рекомендации относительно построения: процедуры поиска решения ближайшего к желаемому, на базе метода покоординатного спуска; процедуры поиска решения ближайшего к области желаемых значений, на базе метода покоординатного спуска; процедуры расширения области допустимых решений для метода системной оптимизации. Рассмотрен пример практического применения полученных результатов.

Основные результаты работы были внедрены на ГП "Завод им. Малышева" для решения задачи формирования производственной программы объединения.

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