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

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

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ КІБЕРНЕТИКИ ІМ. В.М. ГЛУШКОВА

01.05.01 Теоретичні основи інформатики та кібернетики

УДК 519.85

Автореферат

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

ЗАДАЧІ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ ІГРОВОГО ТИПУ

УСТЬЯН НАТАЛІЯ

ЮРІЇВНА

Київ - 2009

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

Робота виконана в Полтавському університеті споживчої кооперації України

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

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

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

Інститут кібернетики ім. В.М. Глушкова НАН України, завідувач відділу економічної кібернетики доктор фізико-математичних наук Ляшенко Ігор Миколайович,

Київський Національний Університет ім. Тараса Шевченка, професор кафедри математичної інформатики.

Захист відбудеться 24.04.2009 р. о 14 годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М. Глушкова НАН України за адресою: 03680 МСП Київ 187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися у науково-технічному архіві Інституту кібернетики імені В.М. Глушкова НАН України

Автореферат розісланий 22.03. 2009 р.

Учений секретар спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась на кафедрі математичного моделювання та соціальної інформатики Полтавського університету споживчої кооперації України згідно з індивідуальним планом аспірантської підготовки та планами науково-дослідної роботи університету, бюджетна тема № 213/04 „Евклідова комбінаторна оптимізація”.

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

Дана мета конкретизується в таких задачах:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вірогідність і обґрунтованість одержаних результатів обумовлюється коректним математичними доведеннями теорем.

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

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

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

[3, 7-9]: побудова моделей розглянутих задач як задач комбінаторної оптимізації ігрового типу з переставними обмеженнями на стратегії одного або обох гравців, розробка графічного методу розв'язування задач комбінаторної оптимізації ігрового типу вимірностей та доведення теорем про еквівалентність моделей задач комбінаторної оптимізації ігрового типу з переставними обмеженнями на стратегії одного гравця парі задач оптимізації, дослідження можливості застосування відомих методів для розв'язування цих задач;

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

[5, 14]: розробка ітераційного методу, знаходження оптимальної стратегії гравця, на стратегії якого накладаються комбінаторні обмеження, в задачах комбінаторної оптимізації на переставленнях;

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

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

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

· VII, VIII Міжнародних науково-практичних конференціях «Наука і освіта» (Дніпропетровськ, 2004, 2005 рр.);

· ІV Міжнародній науково-практичній конференції "Динаміка наукових досліджень '2005" (Дніпропетровськ, 2005 р.);

· XIV Міжнародній конференції “Проблемы теоретической кибернетики”, присвяченій 80-річчю з дня народження С.В.Яблонського (м.Пенза, 2005 р.);

· V Міжнародній науково-практичній конференції "Наука і освіта '2007" (Дніпропетровськ, 2007 р.);

· ІІІ Міжнародній науково-практичній конференції "Наука и образование без граница" (София, 2007 р.);

· ІV Міжнародній науково-практичній конференції "Научная индустрия европейского континента-2007" (Прага, 2007 р.);

· XX Міжнародній науковій конференції імені академіка М.Кравчука. (Київ, 2008 р.);

· Наукових семінарах відділу математичного моделювання та геометричного проектування Інституту проблем машинобудування НАН України (м. Харків, 2007 р., керівник - доктор технічних наук, член-кореспондент НАН України Ю.Г.Стоян);

· Науковому семінарі в Інституті кібернетики НАН України (м. Київ, 2008 р., керівник - доктор фізико-математичних Г.О. Донець);

· Науковому семінарі кафедри системного аналізу і теорії оптимальних рішень Київського національного університету імені Т.Шевченка (м. Київ, 2008., керівник - доктор фізико-математичних О.Г. Наконечний).

Публікації. Основні результати дисертації опубліковано у 15 наукових працях, серед яких 6 статті в наукових фахових журналах, 1 стаття - в збірнику наукових праць, 8 - в збірниках матеріалів та тез доповідей міжнародних конференцій.

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

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

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

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

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

-вибіркою називається -елементна підмультимножина мультимножини . Розглянемо упорядковану -вибірку ()

з мультимножини , де .

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

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

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

Нехай елементи мультимножини впорядковані за не спаданням

Опуклою оболонкою загальної евклідової комбінаторної множини переставлень є, як відомо, загальний переставний многогранник :

;

 при умові (2).

Розглянемо наступну систему однорідних нерівностей:

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

Як відомо, якщо () - фундаментальна система розв'язків системи лінійних нерівностей

рангу над простором і - довільна лінійна нерівність над то ті елементи для яких і ті елементи

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

Якщо таких елементів не існує, то остання не має фундаментальних розв'язків.

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

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

Знайти оптимальні стратегії гравців і де

· знаходиться з виразу

· - з виразу

· функція має вигляд

· - задані числа;

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

2.

 може бути наступного вигляду:

1:

2:

3:

може бути наступного вигляду:

1:

2:

3:

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

Розглянемо систему нерівностей

яка є підсистемою системи (3), що описує переставний многогранник.

Теорема 1. Вершини переставного многогранника є фундаментальними розв'язками системи нерівностей (8).

Теорема 2. Ці фундаментальні розв'язки системи (8) суттєво різні.

Теорема 3. Крім вершин переставного многогранника інших фундаментальних розв'язків система нерівностей (8) не має.

Виходячи з доведених теорем випливає, що вершини переставного многогранника утворюють фундаментальну систему розв'язків системи (8), доведено, що це справедливо і для системи (3).

Теорема 4. Довільний розв'язок системи (3) виражається формулою де - довільні невід'ємні елементи поля а - вершини переставного многогранника (3).

Теорема 5. Суміжні вершини переставного многогранника перетворюють в рівності нерівності системи (8) з лінійно незалежними лівими частинами, і ніякі інші фундаментальні розв'язки цієї системи не перетворюють в рівності ці нерівності. Будь-які несуміжні вершини перетворюють в рівність не більш, ніж нерівності системи (8) з лінійно незалежними лівими частинами.

Нехай

Теорема 6. Елементи вигляду (9) будуть фундаментальними розв'язками системи нерівностей (7), несуттєво різними для (6) тому при переході від системи нерівностей (5) до (7) замість елементів в фундаментальну систему нової системи нерівностей (7) можна включати

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

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

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

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

2. При переході від таблиці до в таблиці в рядках рівноваги в стовпцях, що відповідають , елементи будуть дорівнювати 0, якщо обидва відповідних елементи припустимих рядків дорівнюють 0; і 1 - в протилежному випадку.

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

Теорема 7. Модель: Знайти оптимальні стратегії гравців і

· знаходиться з виразу

· - з виразу

· функція має вигляд

· - задані числа;

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

1. задовольняє умовам

2. задовольняє умовам

- еквівалентна такій парі задач оптимізації. Перша з них є задачею евклідової комбінаторної оптимізації на переставленнях: знайти



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

друга - це ЗЛП: знайти

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

Теорема 8. Модель: Знайти оптимальні стратегії гравців і

· знаходиться з виразу

· - з виразу

· функція має вигляд

· - задані числа;

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



вектор задовольняє умовам

1. задовольняє умовам

еквівалентна двом задачам оптимізації. Перша з них має вигляд: Знайти

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

Друга задача має вигляд: знайти

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

Теорема 9. Модель: Знайти оптимальні стратегії гравців і

· знаходиться з виразу

· - з виразу

· функція має вигляд

· - задані числа;

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

1.

вектор задовольняє умовам

2. задовольняє умовам

еквівалентна двом задачам оптимізації. Перша з них має вигляд: Знайти

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

Друга задача має вигляд: знайти

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

Якщо то (10) має вигляд:

Метод розв'язування задачі (11):

1. Обчислимо

.

Впорядкуємо коефіцієнти при фіксованих і елементи множини по зростанню: отримані елементи позначимо і відповідно. Тоді

і

2. Спочатку вибираємо

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

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

4. Для знаходимо і Величині привласнюємо ,

5. Нехай

6. Перевіряємо умову Якщо ця умова виконується, то переходимо на крок 9, якщо ні - на крок 7.

7. Розв'язуємо лінійну, умовну, повністю комбінаторну задачу комбінаторної оптимізації на переставленнях:

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

8. Для точки знаходимо значення і Присвоюємо величині значення Збільшуємо на 1, переходимо на крок 6.

9. - розв'язок вихідної задачі.

Ітераційний метод знаходження оптимальної стратегії в моделі 1:

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

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

ВИСНОВКИ

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

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

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

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: VIIІ Міжнародна науково-практична конференція. Дніпропетровськ, 7-21 лютого, 2005 р. - Дніпропетровськ: Наука і освіта, 2005. - Т. 22. - С. 26-31.

10. Устьян Н. Ю. Модифікований графічний метод для розв'язування задач комбінаторної оптимізації на переставленнях ігрового типу / Н. Ю. Устьян // Динаміка наукових досліджень '2005: ІV Міжнародна наук.-практ.конф. Дніпропетровськ, 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: ІV Міжнародна науково-практична конференція. Прага, 1-15 грудня, 2007 р. - Прага: Publishing House "Education and Science" s.r.o., 2007. - Т.15. - С. 27-30.

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

АНОТАЦІЇ

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

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

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

Ключові слова: комбінаторна оптимізація, оптимальні стратегії гравців, системи лінійних нерівностей.

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

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

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

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

Ustyan N.Yu. The combinatorial optimization problems of the game type. - Manuscript.

Thesis for a candidate degree on physics and mathematics (Ph.D.) by speciality 01.05.01 - theoretical bases of informatics and cybernetics. - V.M.Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, Kiev, 2008.

The mathematical models of the combinatorial optimization problems of the game type are investigated. The properties of points of the permutation polyhedron are proved. The modification of Chernikova's method for finding the general formula of the solutions of the system of the linear inequalities which describes the permutation polyhedron with the additional linear inequalities is done. The graphical method for solving the combinatorial optimization problems of the game type with the dimension and is created. The theorems about the equivalence of three models of the combinatorial optimization problems of the game type and two optimization problems are proved. Two methods for finding of the optimal strategy of the player which has the combinatorial restrictions which are determined by the permutations are created.

Key words: combinatorial optimization, optimal strategies of the players, system of the linear inequalities.

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

...