Диссертации и авторефераты Украины
Перейти на каталог
Каталог диссертаций

Я ищу:
Диссертация / Автореферат

Диссертационная работа:

Устьян Наталія Юріївна. Задачі комбінаторної оптимізації ігрового типу : Дис... канд. наук: 01.05.01 - 2009.

Скачать диссертацию *

* Ссылка размещена на правах рекламы



Аннотация к работе:

Устьян Н.Ю. Задачі комбінаторної оптимізації ігрового типу. – Рукопис.

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

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

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

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

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

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

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

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

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

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

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

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

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


Меню
Реклама



2006-2009 © Диссертации и авторефераты Украины