Питання для самоконтролю.

1. Сформулюйте задачу дробово-лінійного програмування.

2. Сформулюйте задачу цілочисельного програмування.

3. Напішить рівняння Гоморі.

4. Сформулюйте загальну задачу НП.

5. Сформулюйте задачу сепарабельного програмування.

6. Сформулюйте задачу квадратичного програмування.

7. Сформулюйте задачу опуклого програмування.

8. Поясніть метод множників Лагранжа.

9. Сформулюйте означення сідловок точки функції Лагранжа.

10. Сформулюйте теорему Куна-Такера.

11. Сформулюйте означення додатньо-визначеної квадратичної форми.

12. Сформулюйте означення додатньо-напіввизначеної квадратичної форми.

Тема 7. Елементи теорії ігор

Лекція 7.

Тема лекції: Матричні ігри

Мета: ознайомити студентів з методами розв’язання задач теоріі ігор та зведення їх до задач ЛП.

План лекції

1. Постановка задач теорії ігор з нульовою сумою.

2. Задачі з сідловою точкою. Задачі в чистих стратегіях.

3. Ігри в мішаних стратегіях.

4. Зведення задач теорії ігор до задач ЛП.

Література:

1. Акулич и.Л. Математическое программирование в примерах и задачах. – м.: Высшая школа, 1993. – 336 с.

2. Іванюта і.Д. Практикум з математичного програмування: Навчальний посібник/ і.Д. Іванюта, в.І. Рибалка, і.А. Рудоміра – Дусятська. – к. : «Слово», 2008. – 296 с.

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

1. Постановка задач теорії ігор з нульовою сумою.

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

В 1944 році з’явилася математична дисципліна – теорія ігор, основою для якої стала монографія американського економіста Неймана.

Теорія ігор – це теорія математичної моделі конфліктних ситуацій, інтереси гравців котрих різні і кожний з них досягає своєї цілі (мети) різними шляхами.

Результат гри є виграшем для одних і програшем для других.

Означення 1. Модель любої конфліктної ситуації зветься грою.

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

Означення 3. гра зветься парною, якщо в ній беруть участь дві сторони.

Означення 4. Кількісна оцінка результатів гри зветься платою.

Означення 5. Парна гра зветься грою з нульовою сумою, якщо програш одного є виграшем іншого.

Означення 6. стратегія гравця називається оптимальною, якщо при повторенні гри вона забезпечує гравцю максимально можливий середній виграш (або теж само- мінімально можливий середній програш).

2. Задачі з сідловою точкою. Задачі в чистих стратегіях.

Розглянемо парну гру:

Приклад 1.Задана платіжна матриця А парної гри з нульовою сумою: А= . Знайти ціну гри, сідлову точку гри.

Приклад 2. .Задана платіжна матриця А парної гри з нульовою сумою: А= . Знайти верхнью та нижню ціну гри.