МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ <<ЛЬВІВСЬКА ПОЛІТЕХНІКА>> Інститут ІКНІ Кафедра автоматизовані системи управління ЗВІТ Лабораторна робота №14 З курсу “ Математичні методи дослідження операцій ”  Лабораторна робота №14 Матричні ігри та їх розв’язування в середовищі EXCEL і MATHCAD Мета роботи: набуття навиків побудови математичної моделі задачі конфліктної ситуації між двома гравцями та застосування симплекс методу для знаходження її розв’язку в середовищах Excel і MathCad. Короткі теоретичні відомості. Матричні ігри визначені як трійки Г = <x, y, H> (1) де x і y – множини, елементи яких називаються чистими стратегіями 1-го і 2-го гравців; H – функція від двох змінних x і y, яка визначає виграш 1-го гравця і називається функцією виграшу. Пара (x, y) – ситуація в чистих стратегіях. Враховуючи те, що кількість можливих дій (стратегій) кожного з гравців скінченна і рівна відповідно m і n, функцію виграшу представляють у вигляді матриці: H = || hi,j ||, i = 1, 2, ..., m, j = 1, 2, ..., n. (2) Будь-яку скінченну, антагоністичну гру можна задати дійсною матрицею (матрицею виграшів), тому вона й отримала назву матрична. Вибір 1-им гравцем стратегії i – це вибір рядка i, а вибір 2-им, стратегії j – вибір стовпця j. Виграш 1-го гравця при цьому дається елементом матриці, що стоїть на перетині i-го рядка та j-го стовпця. Матрична гра двох гравців з нульовою сумою(антагоністична гра) полягає в тому, що кожен із гравців робить один хід: І гравець вибирає свою і-ту стратегію (і = 1,2,...m), ІІ – свою j-ту стратегію (j = 1, 2, ..., n), після чого перший гравець дістає виграш
за рахунок другого гравця (якщо
< 0, то це означає, що І платить ІІ
). На цьому гра завершується. Розв’язок матричної гри шукаємо як розв’язок системи лінійних нерівностей H(X*, y) ( v при y ( y, (3) H(x, Y*) ( v при x ( x, (4) і лінійних рівнянь X = ((1, (2, ..., (m), (i ( 0,
, (5) Y = ((1, (2, ..., (n), (j ( 0,
, (6) де X*, Y* – оптимальні стратегії гравців 1-го і 2-го; v – ціна матричної гри; m, n – кількість чистих стратегій 1-го і 2-го гравців; (i і (j – ймовірності застосування гравцями своїх чистих стратегій i – 1-им і j – 2-им гравцем. Перевіркою виконання рівності
(7) встановлюємо тип оптимальних стратегій, які застосовуються гравцями. Якщо рівність виконується, то гравці застосовують свої чисті оптимальні стратегії, а якщо ні, то хоча б у одного з них стратегії будуть змішаними. Позначимо

. (8) Означення. Число (, знайдене за формулою (8), називається нижньою чистою ціною гри і показує, який мінімальний виграш може гарантувати собі перший гравець, застосовуючи свої чисті стратегії при будь-яких можливих діях другого гравця. Другий гравець при оптимальній поведінці повинен за рахунок своїх стратегій досягти максимального зменшення виграшу першого гравця. Тому для другого гравця знаходиться
, тобто максимальний виграш першого гравця при умові, що другий гравець застосує свою j – ту чисту стратегію, далі другий гравець знаходить таку свою j = j1 стратегію, при якій перший гравець отримує мінімальний виграш, тобто другий гравець знаходить
. (9) Означення. Число (, яке знайдене за формулою (9), називається чистою верхньою ціною гри і показує, який максимальний виграш за рахунок своїх стратегій може гарантувати собі перший гравець. Іншими словами, застосовуючи свої чисті стратегії, перший гравець може забезпечити собі виграш, не менший за (, а другий гравець за рахунок застосування своїх чистих стратегій може не допускати більший, ніж ( виграш першого гравця. Означення. Якщо для гри з матрицею А нижня і верхня чисті ціни гри співпадають, тобто ( = (, то кажуть, що ця гра має оптимальні чисті стратегії і чисту ціну гри: υ = ( = (. Означення. Сідлова точка – це пара чистих стратегій (i0, j0) відповідно першого та другого гравця, при яких виконується нерівність aioj ( aiojo ( aioj, (10) де i, j – будь-які чисті...