Методи та алгоритми розв’язування нечітких задач оптимального розбиття множин
Ознайомлення з методами формулювання математичних постановок нечітких задач оптимального розбиття множин. Аналіз застосування теорії неперервних задач оптимального розбиття множин у нейронечітких технологіях та до розв’язання задач ідентифікації систем.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | автореферат |
| Язык | украинский |
| Дата добавления | 30.07.2015 |
| Размер файла | 151,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Дніпропетровський національний університет імені Олеся Гончара
УДК 519.85:519.863
Автореферат дисертації на здобуття наукового ступеня кандидата фізико-математичних наук
Методи та алгоритми розв'язування нечітких задач оптимального розбиття множин
01.05.01 - теоретичні основи інформатики та кібернетики
Лебідь Оксана Юріївна
Дніпропетровськ - 2011
Дисертацією є рукопис.
Робота виконана на кафедрі обчислювальної математики та математичної кібернетики Дніпропетровського національного університету імені Олеся Гончара Міністерства освіти і науки України.
Науковий керівник: заслужений діяч науки і техніки України, доктор фізико-математичних наук, професор Кісельова Олена Михайлівна, Дніпропетровський національний університет імені Олеся Гончара, декан факультету прикладної математики.
Офіційні опоненти:
доктор фізико-математичних наук, професор Крак Юрій Васильович, Київський національний університет імені Тараса Шевченка, професор кафедри моделювання складних систем;
кандидат фізико-математичних наук, доцент Ус Світлана Альбертівна, Національний гірничий університет, доцент кафедри системного аналізу і управління.
Захист відбудеться «10» червня 2011 р. о 14 годині на засіданні спеціалізованої вченої ради К 08.051.09 при Дніпропетровському національному університеті імені Олеся Гончара за адресою: 49044, м. Дніпропетровськ, пр. Карла Маркса, 35, корп. 3, ауд. 25.
З дисертацією можна ознайомитись у бібліотеці Дніпропетровського національного університету імені Олеся Гончара за адресою: 49050, м. Дніпропетровськ, вул. Козакова, 8.
Автореферат розісланий «6» травня 2011 р.
Вчений секретар спеціалізованої вченої ради В.А. Турчина.
Загальна характеристика роботи
Актуальність теми. Значний інтерес до розвитку теорії оптимального розбиття множин (ОРМ) пов'язаний з тим, що методи та алгоритми ОРМ знаходять ефективне застосування до розв'язання актуальних практичних задач різних сфер людської діяльності. Питанням теорії оптимального розбиття множин та питанням, близьким до цієї теорії присвячена, особливо останнім часом, велика кількість публікацій, що свідчить про необхідність, важливість та актуальність подібних досліджень. У цьому зв'язку слід відзначити публікації H. W. Corley, S. D. Roberts, R. L. Francis, M. Friedman, Н. Jandl, К. Wieder, Ю. В. Крака, Ю. Г. Стояна, В. Р. Хачатурова, С. В. Туєва, С. В. Яковлева, а також праці науковців Дніпропетровської наукової школи під керівництвом О. М. Кісельової. Представниками цієї школи розвивається теорія неперервних задач оптимального розбиття множин, які є некласичними задачами нескінченновимірного математичного програмування з булевими змінними.
Оскільки моделі економічних, виробничих, соціальних та інших процесів, що враховують природну невизначеність вихідної інформації, більш адекватні реальним, то важливим і актуальним стає дослідження неперервних задач оптимального розбиття множин в умовах невизначеності. Цим питанням присвячено праці О. М. Кісельової, К. А. Кузнєцова, Л. І. Лозовської, О. О. Жильцової, Я. Є. Кадочнікової, С. А. Ус і ін.
Актуальним залишається дослідження неперервних задач ОРМ, у яких для формалізації невизначеної вихідної інформації, яка має не ймовірнісно-статистичну, а нечітко-можливісну природу, використовується апарат теорії нечітких множин, яку ввів Л. Заде у 1965 р. Дисертаційна робота продовжує дослідження у зазначеному актуальному напрямі. Вона присвячена розробці й обґрунтуванню методів та алгоритмів розв'язування нечітких задач ОРМ.
Зв'язок роботи з науковими програмами, планами, темами. Дисертаційні дослідження проводилися на кафедрі обчислювальної математики та математичної кібернетики Дніпропетровського національного університету імені Олеся Гончара згідно з індивідуальним планом підготовки аспіранта. Наукові дослідження, результати яких увійшли до дисертаційної роботи, проводились у межах держбюджетних тем № 5-035-03 «Нейронечітке моделювання в задачах охорони навколишнього середовища з використанням методів оптимального розбиття» (2003-2005 рр., ДР № 0103U000562) та № 5-128-06 «Математичні моделі та алгоритми розв'язання задач оптимального розбиття множин в умовах невизначеності» (2006-2008 рр., ДР № 0106U000800).
Мета і завдання дослідження. Мета роботи - розробка та обґрунтування методів розв'язування неперервних нечітких задач оптимального розбиття множин з -вимірного евклідового простору на підмножини з фіксованим положенням центрів цих підмножин, створення алгоритмів та їх програмна реалізація.
Основні завдання дослідження:
– проведення аналізу сучасного стану теорії оптимального розбиття множин на підмножини в умовах невизначеності;
– формулювання математичних постановок нечітких задач ОРМ;
– розробка й теоретичне обґрунтування методів розв'язування неперервних нечітких задач ОРМ;
– розробка алгоритмів на основі створених методів розв'язування неперервних нечітких задач оптимального розбиття множин;
– програмна реалізація побудованих алгоритмів;
– застосування теорії неперервних задач ОРМ у нейронечітких технологіях, а також до розв'язання задач ідентифікації систем за допомогою радіальних мереж.
Об'єктом дослідження є неперервні задачі оптимального розбиття множин в умовах невизначеності, які є задачами нескінченновимірного математичного програмування з булевими змінними.
Предметом дослідження є неперервні нечіткі задачі оптимального розбиття множин на підмножини з фіксованим положенням центрів цих підмножин, методи та алгоритми їх розв'язання.
Методи дослідження - методи нескінченновимірного математичного програмування, недиференційовної оптимізації, нечіткого математичного програмування; комплексне використання теорії нечітких множин; методи розв'язання неперервних лінійних задач ОРМ; функціональний аналіз.
Наукова новизна одержаних результатів. Основні результати, які визначають наукову новизну і виносяться на захист, такі:
– дістало подальший розвиток розкриття невизначеності в задачах ОРМ за допомогою теорії нечітких множин;
– вперше побудовано нові математичні моделі неперервних нечітких задач оптимального розбиття чіткої множини на підмножини з фіксованим положенням центрів цих підмножин;
– теоретично обґрунтовано новий метод розв'язання задачі нечіткого оптимального розбиття множин, що використовує функцію належності аналітичного виду (функцію Гаусса);
– вперше теоретично обґрунтовано метод розв'язування задачі ОРМ із інтервальними правими частинами, які задаються у системі обмежень;
– розроблено й теоретично обґрунтовано нові методи розв'язування задач ОРМ із нечіткими параметрами у цільовому функціоналі або обмеженнях;
– вперше застосовано теорію неперервних задач ОРМ до розв'язання задач прогнозування з використанням нейронечітких технологій, а також до розв'язання задач ідентифікації систем за допомогою радіальних мереж.
Практичне значення одержаних результатів. Сформульовані в дисертації постановки неперервних нечітких задач ОРМ із фіксованим положенням центрів цих підмножин за наявності обмежень у формі нерівностей дозволяють більш адекватно моделювати певні реальні процеси через урахування нечіткості вихідної інформації.
Розроблені в дисертації методи й алгоритми можуть бути застосовані для розв'язання як теоретичних, так і практичних задач з різних предметних областей, що зводяться в математичній постановці до неперервних нечітких задач ОРМ. Так, до практичних задач відносяться задачі складського планування, оптимального покриття, розміщення-розподілу, класифікації, кластеризації, розпізнавання образів і ін. Серед теоретичних задач слід зазначити задачі групового вибору, побудови оптимальних квадратур, глобальної оптимізації і ін.
Розроблено систему FuzzyORM, що програмно реалізує відомі та розроблені в дисертаційній роботі алгоритми, яка призначена для розв'язання неперервних чітких та нечітких задач оптимального розбиття множин на підмножини з фіксованим положенням центрів цих підмножин і може бути використана для розв'язання практичних задач у сферах економіки і виробництва, а також може бути впроваджена в навчальний процес вищих навчальних закладів при вивченні теорії і методів нечіткої логіки, оптимального розбиття множин, системного аналізу та ін.
Окремі теоретичні результати і система FuzzyORM використовуються в навчальному процесі на факультеті прикладної математики Дніпропетровського національного університету імені Олеся Гончара при виконанні дипломних і курсових робіт, а також у відділах інформаційної роботи та митної статистики Державної митної служби України.
Особистий внесок здобувача. Усі результати дисертаційної роботи, що виносяться на захист, одержані автором особисто. У працях, опублікованих у співавторстві, здобувачу належить: побудова математичних моделей нечітких задач ОРМ (у публікаціях [4-11]); розробка підходів до розв'язання деяких нечітких задач ОРМ (у [1, 6, 9]); розробка та обґрунтування методів і алгоритмів розв'язання нечітких задач ОРМ [4-7, 10, 11]; створення системи FuzzyORM [12]; розробка алгоритму ОРМ та його застосування у нейронечітких технологіях, а також до розв'язання задач ідентифікації систем за допомогою радіальних мереж [2, 3].
Апробація результатів дисертації. Результати дисертаційної роботи доповідались і обговорювались на семінарах кафедри обчислювальної математики та математичної кібернетики факультету прикладної математики Дніпропетровського національного університету імені Олеся Гончара; на семінарах кафедри вищої математики та інформатики Академії митної служби України; на міжнародних конференціях «Problem of decision making under uncertainties» (Алушта, Тернопіль, Чернівці, 2003, 2004, 2006, 2007 рр.); на І всеукраїнській конференції «Математичне та програмне забезпечення інтелектуальних систем» (Дніпропетровськ, 2003 р.); на XI міжнародній конференції «Математика. Компьютер. Образование» (Росія, Дубна, 2004 р.); на II-VІ, VІII міжнародних науково-практичних конференціях «Математичне та програмне забезпечення інтелектуальних систем» (Дніпропетровськ, 2005-2008, 2010 рр.).
Публікації. Основні результати дисертаційної роботи опубліковано в 12 наукових працях: 7 статей [1-7] у наукових фахових виданнях з фізико-математичних наук, які входять до переліку, затвердженого ВАК України; 5 тез доповідей у збірниках матеріалів міжнародних наукових конференцій [8-12].
Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, п'яти розділів, висновків, списку використаних джерел та трьох додатків. Загальний обсяг дисертації становить 230 сторінок, містить 137 сторінок основної частини, включає 38 рисунків, 14 таблиць, 193 джерел бібліографічних найменувань.
Основний зміст роботи
Перший розділ містить аналітичний огляд наукової літератури за темою дисертації та формалізацію проблеми. Особливу увагу приділено аналізу досліджень неперервних нечітких задач ОРМ та методу знаходження нечіткого оптимального розбиття множин з фіксованим положенням центрів підмножин без наявності обмежень. Коротко описано сучасний стан досліджень у теорії ОРМ. Проведено аналіз застосування теорії нечітких множин та нечіткого математичного програмування до розв'язання практичних задач.
Виявлено актуальний напрям подальшого розвитку теорії ОРМ та обґрунтовано вибір предмета наукового дослідження дисертаційної роботи, а саме неперервних нечітких задач оптимального розбиття множин.
У другому розділі уводяться необхідні позначення, які використовуються для формулювання неперервних нечітких задач оптимального розбиття множин.
Нехай - непорожня, обмежена, вимірна за Лебегом множина -вимірного евклідового простору ; - множина всіх можливих розбиттів множини , а саме
Вводимо до розгляду функціонал
,(1)
де - розбиття множини на підмножини , ; - множина точок , , які називаються «центрами» підмножин та координати яких задані заздалегідь; - будь-яка точка множини ; - дійсні, обмежені, визначені на функції; - невід'ємна, дійсна, обмежена функція; - задані дійсні невід'ємні числа.
Тут і надалі інтеграли та міра множин розуміються в сенсі Лебега.
Уводиться стандартна задача ОРМ, на основі якої формулюються неперервні нечіткі задачі ОРМ. Під стандартною задачею ОРМ розуміємо неперервну однопродуктову задачу оптимального розбиття множини з на її підмножини при обмеженнях у формі нерівностей із фіксованим положенням центрів підмножин у такій постановці.
Задача 2.1. Знайти
,
за умов
(2)
де - задані дійсні додатні числа, причому виконується умова розв'язності задачі
, , (3)
Задачу оптимального розбиття множин вважаємо нечітко сформульованою (нечіткою), якщо в задачі ОРМ структура цільового функціонала, параметри цільового функціонала та (або) обмежень є нечіткими, неточними, недовизначеними; функції, які входять до цільового функціонала або до системи обмежень, задані у вигляді нечітких множин або мають нечіткі параметри, тощо.
У підрозділі 2.1 наведено класифікацію неперервних нечітких задач оптимального розбиття множин. Підрозділ 2.2 містить загальні підходи до розв'язання нечітких задач ОРМ. У підрозділі 2.3 розроблено підходи до розв'язання задач ОРМ у випадку нечіткої множини можливих розбиттів.
Уведено нечітку множину допустимих розбиттів
.
Сформульовано задачу ОРМ із нечіткою множиною можливих розбиттів.
Задача 2.2. Знайти таке , щоб функціонал вигляду (1) набирав у деякому сенсі мінімального значення на множині .
Означення 2.1. Розв'язком 1 задачі 2.2 називаємо нечітку підмножину множини , яка описується функцією належності вигляду
,
де ; - множина рівня нечіткої множини можливих розбиттів .
Доведено наступну пропозицію.
Пропозиція 2.1. Якщо , то .
Означення 2.3. Розв'язком 2 задачі 2.2 називаємо нечітку множину з функцією належності вигляду
де - множина всіх ефективних розбиттів для функціонала та функції , тобто таких розбиттів , для яких вибором іншого розбиття з неможливо зменшити значення функціонала, не зменшивши при цьому значення , або навпаки.
Для розв'язків 1 та 2 доведено теорему про їх еквівалентність.
Теорема 2.1. Якщо множина компактна, функціонал неперервний на , а функція напівнеперервна зверху на , то при будь-яких значеннях виконується рівність
,
де ;
, .
У підрозділі 2.4 розроблено алгоритм розв'язання неперервної задачі ОРМ з «м'якими» обмеженнями в такій постановці.
Задача 2.3. Знайти
,
за умов
,
де цільовий функціонал має вигляд (1); знак означає нечітке виконання відповідних нерівностей; - задані дійсні додатні числа, причому виконується умова (3).
У третьому розділі досліджується неперервна задача нечіткого оптимального розбиття множин на підмножини з фіксованим положенням центрів цих підмножин та задача ОРМ з інтервальними правими частинами в системі обмежень.
У підрозділі 3.1 сформульовано постановку неперервної задачі оптимального нечіткого розбиття множин на підмножини з фіксованим положенням центрів цих підмножин без наявності обмежень, для якої розроблено метод розв'язання і створено алгоритм.
Означення 3.1. Можливим нечітким розбиттям чіткої множини з , де - обмежена, вимірна за Лебегом множина, будемо називати таке , для якого виконуються умови
, ,
де , ,
Позначимо множину можливих нечітких розбиттів через , на якій введено цільовий функціонал у вигляді
,(4)
де функції - задані, дійсні, обмежені, визначені на , вимірні за при будь-якому фіксованому підмножини , ; - задана, обмежена, вимірна на функція; інтеграли беруться за нечіткими множинами.
Сформульовано таку постановку неперервної задачі нечіткого оптима-льного розбиття множини.
Задача 3.1. Знайти
,
де цільовий функціонал має вигляд (4).
Задачу 3.1 переформульовано в термінах функцій належності , де .
Задача 3.2. Знайти
,
, (5)
,
майже всюди (м. в.) для х?, ;
- операція драстичного об'єднання, яка визначається таким чином:
До розв'язання задачі 3.2 запропоновано наступний підхід. У ролі функцій належності , використовуються функції аналітичного вигляду, а саме функції Гаусса, причому
,
, (6)
де ; - центр нечіткої множини , який відомий заздалегідь, , Зауважимо, що при кожному фіксованому наборі вигляд (6) забезпечує виконання умови .
Від задачі 3.2 здійснюється перехід до задачі
Задача 3.2". Знайти
де .
Означення 3.2. Розв'язок , м. в. для будемо називати -розв'язком задачі 3.2", якщо при довільному заданому , .
Доведено теорему про необхідну та достатню умову існування -розв'язку задачі 3.2".
Теорема 3.1. Нехай : , , , - евклідова норма. Тоді для існування -розв'язку задачі 3.2" необхідно та достатньо, щоб
При виконанні умов теореми 3.1 задача 3.2" еквівалентна наступній задачі.
Задача 3.3. Знайти
де
Означення 3.3. Вектор , який при заданих та належить множині та доставляє максимальне значення функціоналу , будемо називати -оптимальним розв'язком задачі 3.3.
Лема 3.1. Максимального значення функціонал набуває при значеннях , які відповідають правим границям відповідних проміжків з .
З леми 3.1 випливає, що -оптимальний розв'язок задачі 3.3 має вигляд
, . (7)
Алгоритм 3.1 розв'язання задачі 3.3.
1. Область розміщуємо в -вимірний паралелепіпед сторони якого паралельні осям декартової системи координат, задаємо для . Паралелепіпед покриваємо прямокутною сіткою.
2. Задаємо необхідну точність .
3. Визначаємо -оптимальний розв'язок з (7).
4. Для кожного вузла сітки знаходимо , де , з (6).
5. Обчислюємо оптимальне значення цільового функціонала
.
Підрозділ 3.2 присвячено дослідженню неперервної задачі ОРМ із інтервальними правими частинами, які задано у системі обмежень.
Задача 3.4. Знайти
,
за умов
(8)
де цільовий функціонал має вигляд (1);
, - задані дійсні невід'ємні числа, причому для них виконується умова
, , (9)
Задачу 3.4 переписано в термінах характеристичних функцій підмножин ,
у якій нерівності (8) переписано у термінах інтервальних величин.
Задача 3.5. Знайти :
,
де м. в. для ; , , ;
,
, м. в. для .
Від задачі 3.5 нескінченновимірного математичного програмування з булевими змінними здійснено перехід до задачі зі значеннями з відрізка . нейронечіткий математичний множина
Задача 3.6. Знайти :
,
де м. в. для ; , , ;
, м. в. для .
Для обґрунтування методу розв'язання задачі 3.6 на множині вводимо функціонал Лагранжа
, (10)
де м. в. для ; - вектор дійсних чисел, ; .
Двоїста задача до задачі 3.6 має вигляд
, , (11)
де .
При виконанні умов (9) має місце
Теорема 3.5. Задачі 3.6 і (11) пов'язані співвідношенням двоїстості
,
де - екстремальні значення вихідної (задачі 3.6) та двоїстої задач відповідно, причому верхня грань в задачі (11) досягається.
Встановлено, що розв'язання пари двоїстих задач еквівалентно відшуканню сідлової точки функціонала Лагранжа (10) на множині і справедлива теорема
Теорема 3.9. Сідлова точка функціонала з (10) на множині визначається для і м. в. для у такий спосіб
(12)
де - оптимальний розв'язок задачі 3.6;
в якості , обирається оптимальний розв'язок двоїстої задачі (11), приведеної до вигляду
(13)
Для побудови алгоритму розв'язання задачі 3.6 здійснено перехід від задачі умовної оптимізації (13) до задачі безумовної оптимізації, шляхом уведення в цільову функцію (13) негладкої штрафної функції множини ,
, ,
де - достатньо велике додатне число (значно більше за максимальний множник Лагранжа для функції (10)).
Розроблено алгоритм розв'язання неперервної задачі ОРМ з інтервальними правими частинами в системі обмежень, складовою частиною якого є метод узагальненого градієнтного спуску з розтягненням простору у напрямку різниці двох послідовних узагальнених градієнтів (модифікація -алгоритму Шора).
Четвертий розділ присвячено дослідженню неперервних нечітких задач ОРМ з нечіткими параметрами в цільовому функціоналі або обмеженнях.
У підрозділі 4.1 досліджено неперервну задачу ОРМ з нечітким параметром в обмеженнях.
Задача 4.1. Знайти
,
за умов
, (14)
де цільовий функціонал має вигляд (1); - задані дійсні додатні числа; - нечіткий параметр, який є нечіткою підмножиною універсальної множини .
У роботі досліджена задача 4.1 на випадок, коли - дискретний, тобто
де - потужність даної множини.
Нечітка множина допустимих розбиттів визначається в такий спосіб:
,
де - деяке значення нечіткого параметра , яке має степінь належності ;
.
Доведено таке твердження.
Твердження 4.1. Якщо вектор задовільняє умові
, , (15)
де - невід'ємна нечітка величина, то множина розв'язків задачі 4.1 не порожня.
Будемо називати нечітким розв'язком задачі 4.1 наступну множину
,
де .
Доведено таке твердження.
Твердження 4.2. Для будь-якого із функцією належності існує розбиття із функцією належності таке, що
, , або , .
Для вибору єдиного раціонального розбиття з нечіткої множини запропоновано застосувати підхід Беллмана-Заде, за яким в якості розв'язку задачі 4.1 обирається розбиття з , яке реалізує величину:
де - функція належності нечіткої множини мети при виборі розбиття .
У пункті 4.1 розроблено алгоритм розв'язання задачі 4.1 на випадок дискретно заданих носіїв нечітких параметрів на основі наведених вище тверджень, а також представлено інші підходи до розв'язання цієї задачі.
У підрозділі 4.2 досліджується неперервна задача ОРМ з нечіткими параметрами у функціоналі вигляду
,(16)
де ; - набір нечітких параметрів; ;
, - задані центри відповідних підмножин;
- визначена на , дійсна, обмежена, вимірна за аргументом функція.
Задача 4.2. Нехай - нечіткі параметри, які мають такий вигляд
де - потужність даних множин.
Необхідно
,
за умов
, (17)
де цільовий функціонал вигляду (16); - задані дійсні додатні числа, які задовільняють умову (3).
Позначаємо через - множину всіх допустимих розбиттів, тобто таких , для яких виконується умова (17).
Від задачі 4.2 здійснюється перехід до задачі мінімізації в певному сенсі функції належності нечіткої множини мети
,
де ; ;
для деякого заданого набору значень .
У роботі показано, що допустимі, але заздалегідь неприйнятні розв'язки будуть роз'язками, які не належать множині, що складається з оптимальних розв'язків стандартних задач ОРМ при фіксованих значеннях нечітких параметрів і позначається через
,
де ;
.
Оскільки функціонал (16) нечіткий, то для будь-якого існує нечітка множина .
Доведено таке твердження.
Твердження 4.3. Для будь-якого розбиття та існує розбиття та таке, що
,
коли , або ,
де .
З твердження 4.3 випливає, що розв'язком задачі 4.2 буде множина Для раціонального вибору єдиного розв'язку з розроблено два методи. Перший метод базується на принципі узагальнення Заде, а другий - на недомінованих розбиттях.
За першим методом від нечіткої задачі оптимального розбиття множин здійснюється перехід до двокритеріальної задачі оптимізації
де
.
Для розв'язання отриманої задачі запропоновано використовувати підхід виділення основного критерію.
Розроблений метод 2 розв'язання задачі 4.2 передбачає, що будь-якому розбиттю певна функція ставить у відповідність нечітку оцінку цього розбиття у формі нечіткої підмножини множини оцінок з .
Степенем переваги розбиття над розбиттям вважаємо перевагу нечіткої оцінки над нечіткою оцінкою , тобто , де - природний порядок на числовій осі.
Функція та індукують на множині нечітке відношення переваги вигляду:
де .
Розв'язком вихідної задачі вважаємо функцію вигляду
,
де .
Раціональним вибором з нечіткої множини недомінованих розбиттів будемо вважати вибір розв'язку з найбільшим значенням . На основі запропонованого методу 2 розв'язання задачі 4.2 розроблено алгоритм.
П'ятий розділ присвячено застосуванню методу ОРМ до прикладних задач, а саме: у підрозділі 5.1 розглянуто застосування методу ОРМ у нейронечітких технологіях; підрозділ 5.2 присвячено застосуванню методу ОРМ для підбору початкових параметрів радіальної мережі.
Висновки
У дисертаційній роботі вперше розв'язано нову актуальну наукову задачу розробки й обґрунтування методів та алгоритмів розв'язання неперервних нечітких задач оптимального розбиття множин на підмножини з фіксованим положенням центрів цих підмножин.
Основні наукові результати дисертації полягають у такому.
1. Вперше сформульовано математичну постановку неперервної задачі ОРМ із інтервальними правими частинами, що задаються у системі обмежень.
2. Сформульовано нову постановку неперервної задачі нечіткого оптимального розбиття множин на підмножини з фіксованим положенням центрів цих підмножин без наявності обмежень, а також неперервної задачі ОРМ з нечітким параметром в системі обмежень.
3. Розроблено й теоретично обґрунтовано новий метод розв'язання неперервної задачі нечіткого оптимального розбиття множин, що ґрунтується на введенні до цільового функціонала функції належності аналітичного вигляду, а саме функції Гаусса. Такий підхід, у порівнянні з відомими методами, суттєво спрощує знаходження нечіткого оптимального розбиття множини на її підмножини.
4. Вперше розроблено й теоретично обґрунтовано метод розв'язання неперервної задачі ОРМ з інтервальними правими частинами, що задаються у системі обмежень. В основі цього методу лежить зведення нескінченновимірних вихідних задач до скінченновимірних негладких задач.
5. Вперше розроблено й теоретично обґрунтовано метод розв'язання неперервної задачі ОРМ з нечітким параметром в обмеженнях. В основі розробленого методу лежить перехід до задачі ОРМ з нечіткою множиною допустимих розв'язків та застосування підходу Беллмана-Заде для раціонального вибору розв'язку з нечіткої множини оптимальних розбиттів.
6. Вперше розроблено методи розв'язання неперервної задачі ОРМ з нечіткими параметрами у цільовому функціоналі. Один з методів розв'язання базується на принципі узагальнення Заде, а інший - на недомінованих розбиттях.
7. Вперше розроблено алгоритм розв'язання «м'якої» задачі ОРМ, що базується на поданні вихідної нечіткої множини у вигляді розкладання на скінченну кількість її множин рівня.
8. Розроблено новий алгоритм розв'язання задачі знаходження оптимального розбиття чіткої множини на нечіткі підмножини з фіксованим положенням центрів цих підмножин та без наявності обмежень.
9. Для неперервної задачі ОРМ з інтервальними правими частинами, що задаються у системі обмежень, вперше побудовано алгоритм, у якому для розв'язання отриманих скінченновимірних негладких задач застосовується модифікація -алгоритму Шора.
10. На основі розроблених методів уперше створено алгоритми розв'язання неперервної задачі ОРМ з нечітким параметром у системі обмежень та неперервної задачі ОРМ з нечіткими параметрами у цільовому функціоналі.
11. Створено систему FuzzyORM, у якій програмно реалізовано всі розроблені в дисертаційній роботі алгоритми. У системі також реалізовано алгоритм розв'язання чіткої задачі ОРМ, а саме алгоритм розв'язання неперервної лінійної задачі оптимального розбиття множин на підмножини з фіксованим положенням центрів цих підмножин за наявності обмежень у формі нерівностей, що дозволяє для деяких неперервних нечітких задач ОРМ проводити порівняльний аналіз отриманих числових розв'язків.
12. Алгоритм розв'язання неперервної задачі нечіткого оптимального розбиття множин протестовано на модельній задачі розбиття множини суб'єктів зовнішньоекономічної діяльності на зони обслуговування відділами митного оформлення, що розташовані у Дніпропетровській області. Усі інші розроблені алгоритми протестовано на модельних задачах розбиття заданої множини споживачів однорідної продукції на зони обслуговування підприємствами з обмеженнями на їх виробничі потужності.
13. Застосовано теорію неперервних задач ОРМ у нейронечітких технологіях. Вперше розроблено алгоритм визначення параметрів нейронечіткої бази знань на основі розв'язання неперервної лінійної задачі оптимального розбиття множин з розміщенням центрів, який дозволяє виключити втручання експерта при побудові нейронечіткої бази знань і функцій належності, що спрощує використання на практиці нейронечітких технологій для розв'язання задачі прогнозування.
14. Розроблено алгоритм підбору початкових параметрів радіальних мереж (їх кількість і центри), який може бути застосований при створенні на основі таких мереж систем ідентифікації, прогнозування тощо.
Список опублікованих праць за темою дисертації
1. Киселёва Е. М. Классификация нечетких задач оптимального разбиения множеств и некоторые подходы к их решению / Е. М. Киселёва, О. Ю. Лебедь // Проблемы управления и информатики. - 2009. - № 1. - С. 40-51.
2. Кісельова О. М. Побудова моделі прогнозу на основі нейронечіткої технології із застосуванням методу оптимального розбиття множин / О. М. Кісельова, О. Ю. Лебідь // Питання прикладної математики і математичного моделювання : збірник наукових праць. - Дніпропетровськ : ДНУ, 2003. - С. 90-99.
3. Лебідь О. Ю. Застосування методу оптимального розбиття множин для підбору початкових параметрів радіальної мережі / О. Ю. Лебідь // Питання прикладної математики і математичного моделювання : збірник наукових праць. - Дніпропетровськ : ДНУ, 2004. - С. 132-139.
4. Кісельова О. М. Задача оптимального розбиття множин із інтервальним завданням параметрів системи обмежень / О. М. Кісельова, О. Ю. Лебідь // Питання прикладної математики і математичного моделювання : збірник наукових праць. - Дніпропетровськ : ДНУ, 2006. - С. 100-108.
5. Кісельова О. М. Методи розв'язання задач оптимального розбиття множин із нечіткими параметрами у функціоналі / О. М. Кісельова, О. Ю. Лебідь // Питання прикладної математики і математичного моделювання : збірник наукових праць. - Дніпропетровськ : ДНУ, 2007. - С. 115-123.
6. Кісельова О. М. Деякі підходи до розв'язання задач оптимального розбиття множин із нечітким параметром у системі обмежень / О. М. Кісельова, О. Ю. Лебідь // Питання прикладної математики і математичного моделювання : збірник наукових праць. - Дніпропетровськ : ДНУ, 2009. - С. 169-175.
7. Кісельова О. М. Метод розв'язання задачі нечіткого розбиття множин / О. М. Кісельова, О. Ю. Лебідь // Питання прикладної математики і математичного моделювання : збірник наукових праць. - Дніпропетровськ : ДНУ, 2010. - С. 139-145.
8. Кісельова О. М. Постановка нечіткої задачі оптимального розбиття множин / О. М. Кісельова, О. Ю. Лебідь // Математичне та програмне забезпечення інтелектуальних систем : І всеукр. конф., 19-21 лист. 2003 р. : тези допов. - Дніпропетровськ, 2003. - С. 31.
9. Кісельова О. М. Задача оптимального розбиття множин із нечіткою множиною обмежень / О. М. Кісельова, О. Ю. Лебідь // Математичне та програмне забезпечення інтелектуальних систем : ІІІ міжнарод. наук.-практ. конф., 16-18 лист. 2005 р. : тези допов. - Дніпропетровськ, 2005. - С. 74-75.
10. Кісельова О. М. Метод розв'язування задачі нечіткого оптимального розбиття множин із фіксованими центрами за наявності обмежень / О. М. Кісельова, О. Ю. Лебідь // Математичне та програмне забезпечення інтелектуальних систем : VI міжнарод. наук.-практ. конф., 12-14 лист. 2008 р. : тези допов. - Дніпропетровськ, 2008. - С. 167-168.
11. Кісельова О. М. Один із підходів до розв'язання задачі нечіткого оптимального розбиття множин із фіксованими центрами без наявності обмежень / О. М. Кісельова, О. Ю. Лебідь // Системний аналіз та інформаційні технології : 12 міжнарод. наук.-техн. конф. SAIT 2010, 25-29 трав. 2010 р. : тези допов. - К., 2010. - С. 258.
12. Кісельова О. М. Особливості програмної реалізації алгоритмів розв'язання нечітких задач оптимального розбиття множин / О. М. Кісельова, О. Ю. Лебідь // Математичне та програмне забезпечення інтелектуальних систем : VIІІ міжнарод. наук.-практ. конф., 10-12 лист. 2010 р. : тези допов. - Дніпропетровськ, 2010. - С. 102.
Анотація
Лебідь О. Ю. Методи та алгоритми розв'язування нечітких задач оптимального розбиття множин. - Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук зі спеціальності 01.05.01 - теоретичні основи інформатики та кібернетики. - Дніпропетровський національний університет імені Олеся Гончара. - Дніпропетровськ, 2011.
Дисертація присвячена розв'язанню неперервних нечітких задач оптимального розбиття множин на підмножини з фіксованим положенням центрів цих підмножин.
Побудовано математичні моделі неперервних нечітких задач оптимального розбиття множин на підмножини з фіксованим положенням центрів цих підмножин при наявності обмежень у формі нерівностей. Розроблено та теоретично обґрунтовано методи розв'язання поставлених задач.
На основі розроблених методів створено і програмно реалізовано алгоритми розв'язання неперервних нечітких задач оптимального розбиття множин на підмножини з фіксованим положенням центрів цих підмножин.
Застосовано теорію неперервних лінійних задач оптимального розбиття множин на підмножини у нейронечітких технологіях, а також до розв'язання задач ідентифікації систем за допомогою радіальних мереж.
Ключові слова: оптимальне розбиття множин, нечітка множина, нечітка задача оптимального розбиття множин, нескінченновимірне математичне програмування, недиференційовна оптимізація.
Аннотация
Лебедь О. Ю. Методы и алгоритмы решения нечетких задач оптимального разбиения множеств. - Рукопись.
Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Днепропетровский национальный университет имени Олеся Гончара. - Днепропетровск, 2011.
Диссертация посвящена разработке и обоснованию методов решения непрерывных нечетких задач оптимального разбиения множеств с фиксированным положением центров этих подмножеств, а также построению алгоритмов на их основе.
Сформулированы математические постановки непрерывных нечетких задач оптимального разбиения множеств, а именно: непрерывная задача оптимального разбиения множеств с интервальным заданием правых частей системы ограничений; непрерывная задача нечеткого оптимального разбиения множеств на подмножества с фиксированным положением центров этих подмножеств без ограничений; непрерывная задача оптимального разбиения множеств на подмножества с фиксированным положением центров этих подмножеств и нечетким параметром в системе ограничений.
Разработан и теоретически обоснован метод решения непрерывной задачи нечеткого оптимального разбиения множеств на подмножества с фиксированным положением центров этих подмножеств без ограничений, основанный на введении в целевой функционал функции принадлежности аналитического вида, а именно функции Гаусса.
Для непрерывной задачи оптимального разбиения множеств с интервальным заданием правых частей системы ограничений разработан и теоретически обоснован метод решения, в основе которого лежит сведение бесконечномерной исходной задачи к конечномерной негладкой задаче.
Разработан и теоретически обоснован метод решения непрерывной задачи оптимального разбиения множеств на подмножества с фиксированным положением центров этих подмножеств и с нечетким параметром в ограничениях, в основе которого лежит переход к непрерывной задаче оптимального разбиения множеств с нечетким множеством допустимых решений и применения подхода Беллмана-Заде для рационального выбора решения из нечеткого множества оптимальных разбиений.
Для решения непрерывной задачи оптимального разбиения множеств на подмножества с фиксированным положением центров этих подмножеств и с нечеткими параметрами в целевом функционале разработаны два метода. Один из методов решения указанной задачи базируется на принципе обобщения Заде, а другой - на недоминируемых разбиениях.
На основе разработанных методов созданы алгоритмы решения непрерывных нечетких задач оптимального разбиения множеств на подмножества с фиксированным положением центров этих подмножеств, которые программно реализованы в виде программного продукта.
Теория непрерывных задач ОРМ применена в нейронечетких технологиях. Впервые разработан алгоритм определения параметров нейронечеткой базы знаний на основе решения непрерывной линейной задачи оптимального разбиения множеств на подмножества с размещением центров этих подмножеств, который позволяет исключить вмешательство эксперта при построении нейронечеткой базы знаний и функций принадлежности, что упрощает использование на практике нейронечетких технологий для решения задачи прогнозирования.
Разработан алгоритм подбора начальных параметров радиальных сетей (их количество и центры), который может быть применен при создании на основе таких сетей систем идентификации, прогнозирования и т. п.
Ключевые слова: оптимальное разбиение множеств, нечеткое множество, нечеткая задача оптимального разбиения множеств, бесконечномерное математическое программирование, недифференцированная оптимизация.
Annotation
Lebed' O. Yu. Methods and algorithms of solving some fuzzy problems of optimal sets splitting. - Manuscript.
The dissertation for a candidate degree in Physics and Mathematics, speciality - 01.05.01 - theoretical bases of informatics and cybernetics. - Oles Honchar Dnipropetrovsk National University, Dnipropetrovsk, 2011.
The dissertation is devoted to continuous fuzzy problems of optimal set splitting with fixed centers.
Mathematical models of continuous fuzzy of optimal sets splitting into subsets with fixed centers under constraints in the form of inequalities. Developed and theoretically proved methods for solving problems in attitudes.
Created and implemented software algorithms for numerical solution of the optimum fuzzy sets splitting based on established methods.
Applied theory of continuous problems of optimal sets splitting in neuro-fuzzy technologies, as well as to the selection of initial parameters of radial networks.
Key words: optimal sets splitting, fuzzy sets, fuzzy problem of optimal sets splitting, infinite mathematical programming, nondifferentiable optimization.
Размещено на Allbest.ru
...Подобные документы
Лінійне програмування як один з найбільш популярних апаратів математичної теорії оптимального управління рішень. Опис існуючих методів розв’язку задач лінійного програмування. Завдання, основні принципи, алгоритми і головна мета лінійного програмування.
курсовая работа [363,8 K], добавлен 03.12.2009Огляд переваг та недоліків мови Пролог, історія її створення. Числення предикатів як математична основа її функціонування. Порівняльна характеристика середовищ програмування Prolog. Алгоритми розв’язування математичних задач за допомогою цієї мови.
курсовая работа [504,5 K], добавлен 23.12.2014Дискретизація задачі із закріпленим лівим і вільним правим кінцем. Необхідні умови оптимальності. Ітераційний метод розв’язання дискретної задачі оптимального керування з двійним перерахуванням. Оптимальне стохастичне керування. Мінімаксне керування.
контрольная работа [221,8 K], добавлен 19.12.2010Застосування симплекс-методу для розв’язання оптимізаційних задач лінійного програмування, що містять три змінні. Функції ітераційної обчислювальної процедури, що виконують приведення до зручного для розв’язання оптимального вигляду ЗЛП за кілька кроків.
курсовая работа [359,5 K], добавлен 18.09.2013Характерна особливість ігрових задач. Основні види ігрових задач: з повною та неповною інформацією. Методи знаходження планів гри і оптимальних стратегій для таких ігор, як шахи, шашки, "хрестики-нулики". Способи побудови систем штучного інтелекту.
контрольная работа [588,5 K], добавлен 22.01.2015Метод розв’язків рівнянь більш високих порядків. Вибір методу розв'язання задачі Коші. Методи розв'язання крайових задач розглядаються на прикладі звичайного диференціального рівняння другого порядку. Вибір методу інструментальних засобів вирішення задач.
курсовая работа [132,0 K], добавлен 03.12.2009Алгоритми розв’язання задач у вигляді блок–схем. Використання мови програмування MS VisualBasic for Application для написання програм у ході вирішення задач на одномірний, двовимірний масив, порядок розв’язання задачі на використання символьних величин.
контрольная работа [742,9 K], добавлен 27.04.2010Види рівнянь та методи їх розв’язань. Чисельні методи уточнення коренів, постановка задачі. Рішення нелінійного рівняння методом простих та дотичних ітерацій. Використання програмних засобів. Алгоритми розв’язку задач. Програми мовою С++, їх тестування.
курсовая работа [232,2 K], добавлен 12.02.2013Початковий опорний план, перехід від одного до іншого. Оптимальний розв’язок, його головні критерії. Знаходження опорного плану задачі, складання симплексної таблиці. Приклад оформлення першої та другої таблиці для розв’язку задач лінійного програмування.
лекция [479,7 K], добавлен 10.10.2013Методы определения оптимального плана производства (приобретения) продукции с учетом ограниченного обеспечения ресурсами различного вида. Технология поиска оптимального решения задач линейного программирования (ЗЛП) с помощью итоговой симплекс-таблицы.
лабораторная работа [42,8 K], добавлен 11.03.2011Теоретичні основи теорії множин. Основні операції над множинами та їх властивості. Складання програми для обчислення результуючої множини за вихідним і спрощеним виразами. Виконання операцій над множинами, застосування їх властивостей, спрощення виразів.
лабораторная работа [11,3 K], добавлен 12.05.2011Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
методичка [366,8 K], добавлен 16.01.2010Классы задач P и NP, их сводимость. Примеры NP-полных и NP-трудных задач. Сущность метода поиска с возвратом. Алгоритмы решения классических задач комбинаторного поиска. Решение задачи о восьми ферзях. Поиск оптимального решения методом ветвей и границ.
презентация [441,5 K], добавлен 19.10.2014Графічне зображення методу половинного ділення. Вибір методу інструментальних засобів вирішення задач. Розробка логічної частини програми для розв’язання нелінійного рівняння методами половинного ділення та січних. Особливість кодування на мові Паскаль.
курсовая работа [135,5 K], добавлен 30.11.2009Виконання "ручного" розв'язування рівняння методом Ньоютона. Розробка програми на мові С#, яка реалізує введення вихідних даних, розв'язання заданого рівняння, виведення результатів у зручній формі на екран. Визначення початкового наближення кореня.
лабораторная работа [120,9 K], добавлен 19.01.2022Приклади застосування цілочисельних задач лінійного програмування у плануванні та управлінні виробництвом, геометрична інтерпретація їх розв’язків на площині. Завдання складання розкладу занять на математичному факультеті. Математична модель розкладу.
дипломная работа [933,1 K], добавлен 23.09.2012Відомості з теорії графів, методи отримання точних розв'язків задачі їх розфарбування. Алгоритм розфарбування графу методом неявного перебору. Комп'ютерна реалізація розв’язку задачі розфарбування графів. Типові задачі та існуючі програмні продукти.
курсовая работа [335,6 K], добавлен 15.06.2015Модель динамического программирования для решения задач оптимального распределения ресурсов. Принцип оптимальности, уравнение Беллмана. Двумерная и дискретная динамическая модель. Значение метода в решении прикладных задач различных областей науки.
курсовая работа [400,2 K], добавлен 01.10.2009Разработка стратегии и выбор способа автоматизации задачи снабжения для предприятия. Построение функциональной модели бизнес-процессов предметной области. Создание программного средства "1С: Конфигурация ОМТС" для оптимального решения задач снабжения.
дипломная работа [7,2 M], добавлен 12.04.2012Рішення задач з дискретної математики. Запис за допомогою операцій над множинами, вирази для множин відповідно заштрихованим областям. Доведення тотожності, користуючись властивостями операцій над множинами. Запис області визначення і області значень.
контрольная работа [74,6 K], добавлен 06.08.2010
