2.2. Елементи теорії ігор. Матрична гра

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

Якщо перший гравець застосовує і-ту стратегію, а другий - j-ту стратегію, то виграш першого гравця відповідає елементу матриці А:

.

Кожна стратегія гравця називається чистою стратегією.

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

Якщо виконується умова

,

то буде чистою оптимальною стратегією першого гравця, a - другого гравця; причому - чиста ціна гри. Двійка називається сідловою точкою, - сідловим елементом. Разом вони утворюють розв'язок гри.

Не кожна гра має розв'язок у чистих стратегіях. Тому вводиться поняття змішаних стратегій. На відміну від перших останні визначаються законом розподілу ймовірностей. Це означає, що рядкам відповідає розподіл ймовірностей

а стовпчикам розподіл ймовірностей

При змішаних стратегіях розв'язок гри існує завжди.

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

Приклад 4.

Знайти розв'язок гри, заданої матрицею:

Розв'язання. Визначимо сідлову точку в чистих стратегіях, яка є гарантом розв'язку.

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

.

Переходимо до постановки задачі в змішаних стратегіях. Позначимо через і , відповідно, змішані стратегії першого і другого гравця, , а через V - ціну гри.

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

Аналогічно для другого гравця

Застосувавши цю теорему до нашої задачі, маємо:

Ці системи можна розв'язувати як разом, так і окремо.

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

Аналогічно чинимо з другою системою:

.

Таким чином отримаємо розв’язок гри в змішаних стратегіях

.

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

2.3. Метод множників Лагранжа

Нехай потрібно розв'язати таку задачу нелінійного програмування:

Розв'язок цієї задачі методом множників Лагранжа включає такі етапи:

1. Складають функцію Лагранжа.

2. Знаходять частинні похідні від функції Лагранжа за змінними і та прирівнюють їх до нуля.

З. Розв'язуючи отриману систему рівнянь, знаходять точки, в яких цільова функція може мати екстремум.

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

Приклад 5.

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

Розв'язування.

Математична постановка задачі:

Складаємо функцію Лагранжа

обчислюємо її частинні похідні за і і прирівнюємо їх до нуля:

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

Через те, що і , то це точка мінімуму.

Отже, якщо перший цех виготовить 180 телевізорів, а другий цех – 120 телевізорів, то загальні витрати будуть мінімальними і складатимуть 109200 млн гривень.