Параметричні задачі та стійкість при моделюванні евклідовими комбінаторними задачами оптимізації

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

Дніпропетровський державний університет

Автореферат

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

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

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

Параметричні задачі та стійкість при моделюванні евклідовими комбінаторними задачами оптимізації

Роскладка Андрій Анатолійович

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

2000

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

Робота виконана в Полтавському державному технічному університеті

імені Юрія Кондратюка Міністерства освіти і науки України

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

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

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

Провідна установа: Інститут кбернетики ім. В. М. Глушкова НАН України, відділ методів розв'язування складних задач оптимізації, м. Київ.

Захист відбудеться 20 вересня 2000 р. о 14 годин 30 хвилин на засіданні спеціалізованої вченої ради К 08.051.09 при Дніпропетровському державному університеті за адресою: 49044, м. Дніпропетровськ, проспект Карла Маркса, 35, корп. 3, ауд. 42.

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

Автореферат розісланий 18 липня 2000 р.

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

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

Актуальність теми. В останній час значно розширилася область застосування методів дискретного програмування. Цьому сприяв той факт, що багато важливих задач проектування, планування, розміщення і управління добре описуються за допомогою моделей дискретного програмування. З'явилася велика кількість публікацій, в яких пропонуються нові підходи до розв'язку задач дискретної оптимізації взагалі і комбінаторної оптимізації зокрема, досліджується ефективність відомих методів, описуються створені програмні засоби, які призначені для реалізації системного підходу до розв'язку цих оптимізаційних задач на ЕОМ. Зусилля багатьох вчених та наукових колективів спрямовані на розробку цієї проблематики. Серед вітчизняних в першу чергу треба відзначити колективи, які працюють під керівництвом академіків НАН України І.В. Сергієнка, Н.З. Шора, член.-кор. НАН України Ю.Г. Стояна.

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

В останні десятиріччя суттєвий прогрес в теорії оптимізації привів до виділення з широкого класу задач дискретного програмування задач на комбінаторних множинах, а евклідова комбінаторна оптимізація розглядається як важливий аспект комбінаторної оптимізації. Роботи в цьому напрямку проводяться в наукових колективах, якими керують Ю.Г. Стоян, С.В. Яковлєв, О.О. Ємець. Параметричні задачі евклідової комбінаторної оптимізації є невивченими і тому їх дослідження є актуальною задачею.

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

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

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

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

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

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

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

Наукова новизна одержаних результатів:

- посилені оцінки екстремальних значень сильно опуклих функцій при оптимізації на сполученнях;

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

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

- розроблено модифікований алгоритм пошуку аналітичного вигляду загального многогранника сполучень;

- отримано новий критерій i-грані довільного многогранника.

Практичне значення одержаних результатів полягає:

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

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

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

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

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

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

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

[5] - розгляд математичної моделі вибору оптимальної підмножини задач на ЕОМ як задачі евклідової комбінаторної оптимізації на сполученнях;

[6] - обгрунтування алгоритму розв'язування загальної параметричної задачі при оптимізації на сполученнях;

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

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

- VII міжнародній науковій конференції імені академіка М. Кравчука (Київ, 1998);

- Міжнародній науковій конференції "Розробка та застосування математичних методів у науково-технічних дослідженнях" (Львів, 1998);

- Міжнародній школі з актуарної та фінансової математики (Київ, 1999);

- 49-52 наукових конференціях професорів, викладачів, наукових співробітників, аспірантів і студентів Полтавського державного технічного університету імені Юрія Кондратюка (Полтава, 1997-2000);

- науковому семінарі відділу математичного моделювання та геометричного проектування Інституту проблем машинобудування НАН України (Харків, 1998);

- науковому семінарі кафедри обчислювальної математики та математичної кібернетики Дніпропетровського державного університету (Дніпропетровськ, 1999).

Публікації. Результати дисертаційної роботи опубліковані у 3 статтях у фахових наукових журналах [1-3], 3 статтях у фахових збірниках наукових праць [4-6], матеріалах конференції [7].

Структура та обсяг дисертації. Дисертація складається зі вступу, п'яти розділів, висновків, списку використаних джерел з 129 найменувань, 2 додатків. Усього 142 сторінки.

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

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

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

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

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

Задача з параметром у цільовій функції. Постановка задачі: знайти пару таку, що при умовах як відомо, розв'язком лінійної задачі без додаткових обмежень на множині сполучень з повтореннями (тобто задачі (3) з t=0 при умові (4)) є точка :

- відповідно найменший та найбільший елементи основи мультимножини , а визначається системою:

Теорема 6. Загальна максимальна кiлькiсть операцiй за алгоритмом A₂ для знаходження розвязків задачi (9) - (11) становить величину порядку .

Ця теорема свідчить про ефективність алгоритму.

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

Задача (14) - (16) має розв'язок (13) при умові ,

де і не має розв'язків при

Схема алгоритму A₃ пошуку розв'язку задачі (14) - (16) така:

Крок 1. Для кожного значення скласти систему (8).

Крок 2. Знайти розв'язки цих систем у вигляді проміжків .

Крок 3. Для кожного переставлення елементів скласти систему (12).

Крок 4. Знайти розв'язки цих систем у вигляді проміжків .

Крок 5. Знайти інтервали .

Крок 6. Знайти переріз інтервалу з відповідними проміжками , що і визначатиме розв'язок (13) задачі (14) - (16).

Теорема 7. Максимальна кількість операцій, яку необхідно здійснити для отримання розв'язку загальної параметричної задачі (14) - (16) за умови лінійної залежності від цільової функції за алгоритмом A₃ не перевищує величину порядку .

Це свідчить про ефективність запропонованого алгоритму.

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

Задача з параметром у цільовій функції - це задача (3) при умові (5) та

як відомо, розв'язком непараметричної лінійної задачі без додаткових обмежень на загальній множині розміщень і точка :

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

Обгрунтовано алгоритм В₁ розв'язування задачі (3),(5),(17), що має таку схему:

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

Крок 2. Знайти розв'язок кожної системи (19) відносно t у вигляді проміжка , , або показати відсутність розвязків цієї системи при даному .

Крок 3. Знайти обєднання знайдених проміжків для фіксованого значення : .

Крок 4. Знайти перетин інтервалу з проміжками , які і будуть визначати розв'язок задачі (3), (5), (17) у представленні (18).

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

Загальна максимальна кiлькiсть операцiй для знаходження розвязків задачi (3), (5), (17) за алгоритмом В₁ є величиною порядка .

Наведений аналіз алгоритмів дає змогу реально оцінити можливості ЕОМ щодо розвязування задач цього типу розглянутим алгоритмом.

Задача з параметром у системі обмежень - це задача (9) при умовах (11) та

Позначимо, Оскільки для знаходження оптимального розв'язку (18) нам необхідно знати точне розташування тільки перших і останніх елементів , то елементи повинні задовольняти наступну систему нерівностей:

Точка з розв'язку цієї задачі задається так:

Обгрунтовано алгоритм В₂ розвязування задачі (9), (11), (20), що має таку схему:

Крок 1. За коефіцієнтами визначити сталі і і записати структуру оптимального розвязку.

Крок 2. Для кожного розміщення з k елементів мультимножини скласти систему (21).

Крок 3. Знайти розв'язок системи (21) у вигляді проміжку .

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

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

Загальна параметрична задача - це задача знаходження (3) при умовах (5) та (20).

Величини і не є фіксованими. Отже, необхідно так упорядковувати елементи , щоб задовольнити будь-яку структуру оптимального розвязку (22). Цього можна досягти шляхом упорядкування перших і останніх елементів мультимножини . Таким чином, ці елементи повинні задовільняти наступну систему нерiвностей: (23)

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

Множина розв'язків , системи (19) розбиває числову вісь на інтервали, кількість яких дорівнює . Множина розв'язків , системи (21) розбиває числову вісь на інтервали, кількість яких дорівнює . Серед цих інтервалів можуть бути порожні.

Задача (3), (5), (20) буде мати розв'язок (22) при умові , де , .

Схема алгоритму В₃ пошуку розв'язку задачі (3), (5), (20) така:

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

Крок 2. Знайти розв'язок кожної системи (19) відносно у вигляді проміжка , або показати відсутність розвязків цієї системи при даному .

Крок 3. Знайти обєднання знайдених проміжків для фіксованого значення : .

Крок 4. Для кожного розміщення елементів скласти систему (23).

Крок 5. Знайти розв'язок системи (23) у вигляді проміжку , .

Крок 6. Знайти інтервали .

Крок 7. Знайти переріз інтервалу з відповідними проміжками , що і визначатиме розв'язок (22) задачі (3), (5), (20).

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

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

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

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

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

1. Із множини виділяється множина регулярних точок .

2. Із множини, що належать виокремлюється множина точок, які не лежать в симплексі.

3. До множини застосовується модифікований алгоритм побудови опуклої оболонки.

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

	N	k				Максимальна к-ть нер-тей при побудові	Кількість гіперграней	Час
4	4	2	6	6	1	4	4	1 сек
5	4	2	7	6	1	4	4	1 сек
5	4	3	10	9	2	6	5	1 сек
8	6	4	36	20	9	8	7	2 сек
8	6	5	30	20	6	16	16	3 сек
8	6	6	17	14	4	15	12	2 сек
10	8	4	113	53	12	11	9	2 сек
10	8	6	113	65	19	19	13	4 сек
10	8	8	30	26	6	27	15	10 сек
12	12	10	66	58	9	29	23	12 сек
15	15	12	455	333	58	80	78	20 cек
15	15	13	105	94	12	52	32	14 cек
20	16	16	2153	1426	313	164	114	14 хв
20	16	17	606	487	86	261	157	1 хв
20	18	18	139	128	15	129	115	24 сек
22	22	20	231	213	19	97	62	29 сек
25	14	22	714	592	100	214	202	17 сек
25	15	22	470	367	72	287	119	7 хв
25	18	22	869	722	115	201	189	16 хв
25	22	22	1603	1304	178	521	362	24 хв
25	25	22	2300	1858	234	426	394	38 хв
25	22	23	234	218	20	231	207	18 сек

У підрозділі 4. 2 сформульовано і доведено критерій і-грані довільного многогранника на основі системи індексів, що визначена в розділі 4.1.

Теорема 8. Точка належить j-грані , якщо серед індексів нерівностей, що описують даний многогранник знайдеться рівно (k-j) таких, що не містять числа i.

Наслідок. Точка є вершиною многогранника, якщо система, що його описує містить рівно k нерівностей, індекси яких не містять числа q.

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

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

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

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

Ємець О.О., Роскладка А.А. Про оцінки мінімумів цільових функцій при оптимізації на сполученнях // Український математичний журнал. - 1999. - Т. 51. - №8. - С. 1118 - 1121.

Емец О.А., Роскладка А.А. Алгоритмическое решение двух параметрических задач оптимизации на множестве сочетаний с повторениями // Кибернетика и системный анализ. - 1999. - №6. - С. 160 - 165.

Ємець О.О., Роскладка А.А. Побудова опуклої оболонки загальної множини сполучень // Радиоэлектроника и информатика. - 1998. - №4. - С. 95 - 96.

Ємець О.О., Роскладка А.А. До оптимізації оцінок екстремальних значень сильно опуклих функцій при оптимізації на сполученнях // Вісник державного університету "Львівська політехніка".- 1998. -№ 337. - С. 320 - 322.

Емец О.А., Роскладка А.А. Модель выбора подмножества задач для ЭВМ с минимизацией количества периферийных устройств как задача комбинаторной оптимизации // Проблемы бионики. - 1999. - № 51. - С. 158 - 161.

Ємець О.О., Роскладка А.А. Параметрична комбінаторна оптимізація на сполученнях // Вісник державного університету "Львівська політехніка". - 1999. - № 364. - С. 32 - 34.

Емец О.А., Роскладка А.А., Роскладка Е.В. Применение евклидовых поликомбинаторных множеств к построению моделей оптимизационных задач // Abstracts of second international school on actuarial and financial mathematics (June 8 - 12, 1999, Kyiv, Ukraine). - C. 20.

АНОТАЦІЯ

Роскладка А.А. Параметричні задачі та стійкість при моделюванні евклідовими комбінаторними задачами оптимізації. - Рукопис.

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

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

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

ANNOTATION

Roskladka А.А. The parametrical tasks and stability at modelling by the Euclidean combinatorial tasks of optimization. - Manuscript.

Thesis for a candidate's degree by speciality 01.05.01 - theoretical bases of informatics and cybernetics. - Dnepropetrovsk State University, Dnepropetrovsk, 2000.

In dissertation a research of the parametrical tasks of Euclidean combinatorial optimization on the combinations and arrangements is explained. For set of combinations with repetitions the amplified estimates of minimum of strongly convex differentiated objectives functions are received. For Euclidean combinatorial sets of combinations with repetitions and arrangements the algorithms of problem solving with a parameter in the linear objectives functions, in systems of restrictions, and also algorithms of a solution of the general parametrical tasks on these sets are created. For all algorithms the complexity of calculations is investigated. For general set of combinations the modified algorithm of a construction a convex environment is developed. New criterion of i-edges of any polyhedron is established. The parametrical optimization mathematical models tasks on combinations are constructed.

Key words: parameter optimization, combinatorial optimization, estimation of complexity, combinatorial set, combination, arrangement, convex environment.

АННОТАЦИЯ

Роскладка А. А. Параметрические задачи и устойчивость при моделировании евклидовыми комбинаторными задачами оптимизации. - Рукопись.

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

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

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

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

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

Анализ системы индексов неравенств при использовании модифицированного алгоритма построения выпуклой оболочки позволил установить новый критерий i-граней произвольного многогранника.

На основе свойств общего множества сочетаний разработаны и построены математические модели и методы решения параметрических задачи о стоимости периферийных устройств и задачи объединения электростанций в энергосистему.

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

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