ІНСТИТУТ КІБЕРНЕТИКИ ІМ. В.М. ГЛУШКОВА

БАРБОЛІНА ТЕТЯНА МИКОЛАЇВНА

УДК 519.85

МЕТОДИ Й АЛГОРИТМИ РОЗВ’ЯЗУВАННЯ ОПТИМІЗАЦІЙНИХ ЗАДАЧ НА РОЗМІЩЕННЯХ З ДОДАТКОВИМИ УМОВАМИ

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

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

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

Київ – 2005

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

Робота виконана в Полтавському державному педагогічному університеті ім. В.Г. Короленка Міністерства освіти і науки України

Науковий керівник: доктор фізико-математичних наук, професор

ЄМЕЦЬ Олег Олексійович, Полтавський університет споживчої кооперації України, завідувач кафедри математичного моделювання та соціальної інформатики

Офіційні опоненти: доктор фізико-математичних наук

ДОНЕЦЬ Георгій Панасович, Інститут кібернетики ім. В.М. Глушкова НАН України, завідувач відділом економічної кібернетики

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

БУРДЮК Володимир Якович, Дніпропетровський національний університет, доцент кафедри обчислювальної математики та математичної кібернетики

Провідна установа: Київський національний університет імені Тараса Шевченка, факультет кібернетики, кафедра теоретичної кібернетики, м. Київ

Захист відбудеться “28” жовтня 2005 р. о 12 годині на засіданні спеціалізованої вченої ради Д 26.194.02 в Інституті кібернетики ім. В.М. Глушкова НАН України за адресою: пр-т Академіка Глушкова, 40, МКЗ

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

Автореферат розісланий “_25_” вересня 2005 р.

Учений секретар

спеціалізованої вченої ради В.Ф.Синявський

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

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

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

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

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

Дана мета конкретизується в таких задачах:

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

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

3. Розробка та обґрунтування алгоритмів розв’язування задач опуклої оптимізації на розміщеннях.

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

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

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

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

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

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

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

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

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

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

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

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

[1, 6, 15]: розробка методу та обґрунтування алгоритму розв’язування задач оптимізації на розміщеннях з лінійною цільовою функцією та опуклими додатковими обмеженнями, а також моделювання економічної задачі оптимізаційною задачею вказаного вигляду;

[2, 8, 11]: встановлення коефіцієнтів правильного відсікання для розв’язування лінійних умовних задач оптимізації на розміщеннях, доведення скінченності запропонованого алгоритму;

[3, 7, 9, 10]: побудова розбиття многогранної множини за допомогою відношення лексикографічної еквівалентності, розробка та обґрунтування алгоритмів перебору одержаних класів еквівалентності та їх застосування до розв’язування лінійних задач лексикографічної комбінаторної оптимізації на розміщеннях;

[4, 5, 14]: визначення коефіцієнтів правильних відсікань для цілочислового методу розв’язування лінійних умовних задач оптимізації на розміщеннях, встановлення умов скінченності алгоритму вказаного методу, а також побудова моделі однієї задачі оптимізації інвестиційних портфелів як лінійної умовної задачі оптимізації на розміщеннях з цілими коефіцієнтами;

[13]: викладення алгоритмів методів комбінаторного відсікання та методу побудови лексикографічної еквівалентності для розв’язування різних класів оптимізаційних задач на розміщеннях.

Апробація результатів дисертації. Основні результати роботи доповідалися, обговорювалися та отримали схвалення на міжнародних та національних наукових конференціях та школах, а саме: 53 – 55-ій наукових конференціях професорів, викладачів, наукових працівників та студентів Полтавського національного технічного університету імені Юрія Кондратюка (м. Полтава, 2001 – 2003 р.р.); звітних наукових конференціях викладачів, аспірантів, магістрантів та студентів фізико-математичного факультету Полтавського державного педагогічного університету ім. В.Г. Короленка (м. Полтава, 2003 – 2005 р.р.); Міжнародній науково-практичній конференції “М.В.Остроградський — видатний математик, механік, педагог” до 200-річчя з дня народження (м. Полтава, 2001 р.); Всеукраїнській науково-практичній конференції “Економічні проблеми розвитку регіонів та підприємств на початку ХХІ століття” (м. Полтава, 2001 р.); IV Міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених “Системний аналіз та інформаційні технології” (м. Київ, 2002 р.); VIII Міжнародному семінарі “Дискретная математика и ее приложения” (м. Москва, 2004 р.); VII науково-практичній конференції “Наука і освіта ’2004” (м. Дніпропетровськ, 2004 р.); Х конференції імені академіка Кравчука (м. Київ, 2004 р.); ІІ Міжнародній школі-семінарі “Теорія прийняття рішень” (м. Ужгород, 2004 р.); XIV Міжнародній конференції “Проблемы теоретической кибернетики”, присвяченій 80-річчю з дня народження С.В. Яблонського (м. Пенза, 2005 р.); науковому семінарі відділу математичного моделювання та геометричного проектування Інституту проблем машинобудування НАН України (м. Харків, 2002, 2003 р.р., керівник — доктор технічних наук, член-кореспондент НАН України Ю.Г.Стоян); науковому семінарі кафедри моделювання складних систем Київського національного університету імені Т. Шевченка (м. Київ, 2003 р., керівник — доктор технічних наук Ф.Г. Гаращенко); науковому семінарі кафедри системного аналізу і теорії оптимальних рішень Київського національного університету імені Т. Шевченка (м. Київ, 2004 р., керівник — доктор фізико-математичних наук О.Г. Наконечний); науковому семінарі в Інституті кібернетики НАН України (м. Київ, 2005 р., керівник — доктор фізико-математичних наук Г.П.Донець); науковому семінарі кафедри теоретичної кібернетики Київського національного університету імені Т. Шевченка (м. Київ, 2005 р., керівник — доктор фізико-математичних наук Ю.А. Бєлов).

Публікації. Основні результати дисертації опубліковано у 16 наукових працях, серед яких 4 статті в наукових журналах, 3 в збірниках наукових праць, 2 депоновані роботи, 7 — в збірниках матеріалів та тез доповідей міжнародних та національних наукових конференцій.

Структура та обсяг дисертації. Дисертація складається із вступу, п’яти розділів, висновків, списку використаних джерел (155 найменувань на 16 сторінках), 2 додатків (18 сторінок), 11 табл. на 12 сторінках, 8 рис. на 7 сторінках Повний обсяг дисертації 175 сторінок, основний зміст викладено на 141 сторінці.

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

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

Множину перших натуральних чисел позначатимемо , тобто .

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

Упорядкованою _вибіркою з мультимножини називається набір

(1)

де , .

Дві упорядковані _вибірки та вигляду (1)вважаються різними, якщо існує такий індекс (), що . Множина , різними елементами якої є різні впорядковані _вибірки вигляду (1) з мультимножини , називається евклідовою комбінаторною множиною (_множиною). Однією із евклідових комбінаторних множин є загальна множина _розміщень , під якою розуміють множину всіх упорядкованих _вибірок вигляду (1) з мультимножини .

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

. (2)

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

, (3)

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

, , (4)

де , , — натуральна константа (), , — функції змінних.

Обмеження (4) називають додатковими обмеженнями _задачі, а — комбінаторним обмеженням. Якщо , то задача (3), (4) називається повністю комбінаторною _задачею, при — частково комбінаторною. Змінні називаються неперервними, — комбінаторними. Якщо , тобто додаткових обмежень немає, то _задача (3), (4) називається евклідовою безумовною задачею комбінаторної оптимізації, інакше — умовною _задачею.

У підрозділах 1.3, 1.4, 1.5 здійснено огляд найбільш поширених методів дискретної оптимізації, окремих методів опуклої оптимізації та методів розв’язування евклідових задач комбінаторної оптимізації відповідно. Методи дискретної оптимізації поділяють на дві групи: комбінаторні методи, в основі яких лежить перебір скінченого числа допустимих розв’язків, та методи відсікання, які ґрунтуються на відсіканні частини околу розв’язку допоміжної задачі, який не містить допустимих точок. Методи, що засновані на такому підході, використовуються також і в опуклому програмуванні, як приклад можна навести метод відсікаючих площин Келлі. В евклідовій комбінаторній оптимізації розповсюдження набули як комбінаторні методи, так і методи відсікання. Останні розроблені тільки для випадків вершинно розташованих множин.

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

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

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

, (5)

або

, (6)

за умов

, (7)

, , (8)

, (9)

, (10)

де , , , — натуральні, а , — цілі невід’ємні константи (, ), ; — опуклі функції змінних, — лінійна функція змінних.

Залежно від накладених додаткових обмежень та умов (5) або (6), розглядаються різні задачі, зокрема:_

задача, яка полягає у знаходженні (5) за умов (7), (9), (10);_

задача знаходження (5) за умов (7), (9), (10) та такої

; (11)_

задача — частинний випадок _задачі, коли елементи мультимножини є натуральними числами, коефіцієнти цільової функції та обмежень (9) — цілими, а на неперервні змінні накладено умову цілочисельності;_

задача (5), (7) – (11);_

задача знаходження пари (6) за умов (7), (9), (10);_

задача (6), (7), (9) – (11).

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

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

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

Означення 1. Під правильним відсіканням у задачах евклідової комбінаторної оптимізації розуміємо лінійну нерівність, яку задовольняють усі точки допустимої комбінаторної множини (умова правильності) і не задовольняє одержаний розв’язок релаксованої задачі, який не є допустимим (умова відсікання).

Правильні відсікання будуються у вигляді

, (12)

де — множина номерів небазисних змінних, яка відповідає недопустимому для вихідної _задачі розв’язку релаксованої задачі. Під релаксованою задачею розуміємо допоміжну задачу, у якій деякі обмеження (комбінаторні, нелінійні) відкидаються або послаблюються (наприклад, умова належності точки комбінаторній множині замінюється умовою належності її опуклій оболонці).

У підрозділі 3.2 обґрунтовуються алгоритми методу комбінаторного відсікання для розв’язування лінійних умовних задач оптимізації на розміщеннях. Побудова комбінаторного відсікання при розв’язуванні _задачі (5), (7), (9) – (11) ґрунтується на використанні як релаксованих задач дискретного програмування такого вигляду: знайти пару, що задовольняє (5) за умов (2), (9) – (11) та такої:

. (13)

Елементи послідовності релаксованих задач вигляду (2), (5), (9) – (11), (13) називатимемо _задачами, де відповідає номеру ітерації в послідовному наближенні до розв’язку вихідної _задачі. _задача є задачею дискретної оптимізації і її розв’язок може бути одержано за допомогою алгоритму Дальтона-Ллевеліна. Якщо розв’язок _задачі не задовольняє умову (7), то для деякої множини

, (14)

де , виконується умова

. (15)

Для всіх , обчислимо величини

(16)

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

. (17)

Сформуємо для всіх кортежі () з чисел , упорядкованих за незростанням:

, , (18)

де — символ мультимножини.

Покладемо ,

, , , (19)

Теорема 1. Нехай — точка, яка дає розв’язок _задачі, але не задовольняє умову (7). Нехай також , таке, що для множини , сформованої згідно з (14), виконується співвідношення (15). Тоді нерівність (12), у якій коефіцієнти обчислені за формулами (16) – (19), є правильним відсіканням.

У випадку розв’язування _задачі як релаксовані можна розглядати повністю цілочислові задачі лінійного програмування, що дозволяє використовувати для їх розв’язування вільний від похибок округлення третій алгоритм Гоморі. Елементи послідовності релаксованих задач називаємо _задачами; _задача полягає у знаходженні пари

(20)

за умов

, (21)

, , (22)

, , (23)

(24)

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

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

Правильні цілочислові відсікання можуть бути записані у формі

, , , (25)

де —найбільший номер змінної у симплекс-таблиці, що відповідає розв’язку _задачі, — номер ітерації, — деяка додатна величина, яка вибирається таким чином, щоб виконувалася умова збереження цілочисельності симплекс-таблиці, — коефіцієнти нерівності вигляду (12), яка є правильним (не обов’язково цілочисловим) відсіканням.

Для обчислення коефіцієнтів сформуємо для всіх множини індексів координат екстремалі _задачі за таким правилом:

(26)

де , (, ).

Якщо

, (27)

то . У цьому випадку для всіх , обчислимо величини (16), де — елементи симплекс-таблиці, з якої одержано розв’язок _задачі,

. (28)

Коефіцієнти обчислимо за формулами

, (29)

де , ()– елементи кортежів вигляду (18) (покладаємо ), які сформовані з упорядкованих за незростанням чисел (), обчислених згідно з (16), (28), та

. (30)

Теорема 2. Нехай — точка, яка дає розв’язок _задачі, але не задовольняє умову (7). Нехай також таке, що для множини , сформованої згідно з (26), виконується умова (27). Тоді нерівність (12), у якій коефіцієнти обчислені за формулами (16), (18), (28) – (30), є правильним відсіканням.

Якщо для жодної з множин (26) не виконується умова (27), але точка не задовольняє умову (7), то знайдеться координата цієї точки, яка не задовольняє (13), і правильне відсікання може бути побудовано згідно з алгоритмом Дальтона-Ллевеліна.

У підрозділі також запропоновано алгоритми методу комбінаторного відсікання для розв’язування _і _задачі, доведено їх скінченність за умови обмеженості допустимої множини задач (2), (5), (9), (10) та (20) – (23) відповідно.

У підрозділі 3.3 розглянуто розв’язування _задач методом комбінаторного відсікання. Релаксованими задачами є задачі лінійного програмування (елемент послідовності називаємо _задачею; _задачею є задача (2), (5), (9), (10)). Для екстремалі релаксованої задачі можливі 4 випадки

1) , ; тоді _задачу розв’язано;

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

. (31)

Для цього до системи обмежень _задачі додається нерівність (12), де

, . (32)

3) , , ; тоді правильне відсікання будується згідно з теоремою 1.

4) або ; коефіцієнти правильного відсікання визначаються за алгоритмом Дальтона-Ллевеліна.

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

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

Означення 3. Точки () називатимемо лексикографічно еквівалентними відносно розміщень (_еквівалентними), якщо не існує такої точки , що ; будь-яка точка вважається _еквівалентною сама собі.

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

Нехай многогранник такий, що .

Означення 4. Елементи фактор-множини за еквівалентністю називатимемо _класами; _клас називається комбінаторним, якщо він утворений точкою з множини , в іншому разі _клас називається некомбінаторним._

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

, . (33)

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

У підрозділі 4.2 викладено алгоритми розв’язування _та _задачі, під якими розуміють пошук для заданого _класу відповідно _класів та таких, що

, , , (34)

, , . (35)

Показано, що розв’язування _задачі може бути здійснено як розв’язування послідовності задач вигляду

, (36)

де ; число таке, що непорожньою є множина ; множина визначається такими умовами:

, (37)

, (38)

. (39)

Розв’язок _задачі може бути одержаний у результаті розв’язування послідовності задач

, (40)

де ; число таке, що непорожньою є множина ; множина визначається умовою (37) та такими:

, (41)

; (42)

У підрозділі 4.3 розглянуто застосування ідей напрямленого перебору _класів до розв’язування _та _задач. В основу алгоритму розв’язування _задачі покладено той факт, що при виконанні умови (11) екстремаль лежить на одній із гіперплощин рівня вигляду

, (43)

де .

Допоміжну задачу пошуку лексикографічно максимального елемента множини називатимемо _задачею.

Твердження 4. Нехай многогранник визначається умовами (2), (9), (43); лексикографічно максимальна точка цього многогранника визначає _клас . Тоді розв’язком _задачі є точка , якщо , або точка , якщо . Якщо і _задача розв’язку не має, то _задача також не має розв’язку.

Теорема 5. Нехай — найбільше число таке, що _задача має розв’язок, який позначимо . Тоді пара є розв’язком _задачі у випадку максимізації.

Теореми, аналогічні теоремам 4 та 5 справедливі і для розв’язування _задачі у випадку мінімізації.

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

, . (44)

де — максимальне (відповідно мінімальне) значення цільової функції серед одержаних на попередніх ітераціях.

Оскільки _задача полягає у відшуканні пари (6), тобто лексикографічного екстремуму заданої функції, то умова покращання допустимого розв’язку в результаті перебору для задач максимізації та мінімізації визначається відповідно таким чином (позначення означає , що є кращим допустимим розв’язком _задачі, ніж точка ):

,

.

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

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

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

Висновки

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

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

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

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

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

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

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

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

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

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

Розробка методів розв’язування оптимізаційних задач на розміщеннях дозволяє знаходити оптимальні розв’язки таких моделей.

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

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

Формулювання та обґрунтування алгоритмів розроблених методів розв’язування задач на розміщеннях дозволяє автоматизувати процес пошуку розв’язків таких задач за рахунок використання ЕОМ. Практична ефективність запропонованих алгоритмів підтверджена числовими експериментами.

Список опублікованих праць за темою дисертації

1. Ємець О.О., Барболіна Т.М. Розв’язування задач нелінійної умовної оптимізації на розміщеннях методом відсікання // Укр. матем. журн. – 2003. – Т.55, №5. – С. –611.

2. Емец О.А., Барболина Т.Н. Решение линейных задач оптимизации на размещениях методом отсечения // Кибернетика и системный анализ. – 2003. – №6. – С. –141.

3. Емец О.А., Барболина Т.Н. Решение задач евклидовой комбинаторной оптимизации методом построения лексикографической эквивалентности // Кибернетика и системный анализ. – 2004. – №5. – С. –125.

4. Барболина Т.Н., Емец О.А. Полностью целочисленный метод отсечения для решения линейных условных задач оптимизации на размещениях // Журн. вычисл. математики и матем. физики. – 2005. – Т.45, №2. – С.254–261.

5. Ємець О.О., Барболіна Т.М. Оптимізація інвестиційних портфелів як евклідова комбінаторна оптимізація на розміщеннях // Економіка і регіон. Науковий вісник Полтавського національного технічного університету ім. Юрія Кондратюка. – 2003. – №1 (1). – С 65-67.

6. Ємець О.О., Барболіна Т.М. Методи відсіканння в нелінійній оптимізації на розміщеннях та їх застосування до розв’язування однієї інвестиційної задачі // Вісник Полтавського державного педагогічного університету ім. В.Г. Короленка. Зб. наук. пр. – Випуск 1(22). – Серія “Фізико–математичні науки”. – Полтава, 2002. – С. .

7. Ємець О.О., Барболіна Т.М. Лексикографічна еквівалентність у задачах евклідової комбінаторної оптимізації // Вісник Полтавського державного університету ім. В.Г.Короленка. Зб. наук. пр.: Випуск 6 (33). – Серія “Фізико–математичні науки”. – Полтава, 2003. – С. .

8. Барболіна Т.М., Ємець О.О. Про один з алгоритмів розв’язування оптимізаційних задач на розміщеннях з додатковими умовами / Полтав. держ. техн. ун–т. – Полтава, 2000. – 7 с. – Деп. в ДНТБ України 29.01.01, №14 – Ук2001.

9. Емец О.А., Барболина Т.Н. Классы лексикографической эквивалентности в евклидовой комбинаторной оптимизации на размещениях / Полтав. нац. техн. ун–т. – Полтава, 2002. – 8 с. – Рус. – Деп. в ГНТБ Украины 10.06.02, №90 – Ук2002.

10. Емец О.А., Барболина Т.Н. Лексикографическая эквивалентность в оптимизации на размещениях // Материалы VIII Международного семинара “Дискретная математика и ее приложения” (Москва, 2 – 6 февраля 2004 г.). – М.: Изд-во механико–математического факультета МГУ, 2004. – С. .

11. Ємець О.О., Барболіна Т.М. Метод відсікання розв’язування лінійних умовних задач оптимізації на розміщеннях // М.В. Остроградський — видатний математик, механік і педагог: Матеріали Міжнародної конференції, присвяченої 200–річчю з дня народження (Полтава, 26 – 27 вересня 2001 року). — Полтава, 2001. – С. .

12. Барболіна Т.М. Методи та алгоритми розв’язування оптимізаційних задач на розміщеннях з додатковими умовами // Матеріали VII Міжнародної науково-практичної конференції “Наука і освіта ’2004”.– Дніпропетровськ: Наука і освіта, 2004. – Т. : Математика. – С. .

13. Барболіна Т.М., Ємець О.О. Розв’язування задач оптимізації на розміщеннях. Методи й алгоритми // Праці ІІ Міжнародної школи–семінару “Теорія прийняття рішень”. – Ужгород: УжНУ, 2004. – С. .

14. Ємець О.О., Барболіна Т.М. Оптимізація на розміщеннях: цілочислові відсікання // Десята міжнародна наукова конференція імені академіка М. Кравчука (Київ, 13 – 15 трав. 2004 р.): Матеріали конференції. – К.: Задруга, 2004. – С. .

15. Ємець О.О., Барболіна Т.М. Оптимізація на розміщеннях у моделюванні інвестиційних задач // Економічні проблеми розвитку регіонів та підприємств на початку ХХІ століття: Тези доповідей Всеукраїнської науково–практичної конференції (Полтава, 22 – 23 листопада 2001 року). У 2 т. – Полтава: ПДТУ ім. Юрія Кондратюка, 2001. – Т.2. – С. .

16. Барболіна Т.М. Лексикографічна оптимізація на розміщеннях у моделюванні економічних процесів // Наукові записки: Матеріали звітної наукової конференції викладачів, аспірантів, магістрантів і студентів фізико–математичного факультету. – Полтава: ПДПУ, 2004. – С. .

АНОТАЦІЯ

Барболіна Т.М. “Методи й алгоритми розв’язування оптимізаційних задач на розміщеннях з додатковими умовами”. Рукопис.

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

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

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

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

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

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

ABSTRACT

Barbolina T.M. "Methods and algorithms for solving optimization problems on arrangements with additional conditions". The manuscript.

The dissertation is the manuscript presented for the scientific degree of the candidate of Physical and Mathematical Sciences on the specialty 01.05.01 – theoretical bases of informatics and cybernetics. – The V.M. Glushkov Institute of cybernetics of National Academy of Sciences of Ukraine, Kiev, 2005.

The models of practical problems are built as Euclidean problems of lexicographic combinatorial optimization on arrangements which are a new class of Euclidian combinatorial optimization problems.

Cutting methods for solving linear and convex optimization problems on arrangements are developed.

The splitting of polyhedral sets with an equivalence relation is proposed. On the basis of such splitting a lexicographic equivalence method for solving all-combinatorial lexicographic optimization on arrangements are developed.

Algorithms of cutting method and lexicographic equivalence method for solving optimization problems on arrangements are proposed and validated. The algorithms based on such ideas are proved to be finite.

Keywords: mathematical programming, combinatorial optimization, arrangements, cutting method, method of exhaustive search, lexicographic

АННОТАЦИЯ

Барболина Т.Н. “Методы и алгоритмы решения оптимизационных задач на размещениях с дополнительными ограничениями”. Рукопись.

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

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

Наиболее общая из рассматриваемых в работе задач состоит в нахождении экстремума (или лексикографического экстремума) и экстремали линейной целевой функции при комбинаторном условии принадлежности общему множеству размещений, а также дополнительных линейных и выпуклых ограничений. При этом под общим множеством размещений понимается следующее. Пусть — мультимножество действительных чисел с основой , первичной спецификацией . Общим множеством _размещений называется множество всех упорядоченных _выборок из мультимножества . Рассматривая элементы множества как точки арифметического евклидового пространства , множество размещений обозначают .

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

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

Предложено разбиение многогранного множества с помощью отношения лексикографической эквивалентности относительно размещений, которое является отношением эквивалентности. Показана возможность упорядочивания элементов фактор-множества по данной эквивалентности (_классов). Разработаны алгоритмы, позволяющие находить для заданного класса эквивалентности комбинаторный _класс (одноэлементый _класс, определенный размещением), который является ближайшим к заданному классу в фактор-множестве, упорядоченном в соответствии с введенным отношением порядка. Используя эти алгоритмы, предложен метод решения полностью комбинаторных линейных условных задач лексикографической оптимизации на размещениях.

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

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