Состязательная задача

Федеральное агентство по образованию 

                         Государственное образовательное  учреждение  
                              высшего профессионального образования

«Южно-Уральский  государственный университет»

Институт  открытого и дистанционного образования

 

 

 

 

                           практическая  РАБОТА №4

                                       по математике

                      Тема: Состязательная задача

 

 

 

 

 

 

 

 

Автор работы

 

студент группы ИОДО – 264

спец. менеджмент Л.А.Гончарова

 

« 15   »         мая               2013 г.

           

 

 

 

 

 

 

 

 

 

 

1. Найти решение игры, предварительно  упростив её:

 

 

 

 

Найдем верхнюю  и нижнюю цену игры.

	В				min
А	3	-2	5	-1	-2
	4	0	6	1	0
	2	-1	3	2	-1
	1	3	7	4	1
max	4	3	7	4

Получили, что нижняя цена игры max(min(=1 и верхняя цена игры

max(min(=3.

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

Уберем из матрицы игры доминируемые строки и столбцы:

- вторая строка доминирует над  первой – все элементы второй  строки больше либо равны соответствующим  элементам первой строки: первую  строку убираем;

Получаем:

Стратегии	В1	В2	В3	В4
А2	4	0	6	1
А3	2	-1	3	2
А4	1	3	7	4

- второй столбец доминирует  над третьим и четвёртым –  все элементы второго столбца  меньше либо равны соответствующим  элементам третьего и четвёртого  столбцов: эти два столбца можно  убрать;

Получаем:

Стратегии	В1	В2
А2	4	0
А3	2	-1
А4	1	3

Запишем для игры с матрицей A*=  математическую модель задачи линейного программирования:

F= при ограничениях-неравенствах:

Решим полученную задачу симплекс-методом.

 

Введем вспомогательные переменные , , для получения из ограничений-неравенств системы уравнений  при этом целевая функция примет вид:

F=

Составим симплекс-таблицу:

базис	Сбаз	А0	1	1	0	0	0
	0	1	4	0	1	0	0
	0	1	2	-1	0	1	0
	0	1	1	3	0	0	1
		0	-1	-1	0	0	0

Условием оптимальности является

Находим минимальное  и определяем минимальное значение ( ):

базис	Сбаз	А0	1	1	0	0	0
	0	1	4	0	1	0	0	0,25
	0	1	2	-1	0	1	0	0,5
	0	1	1	3	0	0	1	1
		0	-1	-1	0	0	0

Произведём замену базисной переменной на переменную и при необходимости продолжим оптимизацию.

базис	Сбаз	А0	1	1	0	0	0
	1	0,25	1	0	0,25	0	0	-
	0	0,5	0	-1	-0,5	1	0	-
	0	0,75	0	3	-0,25	0	1	0,25
		0,25	0	-1	0,25	0	0

 

базис	Сбаз	А0	1	1	0	0	0
	1	0,25	1	0	0,25	0	0
	0	0,75	0	0	-7/12	1	1/3
	1	0,25	0	1	-1/12	0	1/3
		0,5	0	0	1/6	0	1/3

Условие оптимальности выполняется.

Решение прямой задачи X= (0,25; 0,25) при этом =0,5.

Решение двойственной задачи Y= при этом =0,5..

Из решений пары двойственных задач  получим цену игры и оптимальные  стратегии игроков в игре с  исходной матрицей А*, то есть

 V=

  = v  = v  X=5(0,25;0,25)=(0,5;0,5)

Исходная игра имеет оптимальные  стратегии P=  и Q=(0,5;0,5;0;0) и цену игры v=2.

Получаем нижняя цена игры 1, верхняя цена игры 3, оптимальная цена ;

стратегии первого  игрока: P=, второго игрока:

Q = (0,5;0,5;0;0)