НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ ПРОБЛЕМ МАШИНОБУДУВАННЯ

ІМ. А. М. ПІДГОРНОГО

ЄМЕЦЬ ЄЛИЗАВЕТА МИХАЙЛІВНА

УДК 519.85

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

01.05.02 – математичне моделювання та обчислювальні методи

Автореферат

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

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

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

Робота виконана в Полтавському національному технічному університеті ім. Юрія Кондратюка Міністерства освіти і науки України

Науковий керівник: член-кореспондент НАН України, доктор технічних наук СТОЯН Юрій Григорович, Інститут проблем машинобудування ім. А.М. Підгорного НАН України, завідувач відділу математичного моделювання і оптимального проектування (м. Харків)

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

ЯКОВЛЕВ Сергій Всеволодович, Національний університет внутрішніх справ, начальник факультету управління та інформатики (м. Харків)

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

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

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

Захист відбудеться 30 січня 2003 р. о 14 годині на засіданні спеціалізованої вченої ради Д 64.180.01 в Інституті проблем машинобудування ім. А.М.Підгорного НАН України за адресою: 61046, Харків, вул. Дм. Пожарського, 2/10, ауд. 1211.

З дисертацією можна ознайомитись у науковій бібліотеці Інституту проблем машинобудування ім. А.М.Підгорного НАН України за адресою: 61046, м. Харків, вул. Дм. Пожарського, 2/10

Автореферат розісланий 27 грудня 2002 р.

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

спеціалізованої вченої ради Б.П. Зайцев

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась з 1994 року на кафедрі прикладної математики і математичного моделювання Полтавського національного технічного університету імені Юрія Кондратюка згідно з індивідуальним планом аспірантської підготовки та держбюджетною темою "Розробка теорії, моделей, методів і алгоритмів евклідової комбінаторної оптимізації" (ДР№0196U006063), співвиконавцем якої є дисертант, в рамках наукових програм та планів університету.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результати дисертації використовуються з 1996 року у наукових дослідженнях Полтавського національного технічного університету імені Юрія Кондратюка, зокрема при виконанні держбюджетної теми "Розробка теорії, моделей, методів та алгоритмів евклідової комбінаторної оптимізації", ДР№0196U006063, а також впроваджені в навчальний процес цього університету.

Особистий внесок здобувача. Результати, які викладені в дисертаційній роботі і подані до захисту одержано дисертантом. У роботах [3, 5, 6, 7, 12, 14, 16] дисертанту належать доведення теорем, математичні викладки, виконання досліджень, побудова математичних моделей. В роботі [2] дисертанту належить обґрунтування методу відсікання та розробка його алгоритму. В роботах [1, 4, 8, 9, 11] дисертанту належить розробка методу відсікання, його алгоритму та їх реалізація для частково комбінаторних задач.

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

·

· Всеукраїнській науковій конференції "Розробка та застосування математичних методів у науково-технічних дослідженнях", присвяченій 70-річчю професора П.С. Казімірського (м. Львів, 1995 р.);

· 5-7-ій Міжнародних наукових конференціях імені академіка М. Кравчука (м. Київ, 1996-1998 рр.);

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

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

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

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

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

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

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

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

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

Як відомо, мультимножиною називають сукупність елементів , серед яких є, взагалі кажучи, однакові. Будь-яку мультимножину A можна представити її основою , тобто множиною всіх її різних елементів, і первинною специфікацією - списком кратностей елементів основи мультимножини. Нехай A - мультимножина з основою і кратностями елементів , а B - мультимножина з основою і кратностями . Тоді під сумою A+В мультимножин A та В розуміють мультимножину з основою S(A+B)=S(A)ИS(B) і кратностями . Суму n мультимножин будемо позначати . Мультимножина B з основою S(B) називається підмультимножиною мультимножини A з основою S(A), якщо S(B)МS(A), і для кожного елементу aОS(B) виконується нерівність , де - кратність елементу a в мультимножині А. Позначається це тим же знаком М, що і для множин, тобто BМA. Як відомо k-елементну підмультимножину B мультимножини A називають k-вибіркою, тобто B - k-вибірка, якщо BМA, ЅBЅ=k.

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

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

(1)

де .

Вибірки вигляду (1) вважаються різними, якщо таке, що .

Множину E, різними елементами якої є різні упорядковані k-вибірки вигляду (1) з мультимножини G називають евклідовою комбінаторною множиною (коротко - е-множиною).

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

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

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

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

(2)

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

(3)

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

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

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

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

(4)

Покладемо

(5)

Теорема 1. Загальний многогранник полірозміщень описується системою

.

Точку вигляду

(6)

можна ще описати як , де визначається (5), та .

Теорема 2. (Критерій вершини многогранника ). Точка , де визначається співвідношенням (6), є вершиною загального многогранника полірозміщень тоді і тільки тоді, коли компоненти вектора є переставленням чисел при виконанні умови .

Твердження 3. Якщо , то загальна множина полірозміщень збігається з множиною вершин загального многогранника полірозміщень: .

Теорема 4. (Критерій суміжності вершин многогранника ). Якщо - вершина загального многогранника полірозміщень , то всі суміжні з нею вершини одержуються або переставленням в x компонент , , або заміною компоненти на , де відповідно.

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

Показано, що многогранник полірозміщень є добутком многогранників розміщень.

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

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

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

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

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

Розглянемо оптимізаційну задачу на множині : знайти

де , при додаткових обмеженнях: . Якщо остання умова відсутня, то задачу називають безумовною задачею мінімізації на . Якщо F(x) – лінійна функція, то цю задачу називають задачею безумовної лінійної мінімізації на (або лінійною безумовною оптимізаційною задачею на ). Якщо F(x) – опукла (сильно опукла) функція, то поставлену задачу називають задачею безумовної опуклої (сильно опуклої) мінімізації (або безумовною опуклою (сильно опуклою)) оптимізаційною задачею на .

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

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

(7)

Нехай тут і далі . Використовуючи властивості многогранника полірозміщень доведена:

Теорема 6. Якщо , де , виконується умова (4) та, де задовольняють умові , то x* задовольняє умові (7).

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

Теорема 7. Якщо - скінчена опукла функція, яка задана на опуклій замкненій множині , то: 1) ,

2) щоб точка була мінімаллю на множині функції , достатньо виконання умови , де - субградієнт функції в точці y, переставлення елементів множини задовольняє умові , а елементи мультимножини G - упорядковані згідно з нерівностями (4).

Доведено диференційовний аналог теореми 7.

Розглянемо сильно опуклу функцію з параметром r?>0 на опуклій замкненій множині . Позначимо

(8)

Теорема 8. Якщо функція – сильно опукла з параметром r?>0 на опуклій замкненій множині , , то , де точка w означається співвідношенням (8), а переставлення елементів множини і стала - нерівностями , переставлення елементів множини - умовою , а елементи мультимножини G упорядковані згідно з нерівностями (4).

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

Теорема 9. Якщо , а - сильно опукла функція з параметром сильної опуклості r?>0, що задана в ; - множина полірозміщень, то: 1) ;

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

сталі такі:, переставлення елементів множини означається таким співвідношенням для елементів : , а елементи G упорядковані згідно (4).

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

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

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

(9)

при умові

(10)

і додаткових обмеженнях

(11)

де E - евклідова комбінаторна множина, ; m, r, k - задані натуральні константи (mііk); - задані дійсні числа .

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

В багатьох задачах вигляду (9)-(11) евклідова комбінаторна множина E збігається з множиною вершин своєї опуклої оболонки, тобто:

E = vert conv E. (12)

Властивість (12), як відомо виконується для множини переставлень без повторень, парних переставлень, переставлень з j-ою забороною; загальної множини переставлень; загальної множини поліпереставлень; деяких множин розміщень і полірозміщень, що фігурують в твердженні 3.

Наявність властивості (12) дозволяє побудувати метод відсікання для розв'язування задачі (9)-(11), що не має головних труднощів методу відсікання в дискретній оптимізації. А саме: 1) немає необхідності перевіряти "правильність" відсікання (чи задовольняють нерівності-відсіканню всі допустимі розв'язки задачі); 2) відсікання, яке проведено через суміжні вершини з точкою, що відсікається, апріорі має властивісь достатньої "глибини", тобто внутрішніх допустимих точок задача (9)-(11) не має.

Сформулюємо метод відсікання для розв'язування задачі (9)-(11), в якому будемо використовувати умову(13)

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

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

1. Розв'язуємо задачу знаходження (9) при умовах (11), (13). Це - задача лінійного програмування (ЗЛП).

2. За y* формуємо , та перевіряємо для x* умову (10). Якщо , то задача (9)-(11) розв'язана. Інакше переходимо на 3.

3. Знаходимо суміжні з y* вершини многогранника, який описується умовами (11), (13). Визначаємо напівпростір, межа якого проходить через ці суміжні з y* вершини, а точка y* не належить йому: . Цю нерівність додаємо до системи (11) і з врахуванням цього переходимо на 1.

Нехай задача (9), (11), (13) перетворена до канонічного вигляду ЗЛП: знайти

(14)

при умовах

(15)

Зазначимо, що nііm, s>r.

Сформулюємо алгоритм методу відсікання.

Нехай цілочислова змінна q=0.

Крок 1. Розв'язуємо задачу (14)-(15) прямим або двоїстим симплекс-методом. Якщо ця задача нерозв'язна, то нерозв'язна і вихідна задача, зупинка алгоритму. В іншому разі - перехід на крок 2.

Крок 2. Перевіряємо (чи виконується умова (10)). Якщо (10) для х* виконано, то задача (9)-(11) розв'язана, зупинка алгоритму. В іншому разі переходимо на крок 3.

Крок 3. Перевіряємо: q>1. Якщо "так", - перехід на крок 5. Інакше - перехід на крок 4.

Крок 4. Збільшуємо q на одиницю. Додаємо до (15) сформовану нерівність-відсікання

(16)

у вигляді рівності

(17)

ввівши допоміжну змінну . В формулах (16), (17) - номера небазисних змінних в останній точці у*; g? - їх кількість, а знаходиться так:

(18)

Переходимо на крок 1 алгоритму.

Крок 5. Перевіряємо: ( обчислюється за формулою (18)). Якщо "ні", переходимо на крок 4. Якщо "так", то в останній приєднаній до системи (15) рівності (17) замінюємо введену там допоміжну змінну () на 0; переходимо на крок 1 алгоритму.

Обґрунтовує метод наступна теорема.

Теорема 10. Якщо - номери небазисних змінних в розв'язку ЗЛП, то нерівність (16), де обчисляються за формулами (18), всі суміжні з y* вершини допустимої області задовольняє як рівність, а точка y* нерівність (16) не справджує.

Скінченність множини вершин допустимої області і обмеженість числа n забезпечують скінченність алгоритму.

Зазначимо, що метод відсікання тісно пов'язаний з добре дослідженим симплекс-методом для задач лінійного програмування загальною спільною властивістю - перебором суміжних вершин. (В симплекс-методі - після аналізу вершини на оптимальність для переходу до вершини з більшим (в невиродженій задачі на максимум) значенням цільової функції, в методі відсікання - після аналізу вершини на справдження умови (10) та її (вершини) відсікання - до суміжної з меншим значенням цільової функції). Ефективність методу відсікання порівнянна з ефективністю симплекс-методу, оскільки визначається, в основному, цим перебором вершин. Це означає, що, як і для симплекс-методу, можуть бути побудовані “патологічні” приклади, де перебираються всі вершини допустимої області. Але це ж дозволяє зробити і той висновок, що при практичному застосуванні, тобто “в середньому”, метод відсікання буде вести себе так же добре як і симплекс-метод. Це підтверджують і результати проведених числових експериментів.

Числові експерименти по алгоритму методу відсікання проводилися на задачі упаковування прямокутників однакової ширини в смуги в такій постановці.

Задача. Задано р прямокутників однакової ширини h і довжинами . Необхідно упакувати прямокутники в m смужок, , ширини h достатньо довгої смуги ширини mh так, щоб довжина зайнятої частини смуги була мінімальною.

В моделі цієї задачі переставлення має елементів. Зауважимо, що ЗЛП, яка розв'язується на першому кроці методу відсікань, серед обмежень має обмежень многогранника переставлень. Для її (ЗЛП) розв'язку, застосовано відомий метод послідовного приєднання обмежень (МППО). При проведені числових експериментів використана програма Л.М. Колєчкіної [2], яка написана на BORLAND PASCAL 7.0. Розглядалися упаковування до 50 прямокутників, довжини прямокутників вибиралися як випадкові числа, розподілені рівномірно в заданому інтервалі ([1, 1000]). Кількість смужок була від 2 до 5. При цьому використовувались ЗЛП, що містять до 189 змінних та 2189+191 обмежень. Їх розв'язок проводився з застосуванням згаданого вище МППО, в результаті чого кількість обмежень у ЗЛП, які використовувались, не перевищувала 711. Кількість відсікань в задачах цієї серії числових експериментів не перевищувала 142. Розрахунки проводилися на ПК Pentium II. Час розрахунків в залежності від вимірності задачі змінювався від часток секунди до 6 годин.

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

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

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

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

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

2. Розглянуто застосування апарату множин полірозміщень для моделювання ряду задач оптимізації.

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

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

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

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

7. Обґрунтовано алгоритм цього методу відсікання, доведена теорема про вигляд нерівності-відсікання.

8. Обґрунтовано скінченність алгоритму методу відсікання. Проведено числові експерименти, які показали практичну ефективність запропонованого методу комбінаторного відсікання.

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

1. Ємець О.О., Ємець Є.М. Метод відсікання в евклідовій комбінаторній оптимізації: Навч. посібник з курсу "Елементи комбінаторної оптимізації". - Полтава: ПолтТУ, 1997. - 30 с.

2. Емец О.А., Емец Е.М., Колечкина Л.Н. Использование метода отсечений при раскрое // Радиоэлектроника и информатика. - 1998. - № 3. - С. 114-117.

3. Стоян Ю.Г., Ємець О.О., Ємець Є.М. Множини полірозміщень в комбінаторній оптимізації // Доповіді НАН України - 1999. - № 8. – С. 37-41.

4. Ємець О.О., Ємець Є.М. Відсікання в лінійних частково комбінаторних задачах евклідової комбінаторної оптимізації // Доповіді НАН України. - 2000. - №9. – С. 105-109.

5. Ємець О.О., Ємець Є.М. Безумовна оптимізація на полірозміщеннях: достатні умови та оцінки мінімумів сильно опуклих цільових функцій // Вісник Запорізького державного університету. - Запоріжжя: ЗДУ. - 2000. - № 1. - С. 44-48.

6. Ємець О.О., Ємець Є.М. Оцінки та достатні умови мінімуму сильно опуклої функції при її мінімізації на розміщеннях // Волинський математичний вісник. - Рівне: Рівненський державний університет. - 2000. - № 7. - С.67 –69.

7. Емец О.А., Емец Е.М. Моделирование некоторых инвестиционных задач с помощью евклидовой комбинаторной оптимизации// Экономика и матем. методы - 2000. - Т. 36. №2. С. 141-144.

8. Емец О.А., Емец Е.М. Отсечения в линейных частично комбинаторных задачах оптимизации на перестановках // Экономика и матем. методы. - 2001. -Т. 37, №1. - С. 118-121.

9. Ємець О.О., Ємець Є.М. Використання моделей і методів комбінаторної оптимізації в задачах економії ресурсів // В кн.: Проблеми праці, економіки та моделювання: Зб. наук. праць. Ч. 1. / Міносвіти України, Технолог. ун-т Поділля. - Хмельницький: НВП “Евріка”, 1998 - С. 92-93.

10. Ємець Є.М. Безумовна лінійна оптимізаційна задача на полірозміщеннях та її розв'язування // Збірник наук. праць: Вісник Полтав. держ. пед. ін-ту ім. В.Г. Короленка. - Сер. "Фіз.-матем. науки" - 1998 - Вип. 3.- С. 24-28.

11. Ємець О.О., Ємець Є.М. Метод відсікання для лінійних задач евклідової комбінаторної оптимізації // В кн.: Всеукраїнська наук. конф. "Розробка та застосування матем. методів в науково-техн. дослідженнях": Тези доп. Ч. 3. / Міносвіти України. Держ. ун-т "Львівська політехніка". Львів, 1995. - С. 32-33.

12. Ємець О., Ємець Є. Загальний многогранник полірозміщень та його властивості // В кн.: П'ята міжн. наук. конф. ім. ак. М.Кравчука (16-18 травня 1996 р., Київ): Тези доп. - К., 1996.- С.140.

13. Ємець Є.М. Властивості загальної множини полірозміщень та її опуклої оболонки. //В кн.: Шоста міжн. наук. конф. ім. ак. М.Кравчука (15-17 травня 1997 р., Київ): Матеріали конф. - К., 1997. С.158.

14. Yemets O., Yemets Ye. Optimization problems on a set of polyarrangements // В кн.: Сьома міжн. наук. конф. ім. ак. М.Кравчука (14-16 травня 1998 р., Київ): Матеріали конф. - К., 1998. - С. 167-168.

15. Ємець Є.М. Лінійна безумовна мінімізація на евклідовій множині полірозміщень // В кн.: Тези доп. 50 наук. конф. ... ун-ту. Ч. 1 / Міносвіти України. Полт. держ. техн. ун-т ім. Ю.Кондратюка. - Полтава, 1998. - С. 51.

16. Емец О.А., Емец Е.М. Моделирование инвестиций средствами евклидовой комбинаторной оптимизации //Abstracts Second International School on Actuarial and Financial Mathematics (June, 8-12, 1999, Kyiv).- Kyiv, 1999.- P. 19.

АНОТАЦІЯ

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

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

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

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

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

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

ABSTRACT

Yemets Ye. М. "Research of properties of mathematical models of combinatorial optimization problems on the polyarrangements both development of a method and a algorithm of the combinatorial cutting". 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.02 – mathematical modeling and computational methods. – The A.M. Pidgorny Institute for Problem in Machinery of National Academy of Sciences of Ukraine, Kharkov, 2002.

The exposition a convex hull of a set of the polyarrangements by means of a system of linear inequalities is obtained. The structure of this set and this polyhedron is investigated: symmetry, criterion of top, criterion of a contiguity of tops, criterion of an edge, contiguity of edges.

The unconditional linear problem of optimization on the polyarrangements is solved. The evaluations and sufficient conditions of minima convex and strong convex functions in the unconditional problems on the polyarrangements are proved.

The cutting method for one class of linear partially combinatorial problems of Euclidean combinatorial optimization is offered. The algorithm of this method is developed.

Key words: mathematical programming, combinatorial optimization, polyarrangements, cutting method, combinatorial polyhedrons.

АНОТАЦИЯ

Емец Е. М. "Исследование свойств математических моделей комбинаторных задач оптимизации на полиразмещениях и разработка метода и алгоритма комбинаторного отсечения". Рукопись

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 – математическое моделирование и вычислительные методы. – Институт проблем машиностроения им. А.Н. Подгорного НАН Украины , Харьков, 2002.

Рассмотрены необходимые для изложения результатов диссертации элементы теории комбинаторной оптимизации на евклидовых комбинаторных множествах.

В диссертации исследуется множество полиразмещений и задачи оптимизации на нем. Под множеством полиразмещений понимается следующее.

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

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

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

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

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

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