Сведение задачи теории игр к задаче линейного программирования — КиберПедия 

Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...

Сведение задачи теории игр к задаче линейного программирования

2017-11-28 559
Сведение задачи теории игр к задаче линейного программирования 0.00 из 5.00 0 оценок
Заказать работу

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

Для игрока А задача формулируется в виде:

Найти минимум целевой функции , где переменные удовлетворяют системе ограничений (матрица М транспонируется!)

 

 

Для игрока В задача формулируется в виде:

Найти маскимум целевой функции , где переменные , удовлетворяют системе ограничений

 

Доминирование матричной игры

Доминировать матричную игру, значит, сократить ее размер.

Для этого пользуются следующими положениями.

Если в матрице имеются одинаковые (дублирующие) строки, то одна из них оставляется, а другие убираются.

Если в матрице имеются одинаковые (дублирующие) столбцы, то один из них оставляется, а другие убираются.

Если все элементы i – й строки матрицы М меньше или равны соответствующих элементов k – й строки, то i –я стратегия игрока А называется доминирующей и ее следует убрать.

Если все элементы r – го столбца матрицы М больше или равны соответствующих элементов j – го столбца, то для игрока Вr – я стратегия является доминирующей и ее следует убрать.

 

Игры с природой

На практике часто встречается класс матричных игр, в которых стратегия второго игрока неопределена. Это, так называемые, «игры с природой». Например, нас интересует вопрос об объемах поставок продукции на рынок в условиях полной неопределенности о величине спроса на эту продукцию.

В этом случае выбор стратегии осуществляется на основе критериев, которые позволяют оценить «среднюю прибыль».

Критерий Вальда:

Критерий Сэвиджа:

,

где - элементы матрицы R – матрицы риска. Эта матрица составляется по правилу: в столбце определяется наибольший элемент и из этого числа вычитаются последовательно все элементы этого столбца.

Критерий Гурвица:

,

где , значение параметра k - задается самим исследователем.

 

Пример 1. Для заданной матрицы игры

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

Решение.

Выводы:

, решение в чистых стратегиях;

Седловая точка ;

Игрок А выбирает чистую стратегию ;

Игрок В выбирает стратегию . Цена игры .

2) Выполнить доминирование матрицы М.

.

Решение.

1. Элементы 4-го столбца превосходят соответствующие элементы 1-го столбца. Значит, этот столбец доминирующий. Его убираем из матрицы.

2. Во второй матрице доминирующими являются 1-я и 2-я строки, так как их элементы меньше соответствующих элементов 3-й строки. Их убираем.

3. В третьей матрице доминирующими являются 2-й и 3-й столбцы.

4. Получили матрицу, состоящую из одного элемента .

 

Пример 2. Свести исходную матричную игру к паре двойственных ЗЛП.

Решение.

1.

Выводы: . Задача решается в смешанных стратегиях.

2. Сведем матричную игру к паре двойственных ЗЛП.

Сначала получим матрицу с положительными элементами. Для этого к каждому элементу матрицы М прибавим число , то есть абсолютную величину наименьшего элемента матрицы М.

Получим матрицу :

.

ЗЛП для игрока А:

переменные ;

целевая функция ;

система ограничений: (матрицу М1 транспонируем)

.

ЗЛП для игрока В:

переменные ;

целевая функция ;

система ограничений:

.

 

Пример 3. Полагая матрицу

 

матрицей игры с природой найти решение игры, используя критерии Вальда, Сэвиджа и Гурвица при k = 0,7.

Решение.

 

1. Критерий Вальда:

.

Вывод: Активные стратегии А2 или А3.

2. Критерий Сэвиджа:

Построим сначала матрицу рисков R.

Затем вычислим

.

Вывод: Активная стратегия А2.

3. Критерий Гурвица (k = 0,7)

Вывод: Активные стратегии А2 или А3.

Ответ. Рекомендация – выбрать стратегию А2.

 


Поделиться с друзьями:

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...

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

Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...

Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.015 с.