русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Основные понятия теории игр


Дата добавления: 2013-12-23; просмотров: 1240; Нарушение авторских прав


Игровые модели принятия решений

 

 

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

Под неопределенностью следует понимать отсутствие, неполноту информации об объекте, процессе, явлении или неуверенность в достоверности информации. Источниками неопределенности могут быть, например, погодные условия, противодействие противника, уровень надежности изделий, издержки при сборе и обработке информации и т.д. Достаточно частой является и такая ситуация, когда источником неопределенности является само лицо, принимающее решения (например, из-за неполной профессиональной компетентности). Во всех этих случаях говорят о возникновении ситуации риска.

Под ситуацией риска следует понимать сочетание различных обстоятельств и условий затрудняющих тот или иной вид деятельности из-за двух возможных исходов: благоприятного (выигрышного) или неблагоприятного (проигрышного). Причем, величина выигрыша или проигрыша могут быть весьма значительными.

Признаками ситуации риска являются:

· наличие неопределенности;

· необходимость выбора альтернатив (условий, которые, в общем то, невозможно не приять);

· возможность оценить вероятность осуществления выбираемых альтернатив.

С точки зрения полноты исходных данных определенность и неопределенность являются двумя крайними случаями, а риск определяет промежуточную ситуацию, в которой приходится принимать решение. Математический аппарат принятия решений в условиях риска и неопределенности представлен, в основном, в теории игр.

Игра - это совокупность правил, описывающих сущность конфликтной ситуации и возможные выходы из нее. Эти правила устанавливают:

· выбор действий игроков на каждом этапе игры;



· информацию, которой обладает каждый игрок при осуществлении выборов;

· плату для каждого игрока после завершения любого этапа игры.

В общем случае игру можно определить следующим образом:

· имеются n конфликтующих сторон (игроков), принимающих решения и, интересы которых не совпадают;

· сформулированы правила выбора допустимых стратегий, известные игрокам;

· определен набор возможных конечных состояний игры (например, выигрыш, ничья, проигрыш);

· всем игрокам заранее известны платежи, соответствующие каждому возможному конечному состоянию. Платежи задаются в виде матрицы A =aij║.

Каждый игрок имеет множество возможных стратегий. Стратегией игры называется совокупность правил, определяющих поведение игрока от начала игры до ее завершения. Стратегии каждого игрока определяют платежи в игре. Игра называется игрой с нулевой суммой, если проигрыш одного игрока равен выигрышу другого. В противном случае она называется игрой с ненулевой суммой.

Игра называется конечной, если у каждого игрока конечное число стратегий. Результаты конечной парной игры с нулевой суммой можно задавать матрицей, строки и столбцы которой соответствуют различным стратегиям, а элементы - выигрышам одной из сторон (проигрышам другой стороны). Эта матрица называется платежной матрицей.

Если первый игрок имеет m стратегий, а второй n, то говорят, что мы имеем дело с игрой m ґ n. Рассмотрим такую игру. Пусть заданы множество стратегий: для первого игрока {A i}, для второго игрока {Bj}, платежная матрица A m ґ n = aij, где aij - выигрыш первого игрока при выборе стратегий Ai и проигрыш второго - при выборе стратегии Bj. Поскольку интересы игроков противоположны, то первый стремиться максимизировать свой выигрыш, а второй - минимизировать свой проигрыш. Если игроки оба умны, то им целесообразно использовать очень пессимистичный критерий, что позволит им свести к минимуму выигрыш (проигрыш). Величина этого минимума

 

αi=min a ij,i= 1,…, m.

j

Первый игрок (при любых ответах противника) будет стремиться найти такую стратегию, при которой αi обращается в максимум

α=max αi =max min a ij.

i i j

Величина α называется нижней ценой игры. Ей соответствует максиминная стратегия, при которой первый игрок обеспечит себе выигрыш не меньше α. Величина αявляется гарантированным выигрышем первого игрока при любых стратегиях второго игрока.

Аналогично определим по каждому столбцу матрицы βj=max aij,j= 1,…,n, найдем минимальное значение βj

β=min βj=min max a ij.

j j i

Величина βназывается верхней ценой игры. Ей соответствует минимаксная стратегия второго игрока. Величинаβпредставляет собой гарантированный проигрыш второго игрока при любой стратегии первого игрока. Если α=β (то есть верхняя цена игры равна нижней цене), то соответствующие стратегии называют оптимальными, а про игру говорят, что она имеет седловую точку. Седловая точка является минимальным элементом соответствующей строки и максимальным элементом соответствующего столбца. Величина C = β=αназывается ценой игры. Она определяет средний выигрыш игрока А и средний проигрыш игрока В при использовании ими оптимальных стратегий.

Если в платежной матрице А все элементы строки A i = (ai1,ai2,…, ain) не меньще соответствующих элементов строки A k=(ak1,ak2,…,akn), и по крайней мере один больше, то строка A i называется доминирующей, а строка A k - доминируемой. Аналогичны понятия «доминирующий столбец» и «доминируемый столбец». Первому игроку невыгодно применять стратегии, которым соответствуют доминируемые строки; второму игроку невыгодно применять стратегии, которым соответствуют доминирующие столбцы. Поэтому при решении игры можно уменьшить размеры платежной матрицы путем удаления из нее доминирующих столбцов и доминируемых строк.

Отдельные игры могут не иметь седловых точек, то есть у каждого игрока не существует единственной, наиболее надежной стратегии. В этом случае используют смешанную стратегию. Ее суть в том, что в ходе игры происходит случайный выбор стратегии из некоторого множества смешанных стратегий и для каждой смешанной стратегии имеется вероятность ее выбора.

Смешанная стратегия для игрока А представляет собой вектор P= {p1,p2,…,pm}, а смешанная стратегия для игрока В представляет собой вектор Q= {q1,q2,…,qn}, где pi,qj - вероятность выбораi-ой (j-ой) стратегии первым (вторым) игроком. Сумма каждой из этих вероятностей должна быть равна 1. В этом случае платежная матрица игры имеет вид (таблица 8.1)

 

Таблица 8.1

А\В q1 q2 q3 qn
p1 a11 a12 a13 a1n
p2 a21 a22 a23 a2n
p3 a31 a32 a33 a3n
pm am1 am2 am3 amn

Игрок А выбирает стратегию pi так, чтобы максимизировать наименьший ожидаемый выигрыш по столбцам платежной матрицы, тогда как игрок В выбирает стратегию qj с целью минимизировать наибольший ожидаемый проигрыш по строкам. Математически при смешанных стратегиях это описывается следующим образом.

Игрок А выбирает стратегию pi, дающую

 

m m m

max{min(∑ai1∙pi,∑ai2∙pi,…,∑ain∙pi)},

pi i=1 i=1 i=1

 

а игрок В выбирает стратегию qj, дающую

n n n

min{max(∑a1j∙qj,∑a2j∙qj,…,∑amj∙qj)}.

qi j=1 j=1 j=1

 

Когда стратегии p*i и q*j оптимальны, то выполняется строгое равенство между максиминным ожидаемым выигрышем и минимаксным проигрышем, а результирующее значение равно оптимальному (ожидаемому) значению игры:

 

m n

M(p*i, q*j) = ∑ ∑aij∙p*i ∙q*j.

i=1 j=1

Рассмотренные варианты теории игр могут служить основой для эффективного управления системами и процессами.



<== предыдущая лекция | следующая лекция ==>
Понятия о динамическом программировании | Принятие решений в условиях полной определенности


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.008 сек.