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

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

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

Автореферат

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

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

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

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

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

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

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

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

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

Об'єктом дослідження є евклідові полікомбінаторні множини.

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

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

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

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

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

уперше обґрунтовані необхідні та достатні умови невиродженості переставних многогранників;

уперше досліджено клас комбінаторних та полікомбінаторних множин переставлень із спільною первинною специфікацією і доведено еквівалентність їх опуклих оболонок;

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

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

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

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

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

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

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

[1] - доведення леми про надлишкові обмеження та теореми про незвідність системи обмежень загального многогранника розміщень;

[2] використання методів динамічного програмування для знаходження розв'язку задачі розміщення об'єктів обслуговування і поширення викладеного алгоритму для випадку інших полікомбінаторних множин;

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

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

[6] використання властивостей евклідової множини полірозміщень для побудови математичної моделі задачі розміщення об'єктів обслуговування;

[7] - визначення надлишкових обмежень загального многогранника розміщень;

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

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

VIIІ, Х міжнародних наукових конференціях імені академіка М. Кравчука (Київ, 2000, 2004);

Міжнародній науковій конференції «Обчислювальна математика і математичні проблеми механіки» (Дрогобич, 2001);

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

Міжнародній школі математичних і статистичних методів в економіці, фінансах і страхуванні (Ласпі, Крим, 2003)

51-56 наукових конференціях професорів, викладачів, наукових співробітників, аспірантів і студентів Полтавського національного технічного університету імені Юрія Кондратюка (Полтава, 1999-2004);

науковому семінарі кафедри моделювання складних систем Національного університету імені Тараса Шевченка, керівник - д. ф.-м. н., проф. Гаращенко О.Ф. (Київ, 2004);

науковому семінарі Інституту кібернетики НАН України, керівник -

д. ф.-м. н., проф. Донець Г.П. (Київ, 2004).

Публікації. Результати дисертаційної роботи опубліковані у 9 наукових працях, з них 5 статей у фахових наукових виданнях, 4 матеріалів і тез конференцій.

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

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

поле многогранник полікомбінаторний невиродженість

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

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

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

Позначимо через кількість повторень елемента основи в мультимножині .

Теорема 2. Многогранник , що описується незвідною системою (2), є невиродженим тоді і тільки тоді, коли:

при ;

при .

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

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

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

Теорема 6. (Наслідок з теореми 5). Нехай і , , , де , - кількості повторень елемента в мультимножинах і відповідно, ; . Тоді, якщо - невироджений многогранник в , що описується незвідною системою вигляду (4), і , то також є невиродженим.

Нехай система обмежень, що задає комбінаторний многогранник , має вид:

.

Означення 7. Дві евклідові комбінаторні множини і назвемо евклідовими комбінаторними множинами одного типу, якщо системи обмежень вигляду (8), що описують і , мають одну й ту ж матрицю .

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

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

Теорема 9. Якщо в первинній специфікації мультимножини , або , то надлишковими обмеженнями системи (9), (10) многогранника є:

- серед нерівностей підсистеми (9) при - усі нерівності і-спілок, де і задовольняє умовам: , ;

- серед нерівностей підсистеми (10) при - усі нерівності і-спілок, де і таке: , , і тільки вони.

Теорема 10. Якщо існує , для якого або , то загальний многогранник полірозміщень

має надлишкові обмеження:

при - усі нерівності спілок серед нерівностей (12), а при - усі нерівності спілок серед нерівностей (13).

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

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

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

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

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

Розглядаємо задачу на фіксованому рівні. Вважаємо, не обмежуючи загальності міркувань, що . Будемо вважати, що .

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

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

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

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

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

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

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

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

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

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

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

Висновки

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

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

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

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

В дисертації вперше доведені фундаментальні властивості евклідових комбінаторних переставних і поліпереставних многогранників невиродженість та еквівалентність. Доведені необхідні та достатні умови невиродженості опуклих оболонок загальних множин переставлень та поліпереставлень. Обґрунтовані достатні умови еквівалентності опуклих оболонок евклідових комбінаторних і полікомбінаторних множин переставлень.

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

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

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

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

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

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

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

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

Ємець О.О., Роскладка О.В., Недобачій С. І. Незвідна система обмежень для загального многогранника розміщень // Український математичний журнал. - 2003. - т. 55. - №1. - С. 3-11.

Емец О.А., Роскладка Е.В. Решение некоторых евклидовых комбинаторных задач оптимизации методом динамического программирования // Кибернетика и системный анализ. - 2002. - №1. - С. 138-146.

Емец О.А., Роскладка Е.В. Многоуровневая задача обслуживания как задача евклидовой комбинаторной оптимизации и ее решение // Динамические системы (межвед. науч. сб.). - 2001. Вып. №17. - Симферополь: Тавр. нац. ун-т. - С. 205-209.

Ємець О.О., Романова Н.Г., Роскладка О.В. Про властивості деяких задач евклідової комбінаторної оптимізації на переставленнях та методи їх розв'язування // Вісник Львів. нац. ун-ту. Сер. приклад. математика та інформатика. - 2002. - Вип. №5. - С. 89-94.

Роскладка О.В. Незвідна система обмежень загального многогранника полірозміщень // Вісник Запорізького державного університету. - 2002. - №2. - С. 81-84.

Емец О.А., Роскладка А.А., Роскладка Е.В. Применение евклидовых поликомбинаторных множеств к построению моделей оптимизационных задач // Abstracts Second International School on Actuarial and Financial Mathematics (June, 8-12, 1999, Kyiv). - Kyiv, 1999. - P. 20.

Roskladka O.V., Yemets O.O., Nedobachiy S.I. About the system of linear restrictions, which describe a general polyhedron of the arrangements // В кн.: VIII міжнародна наук. конф. ім. ак. М. Кравчука (11-14 травня 2000 р., Київ): Мат-ли конф. - К., 2000. - C. 354.

Ємець О.О., Роскладка О.В. Задачі оптимізації на полікомбінаторних множинах: властивості та розв'язування // Abstracts Seventh International School of Mathematical and Statistical Methods In Economics, Finance and Insurance (September, 8-13, 2003, Laspi). - Laspi, Crimea, Ukraine, 2003. - P. 23.

Роскладка О.В. Про класи еквівалентності комбінаторних многогранників // В кн.: Х міжнародна наук. конф. ім. ак. М. Кравчука: Мат-ли конф. - К., 2004. - С. 537.

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