Розв’язування задач комбінаторної оптимізації на нечітких множинах

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

Національна академія наук України

Інститут кібернетики ім. В.М. Глушкова

УДК 519.85

Автореферат

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Розв'язування задач комбінаторної оптимізації на нечітких множинах

01.05.01 Теоретичні основи інформатики та кібернетики

Ємець Олександра Олегівна

Київ-2009

Дисертацією є рукопис

Робота виконана в Полтавському університеті споживчої кооперації України.

Науковий керівник: доктор фізико-математичних наук, Донець Георгій Панасович, Інститут кібернетики ім. В.М. Глушкова НАН України, завідувач відділу економічної кібернетики.

Офіційні опоненти: доктор фізико-математичних наук, Ляшенко Ігор Миколайович, Київський національний університет ім. Тараса Шевченка, професор кафедри математичної інформатики

доктор технічних наук, Гребеннік Ігор Валерійович, Харківський національний університет радіоелектроніки, професор кафедри системотехніки комбінаторний оптимізація множинний

Захист відбудеться 11 вересня 2009 р. о 1200 годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М. Глушкова НАН України за адресою: 03680 МСП Київ 187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися у науково-технічному архіві Інституту кібернетики імені В.М. Глушкова НАН України.

Автореферат розісланий «24» липня 2009 р.

В. о. вченого секретаря спеціалізованої вченої ради ХІМІЧ О.М.

Загальна характеристика роботи

Актуальність теми. Дослідження і аналіз складних явищ, об'єктів, процесів та систем, прагнення будувати більш адекватні моделі для них приводять, зокрема, до розвитку теорії і методів комбінаторної оптимізації. Як правило, моделі та методи комбінаторної оптимізації є детермінованими та не враховують невизначеності. Відомі поодинокі роботи, в яких розглядаються задачі комбінаторної оптимізації з урахуванням невизначеності, вираженої за допомогою нечітких множин. Таким чином, тематика досліджень, пов'язана з розв'язуванням задач комбінаторної оптимізації на нечітких множинах, є вельми актуальною.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася на кафедрі математичного моделювання та соціальної інформатики Полтавського університету споживчої кооперації України згідно з індивідуальним планом аспірантської підготовки та планами науково-дослідної роботи університету в рамках тем: №275/08 «Розвиток теорії та методів комбінаторної оптимізації» (2009 р.), №213/04 «Евклідова комбінаторна оптимізація» (2005-2008 рр.).

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

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

2. розвиток апарату комбінаторної оптимізації шляхом введення понять нечітких комбінаторних конфігурацій та формалізацією понять взаємного розташування нечітких об'єктів в комбінаторних оптимізаційних задачах геометричного проектування;

3. розвиток підходів та створення точних методів для розв'язування задач комбінаторної оптимізації на нечітких множинах;

4. розвиток наближених методів для задач комбінаторної оптимізації на нечітких множинах та їх дослідження.

Об'єкт дослідження - задачі комбінаторні оптимізації та методи їх розв'язування.

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

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

Наукова новизна одержаних результатів. Всі результати дисертації, що виноситься на захист, є новими:

- розвинуто апарат нечітких множин (введенням нових дій та відношень), доведено, що на відміну від інших вони мають властивості необхідні для розв'язування задач комбінаторної оптимізації;

- розвинуто апарат евклідової комбінаторної оптимізації введенням і обґрунтуванням нових понять: нечіткі переставлення, нечіткі розміщення, нечіткі розбиття, що дозволяє враховувати невизначеність;

- вперше запропоновано підхід до розв'язування задач пакування, в яких метричні характеристики задані нечіткими множинами; формалізовано поняття взаємного розташування нечітких прямокутників, що дозволяє розв'язувати задачі в нечіткій постановці;

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

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

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

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

Особистий внесок здобувача. Всі результати дисертаційної роботи, що виносяться на захист, отримані особисто автором. У працях, що написані у співавторстві, дисертанту належить:

[1] - операції з нечіткими числами, формулювання та доведення тверджень, постановка прикладної задачі комбінаторної оптимізації на нечітких множинах як задачі на переставленнях та побудова математичної моделі цієї задачі; методи розв'язування цієї задачі, їх оцінка.

[3] - формулювання понять, формулювання та доведення теорем.

[4] - формулювання понять та тверджень; постановка прикладної задачі евклідової комбінаторної оптимізації на нечітких множинах як задачі на переставленнях та побудова математичної моделі цієї задачі.

[6] - формулювання поняття евклідової множини розбиттів; формулювання операцій з нечіткими числами; постановка прикладної задачі евклідової комбінаторної оптимізації на нечітких множинах як задачі на розбиттях та побудова математичної моделі цієї задачі.

[7] - формулювання понять та тверджень; постановка прикладної задачі евклідової комбінаторної оптимізації на нечітких множинах як задачі на переставленнях та побудова математичної моделі цієї задачі.

[8, 9] - формулювання поняття нечіткого розміщення, комбінаторної множини всіх нечітких розміщень.

[12] - евристичний алгоритм розв'язування однієї прикладної задачі евклідової комбінаторної оптимізації на нечітких множинах.

Публікації. Основні результати дисертаційної роботи, опубліковані в 13 наукових працях автора: з них 7 статей (4 статті у фахових виданнях), 6 - в збірниках матеріалів та тез доповідей конференцій.

Структура та обсяг дисертації. Дисертація складається з вступу, основної частини з п'яти розділів, висновків, списку використаних джерел з 111 найменувань, трьох додатків. Загальний обсяг дисертації 221 сторінок, основного тексту - 147 сторінок.

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

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

У першому розділі - необхідні відомості з теорії комбінаторної оптимізації та теорії нечітких множин, вибір напрямків дослідження.

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

Розглянемо упорядковану -вибірку

(1)

з мультимножини , тобто , .

Множина переставлень без повторень з різних дійсних чисел - це множина всіх упорядкованих -вибірок вигляду (1) з мультимножини при умові, що . Множина переставлень з повтореннями з дійсних чисел, з яких різні, - це множина всіх упорядкованих -вибірок вигляду (1) з мультимножини при умові, що . Нехай - натуральне число. Розіб'ємо його на доданки:

.

Тоді називається розбиттям числа на частин. Зазначимо: розбиття не є елементом евклідової комбінаторної множини.

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

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

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

Дефазифікація - це процедура перетворення нечіткої множини в число. Дефазифікація нечіткої множини за методом центра ваги відбувається за формулою: .

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

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

2. формалізація понять нечітке розміщення, нечітке переставлення, нечітке розбиття з метою використання їх при постановці та розв'язуванні задач комбінаторної оптимізації;

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

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

5. дослідження можливості застосування відомих та розвиток нових точних, наближених методів розв'язування задач, що можуть бути сформульовані як задачі комбінаторної оптимізації на нечітких множинах.

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

Нечітким числом називаємо нечітку множину вигляду , де , , - носій нечіткої множини, , , - множина значень функції приналежності, , . Будь-яке дійсне число можна представити як нечітке число .

Сума двох нечітких чисел і утворюється побудовою множини пар

. (2)

Перші елементи , де , цих пар утворюють мультимножину . Основа мультимножини : - це носій нечіткого числа . Значення функції приналежності знаходять за правилом:

. (3)

Тобто, значення обирається як сума серед чисел , для яких , а - число різних елементів в .

Таким чином, сумою двох нечітких чисел назвемо нечітке число , де - основа мультимножини , що визначається (2), а значення означається (3).

Сумою трьох нечітких чисел , та назвемо нечітке число , де .

Характеристичною функцією (функціоналом) нечіткого числа будемо називати функцію, що нечіткому числу ставить у відповідність число за правилом:

. (4)

Нехай задані два нечітких числа: і . Позначимо , , . Тоді, число можна записати у вигляді , де . Число запишеться у вигляді: , де .

Порядок для нечітких чисел вводимо так: будемо називати два нечітких числа і впорядкованими за спаданням і казати, що передує за зростанням тоді, коли:

а) або , ();

б) або , тобто , але , …, , , ().

Будемо називати два нечітких числа і впорядкованими за неспаданням порядком (позначати ) тоді, коли: а) або ;

б) або , тобто тоді, коли і , .

Нечітке число будемо називати мінімумом з нечітких чисел , , …, чисел, якщо . А число - максимумом.

Різницею двох нечітких чисел і назвемо число .

Введемо операцію ділення нечіткого числа на нечітке число наступним чином.

1 спосіб. Дефазифікуємо нечітке число . Позначимо результат дефазифікацїї як . Тоді результатом діленням двох нечітких чисел і назвемо число .

2 спосіб. Ділити два нечітких числа за правилом узагальнення Заде.

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

Твердження 1. Операція суми для нечітких чисел комутативна, тобто .

Твердження 2. Операція суми для нечітких чисел асоціативна, тобто .

Теорема 3. Порядок є рефлексивним, антисиметричним та транзитивним, тобто лінійним.

Твердження 4. Коли , то .

Теорема 5. Для будь-яких двох нечітких чисел , і характеристичної функції , заданої за правилом (4), виконується: .

Теорема 6. Для будь-яких трьох нечітких чисел , , , таких, що , , , , виконується: якщо , то .

Твердження 7. , тоді і тільки тоді, коли .

Дана оцінка складності виконання основних операцій над нечіткими числами. Знайдено час роботи при визначенні найбільшого або найменшого серед () нечітких чисел , , , де - носій нечіткої множини , а - множина значень функції приналежності. Нехай , , тоді час роботи буде не більше, ніж , де - асимптотично точна оцінка.

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

Обчислено час роботи для знаходження результату ділення на за першим способом, Позначивши , отримали - . Знайдено час роботи для знаходження результату ділення на за другим способом - .

В третьому розділі дані означення: множини нечітких переставлень, множини нечітких розбиттів, множини нечітких розміщень.

Загальну множину переставлень , де - мультимножина нечітких чисел, назвемо загальною множиною переставлень нечітких чисел.

Розглянемо розбиття числа на частин , де . Задамо порядок елементів в розбитті . Таке розбиття назвемо евклідовим, а множину всіх таких розбиттів числа назвемо евклідовою множиною розбиттів і позначимо її .

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

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

Розглянемо нечітку множину з характеристичною функцією для множини вигляду:

,

де - евклідова множина розміщень з необмеженими повтореннями з мультимножини з основою і первинною специфікацією .

Довільний елемент назвемо нечітким розміщенням. Множину всіх таких розбиттів назвемо комбінаторною множиною всіх нечітких розміщень.

Дано формалізацію понять розташування прямокутників з нечіткими параметрами в смузі.

Нехай розміри прямокутника (смуги) задаються дійсними числами та . Зв'яжемо з нижнім лівим кінцем смуги початок прямокутної декартової системи координат, спрямувавши вісі вздовж смуги.

Позначимо прямокутник, що буде розміщуватися в смузі, . Розміщення прямокутників будемо розглядати такі, що вісі системи координат, зв'язаної з кожним з прямокутників, паралельні осям , та направлені в ті ж сторони. Тоді прямокутник відносно смуги визначається такими параметрами: - абсциса полюса в системі координат ; - ордината полюса в системі координат ; - ширина (висота) прямокутника; - довжина прямокутника. Прямокутник позначимо або просто .

Нехай смуга (прямокутник), в якій відбувається розміщення задана так , де , - це ширина (висота) прямокутника, а - його довжина, система координат розташована як описано вище.

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

Прямокутник назвемо таким, що розміщається (поміщається) в смузі , якщо

(5)

а умови (5) назвемо умовами розміщення прямокутника в смузі .

Прямокутники та назвемо такими, що перетинаються, якщо виконується одна з умов

(6)

а (6) назвемо умовами взаємного перетинання двох прямокутників.

Прямокутники та назвемо такими, що не перетинаються, якщо виконується сукупність нерівностей

Прямокутники та назвемо такими, що дотикаються, якщо виконується одна або декілька наступних систем:

В четвертому розділі для задачі упакування прямокутників з нечіткими розмірами побудовано математичну модель у вигляді задачі на нечітких переставленнях та у вигляді задачі на нечітких розбиттях та запропоновано методи для розв'язування.

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

Математична модель представляється у такому вигляді: знайти

; .(7)

Для розв'язування (7) запропоновано алгоритм методу гілок та меж.

1. Впорядкуємо нечіткі довжини прямокутників .

2. Формуємо початкове розміщення наступним чином: кожний наступний прямокутник з впорядкованого за незростанням набору довжин, починаючи з прямокутника з довжиною , розміщується у ту смужку, довжина зайнятої частини якої є найменшою після розміщення попереднього. Запам'ятовуємо початкове розміщення і значення цільової функції при цьому розміщенні.

3. Крок . Розташовуємо прямокутник з довжиною в першу смужку, . Позначимо отриману множину як . Оцінку будь-якої множини знаходимо як довжину зайнятої частини смуги. Оцінка . Значення збільшуємо на 1.

4. На кроці розбиваємо множину на підмножин : , , , , де - кількість смужок, тобто розміщуємо прямокутник з довжиною : в першу смужку, в другу тощо Для підмножини , де - деяке натуральне число, знаходимо оцінку . Якщо , то множину відсікаємо. Якщо множина відображає переставлення з множини переставлень і , то значенню привласнюємо значення , а розміщенню привласнюємо розміщення, яке відображає множина . Для розгалуження обираємо підмножину , оцінка якої найменша. Усі підмножини, крім підмножини, обраної для розгалуження, переглянутих та відтятих, перепозначаємо на , де , - натуральні числа або нуль. Значення збільшуємо на 1.

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

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

Теорема 8. Час роботи методу гілок та меж залежить від кількості смужок як , від кількості прямокутників як , від максимальної потужності нечітких множин, які характеризують довжини прямокутників, як .

Для цієї ж задачі упакування прямокутників була побудована математична модель, як задачі на нечітких розбиттях: знайти

; . (8)

Для (8) запропоновано метод гілок та меж, алгоритм якого аналогічний алгоритму методу гілок та меж для задачі на переставленнях.

Теорема 9. Час роботи алгоритму методу гілок та меж для задачі на розбиттях залежить від кількості смужок як , від кількості прямокутників як , від максимальної потужності нечітких множин - довжин прямокутників - як .

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

Евристичний алгоритм для розв'язування задачі упакування прямокутників з довжинами, заданими нечіткими числами:

Крок 1. Впорядкуємо нечіткі довжини прямокутників: ….

Крок 2. Прямокутник з довжиною розміщуємо в першу смужку, …, з довжиною - в смужку . Нехай .

Крок 3. Серед смужок визначаємо смужку з найменшою нечіткою довжиною і розміщуємо в ній прямокутник з довжиною .

Крок 4. Збільшуємо на 1, якщо , то - на крок 3, інакше - на 5.

Крок 5. Визначаємо смугу з найбільшою довжиною.

Зауваження. На кроці 5 всі прямокутники розміщені. Найбільше значення довжини дає значення цільової функції.

Теорема 10. Час роботи евристичного алгоритму залежить від кількості смужок як , від кількості прямокутників як , від максимальної потужності нечітких множин - довжин прямокутників - як .

Була розглянута задача про ранець в нечіткій постановці: ранець ємністю необхідно так упакувати неподільними предметами видів з вартістю і ємністю , щоб сумарна вартість упакованих предметів була максимальною, де , , () - нечіткі числа.

Математична модель задачі має вигляд: знайти

(9)

за умов

, (10)

(11)

Для задачі (9)-(11) запропоновано наступний евристичний метод.

Крок 1. Знаходимо для усіх .

Крок 2. Впорядковуємо нечіткі числа : ..., .

Крок 3. Привласнюємо , (тобто - нечіткий нуль).

Крок 4. Перевіряємо чи виконується умова ?. Якщо так, то переходимо до кроку 5. Якщо ні, то переходимо до кроку 6.

Крок 5. , . Переходимо до кроку 7.

Крок 6. . Переходимо до кроку 7.

Крок 7. ? Якщо так, то і переходимо до кроку 4. Якщо ні, то переходимо до кроку 8.

Крок 8. Знаходимо значення цільової функції : .

Теорема 11. Розглянутий евристичний метод для задачі про ранець (9)-(11) має поліноміальну складність.

Висновки

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

В дисертації розглянуто розв'язування задач комбінаторної оптимізації на нечітких множинах.

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

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

У дисертації:

- розвинуто апарат нечітких множин (введенням нових дій та відношень), доведено, що вони мають властивості, необхідні для розв'язування задач комбінаторної оптимізації;

- розвинуто апарат евклідової комбінаторної оптимізації новими поняттями: нечіткі переставлення, нечіткі розміщення, нечіткі розбиття;

- вперше запропоновано підхід до розв'язування задач геометричного проектування, в яких метричні характеристики об'єктів задані нечіткими множинами; формалізовано поняття взаємного розташування нечітких прямокутників;

- вперше запропонована постановка задач евклідової комбінаторної оптимізації на нечітких множинах як задач на нечітких переставленнях, нечітких розбиттях та на прикладі однієї прикладної задачі побудована математична модель задачі, запропоновано методи розв'язування; зроблені оцінки складності для цих методів;

- вперше запропоновані поліноміальні евристичні методи розв'язування задач комбінаторної оптимізації на нечітких множинах для ряду прикладних задач.

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

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

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

Побудовані алгоритми розроблених методів дають можливість швидко та зручно розв'язувати поставлені задачі за допомогою комп'ютерної техніки. Практична ефективність запропонованих алгоритмів підтверджена числовими експериментами.

Основні положення дисертації опубліковані в таких працях

1. Роскладка А.А. Решение одной комбинаторной задачи упаковки с учетом неопределенности данных, описанной нечеткими числами / А.А Роскладка, А. О. Емец // Радиоэлектроника и информатика. - 2007. - № 2. - С. 132-141.

2. Ємець Ол-ра О. Одна задача упакування як комбінаторна оптимізація на нечіткій множині розбиттів і її розв'язування / Ол-ра О. Ємець // Радиоэлектроника и информатика. - 2007. - № 4. - С. 150-160.

3.Ємець О.О. Деякі операції та відношення над нечіткими числами / О.О. Ємець, Ол-ра О. Ємець // Наукові вісті НТУУ «КПІ». - 2008 - №5. - С. 39-46.

4. Ємець О.О. Побудова математичної моделі однієї комбінаторної задачі упакування прямокутників з нечіткими розмірами / О.О. Ємець, Ол-ра О. Ємець // Наукові вісті НТУУ «КПІ». - 2008 - №6. - С. 25-33.

5.Ємець Ол-ра О. Одна задача комбінаторної оптимізації на переставленнях нечітких множин / Ол-ра О. Ємець // Волинський математичний вісник: Серія: прикл. математика. - 2004, вип. 2(11). - С. 101-106.

6. Ємець О.О. Задача евклідової комбінаторної оптимізації в умовах невизначеності / О.О. Ємець, А.А. Роскладка, Ол-ра О. Ємець // Зб. наук. праць: фізико-математичні науки. - 2005. Вип. 1. - Хмельницький: Хмельниц. нац. ун-т. С. 40-45.

7. Ємець О.О. Економіко-математична модель однієї задачі теорії розкладів / О.О. Ємець, Ол-ра О. Ємець // Економіка: проблеми теорії та практики: зб. наук. праць. - 2007. Вип. 233, Т. ІІ. С. 293-301.

8. Емец О.А.Комбинаторное множество нечетких размещений / О.А. Емец , А.О. Емец // Матеріали VII Міжн. наук.-практ. конф. “Наука і освіта - 2004”., 10-15 лют. 2004 р. Том 70. Математика.: тези доп. - Дніпропетровськ: Наука і освіта, 2004. - с.42-43.

9. Ємець Є.М. Нечіткі комбінаторні розміщення / Є.М. Ємець , Ол-ра О. Ємець //ІІІ-а міжн. школа-семінар „Теорія прийняття рішень”, 2-7 жовтня 2006 р: праці школи-семін. - Ужгород: УжНУ, 2006. - С. 52-53.

10. Ємець Ол-ра О. Одна комбінаторна задача оптимізації діяльності багатопроцесорних систем з нечіткими заявками / Ол-ра О. Ємець // Матеріали всеукраїнської наук.-практ. конф. „Структурні зміни в економіці та освіті під впливом інформаційно-комунікаційних технологій”, 24-25 квітня 2008 р.: тези доп. - Полтава, РВВ ПУСКУ, 2008. - С.52-53.

11. Ємець Ол-ра О. Одна задача оптимізації на множині нечітких розбиттів / Ол-ра О. Ємець // Матеріали дванадцятої міжн. наук. конф. ім. акад. М. Кравчука, 15-17 травня 2008 р.: тези доп. - Київ, 2008 - С.611.

12. Донець Г.П. Евристичний алгоритм для комбінаторної задачі упакування нечітких прямокутників / Г.П. Донець, Ол-ра О. Ємець // Матеріали другої ювілейної міжн. наук.-техн. конф. «Комп`ютерна математика в інженерії, науці та освіті» (CMSEE-2008), 29-31 жовтня 2008 р.: тези доп. - Полтава, ПолтНТУ, 2008. - С.8.

13. Ємець Ол-ра О. Одна задача формування портфелю цінних паперів з невизначеністю / Ол-ра О. Ємець // Міжн. наук.-практ. конф. “Споживча кооперація ХХІ століття: уроки трансформаційних реформ і перспективи розвитку”, 20-21 листопада 2008 р.: тези доп. - Полтава, РВВ ПУСКУ, 2008. - С.154-156.

Анотації

Ємець О.О. Розв'язування задач комбінаторної оптимізації на нечітких множинах. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. - Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2008.

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

Ключові слова: комбінаторна оптимізація, нечіткі числа, нечіткі комбінаторні множини, взаємне розташування нечітких прямокутників.

Емец А.О. Решение задач комбинаторной оптимизации на нечетких множествах. - Рукопись.

Диссертация на соискание научной степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2008.

Во вступлении изложена актуальность, сформулированы цель, задачи, предмет, объект и методы исследования, изложена научная новизна и практическое значение полученных результатов.

В первом разделе рассмотрены необходимые сведения комбинаторной оптимизации и теории нечетких множеств. Определены направления диссертационных исследований.

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

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

В четвертом разделе на примере двух задач евклидовой комбинаторной оптимизации как: 1) задачи на нечетких перестановках; 2) задачи на нечетких разбиениях - было показано применение аппарата нечетких чисел. Осуществлено решение этих задач методом ветвей и границ. Даны оценки количества операций при решении этих задач методом ветвей и границ.

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

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

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

Yemets` O.O. Solving the combinatorial optimization problems on fuzzy sets. - Manuscript.

Thesis for a candidate degree on physics and mathematics (Ph.D.) by speciality 01.05.01 - theoretical bases of informatics and cybernetics. - V.M.Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, Kiev, 2008.

The definitions of fuzzy combinatorial sets of permutation, partitions, allocations are introduced. Operations and ratio under fuzzy numbers are introduced. Their necessary properties are proved. Arrangement of rectangles with fuzzy sizes in the fuzzy size bread are defined. Application of the developed apparatus for the one problem of the Euclidean combinatorial optimization as problem on fuzzy permutations and as problem on fuzzy partitions is shown. The problem is solved by branches and measures. A heuristic method for solving the problem of packing rectangles with widths which are described by fuzzy numbers is proposed. The problem about pack under uncertainty which is set fuzzy numbers is formulated. Its mathematical model is constructed. A heuristic method for its approximate solving are proposed. Polynomial estimates of complexity heuristic methods are received.

Key words: combinatorial optimization, fuzzy number, fuzzy combinatorial sets, mutual arrangement of fuzzy rectangles.

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

...