Зведення матричної гри до задачі лінійного програмування icon

Зведення матричної гри до задачі лінійного програмування




Скачати 90.57 Kb.
НазваЗведення матричної гри до задачі лінійного програмування
Дата30.11.2012
Розмір90.57 Kb.
ТипДокументи

Зведення матричної гри до задачі лінійного програмування

М.В. Медвідь, студентка*

Національний університет біоресурсів і природокористування України

Викладено зведення матричної гри до задачі лінійного програмування, приклад розв’язку різними методами

Актуальність теми дослідження. У статті обґрунтовується можливість застосування математичного апарату теорії ігор для задач лінійного програмування розроблено алгоритм .

Аналіз останніх досліджень. Теорія ігор вперше була систематично викладена Нейманом і Моргенштерном та оприлюднена лише 1944 року в монографії «Теорія ігор і економічної поведінки», хоча окремі результати були опубліковані ще в 20-х роках. Нейман і Моргенштерн написали оригінальну книгу, яка містила переважно економічні приклади, оскільки економічні задачі простіше за інші описати за допомогою чисел. Під час другої світової війни і одразу після неї теорією ігор серйозно зацікавились військові, які одразу побачили в ній математичний апарат для дослідження стратегічних проблем і підготовки рішень. Потім головна увага знову була звернута до економічних проблем. Нині сфера застосування теорії ігор значно розширилась. Так, у соціальних науках апарат теорії ігор застосовується у психології для аналізу торгових угод та переговорів, а також для вивчення принципів формування коаліцій тощо.

^ Метою даної роботи є розгляд зведення матричної гри до задачі лінійного програмування.

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


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

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

Допустимо, що гравець А застосовує свою оптимальну стратегію, а гравець В - свою «чисту» -ту стратегію , тоді середній виграш гравця А дорівнюватиме:

. (8.5.1)

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



Розділивши всі обмеження на , отримаємо:



Позначивши , маємо :

, .

Враховуючи умову, що отримуємо .

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

Цільова функція: за умов

, .

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

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

, .

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

Задачі теорії ігор належать до задач прийняття рішень за умов невизначеності та ризику.

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

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

Задача 8.5.1. Знайти розв’язок гри, яка задається матрицею:

.

Розв’язання. Складемо двоїсту пару задач лінійного програмування:

    1. пряма задача: знайти максимум функції за умов



    1. двоїста задача: знайти мінімум функції за умов



Знаходимо оптимальні плани прямої та двоїстої задач (табл. 8.5.1).

Таблиця 8.1.5.


і


Базис


Сб


Р0

1

1

1

0

0

0

Р1

Р2

Р3

Р4

Р5

Р6

1

Р4

0

1

1

2

0

1

0

0

2

Р5

0

1

1

0

1

0

1

0

3

Р6

0

1

2

1

0

0

0

1




0

-1

-1

-1

0

0

0

1

Р4

0

1

1

2

0

1

0

0

2

Р3

1

1

1

0

1

0

1

0

3

Р6

0

1

2

1

0

0

0

1




1

0

-1

0

0

1

0

1

Р2

1





1

0



0

0

2

Р3

1

1

1

0

1

0

1

0

3

Р6

0





0

0

-

0

1








0

0



1

0


З даної таблиці видно, що вихідна задача має оптимальний план , а двоїста задача – оптимальний план . Отже ціна гри , а оптимальні стратегії гравців .

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

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


Список використаної літератури

  1. Наконечний С.І. Математичне програмування / С.І. Наконечний. К.:Вид-во Європейського ун-ту, 2010. 254 с.

  2. Василевич Л.Ф. Теория игр. Уч. Пособие. – Киев: КИИМ.,2000. –98 с.

  3. Василевич Л.Ф. Анализ чувствительности и стабильности нечётких систем. \\ Кибернетика и системный анализ. – 1998. – №1. – С. 166- 171.







Схожі:

Зведення матричної гри до задачі лінійного програмування iconКонтрольні питання
Теорема про активні стратегії. Зведення матричних ігор (2 Х n), (m Х 2) до матричної гри (2 Х 2)
Зведення матричної гри до задачі лінійного програмування iconКонтрольные вопросы по курсу "Исследование операций и теория игр"
Теорема про активні стратегії. Зведення матричних ігор (2 Х n), (m Х 2) до матричної гри (2 Х 2)
Зведення матричної гри до задачі лінійного програмування iconКонтрольные вопросы по дисциплине "Исследование операций и теория игр" Утвержден на заседании кафедры высшей математики и информатики
Теорема про активні стратегії. Зведення матричних ігор (2 Х n), (m Х 2) до матричної гри (2 Х 2)
Зведення матричної гри до задачі лінійного програмування iconПитання на екзамен з дисципліни «Економіко математичне моделювання». Модуль «Математичне програмування»
Перша стандартна форма задачі лп. (Основна задача лінійного програмування з обмеженнями-рівностями)
Зведення матричної гри до задачі лінійного програмування iconЗавдання І. Вирішить графічно наступні задачі лінійного програмування

Зведення матричної гри до задачі лінійного програмування icon3. Транспортна задача лінійного програмування Формолювання задачі
Транспортна задача представляє собою задачу лп, котру можно вирішувати симплекс-методом. Але специфічна структура умов задачі дозволяє...
Зведення матричної гри до задачі лінійного програмування icon3. Транспортна задача лінійного програмування Формулювання задачі
Транспортна задача представляє собою задачу лп, котру можно вирішувати симплекс-методом. Але специфічна структура умов задачі дозволяє...
Зведення матричної гри до задачі лінійного програмування icon2. Двоїста задача лінійного програмування Тема Транспортна задача
Операція, основні поняття І якості. Прямі та зворотні задачі. Управління операцією, оцінка якості. Математичні моделі операцій. Допустимі...
Зведення матричної гри до задачі лінійного програмування icon“Економіко-математичне моделювання”, ек-09, 2010/2011 н р
...
Зведення матричної гри до задачі лінійного програмування iconЗадача динамічного програмування. Загальний випадок
Але у відмінності від лінійного програмування динамічне програмування не зводиться до якийсь стандартної обчислювальної процедури;...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи