Знайдіть оптимальне рішення задачі лінійного програмування за допомогою «Поиск решения» MS Exсel.

4. Знайдіть розв’язок ігрової задачі.

5. Опишіть отримане рішення.

 

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

В ігровому конфлікті беруть участь два супротивники, іменовані гравцями, кожний з яких має деяку множину (кінцеве або нескінченне) можливих виборів, які називаються стратегіями. З кожною парою стратегій пов'язаний платіж, який один з гравців виплачує іншому. Такі ігри відомі як ігри двох осіб з нульовою сумою, оскільки виграш одного гравця рівний програшу іншого. В такій грі достатньо задати результати у вигляді платежів для одного з гравців. При позначенні гравців через А і В з числом стратегій т і п відповідно гру звичайно представляють у вигляді матриці платежів гравцю А:

Таке представлення матричної гри означає, що якщо гравець А використовує стратегію i, а гравець В – стратегію j, то платіж гравця А складає і, отже, гравця В - .

Звичайно вибір критерію в задачах прийняття рішень значною мірою визначається наявною інформацією. Ігри являють собою граничний випадок повної відсутності інформації, коли розумні супротивники знаходяться в стані конфлікту. У силу цього для рішення гри двох осіб з нульовою сумою звичайно пропонується дуже «песимістичний» критерій, так називаний критерій мінімаксу - максиміну.

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

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

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

Оптимальна змішана стратегія А визначається умовами

m m m

max { min ( å a_i1 x_i , å a_i2 x_i , . . ., å a_in x_i) },

x_i i=1 i=1 i=1

x₁+x₂+...+x_m=1, x_i ³0,i1, 2, ..., m.

Ця задача може бути сформульована у виді задачі лінійного програмування. Нехай

m m m

v=min ( å a_i1 x_i , å a_i2 x_i , . . ., å a_in x_i ).

i=1 i=1 i=1

Тоді задача приймає вид максимізувати z=v

при обмеженнях

m

å a_ij x_{i ³} v, i=1, 2, ..., n,

i=1

å x_i =1, x_i ³0 для всіх i,

i=1

де v є значенням гри.