Методы нахождения оптимальных смешанных стратегий. - раздел Информатика, РАЗДЕЛ 1.МЕСТО И РОЛЬ ПРОЦЕССОВ ПОДГОТОВКИ И ПРИНЯТИЯ РЕШЕНИЙ В ОБЩЕЙ ТЕХНОЛОГИИ УПРАВЛЕНИЯ СЛОЖНЫМИ ОРГАНИЗАЦИОННО-ТЕХНИЧЕСКИМИ СИСТЕМАМИ (СОТС Процедура Нахождения Оптимальных Чистых Или Смешанных Стратегий Соответствует...
Процедура нахождения оптимальных чистых или смешанных стратегий соответствует выявлению рациональной линии поведения противников в конфликтной ситуации, описываемой игровой моделью. Поэтому такую процедуру часто называют р е ш е н и е м и г р ы (интерпретируя ее как процесс), а пару оптимальных стратегий (чистых или смешанных) называют решением игры, рассматривая ее как результат.
В качестве п о д г о т о в и т е л ь н о г о этапа при решении игры рассматривается этап упрощения игры, который заключается в:
- преобразовании платежной матрицы к более простому виду;
- выделении доминируемых стратегий игроков.
В результате преобразования платежная матрица сводится к виду, когда все ее элементы неотрицательны. При проведении данного преобразования используются два свойства:
1). Если ко всем элементам платежной матрицы добавить некоторое число P, то решение игры не изменится, но цена игры увеличится на P.
2). Если все элементы платежной матрицы умножить на некоторое число Q, то решение игры останется тем же, но цена игры увеличится в Q раз.
Тогда, например, игра с платежной матрицей
|
| 0.5
| 0.6
| 0.9
| эквивалентна игре
|
|
|
|
| F =
| 0.7
| 0.5
| 0.5
| с платежной матрицей F1=
|
|
|
|
|
| 0.9
| 0.7
| 0.8
|
|
|
|
|
При этом все элементы F были домножены на 10 и из элементов полученной матрицы вычли 5, соответственно изменилась и цена игры. Решение игры осталось прежним - седловая точка (3,2); т.е. оптимальны 3-я стратегия первого игрока и 2-я стратегия второго игрока. Если цену игры, равную 2, подвергнуть обратным преобразованиям (добавить 5 и разделить на 10), то получим исходное значение цены игры 0.7.
Решение матричной игры с использованием методов
линейного программирования.
Пусть задана игра с платежной матрицей F = { fij }, в которой у первого игрока m чистых стратегий, а у второго игрока n чистых стратегий. Требуется найти решение игры, т.е. определить оптимальные смешанные стратегии игроков.
Приведем игру к виду, когда в платежной матрице содержатся только положительные элементы. Предположим, что известна оптимальная смешанная стратегия 1-го игрока p=(p1,p2,.. ...,pm)т. Тогда, используя утверждение об активных стратегиях (2.20), можно записать n неравенств вида
pт F ej ³ C , j = 1,...,n.
Это эквивалентно pт F ³ Cт, или Fт p ³ C .
Последние неравенства можно записать в виде
f11p1 + f21p2 + ... + fm1pm ³ C,
f12p1 + f22p2 + ... + fm2pm ³ C,
………...........................…...
f1np1 + f2np2 + ... + fmnpm ³ C.
Т.е. оптимальная смешанная стратегия, примененная против любой стратегии противника дает выигрыш, не меньший цены игры. Если стратегия противника активная - выигрыш равен цене игры, если пассивная, то выигрыш может быть больше цены игры.
Разделим правую и левую часть неравенств на С (т.к. элементы платежной матрицы неотрицательны, то С ³ 0, и характер неравенств сохранится); введем обозначения xi= pi / C, i=1,. ..,m. Тогда
f11x1 + f21x2 + ... + fm1xm ³ 1,
f12x1 + f22x2 + ... + fm2xm ³ 1,
………............................... (5.15)
f1nx1 + f2nx2 + ... + fmnxm ³ 1,
xi ³ 0, i = 1,...,m.
Последнее условие следует из того, что pi и C положительны. Все эти условия задают множество возможных смешанных стратегий первого игрока. Из этого множества целесообразно выделять стратегию, доставляющую максимальный выигрыш первому игроку, или, что одно и то же, стратегию, максимизирующую цену игры. Рассмотрим для этого линейную форму
L(x) = x1 + x2 + ... + xm. (5.16)
Подставим значения xi (xi = pi/C) и получим,
L(x) = 1/C ( p1 + p2 + ... + pm ) = 1/C.
Действительно, сумма pi, i=1,...,m равна 1 ( из определения смешанной стратегии).
Следовательно, минимизируя L(x) на множестве допустимых x, которое задается (5.15), можно найти оптимальную смешанную стратегию p, доставляющую максимум цене игры. В силу линейности целевой функции и ограничений такая задача может решаться методами линейного программирования. Решение этой задачи всегда существует, т.к. значения F неотрицательны и ищется минимум суммы неизвестных переменных.
Оптимальная смешанная стратегия определяется как pi = xi/L, i = 1,...,m; цена игры C = 1/L.
Оптимальная смешанная стратегия второго игрока находится в результате решения задачи, двойственной к поставленной задаче. Тогда использование метода обратной матрицы [ХХ], позволяющего одновременно получать решения задач двойственной пары, обеспечивает нахождение оптимальных смешанных стратегий обоих игроков.
Все темы данного раздела:
Общая характеристика задач подготовки и принятия решений в СОТС.
Важнейшая особенность современной научно-технической революции состоит в том, что по мере её развития всё большее значение приобретает учёт факторов сложности технико-эконом
Концептуальная модель принятия решений
Анализ многочисленных публикаций по различным аспектам проблемы выбора показывает, что в настоящее время наметилась прогрессивная тенденция к интеграции различных научных направлени
Обобщенная структура современных интегрированных систем поддержки принятия решений
Рис.1.3.1. Функциональная схема интегрированной системы поддержки принятия решений по управлению структурн
Постановка задачи линейного программирования
Значительная часть задач принятия решения – это задачи распределения ресурсовмежду объектами.
Пусть имеется т видов ресурсов, каждый i
Экономическая интерпретация задачи линейного программирования
Пример 2.1. Пусть требуется определить план выпуска четырёх видов продукции П1, П2, П3, П4, для изготовления которы
Анализ существования решений в задаче линейного программирования
Рассмотрим неравенство ах £ b. Если от неравенства мы хотим перейти к уравнению, то введём дополнительную переменную у и запишем
Графический метод решения задач линейного программирования
Вспомним построение линейных зависимостей. Начнём с уравнений.
Линейное уравнение с двумя
Двойственные задачи линейного программирования
Каждой задаче ЛП можно некоторым образом сопоставить другую задачу ЛП, называемую двойственной по отношению к исходной (прямой):
Прямая задача (ПЗ)
Анализ решений задач линейного программирования.
Рассмотрим следующую задачу ЛП:
(1)
Обобщенный алгоритм решения задач НЛП
Эффективное решение различных задач нелинейного программирования может быть осуществлено на основе учета конкретных особенностей этих задач. При этом под эффективностью того или иного алгоритма, ка
Аналитические методы решения задач НЛП
В некоторых случаях задачи НЛП удается решить аналитически. Это, в частности, удается в том случае, если ЦФ и ОДА являются выпуклыми. Обобщенный алгоритм решения задачи НЛП включает в себя следующи
Численные методы решения задач НЛП
В качестве r(xk) используется направление, в котором наиболее сильно возрастает целевая функция. Это направление задается градиентом функции ÑF(xk). Суть метода состоит
Постоянный шаг.
Задается hk = h = const, при этом должно выполняться условие
F(xk+1) = F(xk + hkÑF(xk)) > F(xk).
Пусть
Наискорейший подъем.
Если подставить в выражение для F(x) значение x=xk+1 в соответствии с (1), то получим выражение F(xk+hkÑF(xk)), как функцию от величины шага. След
Функции Лагранжа
Исторически первым способом сведения задачи с ограничениями к задаче безусловной оптимизации явилось использование функции Лагранжа L(x,m)
L(x, m) = f(x) + mт(b - j(x)) = f(x) +
Штрафные функции
Исходная задача условной оптимизации сводится к последовательности задач безусловной оптимизации функций
Fk(x, m) = f(x) - Sk(x, mk), k = 1,2,3,....
Методы прямой условной оптимизации
Методы прямой условной оптимизации предназначены для непосредственного решения задачи выпуклого программирования в условиях ограничений, описывающих множество допустимых решений D.
Итак, п
Метод условного градиента
Существо метода условного градиента состоит в том, что, если известна некоторая точка xkÎD, то направление возрастания целевой функции может задаваться некоторой внутренней или кра
Постановка задачи целочисленного программирования
Первые упоминания о линейных уравнениях возникли ещё за несколько веков до нашей эры.
В Древней Греции Диофант (II-III в.) формулирует уравнения, в которых искомые переменн
Основные этапы решения задачи целочисленного программирования (ЗЦП) методом ветвей и границ
Шаг 1. Исходная ЗЦП решается как задача линейного программирования (ЗЛП) (снимаем ограничения вида (г)). При этом за «рекорд» в ЗЦП принимают значение целевой функц
Постановка задачи бивалентного (булева) программирования
Перейдем теперь к частному случаю задач целочисленного программирования. В этом частном случае искомая переменная
Эвристический метод решения задачи булева программирования.
Существует два метода решения задач с булевыми переменными.
Во-первых, их можно решать как обычные задачи целочисленного программирования, т. е. методом ветвей и границ. Пр
Характерные особенности задач многокритериального выбора
Реальные задачи выбора, возникающие на практике, чрезвычайно разнообразны, но всех их объединяет общая схема поиска решения, суть которой состоит в формировании совокупности операци
Уточненное описание структуры выбора с многими отношениями предпочтения. Общая постановка задач векторной оптимизации
Обобщенная структура выбора с мультипредпочтением, описывающая задачи векторной оптимизации, имеет следующий вид:
Принцип В.Парето в задачах многокритериального выбора
В п. 4.1 было установлено, что для корректного решения задач многокритериального выбора необходимо в исходную постановку задачи (4.1)‑(4.2) привнести дополнительную информацию
Основные свойства множества Парето
Рассмотрим основные свойства множества Парето (множества и соответственно
Методы построения множества Парето
Приведенные в п.4.2.2 свойства множества Парето могут быть использованы для построения (исследования) данного множества (либо его подмножеств) или определения его характеристик в ко
Методы покомпонентного построения результирующих отношений предпочтения
Основное содержание данных методов сводится к формированию сужающейся последовательности множеств (ядер):
Методы построения результирующих отношений предпочтения на основе свертки показателей
Сущность данных методов многокритериальной оптимизации состоит в построении такого результирующего отношения предпочтения
Характеристика задач принятия решений в условиях неопределенности среды
Процессы анализа сложных экономических систем и принятия решений в них связаны с выделением изучаемой системы из некоторой системы большего масштаба (метасистемы), т.е. разделения этой метасистемы
Принятие решений в условиях стохастической среды
Постановка задач принятия решений в условиях стохастической среды имеет вид
(D(w), f(w)), wÎW,
где D(w) - множество допустимых альтернатив, f(w) - целевая функция.
Методы детерминизации.
При решении конкретных задач выбора на вероятностных структурах часто вводится предположение о том, что задание целевой функции f(w) и ограничивающих отношений ri(w), i=1,...,m, определя
Методы имитационной оптимизации.
В методах имитационной оптимизации (прямых методах стохастического выбора) не производится преобразование задачи к ее детерминированному эквиваленту. Суть данных методов заключается в том, что гене
Принятие решений в условиях целенаправленной среды
Принятие решений в условиях целенаправленной среды связано с тем, что известна цель среды, в соответствии с которой она выбирает свои состояния и которую преследует в своих действиях. Эти действия
Постановка задач игрового выбора.
Рассмотрим формализованное представление задачи принятия решений в условиях целенаправленной среды. Обобщенную задачу принятия решения в условиях неопределенности можно записать в виде
(D
Матричные игры. Чистые и смешанные стратегии.
Простейшим вариантом игры является антагонистическая игра, в которой противодействуют две оперирующих стороны (2 игрока), при этом множества различных альтернатив из которых они выбирают решения ко
Принятие решений в условиях неизвестной среды
В случае неизвестной среды нет достаточных оснований для предположений о том, какие значения будут принимать параметры, характеризующие состояние среды на рассматриваемом временном интервале. При э
Новости и инфо для студентов