Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Програма «Технології штучного інтелекту»

Скачати 254.84 Kb.

Програма «Технології штучного інтелекту»




Скачати 254.84 Kb.
Сторінка4/5
Дата конвертації24.05.2017
Розмір254.84 Kb.
ТипПрограма
1   2   3   4   5

Задачі цілочисельного і дискретного програмування


Особливості цілочисельних задач. Цілочисельні моделі практичних задач. Загальна характеристика основних груп методів розв'язування цілочисельних задач: відсікань, комбінаторних, евристичних. Принципи побудови евристичних алгоритмів. Основні ідеї методів відсічень. Метод Гоморі. Схема методу гілок і меж та її основні структурні елементи: стратегії розгалуження, границі та їх властивості, стратегія відтинання вузлів. Булево програмування.

Динамічне програмування


Загальна постановка задачі динамічного програмування. Формалізація багатоетапної оптимізації. Основні типи задач і моделей динамічного програмування. Багатокроковий процес прийняття рішень, метод рекурентних співвідношень. Принцип оптимальності і рівняння Беллмана. Оптимальний розподіл інвестицій як задача динамічного програмування. Заміна устаткування як задача динамічного програмування.

Теорія ігор


Основні поняття теорії ігор: учасники гри, стратегії, виграші. Класифікація ігор за ознаками: кількість гравців, потужність множини стратегій;
Динамічне програмування - розділ математики, який присвячено теорії і методам розв'язання багатокрокових задач оптимального управління.
Тео́рія і́гор - теорія математичних моделей прийняття оптимальних рішень в умовах конфлікту. Оскільки сторони, що беруть участь в більшості конфліктів, зацікавлені в тому, щоб приховати від супротивника власні наміри, прийняття рішень в умовах конфлікту, зазвичай, відбувається в умовах невизначеності.
Потужність множини, або кардинальне число множини, - характеристика множин (у тому числі нескінченних), що узагальнює поняття кількості (числа) елементів скінченної множини. В основі цього поняття лежать природні уявлення про порівняння множин: Будь-які дві множини, між елементами яких може бути встановлено взаємно однозначну відповідність (бієкція), містять однакову кількість елементів (мають однакову потужність). Зворотно: множини, рівні за потужністю, мусять допускати таку взаємно однозначну відповідність. Частина множини не перевершує повної множини за потужністю (тобто за кількістю елементів).
характер взаємодії гравців, розмір виграшів, вид функції виграшів, кількість і характер ходів, інформованість.
Фу́нкція ви́грашів - функція, яка в безкоаліційній грі приписується кожному гравцю.
Загальна характеристика методів розв'язування ігор. Матричні ігри двох осіб з нульовою сумою. Означення, приклади. Оптимальні чисті стратегії. Теореми про ціну гри і максимін. Оптимальні змішані стратегії та їхні властивості. Ціна гри в змішаних стратегіях. Основна теорема матричних ігор. Геометричне розв'язування ігор розміром 2*2, 2*n, m*2. Поняття про кооперативні ігри. Біматричні ігри та положення рівноваги в біматричних іграх.

Нелінійне програмування


Класичний метод оптимізації та метод множників Лагранжа. Метод множників Лагранжа та теорія двоїстості. Необхідні й достатні умови існування сідлової точки. Теорема Куна-Такера. Квадратичне програмування. Геометричне програмування. Задачі опуклого програмування. Методи штрафних функцій. Методи одновимірної оптимізації. Чисельні методи нелінійного програмування. Метод ділення відрізка навпіл, метод золотого перерізу, градієнтні методи, метод Ньютона.

Теорія прийняття рішень


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

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

Квадратичне програмування (англ. Quadratic programming, QP) - особливий тип оптимізаційної задачі. Це задача оптимізації (зведення до мінімуму або максимуму) квадратичної функції декількох змінних при лінійних обмеженнях на ці змінні.
Неліні́йне програмува́ння (NLP, англ. NonLinear Programming) - випадок математичного програмування, у якому цільовою функцією чи обмеженнями є нелінійна функція.
Градіє́нтний спуск (англ. gradient descent) - це ітераційний алгоритм оптимізації першого порядку, в якому для знаходження локального мінімуму функції здійснюються кроки, пропорційні протилежному значенню градієнту (або наближеного градієнту) функції в поточній точці.
Кори́сність - суб'єктивна міра задоволення, що його отримує індивід від споживання блага або набору благ. Іншими словами, корисність визначає, якою мірою індивід задовольнив свої потреби, споживши певні блага.
Мéтоди обрóбки експéртної інформáції - сукупність методів для обробки отриманих результатів згідно методу експертних оцінок.
Метод аналізу ієрархій.

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

Багатокритеріальна оптимізація або програмування (англ. Multi-objective optimization), - це процес одночасної оптимізації двох або більше конфліктуючих цільових функцій в заданій області визначення.
Прийняття рішень в умовах конфлікту.

Некооперативна поведінка ізольованих гравців.

Повна та часткова інформованість гравців.

Поведінка гравців в умовах мінімальної інформованості. Змішані стратегії.



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

Контрольні запитання


  1. Етапи побудови математичної моделі в дослідженні операцій.

  2. Математична модель задачі лінійного програмування.

  3. Графічна інтерпретація та метод вирішення задачі лінійного програмування.

  4. Симплекс-метод вирішення задач лінійного програмування.

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


  6. M-задача лінійного програмування. Метод штучного базису.

  7. Двоїстість у лінійному програмуванні. Зв’язок з прямою задачею. Головні теореми двоїстості.

  8. Дослідження задач лінійного програмування на чутливість.

  9. Двоїстий симплекс-метод.

  10. Лінійне цілочисельне програмування: метод Гоморі.
    Цілочисельне програмування - різновид математичного програмування, що припускає, що шукані значення повинні бути цілими числами.


  11. Лінійне цілочисельне програмування: метод гілок і меж.

  12. Задача про найкоротший ланцюг. Алгоритм Дейкстри.

  13. Задача про багатополюсну мережу. Алгоритм Флойда.

  14. Задача про оптимальне дерево-кістяк.

  15. Транспортна задача. Метод потенціалів.

  16. Задача про призначення. Угорський алгоритм.

  17. Задача про максимальний потік. Алгоритм Форда-Фалкерсона.

  18. Динамічне програмування. Метод Беллмана. Алгоритми прямої і зворотної прогонки рішення задачі.

  19. Динамічне програмування: задача про розподіл капітальних вкладень.
    Капіта́льні вкла́дення - частина інвестицій, спрямована на відтворення основних засобів виробничого і не виробничого призначення, на створення нових, реконструкцію і розвиток наявних основних засобів, включаючи об'єкти соціальної сфери.


  20. Теорія ігор: чисті та мішані стратегії.

  21. Аналітичне і графічне вирішення задач 2x2 в теорії ігор.

  22. Нелінійне програмування: безумовна оптимізація для однієї змінної.

  23. Нелінійне програмування: безумовна оптимізація для багатьох змінних, матриця Гессе.
    Матриця Гессе - квадратна матриця елементами якої є часткові похідні деякої функції. Поняття було введене Людвігом Отто Гессе (1844), який використовував іншу назву. Термін матриця Гессе був введений Джеймсом Джозефом Сильвестром.


  24. Умовна оптимізація: метод множників Лагранжа.

  25. Чисельні методи вирішення задач нелінійного програмування.

  26. Скалярна функція вибору.

  27. Паретівська функція вибору.

  28. Сформулюйте теорему про нормальність функції вибору.

  29. Приведіть основні операції над функціями вибору.

  30. Приведіть основні властивості функцій вибору.

  31. Сформулюйте основні взаємозв’язки між функціями вибору.

  32. Описати загальну схему експертизи.

  33. Дати визначення медіани Кемені-Снела.

  34. Сформулювати правила Кондорсе і Борда.

  35. Сформулювати парадокс Ерроу.

  36. Сформулювати аксіому участі.

  37. Сформулювати теорему Гіббарта-Саттертвайта.

  38. В чому полягає метод аналізу ієрархії Сааті?

  39. Як в методі аналізу ієрархій здійснюється аналіз однорідності суджень?

  40. В чому полягає алгоритм ієрархічного синтезу?

  41. Як в методі Сааті відбувається агрегування думок експертів?

  42. Дайте визначення слабко ефективної оцінки.

  43. Дайте визначення ефективної альтернативи.

  44. Дайте визначення власне ефективної альтернативи.

  45. Сформулюйте необхідну й достатню умови слабкої ефективності альтернативи.

  46. Сформулюйте необхідну й достатню умови ефективності альтернативи.

  47. Сформулюйте необхідну й достатню умови власної ефективності альтернативи.

  48. Які ви знаєте основні типи правил вибору.

  49. Яка основна ідея методу ідеальної точки.

  50. Яка основна ідея вибору з урахуванням кількості домінуючих критеріїв.

  51. Яка основна ідея методу послідовних поступок.

Приклади задач


  1. Розв’язати наступну задачу графічним методом і симплекс-методом:



  1. Розв’язати М - задачу лінійного програмування:



  1. Для наведеного графа визначити:

  • найкоротший ланцюг з початкової вершини в кінцеву і обчислити його довжину;

  • максимальний потік з початкової вершини в кінцеву.





  1. Для нижченаведених варіантів задач розв'язати транспортну задачу. В таблицях такі позначення: ai – запаси однорідного продукту у i-го постачальника , bj – потреба в продукті j-го споживача. У комірках таблиць наведені вартості Сij перевезення одиниці вантажу від i-го постачальника j-му споживачу.



ai\bj

140

150

180

290

170

4

2

6

4

190

3

2

4

2

160

6

4

3

4

100

4

4

3

5


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

№ філії

Фінансові ресурси, млн. грн.

0

1

2

3

4

5

1

0

5

8

10

14

16

2

0

6

7

12

13

15

3

0

7

9

14

16

19

4

0

4

6

11

14

17




  1. Розв’язати аналітично і графічно задачу пошуку оптимальної стратегії для гри 2x2:




  1. Знайти за визначенням множину ефективних альтернатив у наступній двох-критеріальній задачі:



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

5.

  1. Знайти за визначенням множину слабко ефективних альтернатив у наступній двох-критеріальній задачі:



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

2.

  1. Знайти за визначенням множину власне ефективних альтернатив у наступній двох-критеріальній задачі:

.

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

.

  1. Розв’язати методом ідеальної точки (S=1) наступну багатокритеріальну задачу:



  1. Розв’язати методом послідовних поступок наступну багатокритеріальну задачу:



  1. Розв’язати методом бажаної точки наступну багатокритеріальну задачу:



  1. Розв’язати методом задоволених вимог наступну багатокритеріальну задачу:


Література


  1. Волошин О.Ф., Мащенко С.О. Моделі та методи прийняття рішень: навч. посіб. для студ. вищ. Навч. закл. – 2-е вид. доп. та перероблене.-К.:Видавничо-поліграфічний центр ”Київський університет”,-2010,-226с.

  2. Гнатієнко Г.М., Снитюк В.Є. Експертні технології прийняття рішень. Монографія.-К.: ТОВ ”Маклаут”,-2008.-444с.

  3. Дослідження операцій в економіці: Підручник / За ред. І.К.Федоренко, О.І.Черняка. − К.: Знання, 2007. − 558 с.

  4. Зайченко Ю.П. Дослідження операцій. Підручник. – К.: Видавничий дім “Слово”, 2006. - 816 с.

  5. Катренко А.В. Дослідження операцій. Підручник. – Львів: “Магнолія Плюс”, 2004. - 549 с.

  6. Катренко А.В., Пасічник В.В. Прийняття рішень: теорія і практика: Підручник. – Львів: “Новий світ – 2000”, 2013. - 447 с.

  7. Катренко А.В., Пасічник В.В., Пасько В.П. Теорія прийняття рішень: Підручник. – К.: Видавнича група BHV, 2009. - 448 с.

  8. Ржевський С.В., Александрова С.В. Дослідження операцій: Підручник – К.: Академвидав, 2006. – 560 с.

  9. Таха Хэмди, А. Исследование операций. – М.: Издательский дом “Вильямс”, 2017. – 912 с.
1   2   3   4   5


Скачати 254.84 Kb.

  • Динамічне програмування
  • Теорія ігор
  • Нелінійне програмування
  • Теорія прийняття рішень
  • Контрольні запитання
  • Приклади задач
  • Література