Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Задачи теории игр




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

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

Первые работы по теории игр относятся к началу ХХ века. Основателем теории игр является американский математик Дж. фон Нейман, который в 1928 году доказал основополагающую теорему теории игр – теорему о минимаксе. Бурное развитие теория игр получила после выхода в свет в 1944 году книги Дж. фон Неймана и О. Моргенштерна «Теория игр и экономическое поведение», в которой впервые было дано систематизирование электронной вычислительной техники.

Конфликтные ситуации могут возникать и во многих других областях человеческой деятельности. Это ситуации, складывающиеся при планировании и в ходе военных действий, при анализе надежности технических систем. Здесь теория игр нашла широкое применение.

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

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



 

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

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

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

Допустимые действия каждого из игроков, направленные на достижение некоторой цели, назы­ваются правилами игры.

Количественная оценка результатов игры называется платежом.

Игра называется парной, если в ней участвуют только две стороны (два лица).

Парная игра называется игрой с ну­левой суммой, если сумма платежей равна нулю, т. е. если про­игрыш одного игрока равен выигрышу второго.

Однозначное описание выбора игро­ка в каждой из возможных ситуаций, при которой он должен сде­лать личный ход, называется стратегией игрока.

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

Пусть имеется два игрока, один из которых может выбрать i-ю стратегию из m своих возможных стратегий (i= ), а вто­рой, не зная выбора первого, выбирает j-ю стратегию из п своих возможных стратегий (j= ). В результате первый игрок вы­игрывает величину аij, а второй проигрывает эту величину.

Из чисел аij составим матрицу

Строки матрицы A соответствуют стратегиям первого игрока, а столбцы — стратегиям второго. Эти стратегии называются чистыми.



Матрица А называется платежной (или матрицей игры).

Игру, определяемую матрицей А, имеющей m строк и n столбцов, называют конечной игрой размер­ности m×n.

Число α = называется нижней ценой игры или максимином, а соответствующая ему стратегия (строка) — максиминной.

Число β = называется верхней ценой игры или минимаксом, а соответствующая ему стратегия игрока (столбец) — минимаксной.

Теорема 1.Нижняя цена игры всегда не превосходит верх­ней цены игры.

Если α = β = υ, то число υ назы­вается ценой игры.

Игра, для которой α = β, называется игрой с седловой точкой.

Для игры с седловой точкой нахождение решения состоит в выборе максиминной и минимаксной стратегий, которые явля­ются оптимальными.

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

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

Из данного определения непосредственно следует, что сумма компонент указанного вектора равна единице, а сами компоненты не отрицательны. Обычно смешанную стратегию первого игрока обозначают как вектор U = (u1, u2 ..., um), а второго игрока — как вектор Z = (z1, z2 ..., zn), где ui ≥ 0 (i= ), zi ≥ 0 (j= ),

Если U* — оптимальная стратегия первого игрока, a Z* — оптимальная стратегия второго игрока, то число

является ценой игры.

Определение оптимальных стратегий и цены игры и состав­ляет процесс нахождения решения игры.

Теорема 2 Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

Теорема 3 Для того чтобы число v было ценой игры, a U* и Z* — оптимальными стратегиями, необходимо и достаточно выполнение неравенств

и

Если теорема 2 дает ответ на вопрос о существовании ре­шения игры, то следующая теорема дает ответ на вопрос, как найти это решение для игр 2×2, 2×n и n×2, примеры которых приведены ниже.

Теорема 4 Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш равен цене игры υ вне зависимости от того, с какими частотами будет применять второй игрок стратегии, вошедшие в оптимальную (в том числе и чистые стратегии).

Рассмотрим примеры.

 

Пример1. Найти решение игры, заданной матрицей и дать геометрическую интерпретацию этого решения.

 

Решение. Прежде всего проверим наличие седловой точки в данной матрице. Для этого найдем минимальные элементы в каждой из строк (2 и 4) и максимальные элементы в каждом из столбцов (6 и 5). Значит, нижняя цена игры α = mах (2; 4) =4, а верхняя цена игры β = min (6; 5) = 5. Так как α = 4 ≠ β = 5, то решением игры являются смешанные оптимальные стратегии, а цена игры v заключена в пределах 4≤ υ ≤!5.

Предположим, что для игрока А стратегия задается вектором U = (u1; u2). Тогда на основании теоремы 4 при применении игроком В чистой стратегии В1 или В2 игрок А получит средний выигрыш, равный цене игры, т. е.

(при стратегии В1),

(при стратегии В2).

Помимо двух записанных уравнений относительно и доба­вим уравнение, связывающее частоты и .

+ = 1.

Решая полученную систему трех уравнений с тремя неизвест­ными, находим =2/5; =3/5; υ = 22/5.

Найдем теперь оптимальную стратегию для игрока В. Пусть стратегия для данного игрока задается вектором Z=(z1; z2).

Тогда

 

Решая систему уравнений, состоящую из каких-нибудь двух уравнений, взятых из последней системы, получим =1/5; =4/5. Следовательно, решением игры являются смешанные стратегии U* = (2/5; 3/5) и Z* = (1/5; 4/5), а цена игры υ = 22/5.

Дадим теперь геометрическую интерпретацию решения дан­ной игры. Для этого на плоскости uOz введем систему координат и на оси Оu отложим отрезок единичной длины А1А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию U= (u1, u2) = (u1, 1- u1)

(рис. 1). В частности, точке А1 (0; 1) отвечает стратегия A1, точке А2 (1; 0) —страте­гия А2 и т. д.

 

       
   
 
 

 

 


 

 
 
Рис.1


Пример 2. Швейное пред­приятие планирует к мас­совому выпуску новую мо­дель одежды. Спрос на эту модель не может быть точно определен. Однако можно предположить, что его величина характеризу­ется тремя возможными состояниями (I, II, III). С учетом этих состояний анализируются три воз­можных варианта выпуска данной модели (А, Б, В). Каждый из этих вариан­тов требует своих затрат и обеспечивает в конечном счете различный эффект. Прибыль (тыс. руб.), которую получает предприятие при данном объеме выпуска модели и соответствующем состоянии спроса, определяется матрицей

 

 

Требуется найти объем выпуска модели одежды, обеспечива­ющий среднюю величину прибыли при любом состоянии спроса.

Решение. Прежде всего проверим, имеет ли исходная ма­трица седловую точку. Для этого находим минимальные эле­менты в ее строках (22; 21; 20) и максимальные— в столбцах (22; 23; 24). Максимальным среди минимальных элементов строк является число а = 22, а минимальным среди максимальных эле­ментов столбцов — число р = 22. Таким образом, а = |3 = 22. Чи­сло 22 является ценой игры. Игра имеет седловую точку, соответ­ствующую 1 варианту выпуска модели одежды. Объем выпуска модели, соответствующей данному варианту, обеспечивает при­быль в 22 тыс. руб. при любом состоянии спроса.

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


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал