- •Системный анализ и моделирование процессов в техносфере
- •1.1. Понятие системы. Базовые категории систем
- •1.2. Классификация систем
- •1.3. Общее представление о системном анализе
- •1.4. Принципы системного анализа
- •2.1. Этапы анализа и синтеза
- •2.2. Понятие о структурном анализе
- •2.3. Методы декомпозиции
- •2.4. Требования, предъявляемые к декомпозиции
- •2.5. Алгоритм декомпозиции
- •2.5. Программно-целевой подход к решению системных задач
- •1. Область применения и этапы программно-целевого подхода
- •2. Дерево целей
- •3.1. Агрегирование системы и эмерджентность
- •3.2. Виды связей в системе
- •Связи взаимодействия (координации):
- •Связи преобразования:
- •3.3. Виды агрегирования
- •4.1. Общие свойства процесса принятия решений
- •4.2. Участники процесса принятия решения
- •4.3. Схема ппр
- •4.4. Формулирование проблемы
- •4.5. Определение целей
- •4.6. Генерирование альтернатив
- •4.7. Формирование критериев
- •4.8. Физиология принятия решений
- •4.9. Виды и особенности задач принятия решений
- •4.10. Формализация принятия решений
- •Лекция 5. Информационное обеспечение ппр
- •5.1. Понятие информации
- •5.2. Информационная структура процесса принятия решений
- •6.1. Особенности группового выбора
- •6.2. Экспертные методы выбора
- •6.3. Методы типа мозговой атаки или коллективной генерации идей
- •6.4. Методы типа сценариев
- •6.5. Методы типа «Делфи»
- •6.6. Методы типа дерева целей
- •6.7. Морфологические методы
- •7.1 Основные положения теории управления
- •7.2 Аксиомы теории управления
- •7.3 Модели основных функций организационно-технического управления
- •7.4 Описание функций управления
- •Лекция 8. Понятие и классификация моделей
- •8.1 Понятие модели, моделирования
- •8.2 Познавательные и прагматические модели
- •8.3 Статические и динамические модели
- •8.4 Классификация моделей по способу воплощения
- •8.5 Место математического моделирования в системных исследованиях
- •8.6 Типы и виды математических моделей
- •8.7 Процесс построения математической модели
- •8.8 Структура моделирования происшествий в техносфере
- •9.1 Конфликт ‒ предмет рассмотрения теории игр
- •9.2 Понятие игры. Классификация игр. Формальное представление игр
- •9.3 Определение бескоалиционной игры
- •9.4 Приемлемые ситуации и ситуации равновесия
- •9.5 Примеры игровых задач
- •10.1 Граф и его виды
- •10.2 Задача о кратчайшем пути
- •10.3 Задача о максимальном потоке
- •11.1 Поверхность отклика
- •11.2 Этапы планирования эксперимента
- •11.3 Обработка и анализ результатов моделирования
- •12.1 Полный факторный эксперимент
- •12.2 Дробный факторный эксперимент
- •12.3 Метод наименьших квадратов
- •13.1 Основная цель кластерного анализа
- •13.2 Объединение (древовидная кластеризация)
- •13.3 Двувходовое объединение
- •13.4 Метод k средних
- •13.5 Алгоритм нечеткой кластеризации
- •14.1 Понятие когнитивного моделирования
- •14.2 Подсистема представления субъективной информации
- •14.3 Подсистема извлечения предпочтений эксперта
- •14.4 Подсистема обработки
- •14.5 Подсистема представления результатов моделирования
- •14.6 Подсистема поддержки аналитической деятельности эксперта
- •14.7 Моделирование бизнес процессов на основе bpmn-диаграмм
- •14.8 Метод анализа иерархий (маи): введение
- •14.9 Основные принципы маи
- •1. Принцип идентичности и декомпозиции
- •2. Принцип дискриминации и сравнительных суждений
- •3. Принцип синтеза
- •14.10 Общая оценка маи как метода принятия решений
- •15.1 Общий ход решения задачи на основе метода конечных элементов
- •15.2 Сети одномерных конечных элементов
- •15.3 Виды конечных элементов
- •16.1 Основные понятия
- •16.2 Приближенное решение оду при заданных начальных условиях
- •16.3 Метод Эйлера и его модификации
- •16.4 Метод Рунге-Кутта
- •16.5 Приближенное решение ду n-го порядка при заданных начальных условиях
- •16.6 Приближенное решение ду при заданных граничных условиях (краевых задач)
- •16.6.1 Метод начальных параметров
- •16.6.2 Редукция к задаче Коши для линейного ду второго порядка
- •17.1 Основные понятия
- •17.2 Типы элементов
- •17.3 Источники энергии и преобразователи. Аналоги топологических уравнений
- •17.4 Метод получения топологических уравнений
- •18.1 Свойства задач принятия решения со многими критериями
- •18.2. Формирование множества критериев
- •18.3 Методология решения многокритериальных задач
- •18.4 Технологии отыскания эффективных решений
- •18.5 Методы принятия решения при нескольких критериях
9.3 Определение бескоалиционной игры
Бескоалиционной игрой будем называть такую игру, в которой целью каждого игрока является получение по возможности большего индивидуального выигрыша.
Обозначим.
I ‒ множество всех игроков. Далее будем считать I конечным. Обычно принято различать игроков по номерам, т.е. считать I = {1, 2, ..., n};
Si ‒ множество стратегий игрока , т.е. множество возможных действий, имеющихся в распоряжении игрока i. Считается, что Si содержит не менее двух возможных стратегий, иначе его действия заранее определены.
Процесс игры состоит в выборе каждым из игроков одной своей стратегии . Таким образом, в результате каждой партии игры складывается система стратегий s = (s1, s2,...,sn), которая называется ситуацией.
Множество всех ситуаций S=S1×S2×…×Sn, т.е. S является декартовым произведением множеств стратегий всех игроков. Обозначим: Hi(s) ‒ выигрыш игрока i в ситуации s. Функция Hi, определенная на множестве всех ситуаций, называется функцией выигрыша игрока i.
Hi: S → R, т.е. каждой ситуации Hi ‒ сопоставляет вещественное число.
Бескоалиционной игрой называется система , в которой I и Si ( ) являются множествами, а Hi ‒ функции на множестве S=S1×S2×…×Sn, принимающие вещественные значения.
Бескоалиционная игра называется игрой с постоянной суммой, если существует такое постоянное число C, что , т.е. сумма выигрышей игроков постоянна в любой ситуации.
9.4 Приемлемые ситуации и ситуации равновесия
Ситуацию s в игре Г естественно считать приемлемой для игрока i, если этот игрок, изменяя в ситуации s свою стратегию на какую-либо другую, не может увеличить этим своего выигрыша.
Пусть s = (s1, s2,..., si-1, si, si+1,..., sn) ‒ произвольная ситуация в игре, а si ‒ некоторая стратегия игрока i.
Рассмотрим новую ситуацию , получившуюся из ситуации s заменой стратегии si игрока i на s'i . Очевидно, что s||s'i = s, если s'i совпадает с si (s'i = si).
Ситуация s в игре Г называется приемлемой для игрока i, если
Смысл названия «приемлемая» состоит в том, что, если в некоторой ситуации s для игрока i найдется такая стратегия s΄i, что то игрок i в случае складывающейся ситуации s может получить больший выигрыш, выбирая s΄i, вместо si. В этом смысле ситуация s для игрока может считаться неприемлемой.
Ситуация s называется ситуацией равновесия (или равновесной ситуацией), если она приемлема для всех игроков, т.е.
Из определения видно, что в ситуациях равновесия и только в них ни один игрок не заинтересован в отклонении от своей стратегии.
Равновесной стратегией игрока в бескоалиционной игре называется такая его стратегия, которая входит хотя бы в одну из равновесных ситуаций игры.
Процесс нахождения ситуаций равновесия в бескоалиционной игре называется решением игры.
9.5 Примеры игровых задач
«Дилемма заключенных»
Предположим, игроками 1 и 2 являются преступники, находящиеся в предварительном заключении по подозрению в тяжком преступлении. Прямых улик против них нет, и возможность их обвинения в значительной мере зависит от того, сознаются ли преступники сами.
Судья предложил каждому следующую сделку. Если он сознается в преступлении, а другой нет, то сознавшийся получает 1 год наказания, а несознавшийся – 10 лет. Если сознаются оба, то каждый получит по 7 лет. Заключенным известно, что если никто из них не сознается, то оба получат по 3 года.
Запишем функции выигрышей (потерь) игроков в рассмотренной игре.
Пусть П – признание, Н – непризнание, H1 – выигрыш 1-го игрока, H2 – выигрыш 2-го игрока.
H1 (П, П) = H2 (П, П) = -7,
H1 (Н, Н) = H2 (Н, Н) = -3,
H1 (П, Н) = H2 (Н, П) = -1,
H1 (Н, П) = H2 (П, Н) = -10.
Игру можно представить с помощью следующей матрицы, в клетках которой слева вверху стоит выигрыш первого заключенного, а справа внизу – второго.
|
Второй игрок |
||
сознаться |
не сознаваться |
||
Первый игрок |
сознаться |
7 7 |
1 10 |
не сознаваться |
10 1 |
3 3 |
Ситуацией равновесия в данной игре оказывается ситуация, в которой каждый из игроков должен признаться. Тогда каждый из игроков теряет 7, т.е. оказывается осужденным на 7 лет.
В ситуации же, когда ни один не признался, потери каждого всего 3 (каждый осужден на 3 года). Однако данная ситуация явно не устойчива, так как каждый из игроков заинтересован отклониться от выбранной стратегии и признаться, рассчитывая свалить вину на другого и избежать наказания, сведя свои потери к 1 (1 год осуждения, при этом потери партнера составят 10).
Таким образом, разумной стратегией для каждого игрока является признание, так как оно гарантирует игроку неполучение максимального срока в 10 лет. Хотя более выгодной кажется тактика непризнания, дающая возможность получения незначительного наказания (срок в год), однако чревата неожиданностью в виде максимального срока в 10 лет в случае признания со стороны соучастника.
«Обмен закрытыми сумками»
Два человека встречаются и обмениваются закрытыми сумками, понимая, что одна из них содержит деньги, другая — товар. Каждый игрок может уважать сделку и положить в сумку то, о чём договорились, либо обмануть партнёра, дав пустую сумку.
В этой игре обман всегда будет наилучшим решением, означая также, что рациональные игроки никогда не будут играть в неё, и что рынок обмена закрытыми сумками будет отсутствовать.
В вариации, популярной у программистов и хакеров, каждый агент этой игры помнит предыдущие результаты (или имеет доступ к общественному мнению, «коллективной памяти»), и множество обменов повторяются длительное время.
Как отмечено выше, без памяти эта игра имеет мало смысла, она мало что объясняет в поведении систем и групп людей, кроме описания взаимодействий, которые не будут происходить.
Программисты и математики утверждают, что стратегия «око за око» наилучшая общая стратегия
Примеры с заключёнными, карточной игрой и обменом закрытыми сумками могут показаться надуманными, но на самом деле есть множество примеров взаимодействия людей и животных, имеющие такую же матрицу выигрышей.
В политологии, к примеру, сценарий ДЗ часто используется для иллюстрации проблемы двух стран, вовлечённых в гонку вооружений. Обе будут заявлять, что у них есть две возможности: либо увеличить расходы на военные нужды, либо сокращать вооружения. Ни одна из сторон не может быть уверена, что другая будет соблюдать договорённость, следовательно, обе будут стремиться к военной экспансии. Это можно считать теоретическим объяснением политики устрашения. Похожие явления наблюдаются и в автоспорте — «Формула-1», где последние 20 лет происходит гонка бюджетов команд. Из-за этого число машин-участников сократилось с 36 в 1990 году до 20 в 2003.
В велогонках дилемма заключённого возникает, когда два сильных гонщика оторвались от общей группы. Каждый из них может либо предоставить соседу сотрудничество, либо ехать сзади. Для обоих идеалом будет, когда они по очереди «висят» друг у друга на хвосте — но всегда есть желание не дать соседу преимущества (тогда тот постепенно устаёт и «скатывается» в пелотон, а ты финишируешь с большим отрывом).
Случай дилеммы заключённого может быть найден в бизнесе. Две конкурирующие фирмы должны определиться, сколько средств тратить на рекламу. Эффективность рекламы и прибыль каждой фирмы уменьшается с ростом расходов на рекламу у конкурента. Обе фирмы принимают решение увеличить расходы на рекламу, при этом их доли рынка и, возможно, объёмы продаж остаются неизменными, а прибыль сокращается. Предел гонки рекламных бюджетов — прибыль, впрочем, они могут пытаться некоторое время работать и в убыток. Фирмы могут пойти на соглашение о сокращении расходов на рекламу, но всегда есть стимул его нарушить.
В олигополистических рынках ценовая политика — это повторяющаяся ДЗ. Обычно олигополисты сотрудничают друг с другом и не доводят ситуацию до «ценовой войны».
Уильям Паундстоун в книге о дилемме заключённого описывает ситуацию в Новой Зеландии, где газетные ящики оставляют открытыми. Газету можно взять, не заплатив за неё, но мало кто так делает, потому что большинство осознаёт вред, который был бы, если бы все воровали газеты. Поскольку ДЗ в чистом виде одновременна для всех игроков (никто не может повлиять на решения других), эта распространённая линия рассуждений называется «магическое мышление».
Теоретическое заключение ДЗ — одна из причин, почему во многих странах сделка о признании вины запрещена. Часто сценарий ДЗ повторяется очень точно: в интересах обоих подозреваемых сознаться и свидетельствовать против другого подозреваемого, даже если оба невиновны. Возможно, наихудший случай — когда только один виноват, в этом случае невиновный вряд ли сознаётся в чём либо, а виновный пойдёт на это и даст показания против невиновного.
Многие дилеммы в реальной жизни включают множество игроков. Хотя и метафорическую, «трагедию общин» Ардена можно рассматривать как обобщение ДЗ для множества игроков. Каждый житель общины выбирает — пасти ли скот на общем пастбище и получить выгоду, истощая его ресурсы, либо ограничить свой доход. Коллективный результат от всеобщего (или частого) максимального использования пастбища — низкий доход (ведущий к разрушению общины). Однако такая игра не является формальной, поскольку может быть разбита на последовательность классических игр с 2 участниками.
Лекция 10. Моделирование на основе орграфов