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

В Україні серед вчених, роботи яких присвячені різним аспектам дискретної оптимізації, в першу чергу слід виділити І. В. Теорія і методи евклідової комбінаторної оптимізації включають систематичне вивчення властивостей евклідових комбінаторних множин та їх системне дослідження. Поряд з добре відомими евклідовими комбінаторними множинами переставлень, розміщень, сполучень, розбиттів виділяються більш складні структури - полікомбінаторні множини. Для дослідження властивостей задач на полікомбінаторних множинах необхідно визначити і дослідити властивості відповідних комбінаторних множин та їх опуклих оболонок. Дисертаційна робота виконувалась в період з 1998 по 2004 роки на кафедрі прикладної математики, інформатики та математичного моделювання Полтавського національного технічного університету імені Юрія Кондратюка згідно з індивідуальним планом аспірантської підготовки, держбюджетною темою №59/03 «Методи відсікання в евклідовій комбінаторній оптимізації та розвиток її теорії» та планами науково-дослідної роботи університету.У вступі обґрунтовано актуальність теми дисертації, сформульовано мету і завдання дослідження, а також методи, які використовувалися при реалізації завдань. Многогранник , що описується незвідною системою (2), є невиродженим тоді і тільки тоді, коли: при ; Дві евклідові комбінаторні множини і назвемо евклідовими комбінаторними множинами одного типу, якщо системи обмежень вигляду (8), що описують і , мають одну й ту ж матрицю . У третьому розділі розвязане питання виявлення надлишкових обмежень в системах нерівностей, що описують опуклі оболонки комбінаторних та полікомбінаторних множин розміщень та доведена незвідність систем обмежень для загальних евклідових комбінаторних множин розміщень і полірозміщень. Тоді математична модель задачі, що розглядається, буде мати вигляд: знайти при обмеженнях: Для сформульованої задачі розглянуто методи її розвязування, які ґрунтуються на використанні властивостей евклідових комбінаторних та полікомбінаторних множин: метод гілок і меж та аналог методу Дальтона-Ллевеліна для розглянутої вище полікомбінаторної множини .Серед комбінаторних обєктів, які потребують всебічного дослідження все важливіше місце займають більш складні структури - полікомбінаторні множини. Інтерес до дослідження апарату полікомбінаторних множин викликаний їх великим практичним значенням щодо постановки та розвязування задач комбінаторної оптимізації, які описують економічні, соціальні та інші процеси і системи. Методи дослідження полікомбінаторних множин, що використовуються в дисертації, ґрунтуються на розвинутих раніше теорії та методах евклідової комбінаторної оптимізації, а також на інших відомих методах дискретної оптимізації. Встановлення необхідних та достатніх умов невиродженості загальних многогранників переставлень та поліпереставлень дозволяє застосовувати для їх дослідження апарат комбінаторної теорії многогранників, численні методи якого розвинуто, в основному, саме для невироджених многогранників. Доведення достатньої умови еквівалентності комбінаторних многогранників одного типу дозволяє визначити класи еквівалентності за їх первинною специфікацією і досліджувати спільні властивості класу, аналізуючи властивості лише окремого його представника.

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

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

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

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

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

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

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

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

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

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

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

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

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

Ємець О.О., Роскладка О.В., Недобачій С. І. Незвідна система обмежень для загального многогранника розміщень // Український математичний журнал. - 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.

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