Нечітка задача оптимального розбиття множин з обмеженнями на розміщення центрів підмножин

An algorithm is proposed for solving the fuzzy continuous optimal sets partitioning problem with constrains for the centers location. The algorithm is based on a synthesis of methods for solving infinite-dimensional problems of optimal set partitioning from an n-dimensional Euclidean space into subs...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2020
Hauptverfasser:	Kiseleva, Elena M., Prytomanova, Olga M.
Format:	Artikel
Sprache:	Ukrainisch
Veröffentlicht:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020
Schlagworte:	нескінченновимірне математичне програмування теорія оптимального розбиття множин обмеження на розміщення центрів підмножин недиференційовна оптимізація нечіткі параметри r-алгоритм Шора
Online Zugang:	https://journal.iasa.kpi.ua/article/view/209136
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	System research and information technologies
Завантажити файл:

Institution

System research and information technologies

_version_	1866391921820172288
author	Kiseleva, Elena M. Prytomanova, Olga M.
author_facet	Kiseleva, Elena M. Prytomanova, Olga M.
author_sort	Kiseleva, Elena M.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2020-08-11T08:50:57Z
description	An algorithm is proposed for solving the fuzzy continuous optimal sets partitioning problem with constrains for the centers location. The algorithm is based on a synthesis of methods for solving infinite-dimensional problems of optimal set partitioning from an n-dimensional Euclidean space into subsets with neuro-fuzzy technologies and modifications of the Shor’s r-algorithm, which are used for the numerical solution of dual finite-dimensional nonsmooth optimization problems. The developed software implementation of the algorithm is illustrated on the model problem.
doi_str_mv	10.20535/SRIT.2308-8893.2020.1.07
first_indexed	2025-07-17T10:26:44Z
format	Article
fulltext	 О.М. Кісельова, О.М. Притоманова, 2020 78 ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 TIДC МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР УДК 519.8 DOI: 10.20535/SRIT.2308-8893.2020.1.07 НЕЧІТКА ЗАДАЧА ОПТИМАЛЬНОГО РОЗБИТТЯ МНОЖИН З ОБМЕЖЕННЯМИ НА РОЗМІЩЕННЯ ЦЕНТРІВ ПІДМНОЖИН О.М. КІСЕЛЬОВА, О.М. ПРИТОМАНОВА Анотація. Запропоновано алгоритм розв’язання нечіткої неперервної лінійної однопродуктової задачі оптимального розбиття множин на підмножини з від- шуканням координат центрів цих підмножин та обмеженнями на їх розміщен- ня. Алгоритм ґрунтується на синтезі методів розв’язання нескінченновимірних задач оптимального розбиття множин із n -вимірного евклідового простору на підмножини з нейронечіткими технологіями та модифікаціями r -алгоритму Н.З. Шора, які застовуються для числового розв’язання двоїстих скінченнови- мірних негладких задач оптимізації. Розроблену програмну реалізацію алгори- тму проілюстровано на модельній задачі. Ключові слова: нескінченновимірне математичне програмування, теорія оп- тимального розбиття множин, обмеження на розміщення центрів підмножин, недиференційовна оптимізація, нечіткі параметри, r -алгоритм Шора. ВСТУП Актуальність задач оптимального розбиття множин пов’язана з широким практичним і теоретичним застосуванням теорії оптимального розбиття множин [1]. Структуру теорії оптимального розбиття множин, сформовану дотепер, подано у праці [2]. Одним з напрямів розвитку теорії оптимального розбиття множин є до- слідження задач оптимального розбиття множин з n -вимірного евклідового простору nE в нечітких умовах. Нечіткість є природною властивістю навко- лишнього світу, тому врахування у математичній постановці задач оптима- льного розбиття множин можливості нечіткості вхідних даних очікувано зумовить підвищення адекватності досліджуваних математичних моделей. У роботі розглядається нечітка неперервна лінійна однопродуктова за- дача оптимального розбиття множин на підмножини з відшуканням коорди- нат центрів цих підмножин, математична постановка якої ускладнена на- явністю додаткових обмежень на розміщення центрів підмножин та припущенням, що деякі вхідні дані задачі можуть бути задані нечітко. Нечіт- кою задачею вважаємо неперервну задачу оптимального розбиття з додат- ковими обмеженнями на розміщення центрів підмножин з нечіткими па- Нечітка задача оптимального розбиття множин з обмеженнями на розміщення … Системні дослідження та інформаційні технології, 2020, № 1 79 раметрами у цільовому функціоналі. Відзначимо, що одну нескінченновимірну задачу оптимального розбиття в умовах нечітких вхідних даних сформульо- вано та розв’язано у праці [3]. Задача, що розглядається у цій роботі, є її уза- гальненням. ПОСТАНОВКА ЗАДАЧІ Спочатку сформулюємо математичну постановку задачі оптимального роз- биття множин з додатковими обмеженнями на розміщення центрів підмно- жин у чітких умовах. Нехай  — обмежена, вимірна за Лебегом множина у n -вимірному евклідовому просторі nE . Сукупність вимірних за Лебегом підмножин N ,...,1 з NE будемо називати можливим розбиттям множини  на його підмножини N ,...,1 , що не перетинаються, якщо Njijiji N i i ,...,1,,,0)(mes, 1    , де )(mes  — міра Лебега. Позначимо клас усіх можливих розбиттів множини  на підмножини N ,...,1 , що не перетинаються, через N  , тобто          Njijiji N i iN N ,...,1,,,0)(mes,:),...,( 1 1  . Уведемо функціонал dxxaxcF N i iiNN i )()) ,((}),...,{},,...,({ 1 11      . (1) Тоді під неперервною лінійною однопродуктовою задачею оптимального розбиття множини  з n -вимірного евклідового простору nE на підмно- жини N ,...,1 , що не перетинаються, за обмежень у формі рівностей та нерівностей з відшуканням координат центрів N ,...,1 цих підмножин та додатковими обмеженнями на їх розміщення будемо розуміти таку задачу. Задача 1. Знайти }),...,{},,...,({min 11 }),...,{},,...,({ 11 NNF NN   , за умов    ii Npibdxxpibdxx ii ,...,1,)(,,...,1,)( , N N  },...,{ 1 ,   N N A NiNi N AAA     .........,...,,..., 11 , де  ),...,( )()1( n iii ;  ),...,( 1 nxxx ; NAA ,...,1 — замкнені множини простої структури, наприклад, n -вимірний невід’ємний октант, n -вимірний О.М. Кісельова, О.М. Притоманова ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 80 паралелепіпед та ін.; Naa ,...,1 , Nbb ,...,1 — задані невід’ємні числа, причому виконуються умови розв’язуваності задачі 1:      NiSbbdxxS i N i i ,...,1,0,)( 1 . Пару },...,{},,...,({ 1 1 NN  , яка є розв’язком задачі 1, будемо назива- ти оптимальною. Задача 1 є нескінченновимірною задачею оптимального розбиття у чіт- ких умовах (якщо Niai ,...,1,0  , — це нескінченновимірна транспортна задача). Однак нескінченновимірні задачі оптимального розбиття з цільовим функціоналом (1) істотно ускладнюються в умовах невизначеності, зокрема, коли ряд параметрів у (1) є нечіткими, неточними, або є недостовірним ма- тематичний опис деяких залежностей в моделі. У цій роботі розглянемо випадок, коли у функціоналі (1) параметри Naa ,...,1 можуть бути задані нечітко. Для зняття нечіткості в задачі 1 засто- суємо метод нейролінгвістичної ідентифікації складних нелінійних залеж- ностей із праць [4, 5]. Опишемо коротко його суть. МЕТОД НЕЙРОЛІНГВІСТИЧНОЇ ІДЕНТИФІКАЦІЇ Для спрощення опису методу нейролінгвістичної ідентифікації для віднов- лення значень нечітких параметрів Naa ,...,1 позначимо їх відновлені зна- чення як y і розглянемо функціональну залежність виходу y від входів qzz ,...,1 об’єкта ідентифікації у вигляді ),...,( 1 qzzyy  , (2) тут qzz ,...,1 — фактори, що впливають на y , і можуть бути задані нечітко. Для задачі ідентифікації передбачаються відомими області визначення вхо- дів qzz ,...,1 , область зміни виходу y для залежності (2), а також експертно- експериментальна інформація про залежність (2) у вигляді вибірки даних про входи і вихід об’єкта ідентифікації. Задача ідентифікації (відновлення) складної нелінійної залежності ви- гляду (2) розглядається як побудова моделі об’єкта за експертно- експериментальними даними про взаємозв’язки <входи> – <вихід> і розв’язується, як правило, в два етапи [5]: 1) структурна ідентифікація: формування нечіткої бази знань про об’єкт і побудова на її основі нечіткої моделі об’єкта з кількома входами і одним виходом, яка грубо відтворює залежність виходу від входів за допо- могою лінгвістичних правил «ЯКЩО–ТО», що генеруються з експеримен- тальних даних; 2) параметрична ідентифікація (налаштування): пошук таких парамет- рів нечіткої моделі, які мінімізують відхилення модельних значень від екс- периментальних. У результаті застосування методу нейролінгвістичної ідентифікації от- римуємо точне (чітке) значення вихідної змінної y , яке розраховується за такими формулами: Нечітка задача оптимального розбиття множин з обмеженнями на розміщення … Системні дослідження та інформаційні технології, 2020, № 1 81 )( )( 1 * 1 *        L k D L k Dk y yd y k k ; (3)           випадках,інших в1 ,1),...,,(якщо,),...,,( )( 1 21 * 1 21 * * kk k s j q k j s j q k j D zzzpzzzp y (4) ,)(),...,,( 1 ** 21 *    q i i k ij k jq k j zvzzzp (5) 2 * * * 1 1 )(            k ij k iji i k ij e tz z , qi ,...,1 , ksj ,...,1 , Lk ,,2,1  , (6) де у формулах (3)–(6):  )(* y kD — функція належності вихідної змінної y класу kD , Lk ,,2,1  ; L — кількість класів (лінгвістичних термів) вихідної змінної y ; kd — центр класу kD ;  ),...,,( 21 * q k j zzzp — нечіткі продукційні правила, отримувані з експертно-експериментальної інформації про залежність (2); j — номер правила у k -му класі; ksj ,,2,1  , ks — кількість правил у k -му класі; k jv* — вага j -го правила у k -му класі виходу;  )(* i k ij z — дзвонова функція належності змінної iz її лінгвістичному терму у j -му правилі k -го класу виходу вихідної змінної y ; k ijt* — коор- дината максимуму і k ije* — коефіцієнт концентрації цієї функції належності. Зауваження 1. Значення k jv* — ваг правил у (5) та параметрів k ijt* , k ije* функції належності (6) відмічено зірочкою як оптимальні, тобто такі, що отримані у результаті етапу параметричної ідентифікації методу нейролінгвістичної ідентифікації, у яких відхилення експериментальних даних від модельних, отриманих після налаштування нечіткої моделі об’єкта (2), досягає мінімального значення. Значення )(* y kD , ),...,,( 21 * q k j zzzp та )(* i k ij z у формулах (3)–(6) обчислюються за оптималь- них значень k jv* , k ijt* , k ije* . Зауваження 2. Для налаштування нечіткої моделі моделі застосовано r -алгоритм Шора [6]. О.М. Кісельова, О.М. Притоманова ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 82 Таким чином, у функціоналі (1) кожний з параметрів Naa ,...,1 , позна- чених вище як вихід y , що залежить від входів qzz ,...,1 , у методі нейролінгвістичної ідентифікації, розраховується за формулами (3)–(6). АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ Для розв’язання задачі 1 з відновленими значеннями Naa ,...,1 уведемо ха- рактеристичні функції підмножин Nii ,...,1,  :        ,\,0 ,,1 )( i i i x x x і перепишемо задачу 1 у термінах характеристичних функцій )(xi у такому вигляді. Задача 2. Знайти )),((min 1)),((   I NA , де 211 )(:))(),...,(()({  xxxx N майже всюди (м.в.) для x ; pibdxxx ii ,...,1,)()(   , },...,1,)()( Npibdxxx ii   , },...,1, для м.в.)(10)(:)({ 1 2 Nixxxx N i ii    . Функції ) ,( ixc  — дійсні, обмежені, визначені на  , вимірні за ар- гументом x за будь-якого фіксованого ),...,( )()1( n iii  з  для всіх Ni ,...,1 ; ),...,( 1 N — сукупність деяких еталонних точок для підмно- жин N ,...,1 відповідно, які називають центрами цих підмножин, причому координати центрів ),...,( )()1( n iii  заздалегідь невідомі і потребують сво- го визначення за умови   N N A NiNi N AAA     .........,...,,..., 11 ; Nbb ,...,1 — задані невід’ємні числа, причому      NiSbbdxxS i N i i ,...,1,0,)( 1 , dxxxaxI N i iii )(λ )()) τ,(c()),(( 1      . (7) У виразі (7) через ia позначені нечіткі параметри Naa ,...,1 , значення яких відновлені за допомогою методу нейролінгвістичної ідентифікації. За- Нечітка задача оптимального розбиття множин з обмеженнями на розміщення … Системні дослідження та інформаційні технології, 2020, № 1 83 дача 2 є задачею нескінченновимірного математичного програмування з бу- левими змінними )( . Для задачі 2 у праці [7] доведено теорему, яка визначає вид її оптима- льного розв’язку )),(( **  для Ni ,...,1 , і майже всіх x :           випадках,інших в 0 ,тоді ,,...,1, для м.в. ,),(),( ,1 )( * * * ** * i jjjiii i xNjxji axcaxc x (8) де у якості ),...,,,...,( 1 1 NN  обирається оптимальний розв’язок скінчен- новимірної недиференційовної задачі оптимізації:   ),(min)( 1GG NA max)(]),([minmin 1,1              N i iijjj NjA bdxxaxc N (9) за умов Npii ,...,1,0  , (10)     dxxaxcbG jjj Nj N i ii )(]),([min),( ,11 1 . (11) Для відшукання розв’язку задачі (9)–(11) використаємо алгоритм уза- гальнених псевдоградієнтів з розтягуванням простору в напрямку різниці двох послідовних узагальнених градієнтів, близький до r -алгоритму Шора [6]. Для цього від задачі (9)–(11) перейдемо до задачі безумовної максиміза- ції за  за допомогою введення в цільову функцію (9) негладкої штрафної функції множини },...,1,0{ Npii  , знайти ),(minmax   P NN AE , (12) де    N pi isGP 1 1 ),0(max),(),( . Тут s — досить велике додатне число (значно більше максимальне з множників Лагранжа для функції (11)). Можливість переходу від задачі (9)–(11) до (12) показано у праці [7]. Визначимо i -у компоненту N2 -вимірного вектора узагальненого псе- вдоградієнта   )),(),,((),( PPP ggg )),(),...,,(),,(),...,,(( 11   NN PPPP gggg функції (5) у точці ),...,,,...,(),( 11 NN  таким чином: О.М. Кісельова, О.М. Притоманова ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 84              ,,...,1)],(sign,0[max)()( ,,...,1,)()( ),( Npisbdxxx pibdxxx g iii ii P i (13) Nidxxxgxg icP ii ,...,1,)(),()(),(     , (14) де ),( xg i c  — i -а компонента N -вимірного вектора узагальненого градієн- та ),( xgc  функції ),( ixс  у точці ),...,,...,( 1 Ni  . Опишемо алгоритм. Алгоритм. Попередній етап. Область  укладаємо в n-вимірний па- ралелепіпед  , сторони якого паралельні вісям декартової системи коорди- нат; вважаємо 0)(  x для  \x . Паралелепіпед  покриваємо прямо- кутною сіткою і задаємо початкове наближення ),(),( ]0[]0[  . Обчислюємо значення характеристичної функції )(]0[ x у вузлах сітки за формулою (8), якщо ]0[]0[ ,  . Обчислюємо компоненти вектора ),( Pg у вузлах сітки за формулами (13) і (14), якщо ]0[]0[ ,  , )()( ]0[ xx  . Обираємо початковий пробний крок 00 h r-алгоритму. Крок 1. Алгоритм проводимо за формулами: ),(( ]0[]0[ 0 ]0[]1[   PA ghP N ; ),( ]0[]0[ 0 ]0[]1[   Pgh , де NA P — оператор проектування кожного з центрів підмножин ),...,1( NiAii  на його допустиму множину iA . Крок 2. Нехай в результаті обчислень після ,...2,1, kk n кроків алго- ритму отримано певні значення ][][ , kk  , )()( ]1[ xx k у вузлах сітки. Крок ]1[ k -й: 1) обчислюємо значення )(][ xk у вузлах сітки за формулою (8) при ][][ , kk  ; 2) обчислюємо значення ),( Pg в узлах сітки за формулами (13) і (14) для ][k , ][k , )()( ][ xx k ; 3) виконуємо обчислення за ітераційними формулами: ),(( ][][ 1 ][]1[ kk Pkk k A k gBhP N     ; ),( ][][ 1 ][]1[ kk Pkk kk gBh     , Нечітка задача оптимального розбиття множин з обмеженнями на розміщення … Системні дослідження та інформаційні технології, 2020, № 1 85 де  1kB ,  1kB — оператори відображення перетвореного простору в основ- ний простір nE , причому NIB  0 , NI — одинична матриця;  ),(~ [k][k] Pg ),( [k][k]* 1   Pk gB ; kh — величина кроку, яка розраховується з умови міні- муму різниці )],(),([ ]1[][ 1 ][]1[ 1   kkkk GG у напрямку узагальненого ан- типсевдоградієнта ),(  Pg у перетвореному просторі [7]; 4) якщо умова ,0,),(),( ][][]1[]1[   kkkk (15) не виконується, переходимо до ]2[ k -го кроку алгоритму, якщо виконуєть- ся, — то до п.5; 5) вважаємо ][][ , ll  ,  )()( ][* xx l , де l — номер ітерації, на якій виконалась умова (15); 6) обчислюємо оптимальне значення цільового функціонала ),(1 G за формулою (11), якщо ,  , і для контролю правильності розра- хунків оптимальне значення цільового функціонала задачі 2 знаходимо за формулою dxxxaxI N i iii )(λ )()) τ,(c()),(( 1 **     . Завершення роботи алгоритму. Розроблений алгоритм програмно ре- алізований мовою програмування Java у середовищі розробки IntelliJ IDEA. Його роботу проілюстровано на модельній задачі. МОДЕЛЬНА ЗАДАЧА Нехай задано множину }10;10:),{( )2()1( 2 )2()1(  xxExx спо- живачів однорідної продукції, яка може вироблятися за п’ятьма пунктами виробництва. Вартість транспортування одиниці продукції з i -го, 5 ,1i , пункту виробництва до споживача ),( )2()1( xx задається у вигляді 2)2()2(2)1()1( )()(),( iii xxxc  . Попит на продукцію 1),( )2()1(  xx  ),( )2()1( xx . При цьому потуж- ність i-го виробника визначається сумарним попитом споживачів, що нале- жать i , і не перевищує заданих обсягів 1ib , 5,...,1i . Не виключається випадок, коли деякі з підмножин i можуть вияви- тися порожніми. Потрібно розбити множину споживачів  на їх зони обслуговуван- ня i п'ятьма пунктами виробництва та розмістити ці пункти в області  так, щоб мінімізувати функціонал (1) сумарних витрат на доставку про- О.М. Кісельова, О.М. Притоманова ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 86 дукції до споживача. Також на координати i розташування пунктів вироб- ництва накладено додаткові обмеження: варіант 1: 22 A , де };5,03,0;8,06,0:),({ )2()1()2()1( 2  xxxxxA ; варіант 2: 44 A , де ).6,0;3,0(},12,0:),({ 00 )2()1( 4  zzxxxxA Для розв’язання модельної задачі за допомогою описаного алгоритму та його програмної реалізації множина  покривалася прямокутною сіткою з вузлами 100,...,1,100,...,1),,(  jiji . Як початкові значення двоїстих змінних задано 0]0[  , початкові координати розташування пунктів вироб- ництва 5,...,1),0;0(]0[  i . Для умови припинення обчислень (15) задано значення 410 . Наведемо спочатку результати оптимального розбиття множини  за точних значень параметрів ia : 07,01 a ; 1,02 a ; 38,03 a ; 2,04 a ; 05 a . Для випадку відсутності додаткових обмежень на розміщення пунк- тів виробництва у результаті роботи алгоритму за 150 ітерацій отримано: мінімальне значення цільового функціонала 2679,0F ; оптимальні координа- ти центрів: )2415,0;2848,0(1  ; )7632,0;2019,0(2  ; )1496,0;8099,0(4  ; )6575,0;7103,0(5  . Оптимальне розбиття для цього випадку показано на рис. 1, а). Тут замість розбиття на п’ять підмножин оптимальним виявилося розбиття на чотири підмножини, одна підмножина 3 виявилася порож- ньою тому, що значення 3a значно більше за ia , .5,4,2,1i Для випадку наявності додаткових обмежень за варіантом 1 на роз- міщення пунктів виробництва у результаті роботи алгоритму за 8 ітера- цій отримано: мінімальне значення цільового функціонала 2850,0F , 1 4 2 5 1 42 5 1 4 2 5 a б в Рис. 1. Оптимальне розбиття множини споживачів  на зони обслуговування кожним пунктом виробництва для чітких параметрів ia , 5,4,2,1i : а — без дода- ткових обмежень на розміщення пунктів виробництва ( 2679,0F ); б — з додатко- вим обмеженням на розміщення пунктів виробництва ( 2850,0F ); в — з додатковим обмеженням на розміщення пунктів виробництва ( 2850,0F ) Нечітка задача оптимального розбиття множин з обмеженнями на розміщення … Системні дослідження та інформаційні технології, 2020, № 1 87 оптимальні координати центрів: )3981,0;1755,0(1  ; )3000,0;6000,0(2  ; )1861,0;8805,0(4  ; )7402,0;6238,0(5  . Оптимальне розбиття для цього випадку показано на рис. 1, б). Для випадку наявності додаткових обмежень за варіантом 2 на розмі- щення пунктів виробництва у результаті роботи алгоритму за 28 ітерацій отримано: мінімальне значення цільового функціонала 2792,0F , оп- тимальні координати центрів: )2137,0;2798,0(1  ; )8242,0;2813,0(2  ; )5564,0;1882,0(4  ; )5119,0;7446,0(5  . Оптимальне розбиття для цього випадку показано на рис. 1, в). Для розв’язання модельної задачі з нечіткими параметрами 51,...,aa за- стосовано розроблений алгоритм з тими ж вхідними даними, що і для чітких параметрів 51,...,aa . Для випадку наявності додаткових обмежень за варіантом 1 на розмі- щення пунктів виробництва у результаті роботи алгоритму для відновлених значень нечітких параметрів 51,...,aa до налаштування отримано за 21 ітера- цію: мінімальне значення цільового функціонала 3189,0F , оптимальні ко- ординати центрів: )3275,0;2198,0(1  ; )3000,0;6000,0(2  ; ;8689,0(4  )2048,0 ; )7479,0;5792,0(5  . Оптимальне розбиття для цього випадку по- казано на рис. 2, а). За відновлених значень нечітких параметрів 51,...,aa після налаштування отримано за 8 ітерацій: мінімальне значення цільового функціонала 2850,0F , оптимальні координати центрів: )3981,0;1755,0(1  ; )3000,0;6000,0(2  ; )1861,0;8805,0(4  ; )7402,0;6234,0(5  . Оптима- льне розбиття для цього випадку показано на рис. 2, б). Для випадку наявності додаткових обмежень за варіантом 2 на розмі- щення пунктів виробництва у результаті роботи алгоритму для відновлених Рис. 2. Оптимальне розбиття множини споживачів  на зони обслуговування кожним пунктом виробництва з додатковими обмеженнями для варіанта 1: а — для відновлених значень нечітких параметрів ia , 1, 2, 4, 5i  , до налаштування, б — після налаштування 1 42 5 3189,0F a 2850,0F б 4 2 5 1 О.М. Кісельова, О.М. Притоманова ISSN 1681–6048 System Research & Information Technologies, 2020, № 1 88 значень нечітких параметрів 51,...,aa до налаштування отримано за 10 ітерацій: мінімальне значення цільового функціонала 3145,0F , оптимальні координа- ти центрів: )2753,0;2490,0(1  ; )8174,0;1547,0(2  ; ;3801,0(4  )6893,0 ; )4238,0;7523,0(5  . Оптимальне розбиття для цього випадку показано на рис. 3, а). За відновлених значень нечітких параметрів 51,...,aa після налаш- тування отримано за 27 ітерацій: мінімальне значення цільового функці- онала 2792,0F , оптимальні координати центрів: )2090,0;2802,0(1  ; ;)8230,0;2845,0(2  ;)5575,0;1878,0(4  ).5086,0;7439,0(5  Оптимальне розбиття для цього випадку показано на рис. 3, б). Порівнюючи результати розв’язання модельної задачі (див. рис. 1, 2, 3), отримані для чітких параметрів та нечітких параметрів, відновлених за до- помогою методу нейролінгвістичної ідентифікації після налаштування, ба- чимо, що оптимальні розв’язки збігаються з достатнім ступенем точності. Таким чином, можна зробити висновок, що метод нейролінгвістичної ідентифікації з достатнім ступенем точності відновлює значення параметрів, які невідомі або неточні. Причому, як очікувалося, значення цільових функ- ціоналів для задачі з обмеженнями на розміщення центрів не менші, ніж значення цільових функціоналів без таких обмежень. ВИСНОВКИ Роботу присвячено подальшому розвитку теорії оптимального розбиття множин з n -вимірного евклідового простору nE на випадок неперервної лінійної однопродуктової задачі оптимального розбиття множин за наявнос- ті додаткових обмежень на розміщення центрів підмножин та нечітких па- раметрів у цільовому функціоналі. Рис. 3. Оптимальне розбиття множини споживачів  на зони обслуговування кож- ним пунктом виробництва з додатковими обмеженнями для варіанта 2: а — для відновлених значень нечітких параметрів ia , 5,,1i , до налаштування ( 3145,0F ), б — після налаштування ( 2792,0F ) 1 4 2 5 a 3 1 4 2 5 б Нечітка задача оптимального розбиття множин з обмеженнями на розміщення … Системні дослідження та інформаційні технології, 2020, № 1 89 Розроблено алгоритм розв’язання цієї задачі, який ґрунтується на за- стосуванні загального підходу, розробленого у теорії оптимального розбит- тя множин [2], а саме: зведення неперервної нескінченновимірної задачі оп- тимального розбиття до негладкої скінченновимірної задачі оптимізації, для числового розв’язання якої застосовується метод узагальнених псевдо- градієнтів, близький до r -алгоритму Шора. Для відновлення значень нечіт- ких параметрів у цільовому функціоналі задачі застосовано нейронечіткі технології. Розроблений алгоритм програмно реалізований мовою програмування Java у середовищі розробки IntelliJ IDEA. Його роботу проілюстровано на модельній задачі. Аналіз результатів розв’язання модельної задачі показав ефективність роботи розробленого алгоритму. ЛІТЕРАТУРА 1. Kiseleva E.M. The Emergence and Formation of the Theory of Optimal Set Parti- tioning for Sets of the n-Dimensional Euclidean Space. Theory and Application / E.M. Kiseleva // Journal of Automation and Information Sciences. — 2018. — Vol. 50, Issue 9. — P. 1–24. — DOI: 10.1615/JAutomatInfScien. v50.i9.10. 2. Кісельова О.М. Становлення та розвиток теорії оптимального розбиття множин. Теоретичні і практичні застосування: моногр. / О.М. Кісельова. — Д.: Ліра, 2018. — 532 с. 3. Кісельова О.М. Алгоритм розв’язання однієї задачі оптимального розбиття з нечіткими параметрами в цільовому функціоналі / О.М. Кісельова, О.М. Притоманова, С.В. Журавель, В.В. Шаравара // Питання прикладної математики і математичного моделювання. — Д.: Ліра, 2018. — С. 91–104. — DOI: 10.15421/321810. 4. Борисов В.В. Нечеткие модели и сети / В.В. Борисов, В.В. Круглов, А.С. Федулов. — М.: Горячая линия-Телеком, 2015. — 284 с. 5. Kiseleva E.M. Valuation of Startups Investment Attractiveness Based on Neuro- Fuzzy Technologies / E.M. Kiseleva, O.M. Prytomanova, S.V. Zhuravel // Jour- nal of Automation and Information Sciences. — 2016. — Vol. 48, Issue 9. — P. 1–22. — DOI: 10.1615/JAutomatInfScien.v48.i9.10. 6. Шор Н.З. Методы минимизации недифференцируемых функций и их прило- жения / Н.З. Шор. — К.: Наук. думка, 1979. — 200 с. 7. Киселева Е.М. Непрерывные задачи оптимального разбиения множеств: тео- рия, алгоритмы, приложения: моногр. / Е.М. Киселева, Н.З. Шор. — К.: На- ук. думка, 2005. — 564 с. Надійшла 18.02.2020
id	journaliasakpiua-article-209136
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:26:44Z
publishDate	2020
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/bd/c481ca88e0de151e544cd30db75862bd.pdf
spelling	journaliasakpiua-article-2091362020-08-11T08:50:57Z Fuzzy problem of the optimal set partition with constraints on the subsets centers location Нечеткая задача оптимального разбиения множеств с ограничениям на размещение центров подмножеств Нечітка задача оптимального розбиття множин з обмеженнями на розміщення центрів підмножин Kiseleva, Elena M. Prytomanova, Olga M. нескінченновимірне математичне програмування теорія оптимального розбиття множин обмеження на розміщення центрів підмножин недиференційовна оптимізація нечіткі параметри r-алгоритм Шора бесконечномерное математическое программирование теория оптимального разбиения множеств ограничения на размещение центров подмножеств недифференцируемая оптимизация нечеткие параметры r-алгоритм Шора infinite-dimensional mathematical programming the theory of optimal set partitioning constraints on the centers location non-differentiable optimization fuzzy parameters Shor's r-algorithm An algorithm is proposed for solving the fuzzy continuous optimal sets partitioning problem with constrains for the centers location. The algorithm is based on a synthesis of methods for solving infinite-dimensional problems of optimal set partitioning from an n-dimensional Euclidean space into subsets with neuro-fuzzy technologies and modifications of the Shor’s r-algorithm, which are used for the numerical solution of dual finite-dimensional nonsmooth optimization problems. The developed software implementation of the algorithm is illustrated on the model problem. Предложен алгоритм решения нечеткой непрерывной линейной однопродуктовой задачи оптимального разбиения множеств на подмножества с отысканием координат центров этих подмножеств и ограничениями на их размещение. Алгоритм базируется на синтезе методов решения бесконечномерных задач оптимального разбиения множеств из n-мерного евклидова пространства на подмножества с нейронечеткими технологиями и модификациями r-алгоритма Н.З. Шора, которые применяются для численного решения двойственных конечномерных негладких задач оптимизации. Разработанную программную реализацию алгоритма проиллюстрировано на модельной задаче. Запропоновано алгоритм розв’язання нечіткої неперервної лінійної однопродуктової задачі оптимального розбиття множин на підмножини з відшуканням координат центрів цих підмножин та обмеженнями на їх розміщення. Алгоритм ґрунтується на синтезі методів розв’язання нескінченновимірних задач оптимального розбиття множин із n-вимірного евклідового простору на підмножини з нейронечіткими технологіями та модифікаціями r-алгоритму Н.З. Шора, які застовуються для числового розв’язання двоїстих скінченновимірних негладких задач оптимізації. Розроблену програмну реалізацію алгоритму проілюстровано на модельній задачі. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2020-06-23 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/209136 10.20535/SRIT.2308-8893.2020.1.07 System research and information technologies; No. 1 (2020); 78-89 Системные исследования и информационные технологии; № 1 (2020); 78-89 Системні дослідження та інформаційні технології; № 1 (2020); 78-89 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/209136/209248 Copyright (c) 2021 System research and information technologies
spellingShingle	нескінченновимірне математичне програмування теорія оптимального розбиття множин обмеження на розміщення центрів підмножин недиференційовна оптимізація нечіткі параметри r-алгоритм Шора Kiseleva, Elena M. Prytomanova, Olga M. Нечітка задача оптимального розбиття множин з обмеженнями на розміщення центрів підмножин
title	Нечітка задача оптимального розбиття множин з обмеженнями на розміщення центрів підмножин
title_alt	Fuzzy problem of the optimal set partition with constraints on the subsets centers location Нечеткая задача оптимального разбиения множеств с ограничениям на размещение центров подмножеств
title_full	Нечітка задача оптимального розбиття множин з обмеженнями на розміщення центрів підмножин
title_fullStr	Нечітка задача оптимального розбиття множин з обмеженнями на розміщення центрів підмножин
title_full_unstemmed	Нечітка задача оптимального розбиття множин з обмеженнями на розміщення центрів підмножин
title_short	Нечітка задача оптимального розбиття множин з обмеженнями на розміщення центрів підмножин
title_sort	нечітка задача оптимального розбиття множин з обмеженнями на розміщення центрів підмножин
topic	нескінченновимірне математичне програмування теорія оптимального розбиття множин обмеження на розміщення центрів підмножин недиференційовна оптимізація нечіткі параметри r-алгоритм Шора
topic_facet	нескінченновимірне математичне програмування теорія оптимального розбиття множин обмеження на розміщення центрів підмножин недиференційовна оптимізація нечіткі параметри r-алгоритм Шора бесконечномерное математическое программирование теория оптимального разбиения множеств ограничения на размещение центров подмножеств недифференцируемая оптимизация нечеткие параметры r-алгоритм Шора infinite-dimensional mathematical programming the theory of optimal set partitioning constraints on the centers location non-differentiable optimization fuzzy parameters Shor's r-algorithm
url	https://journal.iasa.kpi.ua/article/view/209136
work_keys_str_mv	AT kiselevaelenam fuzzyproblemoftheoptimalsetpartitionwithconstraintsonthesubsetscenterslocation AT prytomanovaolgam fuzzyproblemoftheoptimalsetpartitionwithconstraintsonthesubsetscenterslocation AT kiselevaelenam nečetkaâzadačaoptimalʹnogorazbieniâmnožestvsograničeniâmnarazmeŝeniecentrovpodmnožestv AT prytomanovaolgam nečetkaâzadačaoptimalʹnogorazbieniâmnožestvsograničeniâmnarazmeŝeniecentrovpodmnožestv AT kiselevaelenam nečítkazadačaoptimalʹnogorozbittâmnožinzobmežennâminarozmíŝennâcentrívpídmnožin AT prytomanovaolgam nečítkazadačaoptimalʹnogorozbittâmnožinzobmežennâminarozmíŝennâcentrívpídmnožin

Нечітка задача оптимального розбиття множин з обмеженнями на розміщення центрів підмножин

Institution

Ähnliche Einträge