Системный анализ
Понятие линейного математического программирования. Модели линейного программирования с двумя переменными. Системы линейных уравнений. Принцип максимина в антагонистических играх, седловая точка. Чистые и смешанные стратегии. Теоремы матричных игр.
| Рубрика | Математика |
| Вид | курс лекций |
| Язык | русский |
| Дата добавления | 24.06.2014 |
| Размер файла | 459,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Итак, исходя из принципа осторожности, игрок А должен выбрать стратегию А4, а его противник - В3. Такие стратегии называются максиминными или минимаксными стратегиями (вытекающие из принципа максимина).
До тех пор, пока обе стороны в нашем примере будут придерживаться своих максиминных стратегий, выигрыш игрока А и проигрыш игрока В будет равен а43=5.
Легко показать, что нижняя цена игры никогда не превосходит верхней цены игры.
Случай =, соответствует наличию у платежной матрицы так называемой седловой точки.
Определение. Точка (i*, j*) называется седловой точкой платежной матрицы ||aij||, если для всех остальных i и j этой матрицы выполняется условие
ai*j ai*j* aij*,
т.е. аij является одновременно минимумом своей строки и максимумом своего столбца.
Приведем без доказательства следующую теорему.
Теорема 1. Для того чтобы
необходимо и достаточно, чтобы матрица ||aij|| имела седловую точку. Кроме того, если (i*, j*) - седловая точка матрицы ||aij||, то
(2.4)
Говорят, что матричная игра имеет седловую точку, если соответствующая ей матрица выигрышей (платежная матрица) имеет седловую точку.
4.4 Чистые и смешанные стратегии
Если в игре каждый из противников применяет только одну и ту же стратегию, то про саму игру в этом случае говорят, что она происходит в чистых стратегиях, а используемые игроком А и игроком В пара стратегий называются чистыми стратегиями.
Определение. В антагонистической игре пара стратегий (Аi, Вj) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.
Применять чистые стратегии имеет смысл тогда, когда игроки А и В располагают сведениями о действиях друг друга и достигнутых результатах. Если допустим, что хотя бы одна из сторон не знает о поведении противника, то идея равновесия нарушается, и игра ведется бессистемно.
Рассмотрим матричную игру G (3х4)
|
Bj Ai |
B1 |
B2 |
B3 |
B4 |
i |
|
|
A1 |
5 |
7 |
10 |
8 |
5 |
|
|
A2 |
10 |
9 |
11 |
10 |
9 |
|
|
A3 |
8 |
6 |
7 |
4 |
4 |
|
|
j |
10 |
9 |
11 |
10 |
В этом примере нижняя цена игры равна верхней: ==9, т.е. игра имеет седловую точку.
Оказывается, что в этом случае максиминные стратегии А2 и В2 будут устойчивыми по отношению к информации о поведении противника.
Действительно, пусть игрок А узнал, что противник применяет стратегию В2. Но и в этом случае игрок А будет по-прежнему придерживаться стратегии А2, потому что любое отступление от стратегии А2 только уменьшит выигрыш. Равным образом, информация, полученная игроком В, не заставит его отступить от своей стратегии В2.
Пара стратегий А2 и В2 обладает свойством устойчивости, а выигрыш (в рассматриваемом примере он равен 9), достигаемый при этой паре стратегий, оказывается седловой точкой платежной матрицы.
Признак устойчивости (равновесности) пары стратегии - это равенство нижней и верхней цены игры.
Стратегии Аi и Вj (в рассматриваемом примере А2, В2), при котором выполняется равенство нижней и верхней цены игры, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях.
Величина называется ценой игры.
Если 0, то игра выгодна для игрока А, если 0 - для игрока В; при =0 игра справедлива, т.е. является одинаково выгодной для обоих участников.
Однако наличие седловой точки в игре - это далеко не правило, скорее - исключение. Большинство матричных игр, не имеет седловой точки, а следовательно, не имеет оптимальных чистых стратегий. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это - игры с полной информацией.
Теорема 2. Каждая игра с полной информацией имеет седловую точку, а следовательно, решается в чистых стратегиях, т.е. имеется пара оптимальных чистых стратегий, дающая устойчивый выигрыш, равный .
Если такая игра состоит только из личных ходов, то при применении каждым игроком своей оптимальной чистой стратегии она должна кончаться выигрышем, равным цене игры. Скажем, шахматная игра, как игра с полной информацией, либо всегда кончается выигрышем белых, либо всегда - выигрышем черных, либо всегда - ничьей (только чем именно - мы пока не знаем, так как число возможных стратегий в шахматной игре огромно).
Если матрица игры содержит седловую точку, то ее решение сразу находится по принципу максимина.
Возникает вопрос: как найти решение игры, платежная матрица которой не имеет седловой точки? Применение максиминного принципа каждым из игроков обеспечивает игроку А выигрыш не менее , игроку - проигрыш не больше . Учитывая что , естественно для игрока А желание увеличить выигрыш, а для игрока В - уменьшить проигрыш. Поиск такого решения производит к необходимости применять смешанные стратегии: чередовать чистые стратегии с какими-то частотами.
Определение. Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией.
Таким образом, задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его чистые стратегии.
Будем обозначать смешанные стратегии игроков А и В соответственно
SA=||p1, p2, ..., pm||,
SB=||q1, q2, ..., qn||,
где pi - вероятность применения игроком А чистой с тратегии Аі; ; qj - вероятность применения игроком В чистой стратегии Bj; .
В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.
Применение смешанных стратегий осуществляется, например, таким образом: игра повторяется много раз, но в каждой партии игрок применяет различные чистые стратегии с относительными частотами их применения, равными pi и qj.
Смешанные стратегии в теории игр представляют собой модель изменчивой, гибкой тактики, когда ни один из игроков не знает, какую чистую стратегию выберет противник в данной партии.
Если игрок А применяет смешанную стратегию SA=||p1, p2, ..., pm||, а игрок В смешанную стратегию SB=||q1, q2, ..., qn||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением
.
Естественно, что ожидаемый проигрыш игрока В равен такой же величине.
Итак, если матричная игра не имеет седловой точки, то игрок должен использовать оптимальную смешанную стратегию, которая обеспечит максимальный выигрыш .
Естественно возникает вопрос: какими соображениями нужно руководствоваться при выборе смешанных стратегий? Оказывается принцип максимина сохраняет свое значение и в этом случае. Кроме того, важное значение для понимания решения игр, играют основные теоремы теории игр.
4.5 Основные теоремы матричных игр
Если игрок А выбирает смешанную стратегию SA=||p1, p2, ..., pm||, а игрок В смешанную стратегию SB=||q1, q2, ..., qn||,то средний выигрыш математическое ожидание выигрыша игрока А (проигрыша игрока В) определится суммой
,
которая может рассматриваться в качестве характеристики выбранных SА и SB.
Формируя свою стратегию SА в антагонистической игре, игрок А в соответствии с принципом максимина должен выбрать такую стратегию, при которой минимально возможный выигрыш был бы максимален, т.е. такую стратегию, которая обеспечивает
Аналогичные рассуждения, связанные с поиском оптимальной смешанной стратегии игрока В, приводят к рекомендации выбрать такую стратегию SB, которая обеспечивает
.
Весьма важным для теории и практики является вопрос о том, связаны ли между собой vА и vB. Ответ на него дает теорема о максимине.
Теорема о максимине. В конечной игре двух игроков (коалиций) с нулевой суммой (матричной игре) при имеет место равенство
.(2.9)
Теорема о максимине указывает на существование равновесия для случая vА=vB, при и, следовательно, существования оптимальных смешанных стратегий.
Поэтому другая формулировка теоремы о максимине, называемая основной теоремой матричных игр определяется следующим образом.
Основная теорема матричных игр. Любая матричная игра имеет, по крайней мере, одно оптимальное решение, в общем случае, в смешанных стратегиях и соответствующую цену v.
Обе эти теоремы эквивалентны. Из этих теорем следует, что любая матричная игра имеет цену v. Цена игры v - средний выигрыш, приходящийся на одну партию, - всегда удовлетворяет условию , т.е. лежит между нижней и верхней ценами игры.
Оптимальное решение игры в смешанных стратегиях, также как и решение в чистых стратегиях, обладает тем свойством, что каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии, если его противник применяет свою оптимальную смешанную стратегию, так как это ему невыгодно.
Эта пара стратегий образует в игре положение равновесия: один игрок хочет обратить выигрыш в максимум, другой - в минимум, каждый “тянет” в свою сторону и, при оптимальном поведение обоих, устанавливается равновесие и устойчивый выигрыш .
4.6. Решение матричной игры (2х2)
Пусть матричная игра G (2x2) имеет платежную матрицу
|
Bj Ai |
B1 |
B2 |
|
|
A1 |
a11 |
a12 |
|
|
A2 |
a21 |
a22 |
Предположим, что игра не имеет седловой точки, т.е. . При наличии седловой точки решение очевидно.
В соответствии с основной теоремой игра имеет оптимальное решение в смешанных стратегиях: SA=||p1, p2|| и SB=||q1, q2||, где вероятности применения (относительные частоты применения) чистых стратегий удовлетворяют соотношениям
;(1)
.(2)
В соответствии с теоремой об активных стратегиях, оптимальная смешанная стратегия обладает тем свойством, что обеспечивает игроку максимальный средний выигрыш, равный цене игры , независимо от того, какие действия предпринимает другой игрок, если тот не выходит за пределы своих активных стратегий. В частности, если игрок А использует свою оптимальную смешанную стратегию, а игрок В - свою чистую активную стратегию В1, то цена игры равна
,(3)
а при использовании игроком В чистой активной стратегии В2, выигрыш будет равен
.(4)
Уравнения (2.11), (2.13) и (2.14) образуют систему трех линейных алгебраических уравнений с тремя неизвестным: р1, р2 и .
Решая ее, легко находим, что
.(5)
.(6)
.(7)
Если игрок В использует свою оптимальную смешанную стартегию, а игрок А - свою чистую активную стратегию А1, то цена игры равна
,(8)
а при использовании игроком А чистой активной стратегии А2, выигрыш будет равен
.(9)
Уравнения (2.12), (2.18) и (2.19) образует систему трех линейных алгебраических уравнений с тремя неизвестными: q1; q2 и .
Решая ее, легко находим, что
.(10)
.(11)
.(12)
Естественно, что в обоих случаях цена игры (выражения (7) и (12)) получилась одна и та же.
Чтобы соотношения (5), (6), (7), (10), (11), (12) имели смысл, необходимо потребовать, чтобы
Или
Тогда 0<p1<1; 0<p2<1; 0<q1<1; 0<q2<1.
Нетрудно заметить, что в этих неравенствах отражено предположение об отсутствии в рассматриваемой игре седловой точки. Действительно, ни один из четырех выигрышей а11, а12, а21, а22 не может удовлетворить этим неравенствам, будучи минимальным в своей строке и максимальным в своем столбце.
Решения системы уравнений (5), (6), (7) и (10), (11), (12), полученные алгебраическим методом, удобно получать и графическим методом (рис. 2.4). Для нахождения вероятностей р1, р2 и цены игры v в прямоугольной системе координат по оси абсцисс откладывается вероятность р1[0,1], а по оси ординат - соответствующие этой вероятности - выигрыши игрока А.
При р1=0, игрок А применяет чистую стратегию А2. Если при этом игрок В применяет чистую стратегию В1, то выигрыш игрока А равен а21 (уравнение (3)), а если игрок В применяет чистую стратегию В2, то выигрыш игрока А равен а22 (уравнение (4)). При р1=1, игрок А применяет чистую стратегию А1.
Если при этом игрок В применяет чистую стратегию В1, то выигрыш игрока А равен а11, а при применении чистой стратегии В2 - а12. Так как значения р1 лежат в пределах [0,1], то соединяя крайние точки для стратегий В1 и В2 (строя графики функций vА=(a11-a21)p1+a22 и vА=(a12-a22)p1+a22), получаем значения выигрышей игрока А для всех промежуточных значений р1.
В соответствии с принципом максимина, игрок А должен выбрать такую смешанную стратегию, при которой его минимальный выигрыш максимален. Точка N пересечения отрезков прямых (рис. 2.4) и определяет как оптимальную цену игры vopt, так и оптимальные вероятности p1opt и p2opt=1-p1opt, соответствующие оптимальной смешанной стратегии игрока А, т.е. дает решения системы уравнений (1), (3), (4).
Для графического решения системы уравнений (2), (8), (9) отложим по оси абсцисс вероятность q1[0,1], а по оси ординат соответствующие этой вероятности выигрыши игрока В:
vВ=(a11-a12)q1+a12;(13)
vВ=(a21-a22)q1+a22.(14)
Решением являются координат точки М пересечения прямых, описываемых уравнений (13) и (14):
q1opt;q2opt=1-q1opt и vopt.
Это же следует и из принципа максимина, в соответствии с которым игрок В должен выбрать такую смешанную стратегию, при которой его максимальный проигрыш будет минимальным.
Для игры G(2х2) с седловой точкой геометрическая интерпретация решения быть представлена, например, следующим образом (рис.2.6).
Стратегия В2 игрока В является для него явно невыгодной, так как, применяя ее, он в любой случае проигрывает больше, чем при применении стратегии В1. В данной игре р1opt=1;р2opt=0; vopt=а11, т.е. игра имеет седловую точку N и решается в чистых стратегиях. Игрок А должен применять стратегию А1, а игрок В - стратегию В1.
На рис. 2.7 показан случай, в котором решением игры для игрока А является чистая стратегия А2, а для игрока В - стратегия В1.
Игра имеет седловую точку N.
Пример: Найти алгебраическим и геометрическим методами решение игры, платежная матрица которой имеет вид
|
Bj Ai |
B1 |
B2 |
i |
|
|
A1 |
4 |
-2 |
-2 |
|
|
A2 |
1 |
3 |
1 |
|
|
j |
4 |
3 |
В данной игре нижняя цена игры =1 не равна верхней цены игры =3, поэтому игра не имеет седловой точки и, в соответствии с основной теоремой матричных игр, имеет оптимальное решение в смешанных стратегиях.
Для игрока А, в соответствии с формулами (5) и (6), оптимальные вероятности применения стратегий А1 и А2 равны:
;
.
Для игрока В, в соответствии с формулами (10) и (11), оптимальные вероятности применения стратегий В1 и В2 равны:
;
.
Таким образом, оптимальные смешанные стратегии игроков
; ,
а цена игры в соответствии с формулой (12) равна:
.
Так как , то игра выгодна для игрока А.
Графическое изображение игры для игрока А показана на рис.
Нижняя граница выигрыша игрока А определяется ломаной CND. Оптимальное решение, определяется точкой N, естественно, дает тоже решение, что и алгебраический метод: .
Геометрическое изображение игры для игрока В показано на рис.
Оптимальное решение, определяемое точкой М, дает решение .
Используемая литература
1.Василевич Л.Ф. Теория игр. Учебное пособие, КИИМ, 2000.
2. Гуров С.В. Теория системного анализа и принятия решений. Учебное пособие, СПб.: ЛТА, 2008.
3. Н.Ш. Кремер и др. Исследование операций в экономике. - М.: ЮНИТИ, 2003 г.
4. Е.С. Вентцель. Исследование операций: задачи, принципы и методология. - М.:ДРОФА, 2010.
Размещено на Allbest.ru
Подобные документы
Способы решения системы уравнений с двумя переменными. Прямая как график линейного уравнения. Использование способов подстановки и сложения при решении систем линейных уравнений с двумя переменными. Решение системы линейных уравнений методом Гаусса.
реферат [532,7 K], добавлен 10.11.2009Определение системы с двумя переменными, способ ее решения. Специфика преобразования линейных уравнений с двумя переменными. Способ сложения и замены переменных в этом виде уравнений, примеры их графиков. Алгоритм нахождения количества системы уравнений.
презентация [226,6 K], добавлен 08.12.2011Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.
курсовая работа [197,1 K], добавлен 09.04.2013Сущность линейного программирования. Изучение математических методов решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейной целевой функцией. Нахождение точек наибольшего или наименьшего значения функции.
реферат [162,8 K], добавлен 20.05.2019Системы линейных уравнений и интерпретация их решений как пересечение гиперплоскостей в n-мерном координатном пространстве. Размерность и подпространства линейного пространства. Оптимизационные задачи линейного программирования. Суть симплекс-метода.
курсовая работа [132,2 K], добавлен 10.01.2014Понятие и виды задач математического линейного и нелинейного программирования. Динамическое программирование, решение задачи средствами табличного процессора Excel. Задачи динамического программирования о выборе оптимального распределения инвестиций.
курсовая работа [126,5 K], добавлен 21.05.2010Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
задача [656,1 K], добавлен 01.06.2016Изучение общих сведений о матричных и антагонистических играх. Понятие позиционной игры, дерева, информационного множества. Рассмотрение принципа максимина и принципа равновесия. Оптимальность по Парето. Позиционная неантагонистическая игра, ее свойства.
курсовая работа [1,4 M], добавлен 17.10.2014История зарождения и создания линейного программирования. Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей. Методы составления начального опорного плана. Понятие потенциала и цикла. Задача, двойственная к транспортной.
курсовая работа [166,7 K], добавлен 17.07.2002Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.
курсовая работа [67,5 K], добавлен 25.11.2011
