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

1 2 3 4 5

Приклад 2.

за умов

Для того щоб вирішити задачу, достатньо вирішити двоїсту задачу до неї, яка має вигляд

за умов

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

· Сформулюйте параметричну задачу, параметр якої присутній у функції цілі.

· Дайте економічну інтерпретацію задачі параметричного програмування.

· Сформулюйте параметричну задачу, параметр якої присутній у системі обмежень.

· Вкажіть на взаємозв’язок параметричної задачі та стійкості рішень задачі ЛП.

· Вкажіть взаємозв’язок параметричної задачі на чутливість рішень задачі ЛП.

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

Лекція 13.

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

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

План лекції

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

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

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

Література:

1. Лавріненко Н.М., Латинін С.М., Фортуна В.В., Безкровний О.І. Основи економіко-метематичного моделювання: Навч. Посіб. - Львів: «Магнолія 2006», 2010.- 540с.

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

3. Кучма М. І. Математичне програмування: приклади і задачі: Навчальний посібник / М.І. Кучма. – Львів: «Новий Світ - 2000», 2006. - 344 с.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нехай х₁ – ймовірність вибору 1-ої стратегії;

х₂ - ймовірність вибору 2-ої стратегії;

…………………………………………………

x_m - ймовірність вибору m-ої стратегії.

Означення 1. Мішаною стратегією гравця А називається упорядкований набір m чисел х₁, х₂, ….., x_m, які задовольняють умовам: 0≤x_i≤1, i= =1.

Мішані стратегії гравців А та В позначають =(x₁,x₂, …, x_m), =(y₁,y₂,…,y_n).

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

Теорема. О методі знаходження рішення.

Для того, щоб число ν було ціною гри, а Х^* та Y^* - оптимальними стратегіями, необхідно та достатньо, щоб виконувались умови:

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

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

Розглянемо гру з платіжною матрицею 2х2: A=.

Якщо сідлової точки нема, рішення гри є мішані стратегії =(х₁,х₂) та =(y₁,y₂) стратегії гравців А та В, для котрих ймовірністі x_i y_i відмінні від нуля, звуться активними.

Стратегію гравця А шукаємо по формулі ХА=, де Х=(х₁,х₂), =(ν, ν).

До даної системи рівнянь додаємо норміровочне рівняння х₁+х₂=1.

Для гравця В:

де Y=, =.

Розв’язавши систему рівнянь знайдемо оптимальні стратегії гравців та ціну гри ν.

Наслідок. Для того, щоб х^*, була оптимальною мішаною стратегією матричнох гри з матрицею А та ціною гри ν, необхідно та достатньо, щоб виконувались наступні нерівності:

Аналогічно для гравця В: Для того, щоб у^* була оптимальною мішаною стратегією матричної гри з матрицею А та ціною гри ν, необхідно та достатньо, щоб виконувались наступні нерівності:

Таким чином, для розв’язування гри необхідно визначити стратегії, що задовольняють вишенаведані системи обмежень та умови нормування:

0, =1, i=, , =1, j=.

Цей наслідок дозволяє сформулювати для розв’язання гри пару задач лінійного програмування.

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

Лекція 14.

Тема лекції: Матричні ігри (продовження)

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

План лекції

4. Графічний метод розв’язання задач теорії ігор.

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

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

Література:

3.Кучма М. І. Математичне програмування: приклади і задачі: Навчальний посібник / М.І. Кучма. – Львів: «Новий Світ - 2000», 2006. - 344 с.

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

4. Графічний метод розв’язання теорії ігор.

Графічний метод можна застосовувати до ігор, в яких хоча б один гравець має тільки дві стратегії, тобто до ігор 2xn i mx2.

Основні етапи розв’язку ігор 2xn i mx2:

· Будуємо прямі, що відповідають стратегіям другого (першого) гравця.

· Визначаємо нижню (верхню) межу виграшу.

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

· Визначаємо ціну гри і оптимальні стратегії.

Приклад 3. Знайти розв’язок гри заданої матрицею

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

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

j=, x_i≥0, =1, i=за умов ν→Мах.

Перетворимо цю задачу, здійснивши підстановку p_i=, і отримаємо

→Min,тому що ν→Мах.

Таким чином, маємо задачу ЛП, розв’язуючи яку, отримаємо значення p_i, за допомогою яких шляхом оберної підстановки визначимо оптимальні значення ймовірностей, що складають оптимальну мішану стратегію.

А здійснивши підстановку q_j=і враховуючи, що гравець В прагне мінімізувати програш, отримаємо пару двоїстих задач ЛП, розв’язання яких дозволить визначити оптимальні стратегії гравців А та В:

Таким чином, процедура розв’язування гри двох осіб є наступною:

1. Розраховуємо нижню та верхню ціну гри; якщо вони рівні між собою, то гра розв’язана.

2. Спрощуємо гру шляхом виключення домінованих стратегій.

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

4. За розв’язком прямої задачі знаходимо розвязок двоїстої задачі.

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

Приклад 4. Підприємство виготовляє три види продукції А₁, А₂, А₃, отримуючи при цьому прибуток, що залежить від попиту. Попит може перебувати в одному з чотирьох станів В₁, В₂, В₃, В₄. Прибуток підприємства, який отриманий при виготовленні кожного виду продукції в залежності від попиту, наведено у таблиці 1. Визначити оптимальні обсяги виготовлення продукції, що гарантують середню величину прибутку при будь-якому попиті, вважаючи його невизначеним.

Таблиця 1.

	В₁	В₂	В₃	В₄
А₁
А₂
А₃

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

Якщо пряма задача ЛП має вигляд:

за умов

то матрична гра визначається платіжною матрицею порядку вигляду:

де А – матриця коефіцієнтів при невідомих системи обмежень задачі ЛП; В – матриця вільних членів; С – матриця коефіцієнтів при невідомих цільової функції, індекс Т означає операцію транспонування.

Якщо задача ЛП має вигляд:

за умов

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

Зауважемо, що якщо кожна матрична гра має оптимальні стратегії, то не всяка задача ЛП має розв’язки.

Приклад 5. Побудувати гру задану задачею ЛП:

за умов

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

· Дайте визначення гри двох осіб з нульовою сумою.

· Дайте визначення сідловок точки.

· Дайте визначення середнього виграшу.

· Що таке чиста стратегія?

· що таке мішана стратегія?

· Що таке домінована стратегія?

· Сформулюйте основну теорему теорії ігор для двох осіб.

· Як звести задачу теорії ігор до задачі ЛП?

· Як звести задачу ЛП до задачі теорії ігор?

Тема 7. Нелінійні оптимізаційні моделі економічних систем

Лекція 15.

Тема лекції: Задача дробово-лінійного програмування

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

План лекції

1. Постановка задачі дробово-лінійного програмування.

2. Приведення задачі дробово-лінійного програмування до задач ЛП.

3. Розв’язання задач дробово-лінійного програмування.

4. Графічне розв’язання задачі дробово-лінійного програмування.

Література:

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

1. Постановка задачі дробово-лінійного програмування.

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

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

Загальна постановка задачі дробово-лінійного програмування записується так:

Знайти такі значення змінних , які задовольняють системі обмежень:

(1)

умовам

(2)

при яких цільова функція

(3)

досягає максимуму (мінімуму).

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

2. Приведення задачі дробово-лінійного програмування до задачі лінійного програмування.

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

Таке позначення знаменника означає, що у задачі зявиться нове обмеження

, (4)

або

(5)

Цільова функція тепер має вид

(6)

Всі обмеження (1) помножимо на та одержимо

(7)

Введемо нові змінні

(8)

які будуть мати той жен знак, що й x_j, тому що . Тоді в нових змінних задача (1)-(3) записується у виді:

(9)

, (10)

(11)

(12)

Нагадоємо, що (11) – це нове обмеження, що з’явилося внаслідок підстановки.

У нових змінних t_j задача (9)-(12) уже є задачею лінійного програмування. Звернемо увагу на те, що хоча в початковому вигляді (1) задача записана в канонічному вигляді, це ніяк не обмежує області застосування підстановки, а просто означає, що перед підстановкою (4) систему треба приготувати до розв’язання, тобто вести додаткові змінні й, якщо потрібно, штучні, як того вимагає стандартна схема застосування симплексного методу.

3. Розв’янання задач дробово-лінійного програмування.

Розв’янання задачі дробово-лінійного програмування проілюструємо на конкретному прикладі.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: