Основные понятия и определения. Для практических занятий

РУКОВОДСТВО

Для практических занятий

по курсу

ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ

 

Оглавление

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

1. Тема: Принятие решений в задачах теории антагонистических игр 7

1.1. Игры двух лиц с нулевой суммой. 7

1.2. Аналитическое решение игры (2×2) 11

1.3. Геометрический метод решения игр. 11

1.4. Решение игры методом последовательных приближений. 14

1.5 Решение игр (m×n) методом линейного программирования. 15

1.6. Варианты заданий для самостоятельной работы.. 19

Библиографический список 22

Основная литература. 22

Дополнительная литература. 22

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

Принято различать постановку задачи для индивидуального и группового лица принимающего решение (ЛПР).

Постановка задачи для индивидуального ЛПР формально записывается в виде следующих условий:

,

где слева от вертикальной черты находятся исходные данные задачи принятия решения, справа – неизвестные. Здесь приняты следующие обозначения: S₀ – проблемная ситуация, T– время для принятия решения, Q– ресурсы; S={S₁,…,S_n } – множество альтернативных ситуаций доопределяющих ситуацию S₀ до полной группы взаимоисключающих, независимых или гипотетических ситуаций, причем сумма вероятностей их возникновения равна 1; A– множество целей; B– множество ограничений при принятии решений; Y– множество альтернативных вариантов решений, из которых должно быть выбрано единственное Y* – оптимальное решение; f(A, S, Y) – функция предпочтения для оценки решений; K– критерий выбора наилучшего решения Y*.

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

Возникновение проблемы связано с определенными условиями, которые называются ситуациями. Совокупность проблем и ситуаций в ТПР называют проблемной ситуацией.

Субъектом всякого решения является ЛПР, для поддержки или консультаций которого привлекаются эксперты – специалисты по решаемой проблеме.

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

Для осуществления выбора лучшего решения индивидуальное ЛПР определяет критерии выбора, т.е признаки, на основании которых производится оценка, определение или классификация решений.

Таким образом, общая постановка задачи принятия решения для индивидуального ЛПР состоит в следующем: в условиях проблемной ситуации S₀, располагаемого времени T и ресурсов Q, необходимо доопределить ситуацию S₀ множеством альтернативных ситуаций S, сформулировать множество целей A, ограничений B, множество альтернативных решений Y, произвести оценку предпочтений функции f и найти оптимальное решение Y* из множества Y, руководствуясь критерием выбора К.

Постановка задачи для группового ЛПР формально записывается в виде следующих условий:

,

где F(f) – функция группового предпочтения, зависящая от индивидуальных предпочтений d-лиц, входящих в группу, т.е. от f=(f_1,….,f_d), L – принцип согласования индивидуальных предпочтений (например, принцип большинства голосов), т.е. выбор должен происходить на основе некоторого правила согласования индивидуальных предпочтений.

Общая постановка задачи принятия решения для группового ЛПР состоит в следующем: в условиях проблемной ситуации S₀, располагаемого времени T и ресурсов Q, необходимо доопределить ситуацию S₀ множеством альтернативных ситуаций S, сформулировать множество целей A, ограничений B, множество альтернативных решений Y, произвести оценку группового предпочтений по функции F(f) и найти оптимальное решение Y* из множества Y, руководствуясь принципом согласования индивидуальных предпочтений L.

Задачи принятия решений классифицируют по следующим признакам:

· по степени структурированности условий (хорошо структурированные задачи, в которых все зависимости выявлены четко, выражены в числах или символах; неструктурированные, для которых имеется лишь качественное описание задачи; слабоструктурированные или смешанные задачи);

· по степени определенности информации о множестве и критериях (предпочтениях) при выборе решений (если Y, K или L неизвестны, то речь идет об общей задаче принятия решений; если множество допустимых решений Y известно, то говорят о задаче выбора решений; если Y, K, L известны, то это задача оптимизации;

· в зависимости от того использовался или нет эксперимент, различают задачи принятия решений по апостериорным (опытным) данным или по априорным данным;

· по количеству лиц, принимающих решение (индивидуальные и групповые ЛПР), по количеству целей (одноцелевые и многоцелевые);

· по области применения решений (экономические, политические, технические и т.п.);

· по длительность действия решения (долговременные, среднесрочные, краткосрочные) и значимость (стратегические, тактические).

Теория, которая рассматривает ситуации конфликта двух и более противников называется теорией антагонистических игр. В теории игр противников принято называть игроками. Предполагается, что каждый из игроков обладает конечным (бесконечным) множеством альтернативных решений. Это множество называют множеством стратегий игроков. Результаты игры характеризуются платежными функциями, которые зависят от стратегии игроков. Антагонистические игры с двумя игроками, в которых выигрыш одного равен проигрышу другого, получили название антагонистические игры двух лиц с нулевой суммой. Целью теории игр является выработка рекомендаций для разумного поведения игроков в конфликтных ситуациях, т.е. выработка оптимальных стратегий для каждого игрока. Под оптимальной стратегией игрока понимается такая стратегия, использование которой при многократном повторении игры обеспечивает игроку максимально возможный средний выигрыш или минимально возможный средний проигрыш. Игра G задается тройкой множеств (X, Y, L(x, y)), где X={x₁, x₂,…,x_m}- множество стратегий 1-го игрока, Y={y₁, y₂,…,y_n}- множество стратегий 2-го игрока, L(x, y) - платежная функция (ограниченная числовая функция одного из игроков, определенная на декартовом произведении множеств X×Y и равная математическому ожиданию выигрыша/проигрыша данного игрока). Функцию L задают в виде платежной матрицы Q=║q_ij║_m×n, где q_ij=L(x_i, y_j).

Нижняя чистая цена игры равна . Верхняя чистая цена игры равна . Если α=β=ν, то игра имеет седловую точку (точка равновесия или точка Нэша), т.е. решение в чистых стратегиях. Это означает, что в платежной матрице имеется как минимум один элемент, который одновременно является минимумом в строке и максимумом в столбце платежной матрицы игры. Оптимальное решение достигнуто, если ни одному из игроков невыгодно изменять свою стратегию.

Если α<β, то при многократном повторении игры игроки должны использовать смешанные стратегии, когда чистые стратегии 1-й игрок чередует случайным образом с вероятностями ξ=(ξ₁,…,ξ_m), а 2-й игрок – с вероятностями η=(η₁,…,η_n), где ξ_i- вероятность применения 1-м игроком своей чистой стратегии x_i, а η_j - вероятность применения 2-м игроком своей чистой стратегии y_j, при условиях:

Активной называется такая стратегия x_i или y_j, которая входит в состав оптимальной смешанной стратегии ξ*=(ξ*₁,…,ξ*_m) или η*=(η*₁,…,η*_n) с вероятностью отличной от нуля, т.е. ξ*_i>0 или η*_j>0.

В статистических играх участвуют ЛПР и природа, под которой обычно понимают некоторую совокупность внешних не всегда определенных факторов, в условиях которых приходится принимать решение. Обозначим через E={E₁,E₂,…,E_m} – множество альтернативных решений ЛПР, а через F={F₁, F₂,…, F_n} – множество состояний природы. Cтатистическая игра описывается матрицей E=║e_ij║_m×n, где e_ij - оценка полезности i-го решения в j-й ситуации (выигрыш, надежность и т.п.). Задача теории статистических игр состоит в том, чтобы, используя критерий выбора, найти оптимальное решение ЛПР. Классическими критериями выбора считаются критерии максимина (ММ), Байеса-Лапласа (BL), Сэвиджа (S); производными критериями – критерии Гурвица (HW), Ходжа-Лемана (HL), Гермейера (G), BL(MM), произведений (Р).

Полезность - это величина, которую ЛПР максимизирует в процессе выбора решения.

Под измерением будем понимать процедуру сравнения решений по определенным показателям (признакам, характеристикам).

Шкала измерений – это совокупность трех систем: <M, N, f>, где М - эмпирическая система, состоящая из множества измеряемых решений и множества отношений между ними; N - универсальная числовая система, состоящая из множества действительных чисел и множества отношений между ними, f - взаимно однозначное или просто однозначное отображение эмпирически измеренных решений на числовую систему. Наиболее часто на практике используются следующие типы шкал измерений: наименований, порядковая, интервалов, отношений, разностей, абсолютная. Различают следующие методы субъективных измерений: ранжирование; парное сравнение; непосредственная оценка; последовательное сравнение.

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

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

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

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