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

Задание 1

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

.

Решение

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

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

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

.

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

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

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

 

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

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

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

Ответ: ,. .

 

 

Задание 2

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

Решение

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

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

 

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

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

Заполним симплексную  таблицу по исходным данным (таблица 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

 

 

Так как среди элементов  строки целевой функции (не считая свободного члена) отрицательных нет, решение  прямой задачи найдено – вектор . Решение двойственной задачи выписываем из последней симплексной таблицы: свободным переменным y₁, y₂ прямой задачи соответствуют базисные переменные x₃, x₄ двойственной, а базисным переменным y₃, y₄ соответствуют свободные переменные x₁, x₂. Получаем решение двойственной задачи: .

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

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

Ответ: ; ; .

 

Задание 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 р. за один лоток. Если хлеб не реализован в течение дня, магазин несет убытки. Определить оптимальную стратегию по количеству приобретенных для продажи лотков хлеба, используя известные критерии: Гурвица (по матрице выигрышей и по матрице рисков), Вальда, Сэвиджа, Лапласа, Байеса-Лапласа, максимаксный критерий.