Исследование операций построение, разработка и приложения математических моделей принятия оптимальных решений
| скачать 14.0207 Антагонистические игрыТеория исследования операцийОпределение. Теория игр – теория принятия решений в условиях конфликта и/или неопределенности.
Теория исследования операций. Исследование операций – построение, разработка и приложения математических моделей принятия оптимальных решений Системный анализ – дисциплина, занимающаяся проблемами принятия решений в условиях, когда выбор альтернативы требует анализа сложной информации различной физической природы Кибернетика – наука об управлении, связи и переработке информации (буквально: искусство управления рулем) Теория автоматического регулирования Теория вероятностей Определение. Операция – совокупность действий, мероприятий, направленных на достижение некоторой цели. Определение. Совокупность тех лиц или автоматов, которые стремятся в данной операции к поставленной цели, называется оперирующей стороной.
Принцип Гермейера. Исследователь операции входит в оперирующую сторону и проводит исследование в его интересах
Определение. Модель операции в нормальной форме <U,A,g>, где U – множество стратегий оперирующей стороны, A – множество неопределенных факторов, g:UA  – критерий оперирующей стороны.
Второй принцип Гермейера. В каждой операции должен быть только один критерий. Неопределенность может возникать по различным причинам:
Третий принцип Гермейера. Исследователь операций должен быть осторожен.
Четвертый принцип Гермейера. Исследователь операции должен учитывать всю информацию, которая будет у оперирующей стороны в момент принятия решения ^ Сужать множество неопределенных факторов может оперирующая сторона, но не исследователь операций.
^ Определение. Антагонистической игрой в нормальной форме называется набор <U,V,g>, где U и V – множества, а функция g:UVR. Элементы множество U и V интерпретируются как стратегии (управления) первого и второго игрока соответственно. Цель первого игрока описывается как стремление к увеличению значения функции выигрыша g, а цель второго игрока – как стремление к его уменьшению.
Лемма. Для любой функции g:UVR выполняется неравенство  .Доказательство. Очевидно, для любых управлений u и v выполняются неравенства  или  .Правая часть от u не зависит, поэтому в силу произвольности u выполняется неравенство  Левая часть последнего неравенства – это просто число, значит, в силу произвольности v, имеет место неравенство , что и требовалось доказать.
Определение 1. Игра <U,V,g> имеет седловую точку, если существуют число p и стратегии u0U и v0V такие, что  . Число p называют ценой игры, а пару (u0,v0) – седловой точкой.Определение 2. Игра <U,V,g> имеет седловую точку, если  . Если u0 реализует максимум в правой части равенства, а v0 реализует минимум в левой части, то пару (u0,v0) называют седловой точкой, а общее значение левой и правой частей – ценой игры.^ Определения 1 и 2 эквивалентны. Доказательство. Пусть выполнено определение 1. Из равенства  следует, что  , а из равенства  получается неравенство  , то есть  . В силу предыдущей леммы выполняется и обратное неравенство, а значит, на самом деле имеет место равенство .Пусть выполнено определение 2. Обозначим  . По определению точки u0 имеем , а из определения точки v0 получаем . Лемма доказана.
Определение. Если U и V – компактные выпуклые подмножества конечномерных евклидовых пространств, а функция g:UVR непрерывна, вогнута по u при любом фиксированном v и выпукла по v при любом фиксированном u, то игра Г=<U,V,g> называется выпуклой. Терема (С. Какутани, 1941). В выпуклой игре существует седловая точка. Доказательство. Рассмотрим сначала «типичный» частный случай, когда функция g строго вогнута по u при любом фиксированном v и строго выпукла по v при любом фиксированном u. Тогда при каждом v максимум  достигается в единственной точке, то есть корректно определена функция  . Аналогично, единственным образом определена функция  . В силу следствия из леммы о замкнутом графике (см. лекцию 1) обе эти функции непрерывны. Рассмотрим отображение F(u,v)=(f1(v),f2(u)). Оно непрерывно и отображает выпуклый компакт :UV в себя. В силу теоремы Брауэра это отображение имеет неподвижную точку, то есть существует решение (u0,v0) системы уравнений  Но тогда  то есть (u0,v0) – седловая точка. Вернемся к рассмотрению общего случая. Наряду с игрой Г рассмотрим игру Г=<U,V,g>, где функция g определена равенством  . При любом >0, функция g непрерывна, строго вогнута по u при любом фиксированном v и строго выпукла по v при любом фиксированном u. Как только что доказано, в игре Г существует седловая точка (u,v).Произвольным образом зададим сходящуюся к нулю последовательность положительных чисел (1), (2),…,(n)… Рассмотрим последовательность игр  и соответствующую последовательность седловых точек  В силу компактности множества UV эта последовательность имеет сходящуюся подпоследовательность. Не ограничивая общности, можно считать, что сама последовательность сходится к некоторой точке (u0,v0).Покажем, что (u0,v0) есть седловая точка в игре Г. Пусть u и v – произвольные управления первого и второго игроков соответственно. Так как  – седловая точка в игре  , то для любого n выполняются неравенства Переходя в этих неравенствах к пределу при n, получим  что в силу произвольности u и v завершает доказательство теоремы Пример. Вычислить  и  , где U=V=[0,1] и g(u,v)=–u2+v3+uv2–4v. Решение. Вычислим . Преобразуем g(u,v)=–u2+v3+uv2–4v=–(u2–uv2+v4/4)+ v4/4+v3–4v=–(u–v2/2)2+v4/4+v3–4v. Теперь видно, что  и достигается при u=v2/2. Остается найти максимум функции v4/4+v3–4v на отрезке [0,1]. Ее производная v3+3v2–4=(v3–v2)+4(v2–1)=(v–1)(v2+4v+4)= (v–1)(v+2)2 на этом отрезке имеет единственный корень v=1. Поэтому  .Попытка аналогичным образом вычислить наталкивается на серьезные аналитические трудности. Поэтому целесообразно заметить, что рассматриваемая игра – выпуклая, и значит .^ Лемма. Если a – положительное, а b – произвольное число, то множества седловых точек в играх <U,V,g> и <U,V,ag+b> совпадают. Доказательство. Данная лемма – частный случай следующей. Лемма. Если f – возрастающая функция, то множества седловых точек в играх <U,V,g> и <U,V,fg> совпадают. Доказательство. Пусть (u0,v0) – седловая точка в игре <U,V,g>. Это значит, что для любых u и v выполняются неравенства g(u,v0)g(u0,v0)g(u0,v). В силу монотонности функции f отсюда следуют неравенства f(g(u,v0))f(g(u0,v0))f(g(u0,v)). В силу произвольности u и v это означает, что (u0,v0) – седловая точка в игре <U,V,fg>. Обратно, пусть (u0,v0) – седловая точка в игре <U,V,fg>. Тогда для любых u и v выполняются неравенства f(g(u,v0))f(g(u0,v0))f(g(u0,v)). И снова с помощью монотонности функции f получаем неравенства g(u,v0)g(u0,v0)g(u0,v), откуда следует, что (u0,v0) – седловая точка в игре <U,V,g>.
Определение. Антагонистическая игра называется симметрической, если U=V и g(u,v)=–g(v,u). Лемма. Значение симметрической игры равно нулю (если оно существует). Доказательство. Преобразуем с учетом симметрии игры:  .Отсюда и следует, что p=0. ^ Лемма. Если (u1,v1) и (u2,v2) – седловые точки некоторой игры, то (u1,v2) и (u2,v1) – тоже седловые точки этой игры. Доказательство. Так как (u1,v1) – седловая точка, выполняются неравенства g(u2,v1)g(u1,v1)g(u1,v2), а так как (u2,v2) – седловая точка, имеем g(u1,v2)g(u2,v2)g(u2,v1). Сравнивая, получим g(u2,v1)g(u1,v1)g(u1,v2) g(u2,v2)g(u2,v1). Значит, на самом деле все эти неравенства обращаются в равенства: g(u2,v1)=g(u1,v1)=g(u1,v2) =g(u2,v2)=g(u2,v1). Но тогда  и  , то есть точка (u2,v1) – седловая. Аналогично доказывается, что и точка (u1,v2) является седловой.Следствие. Пусть S1 – множество таких точек u0U, для которых найдется такое v0V, что точка (u0,v0) является седловой. Пусть S2 – множество таких точек v0V, для которых найдется такое u0U, что точка (u0,v0) является седловой. Тогда множество седловых точек равно декартовы произведению S1S2. Лемма. Если U и V – компактные множества, а функция g:UVR непрерывна, то множество седловых точек игры <U,V,g> замкнуто. Доказательство. Пусть точки (u1,v1),(u2,v2),…,(un,vn) – седловые, и последовательность (u1,v1),(u2,v2),…,(un,vn) сходится к точке (u0,v0). Тогда для любых uU, vV и n выполняются неравенства g(u,vn)g(un,vn)g(un,v). Переходя в этих неравенствах к пределу при n и пользуясь непрерывностью функции f, получим g(u,v0)g(u0,v0)g(u0,v), что в силу произвольности u и v означает, что (u0,v0) – седловая точка. Итак, предел любой последовательности седловых точек является седловой точкой. Значит, множество седловых точек замкнуто. ^ Множество седловых точек выпуклой игры выпукло Доказательство. Пусть (u0,v0). Тогда в обозначениях следствия к первой лемме данного раздела  . Множество точек максимума вогнутой функции выпукло, значит выпукло множество ^ 1. Аналогично, множество точек минимума выпуклой функции выпукло, значит выпукло множество S2. Но тогда выпукло и их произведение.Лемма. (Независимость от посторонних альтернатив) Если (u0,v0) – седловая точка в игре <U,V,g>, а множество W содержит v0, а само содержится в V, то ситуация (u0,v0) является седловой точкой в игре <U,W,g>. Доказательство. По определению седловой точки  , а по определению минимума  . Значит на самом деле  . Равенство  непосредственно следует из определения седловой точки.
Примеры
Задачи
***
***
А) aij=i–j; Б) aij=f(i)+g(j); В)  , a,b,c,d – произвольные числа;Г)  , a,b,c,d,e,f,g – произвольные числаЕ) m=n и для любых i,j,k имеет место тождество aij+ajk+aki=0.
А) p(A+B)<p(A)+p(B); Б) p(A+B)>p(A)+p(B); В) p(A+B)=p(A)+p(B), где p(A) – цена игра с матрицей A? ***
А) U=V=[0,1], g(u,v)=2u2–3uv+2v2; Б) U=[–2,3], V=[–1,2], g(u,v)=–u2+4uv–5v2+3u–2v; В) U=V=[0,1], g(u,v)=4uv2–2u2–v; Г) U=[,2], V=[/2,3/2], g(u,v)=ucosv–sinu;
***
(Указание. См. задачу (*))
***
Литература
|
имеет седловую точку тогда и только тогда, когда отрезок числовой прямой с концами a и d имеет, по крайней мере, одну общую точку с отрезком, ограниченным точками b и c. Выполняется ли в данном случае «принцип хрупкости хорошего»?
имеет седловую точку.
, где ai,bj – произвольные числа, ci, dj – положительные числа.
имеет седловую точку, если a и c – функции непрерывные на компакте U, а b и d – функции непрерывные на компакте V, и, кроме того, c и d положительны.
имеет цену p, которая удовлетворяет неравенствам max{min{a,b},min{c,d}}p max{min{a,c},min{b,d}}
и 
имеет седловую точку. Существует ли такое значение x, при котором выполняется соотношение
?
. Докажите, что цена игры равна 
, а 
– седловая точка.
.
.
. Найдите 
, где p и q убывающие непрерывные функции отображающие отрезок [0,1] на себя. Существует ли в этой игре седловая точка?
, где p и q убывающие непрерывные функции отображающие отрезок [0,1] на себя. Существует ли в этой игре седловая точка?
Докажите, что в игре <U,V,g> нет седловой точки.
. Найдите цену игры.
Найдите цену игры и -оптимальные стратегии игроков. Существует ли в этой игре седловая точка?
Докажите, что игра <U,V,g> имеет седловую точку.
имеет седловую точку, если U и V – выпуклые компакты, функция f вогнута по u, выпукла по v и положительна, а функция h выпукла по u, вогнута по v и положительна.
. Докажите, что множество игр, имеющих седловую точку, замкнуто.Ваша оценка этого документа будет первой.
Ваша оценка: 