МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА" Інститут КНІТ Кафедра ПЗ ЗВІТ До лабораторної роботи № 5 На тему: “Ігрові задачі дослідження операцій” З дисципліни: “Дослідження операцій” Лектор: доц. каф. ПЗ [ім’я автора приховано] Львів – 2010 Тема роботи: Ігрові задачі дослідження операцій. Мета роботи: Ознайомитись із поняттям ігрових задач. Навчитись розв’язувати матричні ігри методами лінійного програмування. Теоретичні відомості В теорії ігор розглядаються ситуації, пов'язані з ухваленням рішень, в котрих двоє розумних супротивників мають конфліктуючу мету. До числа типових прикладів відносяться рекламування конкуруючих товарів і планування військових стратегій протиборчих армій. В ігровому конфлікті беруть участь два супротивники, іменовані гравцями, кожний з яких має деяку множину (скінченну або нескінченну) можливих виборів, які називаються стратегіями. З кожною парою стратегій пов'язаний платіж, який один з гравців виплачує іншому. Такі ігри відомі як ігри двох осіб з нульовою сумою, оскільки виграш одного гравця рівний програшу іншого. В такій грі достатньо задати результати у вигляді платежів для одного з гравців. При позначенні гравців через А і В з числом стратегій m i n відповідно, гру звичайно представляють у вигляді матриці платежів гравцю А:
Таке представлення матричної гри означає, що якщо гравець А використовує стратегію i, а гравець В — стратегію j, то платіж гравцю А складає аij, а гравцю В – (-аij). Рішення матричних ігор методами лінійного програмування. Теорія ігор знаходиться в тісному зв'язку з лінійним програмуванням, оскільки будь-яку кінцеву гру двох осіб з нульовою сумою можна представити у вигляді задачі лінійного програмування і навпаки. Дж. Данциг відзначає, що, коли в 1947 році творець теорії ігор Дж. фон Нейман вперше ознайомився з симплекс-методом, він відразу встановив цей взаємозв'язок і звернув особливу увагу на концепцію двоїстості в лінійному програмуванні. Оптимальні значення ймовірності xi i = 1, 2 ..., m, гравця A можуть бути визначені шляхом вирішення наступної задачі лінійного програмування:
Звідси витікає, що
Отже, задача гравця А може бути полягає у максимізації z = v при обмеженнях:
Задача гравця В є двоїстою до задачі гравця А. Це означає, що оптимальне рішення однієї із задач автоматично визначає оптимальне рішення іншої. Завдання
Розв’язати гру методами лінійного програмування і визначити виграшні стратегії. Код та результати роботи
Висновок На цій лабораторній роботі я ознайомився із поняттям ігрових задач та навчився розв’язувати матричні ігри методами лінійного програмування, використовуючи програмний засіб MathCad.