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

Такі задачі з комбінаторними обмеженнями ігрового типу потребують вивчення їхніх моделей та розробки методів для їхнього розвязування. Методи дослідження: для доведення нових властивостей вершин переставного многогранника використовуються методи алгебри; в розробці нового методу для знаходження оптимальної стратегії одного гравця в задачах комбінаторної оптимізації ігрового типу на переставленнях та розміщеннях з комбінаторними обмеженнями на стратегії цього гравця використовується метод комбінаторної оптимізації; для знаходження оптимальної стратегії гравця, який не має комбінаторних обмежень, використовуються методи лінійного програмування. Уведено до розгляду новий клас задач, які поєднують в собі риси задач комбінаторної оптимізації та теорії ігор - задачі комбінаторної оптимізації ігрового типу, в яких на стратегії одного або обох гравців накладаються комбінаторні обмеження, що визначаються переставленнями та розміщеннями, побудовано моделі практичних задач, що зводяться до таких задач комбінаторної оптимізації. Вперше досліджено застосування різних критеріїв прийняття рішень в задачах комбінаторної оптимізації ігрового типу, в яких на стратегії одного гравця накладаються комбінаторні обмеження, що визначаються переставленнями, а другим гравцем є природа. В працях, які написані в співавторстві, дисертанту належать: [1, 2, 11]: побудова моделей задач як задач оптимізації ігрового типу з комбінаторними обмеженнями, що визначаються розміщеннями та переставленнями, на стратегії одного або обох гравців, розробка графічного методу розвязування задач комбінаторної оптимізації ігрового типу вимірностей та доведення теорем про еквівалентність моделей задач комбінаторної оптимізації ігрового типу з обмеженнями, що визначаються розміщеннями та переставленнями, на стратегії одного або обох гравців парі задач оптимізації, дослідження застосування відомих методів для розвязування цих задач;Як відомо, якщо () - фундаментальна система розвязків системи лінійних нерівностей рангу над простором і - довільна лінійна нерівність над то ті елементи для яких і ті елементи з (що відрізняються один від іншого хоча б одним з індексів ), для кожного з яких існують лінійно незалежних нерівностей що обертаються в рівності як для так і для становлять фундаментальну систему розвязків системи У другому розділі наведені деякі змістовні формулювання задач та побудовані математичні моделі цих задач та загальна математична модель задач такого типу як задач комбінаторної оптимізації ігрового типу з обмеженнями, що визначаються переставленнями або розміщеннями, на стратегії одного або обох гравців. Досліджено застосування різних критеріїв в задачах комбінаторної оптимізації ігрового типу, в яких на стратегії одного гравця накладаються обмеження, що визначаються переставленнями, а другим гравцем є природа. Загальна математична модель задач комбінаторної оптимізації ігрового типу, в яких на стратегії одного (обох) гравців накладаються обмеження, що визначаються переставленнями (розміщеннями), така: Знайти оптимальні стратегії гравців і де Суміжні вершини переставного многогранника перетворюють в рівності нерівності системи (8) з лінійно незалежними лівими частинами, і ніякі інші фундаментальні розвязки цієї системи не перетворюють в рівності ці нерівності.Проведений аналіз методів комбінаторної оптимізації та теорії ігор показав, що вони не можуть застосовуватися для розвязування задач комбінаторної оптимізації ігрового типу, тому цей новий клас задач вимагає дослідження та модифікації існуючих, а також розробки спеціальних методів для їхнього розвязування. Уперше доведені теореми про еквівалентність задач комбінаторної оптимізації ігрового типу, в яких тільки один гравець має комбінаторні обмеження на застосування своїх стратегій, двом задачам оптимізації (задачі комбінаторної оптимізації та лінійного програмування). Вперше розроблено: модифікації графічного методу розвязування задач комбінаторної оптимізації ігрового типу вимірностей та наближений ітераційний метод розвязування задач комбінаторної оптимізації на переставленнях, в яких комбінаторні обмеження накладаються тільки на стратегії одного гравця. Уперше розроблено метод знаходження оптимальної стратегії гравця, на стратегії якого накладаються комбінаторні обмеження в задачах комбінаторної оптимізації на переставленнях, в яких комбінаторні обмеження накладаються тільки на стратегії одного гравця. Формулювання та обґрунтування алгоритмів розроблених методів розвязування задач комбінаторної оптимізації ігрового типу дозволяє автоматизувати процес пошуку розвязків таких задач за допомогою ЕОМ.

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

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

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

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

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

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

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

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

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

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

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

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ

1. Емец О. А. Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках игрового типа / О. А. Емец, Н. Ю. Устьян // Проблемы управления и информатики. - 2006. - № 3. - С. 37-47.

2. Емец О. А. Исследование задач комбинаторной оптимизации игрового типа на размещениях / О. А. Емец, Н. Ю. Устьян // Проблемы управления и информатики. - 2007. - № 1. - С. 26-36.

3. Емец О. А. Исследование математических моделей и методов решения задач на перестановках игрового типа / О. А. Емец, Н. Ю. Устьян // Кибернетика и сист. анализ. - 2007. - №6. - С. 103-114.

4. Ємець О. О. Розвязування ігрових задач на переставленнях / О. О. Ємець, Н. Ю. Устьян // Наукові вісті НТУУ “КПІ”. - 2007. - №3. - С. 47-52.

5. Ємець О. О. Один ітераційний метод розвязування ігрових задач на переставленнях / О. О. Ємець, Н. Ю. Устьян // Наукові вісті НТУУ “КПІ”. - 2008. - №3. - С.5-10.

6. Емец О. А. Игры с комбинаторными ограничениями / О. А. Емец, Н. Ю. Устьян // Кибернетика и сист. анализ. - 2008. - №4. - С.134-141.

7. Емец О. А. Задачи на перестановках игрового типа / О. А. Емец, Н. Ю. Устьян // Проблемы теоретич. кибернетики: XIV Международ. конф. Пенза, 23-28 мая 2005г. - М.:Изд-во мех.-мата. МГУ,2005-С. 46.

8. Ємець О. О. Ігрова комбінаторна модель однієї задачі сільськогосподарського виробництва / О. О. Ємець, Н. Ю. Устьян // Наука і освіта"2004: VII Міжнарод. наук.-практ. конф. Дніпропетровськ, 10-25 лютого, 2004р. - Дніпропетровськ: Наука і освіта, 2004. - Т. 70. - С. 46-49.

9. Ємець О. О. Ігрові комбінаторні задачі на переставленнях / О. О. Ємець, Н. Ю. Устьян // Наука і освіта "2005: VIII Міжнародна науково-практична конференція. Дніпропетровськ, 7-21 лютого, 2005 р. - Дніпропетровськ: Наука і освіта, 2005. - Т. 22. - С. 26-31.

10. Устьян Н. Ю. Модифікований графічний метод для розвязування задач комбінаторної оптимізації на переставленнях ігрового типу / Н. Ю. Устьян // Динаміка наукових досліджень "2005: IV Міжнародна наук.-практ.конф. Дніпропетровськ, 20-30 червня, 2005 р. - Дніпропетровськ: Наука і освіта, 2005. - Т.27. - С. 29-31.

11. Ємець О. О. Моделювання і розвязування деяких ігрових задач комбінаторної оптимізації економічного змісту / О. О. Ємець, Н. Ю. Устьян // Економіка: Проблеми теорії і практики: Зб. наук. праць. - Дніпропетровськ: ДНУ, 2005 - Вип. 207, Т.1. - С. 82-99.

12. Емец О. А. Метод нахождения оптимальной стратегии игрока в игровых комбинаторных задачах на перестановках / О. А. Емец, Н. Ю. Устьян // Наука і освіта "2007: V Міжнар. наук.-прак. конф. Дніпропетровськ, 3-15 січня, 2007 р. - Дніпропетровськ: Наука і освіта, 2007. - Т.11. - С. 6-9.

13. Ємець О. О. Застосування різних критеріїв прийняття рішень в ігрових комбінаторних задачах на переставленнях / О. О. Ємець, Н. Ю. Устьян // Наука и образование без граница: 3-а международна научна практична конференція. София, 16-27 декабря, 2007 г. - София: "Бял ГРАД-БГ" ООД, 2007. - Т.17. - С. 17-19.

14. Ємець О. О. Ітераційний метод знаходження оптимальної стратегії гравця в ігрових комбінаторних задачах на переставленнях / О. О. Ємець, Н. Ю. Устьян // Научная индустрия европейского континента-2007: IV Міжнародна науково-практична конференція. Прага, 1-15 грудня, 2007 р. - Прага: Publishing House "Education and Science" s.r.o., 2007. - Т.15. - С. 27-30.

15. Устьян Н. Ю. Розвязування ігрових задач з комбінаторними обмеженнями на стратегії одного або обох гравців / Н. Ю. Устьян // XX Міжнародній науковій конференції імені академіка М.Кравчука. Київ, 15-17 травня, 2008 р. - Київ: ТОВ “Задруга”, 2008. - С. 834.