Методи та алгоритми розв’язання неперервних задач оптимального розбиття множин з обмеженнями

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

Дніпропетровський національний університет імені Олеся Гончара

КАДОЧНІКОВА ЯНА ЄВГЕНІВНА

УДК 519.8

МЕТОДИ ТА АЛГОРИТМИ РОЗВ'ЯЗАННЯ НЕПЕРЕРВНИХ ЗАДАЧ ОПТИМАЛЬНОГО РОЗБИТТЯ МНОЖИН З ОБМЕЖЕННЯМИ

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

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

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

Дніпропетровськ - 2010



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

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

Науковий керівник:

заслужений діяч науки і техніки України, доктор фізико-математичних наук, професор Кісельова Олена Михайлівна, Дніпропетровський національний університет імені Олеся Гончара, декан факультету прикладної математики, завідувач кафедри обчислювальної математики та математичної кібернетики;

Офіційні опоненти: заслужений діяч науки і техніки України, доктор фізико-математичних наук, професор Яковлев Сергій Всеволодович, Харківський інститут управління, завідувач кафедри вищої математики та прикладної інформатики;

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

Захист відбудеться « 12 » лютого 2010 р. о 14 годині на засіданні спеціалізованої вченої ради К 08.051.09 при Дніпропетровському національному університеті імені Олеся Гончара, 49044, м. Дніпропетровськ, пр. Карла Маркса, 35, корп. 3, ауд. 25.

З дисертацією можна ознайомитись у науковій бібліотеці імені Олеся Гончара Дніпропетровського національного університету імені Олеся Гончара, 49050, м. Дніпропетровськ, вул. Козакова, 8.

Автореферат розісланий « 11» січня 2010 р.

Вчений секретар спеціалізованої вченої ради К 08.051.09 В.А. Турчина



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

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

Велику кількість вітчизняних та зарубіжних публікацій присвячено подібним дослідженням, серед яких можна виділити роботи авторів: О.М. Кісельової, Ю.Г. Стояна, Н.З. Шора, С.В. Яковлева, J. E. Beasley, L. Cooper, H.W. Corley, Z. Drezner, M. Padberg.

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

- задачі з дискретною множиною, що розбивається (дискретні задачі розбиття);

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційну роботу було виконано на кафедрі програмного забезпечення та обчислювальної техніки Дніпродзержинського державного технічного університету згідно з індивідуальним планом підготовки аспіранта. Крім того, бралась участь у роботі науково-дослідницької лабораторії «Оптимізація складних систем» Дніпропетровського національного університету імені Олеся Гончара за держбюджетною темою № 5-128-06 «Математичні моделі та алгоритми розв'язання задач оптимального розбиття множин в умовах невизначеності».

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

Поставлена мета визначає такі завдання дослідження:

- формулювання та доведення необхідних умов оптимальності для неперервних задач ОРМ на підмножини із розміщенням їх центрів при додаткових обмеженнях;

- побудова конструктивних умов розв'язності неперервних задач ОРМ із розміщенням центрів при додаткових обмеженнях;

- розробка та теоретичне обґрунтування методів розв'язання названих задач ОРМ в умовах визначеності та невизначеності;

- створення ефективних алгоритмів розв'язання детермінованих та стохастичних задач ОРМ із розміщенням центрів при додаткових обмеженнях;

- розробка на основі побудованих алгоритмів програмного продукту для розв'язання неперервних лінійних задач ОРМ;

- застосування розроблених методів до розв'язання задач розміщення-розподілу в умовах визначеності та невизначеності.

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

Предметом дослідження є методи та алгоритми розв'язання неперервних лінійних задач ОРМ на підмножини із розміщенням їх центрів при додаткових обмеженнях.

Методи дослідження, що використовуються в роботі: для доведення необхідних умов оптимальності застосовуються методи нескінченновимірної оптимізації та теорію функціонального аналізу; для обґрунтування методів розв'язання задач ОРМ використовуються теорія двоїстості, теорія ОРМ; для розв'язання скінченновимірних задач оптимізації - методи недиференційованої оптимізації.

Наукова новизна одержаних результатів. У дисертаційній роботі:

- побудовано нові математичні моделі неперервних лінійних задач ОРМ із розміщенням центрів при додаткових обмеженнях в умовах визначеності та невизначеності;

- вперше отримано необхідні умови оптимальності для неперервних лінійних задач ОРМ із розміщенням центрів при додаткових обмеженнях в рамках загальної схеми Дубовицького та Мілютіна;

- вперше наведено умови розв'язності для неперервних задач ОРМ із розміщенням центрів при додаткових обмеженнях;

- розроблено та теоретично обґрунтовано нові методи розв'язання неперервних лінійних задач ОРМ із розміщенням центрів при додаткових обмеженнях із застосуванням теорії двоїстості;

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

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

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

Окремі теоретичні результати та розроблений програмний продукт для розв'язання неперервних лінійних задач ОРМ (в умовах визначеності та невизначеності) використовуються у навчальному процесі факультету прикладної математики Дніпропетровського національного університету імені Олеся Гончара при виконанні дипломних та курсових робіт.

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

Апробація результатів дисертації. Включені до дисертації результати досліджень доповідались та обговорювались на: II, III, IV, V та VI міжнародних науково-практичних конференціях «Математичне та програмне забезпечення інтелектуальних систем» (м. Дніпропетровськ, 2004-2008 рр.); міждержавних науково-методичних конференціях «Проблеми математичного моделювання» (м. Дніпродзержинськ, 2008, 2009 р.); семінарі Наукової ради з проблеми «Кібернетика» НАН України при Дніпропетровському національному університеті імені Олеся Гончара «Сучасні питання оптимізації та дискретної математики» (м. Дніпропетровськ, 2009 р.).

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

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

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

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

Виявлено актуальний напрям подальшого розвитку теорії ОРМ - вивчення неперервних лінійних задач ОРМ на підмножини із розташуванням їх центрів при додаткових обмеженнях в умовах невизначеності. Таким чином, обґрунтовано вибір предмету наукового дослідження дисертаційної роботи.

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

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

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

Задача 1. Знайти

множина обмеження алгоритм розподіл

при обмеженнях



, ,

, ,

, , (1)

, ,

де ,

,

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

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

- дійсна, обмежена, вимірна і невід'ємна на функція;

- деяка невідома заздалегідь точка підмножини , , що називається центром цієї підмножини;

- будь-яка точка множини ;

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

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



, , ,

де ,, для всіх , .

Задача 1 переписана в термінах характеристичних функцій підмножин , ,

у наступному вигляді

Задача 2. Знайти

при обмеженнях

,

,

,

, ,

де ,

.

Від задачі 2 нескінченновимірного математичного програмування з булевими змінними здійснено перехід до задачі із значеннями з відрізку [0,1].

Задача 3. Знайти

при обмеженнях

, (2)

, (3)

, (4)

, , (5)

де

.

Доведено, що задачі 2 та 3 при кожному фіксованому мають розв'язки,

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

У підрозділі 2.2 отримано необхідні умови оптимальності для задачі 3 в рамках загальної схеми Дубовицького та Мілютіна у вигляді наступної теореми.

Теорема 2. Нехай - оптимальний розв'язок задачі 3. Тоді знайдуться числа



не всі рівні нулю,

, , , ,

такі, що

для всіх ,

де - -а компонента вектору узагальненого градієнта функції по в точці , , .

Для обґрунтування методу розв'язання в підрозділі 2.3 вводиться функціонал Лагранжа для задачі 3

++. (6)

Тут м.п. для , , змінні , де , , , , ,, визначені на множинах

, ,

, .



Побудована двоїста задача до задачі 3

(7)

за умов

, (8)

де , .

Теорема 3 (Умова Слейтера).

Для того, щоб множина обмежень (2)-(5) задачі 3 задовольняла умові Слейтера, достатньо, щоб виконувалися наступні умови:

., ,

, ,

де , , .

Для опуклих функціоналів та , , доведено теорему двоїстості, яка гарантує не лише виконання співвідношення двоїстості, але і досяжність верхньої грані двоїстого функціоналу на множині .

Теорема 4 (Теорема двоїстості).

Якщо обмеження задачі 3 задовольняють умову Слейтера, то задача 3 і двоїста до неї задача (7)-(8) пов'язані співвідношенням двоїстості



,

причому у випадку верхня грань в двоїстій задачі досягається.

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

Пару елементів будемо називати сідловою точкою функціоналу Лагранжа, якщо

для всіх ,.

Встановлено, що розв'язання пари двоїстих задач (задачі 3 та задачі (7)-(8)) еквівалентно відшуканню сідлової точки функціоналу Лагранжа (6) на множині , для чого здійснено перехід до наступної задачі.

Задача 4. Знайти

, , .

Нехай , , .

Теорема 5. Узагальнений градієнт функції у точці , , може бути обчислений за формулою

.



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

для задачі 4 взятого в точці ,  - оптимальний узагальнений множник Лагранжа.

Теорема 6. Сідлова точка функціоналу (6) на множині , перша компонента якою є оптимальним розв'язком задачі 3, визначається для , і майже всіх таким чином:

де

,

причому у якості вибирається оптимальний розв'язок двоїстої задачі (7)-(8), зведеної до вигляду

, (9)

за умов . (10)

У підрозділі 2.4 на основі теореми 6 розроблено алгоритм розв'язання задачі 3, складовою частиною якого є модифікація -алгоритму Шора.

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

, (11)

де

,

,,, - достатньо великі додатні числа.

Отримано вигляд вектору узагальнених псевдоградієнтів

функції в точці , -ті компоненти якого визначаються за формулами:

,

,



,

де

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

У розділі 3 досліджується багатопродуктова неперервна лінійна задача ОРМ на підмножини з розміщенням їх центрів при додаткових обмеженнях, яка є узагальненням однопродуктової задачі ОРМ з розділу 2.

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

Задача 5. Знайти

при обмеженнях

, ,



, ,

, ,

, ,

де ,

,

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

, , - дійсні, обмежені, вимірні і невід'ємні на функції;

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

- будь-яка точка множини ;

- задані дійсні невід'ємні числа.

Задачу 5 переписано в термінах характеристичних функцій підмножин ,,



(12)

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

.

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

У підрозділі 3.3 наведено обґрунтування методу розв'язання багатопродуктової задачі 5, який базується на зведенні вихідної нескінченновимірної задачі оптимізації через функціонал Лагранжа, із застосуванням теорії двоїстості Гольштейна, до задачі пошуку сідлової точки функціоналу.

Теорема 7. Оптимальний розв'язок задачі 5 може бути знайдено, як першу компонента сідлової точки функціоналу Лагранжа на множині , яка визначається для , , і майже всіх за формулою:

у якості вибирається оптимальний розв'язок двоїстої задачі до задачі 5, зведеної до вигляду

за умов (14)

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

Розділ 4 присвячено дослідженню неперервних задач ОРМ з розміщенням центрів при додаткових обмеженнях в умовах невизначеності, які є стохастичними аналогами багатопродуктової задачі ОРМ з розділу 3.

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

Задача 6. Знайти

при обмеженнях

() - випадкові величини на імовірнісному просторі із заданими суб'єктивними математичними очікуваннями і дисперсіями ;

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

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

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

Задача 7 (Детермінований еквівалент).

Наведено обґрунтування методу розв'язання задачі 7, в основі якого лежить зведення отриманої нескінченновимірної задачі оптимізації, через функціонал Лагранжа, до двоїстої скінченновимірної задачі з негладкою цільовою функцією

Для розв'язання задачі (15)-(16), яка зводиться до задачі безумовної оптимізації способом аналогічним описаному в підрозділі 2.4, застосовано евристичний алгоритм узагальнених псевдоградієнтів з розтягуванням простору, близький до -алгоритму Шора.

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

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

де - залишковий член многочлена Тейлора для цільового функціоналу.

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

У підрозділі 4.2 встановлено, що в М-моделі багатопродуктової стохастичної задачі ОРМ на підмножини з розміщенням їх центрів при додаткових обмеженнях, не враховується розкид значень функціоналу і обмежень відносно середнього, тому сформульована так звана MD-модель стохастичної багатопродуктової задачі ОРМ при додаткових обмеженнях в наступній постановці.

Задача 8. Знайти

Тут коефіцієнт - міра неприйняття ризику, наприклад, абсолютна міра

Ерроу-Пратта

,

де - функція корисності.

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

У додатку А наводиться опис створеного програмного продукту призначеного для розв'язання широкого класу неперервних лінійних задача ОРМ як в умовах визначеності, так і в умовах невизначеності. Названий програмний продукт реалізовано на мові “C++” у середовищі “Borland Builder C++ 6” на основі алгоритмів, розроблених та описаних в дисертаційній роботі.

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



ВИСНОВКИ

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

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

Для задач ОРМ в умовах повної визначеності:

- сформульовано нові математичні постановки неперервних лінійних задач ОРМ із розміщенням центрів при додаткових обмеженнях;

- вперше отримано необхідні умови оптимальності для неперервних лінійних задач ОРМ із розміщенням центрів при додаткових обмеженнях в рамках загальної схеми Дубовицького та Мілютіна;

- побудовано та програмно реалізовано конструктивні умови розв'язності для неперервних задач ОРМ із розміщенням центрів при додаткових обмеженнях;

- вперше розроблено та теоретично обґрунтовано методи розв'язання неперервних лінійних задач ОРМ із розміщенням центрів при додаткових обмеженнях (що є задачами нескінченновимірного математичного програмування з булевими змінними) із застосуванням теорії двоїстості Гольштейна. В основі цих методів лежить зведення нескінченновимірних вихідних задач до скінченновимірних негладких задач;

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

Для задач ОРМ в умовах невизначеності:

- побудовано нові моделі неперервних лінійних задач ОРМ із розміщенням центрів при додаткових обмеженнях, в яких частина вихідної інформації має імовірнісний характер, або нечітко визначена;

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

- вперше отримано оцінки похибки апроксимації детермінованим еквівалентом стохастичної задачі ОРМ із розміщенням центрів при додаткових обмеженнях;

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

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



ОСНОВНІ РОБОТИ, ЩО ОПУБЛІКОВАНІ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Киселёва Е.М. Решение непрерывных задач оптимального покрытия множеств в пространстве с метрикой Чебышева / Е.М. Киселёва, Л.И. Лозовская, Я.Е. Кадочникова // Питання прикладної математики i математичного моделювання: збірник наукових праць. - Д.: ДНУ, 2006. - С. 109-121.

2. Кісельова О.М. Розв'язання задач оптимального розбиття множин з обмеженнями на пропускні можливості комунікацій в умовах невизначеності / О.М. Кісельова, Л.І. Лозовська, Я.Є. Кадочнікова // Питання прикладної математики i математичного моделювання: збірник наукових праць. - Д.: ДНУ, 2007. - С. 123-139.

3. Киселёва Е.М. Обоснование метода решения многопродуктовой задачи оптимального разбиения множеств при дополнительных ограничениях / Е.М. Кисе-лёва, Я.Е. Кадочникова // Питання прикладної математики i математичного моделювання: збірник наукових праць. - Д.: ДНУ, 2008. - С. 92-107.

4. Киселёва Е.М. Решение непрерывной однопродуктовой задачи оптимального разбиения с дополнительными ограничениями / Е.М. Киселёва, Я.Е. Ка-дочникова // Проблемы управления и информатики. - 2009. - №4. - С. 47-61.

5. Киселёва Е.М. Применение R-алгоритма Н.З. Шора к решению задач беско-нечномерной оптимизации / Е.М. Киселёва, Я.Е. Кадочникова // Математичне та програмне забезпечення інтелектуальних систем: Тези доповідей II Міжнародної науково-практичної конференції, листопад 17-19, 2004 р. - Д.: ДНУ, 2004. - С. 61.

6. Киселёва Е.М. Условия разрешимости непрерывной задачи оптимального разбиения с дополнительными ограничениями / Е.М. Киселёва, Я.Е. Кадочникова // Математичне та програмне забезпечення інтелектуальних систем: Тези доповідей ІII Міжнародної науково-практичної конференції, листопад 16-18, 2005 р. - Д: ДНУ, 2005. - С. 73.

7. Киселёва Е.М. О решении задачи оптимального разбиения множеств с размещением центров тяжести подмножеств при дополнительных ограничениях / Е.М. Киселёва, Я.Е. Кадочникова // Математичне та програмне забезпечення інтелектуальних систем: Тези доповідей ІV Міжнародної науково-практичної конференції, листопад 15-17, 2006 р. - Д.: ДНУ, 2006. - С. 63.

8. Киселёва Е.М. О решении одной многопродуктовой задачи оптимального разбиения с ограничениями на пропускные способности коммуникаций / Е.М. Кисе-лёва, Я.Е. Кадочникова // Математичне та програмне забезпечення інтелектуальних систем: Тези доповідей V Міжнародної науково-практичної конференції, листопад 14-16, 2007 р. - Д.: ДНУ, 2007. - С. 77-78.

9. Кадочникова Я.Е. Непрерывная задача оптимального нечёткого разбиения множеств с размещением центров при дополнительных ограничениях / Я.Е. Кадочникова // Проблеми математичного моделювання: Тези доповідей міждержавної науково-методичної конференції, 28-30 травня 2008 р. - Д.: ДДТУ, 2008. - С. 20-22.

10. Киселёва Е.М. Математическая модель стохастической задачи оптимального разбиения множеств с размещением центров / Е.М. Киселёва, Я.Е. Кадочникова // Математичне та програмне забезпечення інтелектуальних систем: Тези доповідей VІ Міжнародної науково-практичної конференції, листопад 12-14, 2008 р.- Д.: ДНУ, 2008. - С. 161-162.

11. Кадочникова Я.Е. О применении основной теоремы антагонистических игр для решения задачи оптимального разбиения / Я.Е. Кадочникова // Проблеми математичного моделювання: Тези доповідей міждержавної науково-методичної конференції, 27-29 травня, 2009 р.- Д.: ДДТУ, 2009. - С. 16-18.



АНОТАЦІЯ

Кадочнікова Я.Є. Методи та алгоритми розв'язання неперервних задач оптимального розбиття множин з обмеженнями. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. - Дніпропетровський національний університет імені Олеся Гончара, Дніпропетровськ, 2009.

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

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

Створено і програмно реалізовано алгоритми розв'язання лінійних задач оптимального розбиття множин в умовах визначеності та невизначеності. Програмний продукт застосовано до розв'язання задач розміщення-розподілу.

Ключові слова: оптимальне розбиття множин, нескінченновимірне

математичне програмування, недиференційована оптимізація, задача розміщення-розподілу, умови невизначеності.



АННОТАЦИЯ

Кадочникова Я.Е. Методы и алгоритмы решения непрерывных задач оптимального разбиения множеств с ограничениями. - Рукопись.

Диссертация на соискание учёной степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Днепропетровский национальный университет имени Олеся Гончара, Днепропетровск, 2009.

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

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

Разработаны методы решения непрерывных линейных задач ОРМ, основывающиеся на сведении бесконечномерных задач оптимизации через функционал Лагранжа, с применением теории двойственности Гольштейна, к двойственным конечномерным задачам с негладкой целевой функцией, для решения которых применяются модификации -алгоритма Шора. На основании методов построены алгоритмы решения задач ОРМ при дополнительных ограничениях.

Проведено обобщение рассмотренных задач на случай неполной информации об исходных данных: построены математические модели, являющиеся стохастическими аналогами задач ОРМ. Для их решения применён непрямой метод стохастического программирования, при котором исходная задача заменяется детерминированным эквивалентом. Разработаны методы и алгоритмы решения построенных задач, для применения которых достаточно знать субъективные математические ожидания и дисперсии конечного числа случайных параметров задачи. Получены оценки погрешности аппроксимации исходной задачи её детерминированным эквивалентом.

Все построенные алгоритмы реализованы в виде программного продукта, позволяющего получать решения широкого класса непрерывных линейных задач ОРМ в условиях определённости и неопределённости.

С использованием разработанного программного продукта решены приближённые к реальным условиям задачи размещения точек интернет-магазинов и распределения зон влияния между ними.

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



ANNOTATION

Kadochnikova I. E. Methods and algorithms of solving some continuous problems of optimal set partitioning with conditions. - Manuscript.

The dissertation for a candidate degree in Physics and Mathematics, speciality - 01.05.01 - theoretical bases of informatics and cybernetics. - Dniepropetrovsk National University, Dniepropetrovsk, 2009.

The thesis is devoted to the solution of linear continuous optimal partitioning problem in terms of certainty and uncertainty.

Mathematical models of deterministic and stochastic linear continuous optimal partitioning of set into subsets with centers location using additional conditions, such as communication capacity conditions. Developed and theoretically justified methods for solving tasks, which are based on reduction of infinite optimization problem to dual finite nonsmooth problem, for solution of which differentiable optimization method is applied.

Algorithms for solving optimal partitioning problem in terms of certainty and uncertainty were created and implemented as computer software. The software is used to solve location-allocation problems.

Key words: optimal partitioning problem, infinite math programming, non-differentiable optimization, location-allocation problem, uncertainty conditions.

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

...