Контрольная работа по "Высшей математике"

Автор работы: Пользователь скрыл имя, 23 Апреля 2013 в 13:05, контрольная работа

Краткое описание

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

Прикрепленные файлы: 1 файл

теория игр.docx

— 223.65 Кб (Скачать документ)

Задание 1

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

.

Решение

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

соответственно

Так как  , игра седловой точки не имеет. Теперь упростим матрицу игры, используя принцип доминирования. Для определенности сначала сравним между собой элементы строк и доминируемые строки, если такие имеются, вычеркнем. Итак, все элементы третьей строки строго больше соответствующих элементов второй строки, значит, третья строка доминирует над второй, то есть третья строка является доминирующей, а вторая - доминируемой, поэтому вторую строку вычеркиваем. Аналогично третья строка доминирует над четвертой, значит, вычеркиваем и четвертую строку. Остальные строки не являются доминируемыми или доминирующими. В оставшейся матрице порядка 2´4 сравниваем между собой соответствующие элементы столбцов. Второй и третий столбцы доминируют над первым и четвертым, значит, второй и третий столбцы является доминирующими, а первый и четвертый - доминируемыми, следовательно, вычеркиваем второй и третий столбцы. В результате получаем квадратную матрицу второго порядка, которую больше не упростить:

.

С помощью графического метода найдем решение полученной игры порядка 2´2. Построим графики для первого и второго игроков.

Рисунок 1 – Графики для  определения стратегий игроков, цены игры

Сделаем проверку аналитически, для этого нужно решить две  системы уравнений; для первого  игрока:

 

Для второго игрока:

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

Таким образом, цена игры , а полученные оптимальные стратегии игроков соответственно равны: . Нулевые вероятности соответствуют вычеркнутым при упрощении строкам и столбцам.

Ответ: ,. .

 

 

Задание 2

Найти цену игры и оптимальные  стратегии игроков для заданной матрицы игры Н, предварительно упростив ее по возможности; для решения применить симплекс-метод, составив соответствующую ЗЛП (задачу линейного программирования).

Решение

Сначала упростим платежную  матрицу, используя принцип доминирования. Например, вторая строка доминирует над первой, следовательно, первая строка – доминируемая, а вторая – доминирующая, поэтому первую строку вычеркиваем. В оставшейся матрице сравниваем столбцы: первый столбец доминирует над вторым, поэтому является доминирующим, значит, его вычеркиваем. Получаем квадратную матрицу второго порядка, в которой уже ничего не упростить.

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

 

Решение найдем, используя  симплекс – метод. Сначала нужно  найти решение прямой задачи (вектор ), а затем по симплексной таблице записать решение двойственной задачи (вектор ).

В ограничениях перейдем от неравенств к равенствам, для этого  введем базисные переменные y3, y4:

Заполним симплексную  таблицу по исходным данным (таблица 1).

Таблица 1 – Итерация №0

Базисные

переменные

Свободные

члены

Свободные переменные

-y1

-y2

y3

1

0

3

y4

1

1

0

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

0

-1

-1


 

 

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

Таблица 2 – Итерация №1

Базисные

переменные

Свободные

члены

Свободные переменные

-y1

-y3

y2

1/3

0

1/3

y4

1

1

0

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

1/3

-1

1/3


 

 

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

 

Таблица 3 – Итерация №2

Базисные

переменные

Свободные

члены

Свободные переменные

-y4

-y3

y2

1/3

0

1/3

y1

1

1

0

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

1 1/3

1

1/3


 

 

Так как среди элементов  строки целевой функции (не считая свободного члена) отрицательных нет, решение  прямой задачи найдено – вектор . Решение двойственной задачи выписываем из последней симплексной таблицы: свободным переменным y1, y2 прямой задачи соответствуют базисные переменные x3, x4 двойственной, а базисным переменным y3, y4 соответствуют свободные переменные x1, x2. Получаем решение двойственной задачи: .

Запишем решение матричной  игры: цена игры вычисляется следующим  образом -  , то есть  . Оптимальные стратегии найдем по формулам:  , .

Нулевые вероятности соответствуют  вычеркнутым при упрощении строкам и столбцам. Таким образом, решение игры имеет вид:

Ответ: ; ; .

 

Задание 3

Решить матричную игру с платежной матрицей В итерационным методом Брауна с точностью ε=0,3.

Решение

Седловая точка отсутствует, так как  , действительно

Решение ищем в смешанных  стратегиях. Следуя правилам, заполним таблицу метода Брауна, начиная с произвольной стратегии игрока 1, например, с первой.

Таблица 4 – Таблица метода Брауна

k

i

B1

B2

B3

j

A1

A2

A3

C*

1

1

-1

0

1

1

-1

1

0

-1

1

0

2

2

0

-1

1

2

-1

0

1

-1/2

1/2

0

3

3

0

0

0

3

0

0

0

0

0

0

4

2

1

-1

0

2

0

-1

1

-1/4

1/4

0

5

3

1

0

-1

3

1

-1

0

-1/5

1/5

0

6

1

0

0

0

1

0

0

0

0

0

0

7

3

0

1

-1

3

1

0

-1

-1/7

1/7

0

8

1

-1

1

0

1

0

1

-1

-1/8

1/8

0

9

2

0

0

0

2

0

0

0

0

0

0


 

 

Итак, сделав достаточное  число итераций, запишем смешанные  стратегии игрока 1 и игрока 2 (по частоте появления) и цену игры.

Ответ: ; ; .

 

 

Задание 4

Найти полное решение матричной  игры с заданной платежной матрицей С, используя метод Шепли-Сноу.

 

Решение

Находим , значит, седловой точки у данной матрицы нет. Запишем все квадратные подматрицы порядка 2´2 и исключим непригодные:


 

То есть осталось 4 подматрицы порядка 2´2, в которых нужно искать решение.

1 Рассмотрим квадратную подматрицу порядка 3´3, какой является исходная матрица:

.

Составим соответствующую  систему неравенств для нахождения стратегий первого игрока:

Решаем любым известным  методом, например, методом Гаусса:

.

Условие неотрицательности  выполняется, так как найденные  вероятности не отрицательны.

Далее составляем соответствующую  систему неравенств для определения  стратегии второго игрока и решаем её:

Условие неотрицательности  выполняется, потому что полученные вероятности положительны. Таким  образом, подматрица дает решение:

;

2 Рассмотрим квадратные подматрицы порядка 2´2:

а) Подматрица вида

Составляем соответствующую  систему неравенств и определяем её решение:

Условие неотрицательности  выполняется. Проверяем условие  оптимальности для вычеркнутого столбца: то есть верно, соответственно условие оптимальности выполняется.

Далее составляем соответствующую  систему неравенств для определения  стратегии второго игрока и решаем её:

В найденном решении условие  неотрицательности выполняется (найденные вероятности положительны), сделаем проверку условия оптимальности для вычеркнутой строки: то есть верно, соответственно условие оптимальности выполняется. Таким образом, подматрица дает решение:

;

б) Подматрица вида

Составляем соответствующую  систему неравенств и решаем её:

Условие неотрицательности  выполняется (полученные вероятности  положительны). Проверяем условие оптимальности для вычеркнутого столбца: то есть . Условие оптимальности не выполняется. Следовательно, данная подматрица решения не дает.

в) Подматрица вида

Составляем соответствующую  систему неравенств и находим  её решение:

Условие неотрицательности  выполняется (найденные вероятности  положительны). Проверим условие оптимальности для вычеркнутого столбца: то есть - верно. Условие оптимальности выполняется.

Далее составляем соответствующую  систему неравенств для определения  стратегии второго игрока и определяем ее решение:

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

;

г) Подматрица вида

Составляем соответствующую  систему неравенств и находим  её решение:

Условие неотрицательности  выполняется, так как полученные вероятности положительны. Проверим условие оптимальности для вычеркнутого столбца: то есть - верно. Условие оптимальности выполняется.

Далее составляем соответствующую  систему неравенств для определения  стратегии второго игрока и определяем ее решение:

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

;

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

Ответ:

 

Задание 5

По предложенной игровой  ситуации составить платежную матрицу  и найти решение игры с природой.

Магазин «Горячий хлеб» продает  в розницу хлебобулочные изделия. Заведующий должен определить, сколько  лотков хлеба следует закупать у  хлебозавода ежедневно. Вероятности того, что спрос на хлеб в течение дня будет 5, 7, 9 или 10 лотков, равны соответственно 0,45; 0,3; 0,15 и 0,1. Покупка одного лотка хлеба обходится магазину в 50 р., а продается хлеб по цене 95 р. за один лоток. Если хлеб не реализован в течение дня, магазин несет убытки. Определить оптимальную стратегию по количеству приобретенных для продажи лотков хлеба, используя известные критерии: Гурвица (по матрице выигрышей и по матрице рисков), Вальда, Сэвиджа, Лапласа, Байеса-Лапласа, максимаксный критерий.

Информация о работе Контрольная работа по "Высшей математике"