Исследование операций построение, разработка и приложения математических моделей принятия оптимальных решений icon

Исследование операций построение, разработка и приложения математических моделей принятия оптимальных решений


Смотрите также:
Курс, 2 семестр Лектор: Кочетов Юрий Андреевич...
Программа дисциплины опд. Ф. 10 «Теория игр и исследование операций» Рекомендуется умц кгту им...
Темы лекций Тема 1 Причины возникновения исследования операций. Предмет исследования операций...
Автор программы: к ф. м н., доцент Стрелкова Нина Александровна Требования к студентам...
И. И. Горбань Институт проблем математических машин и систем нан украины...
2. классическая и поведенческая модели принятия решении...
Применение таблиц решений при управлении в аварийных ситуациях на производстве флоат-стекла...
Управление знаниями корпорации и реинжиниринг бизнеса...
Лекция №8 Построение математических моделей технологических объектов и систем аналитическим...
Методическая разработка по курсу «системы принятия решений» Нижний Новгород, 2010...
Изучение математических функций с использованием км-школы в VII-VIII классах...
Общие положения теории принятия решений Глава Задачи принятия решений...



Загрузка...
скачать


14.0207

Антагонистические игры

Теория исследования операций


Определение. Теория игр – теория принятия решений в условиях конфликта и/или неопределенности.

      • Конфликт

      • Терминология

      • Нормативный аспект

      • Контрпример: теория фон Неймана

      • Рациональность

Теория исследования операций. Исследование операций – построение, разработка и приложения математических моделей принятия оптимальных решений

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

Кибернетика – наука об управлении, связи и переработке информации (буквально: искусство управления рулем)

Теория автоматического регулирования

Теория вероятностей

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

Определение. Совокупность тех лиц или автоматов, которые стремятся в данной операции к поставленной цели, называется оперирующей стороной.

      • Исследователь операций

Принцип Гермейера. Исследователь операции входит в оперирующую сторону и проводит исследование в его интересах

      • Уточнение

      • Пример – компьютеризация специализированных сельскохозяйственных предприятий

Определение. Модель операции в нормальной форме <U,A,g>, где U – множество стратегий оперирующей стороны, A – множество неопределенных факторов, g:UA – критерий оперирующей стороны.

      • Управление

      • Контрпример: Гордиев узел

      • Неопределенность

      • Критерий

      • Контрпример: нетранзитивное предпочтение

      • Контрпример: парадокс кучи

Второй принцип Гермейера. В каждой операции должен быть только один критерий.

Неопределенность может возникать по различным причинам:

      • Природа

      • Противник

      • Неопределенность цели

      • Стохастика

Третий принцип Гермейера. Исследователь операций должен быть осторожен.

  • Минимакс

Четвертый принцип Гермейера. Исследователь операции должен учитывать всю информацию, которая будет у оперирующей стороны в момент принятия решения

^ Пятый принцип Гермейера. Сужать множество неопределенных факторов может оперирующая сторона, но не исследователь операций.

      • Пример: формирование гипотез при испытании самолетов



^

Антагонистическая игра в нормальной форме


Определение. Антагонистической игрой в нормальной форме называется набор <U,V,g>, где U и V – множества, а функция g:UVR. Элементы множество U и V интерпретируются как стратегии (управления) первого и второго игрока соответственно. Цель первого игрока описывается как стремление к увеличению значения функции выигрыша g, а цель второго игрока – как стремление к его уменьшению.

  • Пример: игра «орел–решка»

  • Пример: Автопилот

  • Пример: Игра «крестики–нолики»

  • Агрегирование

    1. Матричные игры

      • Игра «орел–решка»
^

Максимальный гарантированный результат


    1. максимальный гарантированный результат

      • за первого игрока

      • за второго игрока

      • Пример: игра «орел–решка»

Лемма. Для любой функции g:UVR выполняется неравенство .

Доказательство. Очевидно, для любых управлений u и v выполняются неравенства



или

.

Правая часть от u не зависит, поэтому в силу произвольности u выполняется неравенство



Левая часть последнего неравенства – это просто число, значит, в силу произвольности v, имеет место неравенство , что и требовалось доказать.


      • Пример: каре

      • Доказательство
^

Седловые точки


    1. Мотивация

      • Простейший случай

      • Ключевой случай

      • Природная неопределенность

      • «Принцип бутерброда»

Определение 1. Игра <U,V,g> имеет седловую точку, если существуют число p и стратегии u0U и v0V такие, что . Число p называют ценой игры, а пару (u0,v0) – седловой точкой.

Определение 2. Игра <U,V,g> имеет седловую точку, если . Если u0 реализует максимум в правой части равенства, а v0 реализует минимум в левой части, то пару (u0,v0) называют седловой точкой, а общее значение левой и правой частей – ценой игры.

^ Лемма. Определения 1 и 2 эквивалентны.

Доказательство. Пусть выполнено определение 1. Из равенства следует, что , а из равенства получается неравенство , то есть . В силу предыдущей леммы выполняется и обратное неравенство, а значит, на самом деле имеет место равенство .

Пусть выполнено определение 2. Обозначим . По определению точки u0 имеем , а из определения точки v0 получаем . Лемма доказана.

    1. Существование (примеры)

      • g(u,v)=uv
^

Выпуклые игры.


Определение. Если U и V – компактные выпуклые подмножества конечномерных евклидовых пространств, а функция g:UVR непрерывна, вогнута по 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+uv24v.

Решение. Вычислим . Преобразуем

g(u,v)=–u2+v3+uv24v=–(u2uv2+v4/4)+ v4/4+v3–4v=–(uv2/2)2+v4/4+v3–4v.

Теперь видно, что и достигается при u=v2/2. Остается найти максимум функции v4/4+v3–4v на отрезке [0,1]. Ее производная

v3+3v2–4=(v3v2)+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:UVR непрерывна, то множество седловых точек игры <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). Тогда в обозначениях следствия к первой лемме данного раздела . Множество точек максимума вогнутой функции выпукло, значит выпукло множество ^ S1. Аналогично, множество точек минимума выпуклой функции выпукло, значит выпукло множество S2. Но тогда выпукло и их произведение.

Лемма. (Независимость от посторонних альтернатив) Если (u0,v0) – седловая точка в игре <U,V,g>, а множество W содержит v0, а само содержится в V, то ситуация (u0,v0) является седловой точкой в игре <U,W,g>.

Доказательство. По определению седловой точки , а по определению минимума . Значит на самом деле . Равенство непосредственно следует из определения седловой точки.

      • Терминология (Теория особенностей)

Примеры


  • Пример: U=V=[–1,1], g(u,v)=(uv)2

  • Пример: исследование игры фан-тан исходя из соображений симметрии



Задачи


        1. Докажите, что игра с матрицей имеет седловую точку тогда и только тогда, когда отрезок числовой прямой с концами a и d имеет, по крайней мере, одну общую точку с отрезком, ограниченным точками b и c. Выполняется ли в данном случае «принцип хрупкости хорошего»?

        2. Докажите, что игра с матрицей имеет седловую точку.

        3. Докажите, что если каждая 22 подматрица матрицы A имеет седловую точку, то матрица A также имеет седловую точку.

        4. Докажите, что игра с матрицей A=(aij) имеет цену в чистых стратегиях и найдите соответствующую седловую точку, если , где ai,bj – произвольные числа, ci, dj – положительные числа.

        5. Докажите, что игра <U,V,g> с функцией выигрыша имеет седловую точку, если a и c – функции непрерывные на компакте U, а b и d – функции непрерывные на компакте V, и, кроме того, c и d положительны.

        6. Докажите, что если множества U и V компактны, а функция g непрерывна, и если для любых u1,u2U, v1,v2V игра <{u1,u2},{v1,v2},g> имеет седловую точку, то и игра <U,V,g> имеет седловую точку.

***

        1. Докажите, что если каждая подматрица матрицы ^ A имеет седловую точку, что и сама матрица A имеет седловую точку.

        2. Пусть задана антагонистическая игра с ml матрицей выигрыша A все элементы которой попарно различны. Докажите, что если существуют k,n>1 такие, что каждая kn подматрица, получающаяся отбрасыванием mk строк и ln столбцов, имеет седловую точку, то и игра с матрицей A имеет седловую точку.

        3. Приведите пример, показывающий, что в предыдущей задаче условие попарного различия всех элементов матрицы существенно.

        4. Пусть A – невырожденная nn матрица. Докажите, что если каждая подматрица размера n(n–1) имеет седловую точку, то матрица A также имеет седловую точку.

***

        1. Докажите, что для любых действительных чисел a,b,c,d игра с матрицей имеет цену p, которая удовлетворяет неравенствам max{min{a,b},min{c,d}}p max{min{a,c},min{b,d}}

        2. Докажите, что игра с матрицей A=(aij) имеет цену в чистых стратегиях и найдите соответствующую седловую точку, если

А) 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.

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

А) p(A+B)<p(A)+p(B);

Б) p(A+B)>p(A)+p(B);

В) p(A+B)=p(A)+p(B),

где p(A) – цена игра с матрицей A?

***

        1. Докажите, что в игре <U,V,g>, где U=V=[0,1],

        2. Существует ли седловая точка в игре <U,V,g>, где U=V=[0,1], ?

        3. Найдите и , если g(u,v)=(uv)2 нет седловой точки.

А) 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–2u2v;

Г) U=[,2], V=[/2,3/2], g(u,v)=ucosv–sinu;

        1. (*) Пусть U=V=[0,1] и . Докажите, что цена игры равна , а – седловая точка.

        2. Пусть U=V=[0,1]. Докажите, что при любых ,, игра <U,V,g> с функцией выигрыша g(u,v)=uvuv+ имеет седловую точку.

        3. Пусть U=V=[0,1]. При каких ,, игра <U,V,g> с функцией выигрыша g(u,v)=uvuv+ имеет седловую точку внутри квадрата UV?

        4. Пусть U=V=[0,1] и игра <U,V,g> имеет седловую точку (u0,v0), ледащую внутри квадрата UV. Докажите, что тогда .

        5. Пусть A1 и A2 – две положительно определенные pp матрицы, B – произвольная матрица и, наконец, a1,a2p-мерные векторы. Рассмотрим антагонистическую игру, в которой U=V=Rp , g(u,v)=–(A1u,u)/2+(Bu,v)+(A2v,v)+(a1,u)+(a2,v). Докажите, что эта игра имеет единственную седловую точку, и найдите ее.



        6. Пусть a1,…,an – положительные числа, а U={(u1,…,un): u1+…+un=1, u10,…,un0}. Найдите .

        7. Пусть a1,…,an – положительные числа, а U={(u1,…,un): u1+…+un=1, u10,…,un0}, V={(v1,…,vn): v1+…+vn=1, v10,…,vn0}, . Найдите и .

        8. Пусть U=V=[0,1], , где p и q убывающие непрерывные функции отображающие отрезок [0,1] на себя. Существует ли в этой игре седловая точка?

        9. Пусть U=V=[0,1], , где p и q убывающие непрерывные функции отображающие отрезок [0,1] на себя. Существует ли в этой игре седловая точка?

        10. Пусть p и q – непрерывные возрастающие функции, отображающие отрезок [0,1] на себя, U=V=[0,1], и Докажите, что в игре <U,V,g> нет седловой точки.

        11. Игрок 1 выбирает системы u из m точек отрезка [–1,1]. Одновременно игрок 2 выбирает систему v из n точек того же отрезка Функция выигрыша имеет вид . Найдите цену игры.

        12. Игрок А выбирает три точки A, B, C на окружности, а игрок Б выбирает точку X в круге, ограниченном этой окружностью. Цель игрока А состоит в максимизации суммы длин AX+BX+CX. Существует ли в этой игре седловая точка?

        13. Игрок А выбирает три точки A, B, C на окружности, а игрок Б выбирает точку X в круге, ограниченном этой окружностью. Цель игрока А состоит в минимизации суммы длин AX+BX+CX. Существует ли в этой игре седловая точка?

        14. Пусть U=V=[0,1], Найдите цену игры и -оптимальные стратегии игроков. Существует ли в этой игре седловая точка?

***

        1. Пусть U=V=[0,1], f и h – определенные на UV функции и Докажите, что игра <U,V,g> имеет седловую точку.

(Указание. См. задачу (*))

        1. Показать, что игра <U,V,g> с функцией выигрыша имеет седловую точку, если U и V – выпуклые компакты, функция f вогнута по u, выпукла по v и положительна, а функция h выпукла по u, вогнута по v и положительна.

        2. Найдите вероятность того, что игра с матрицей A=(aij) имеет седловую точку, если aij – независимые случайные величины, имеющие одну и ту же плотность распределения.

        3. Рассмотрим семейство игр с фиксированными множествами стратегий U и V и непрерывными функциями выигрыша. Снабдим это семейство метрикой, определив расстояние между играми Г1=<U,V,g1> и Г2=<U,V,g2> условием . Докажите, что множество игр, имеющих седловую точку, замкнуто.

***

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

        2. ф



Литература


  1. Васин А.А., Морозов В.В. Теория игр и модели математической экономики. М.:МАКС Пресс, 2005.

  2. Мулен Э. Теория игр с примерами из математической экономики. М.: Мир, 1985.

233342.doc 13.10.2011




Скачать 149.08 Kb.
оставить комментарий
Дата13.10.2011
Размер149.08 Kb.
ТипИсследование, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх