Контрольная работа по дисциплине "Теория игр"

S*(a)= (1/4; 1/2; 1/4)   S*(b)= (1/4; 1/2; 1/4)

 

Задание 2. 
Сторона А (ОАО «Магнит») располагает 3 видами товара (А1,А2,А3), а сторона В (конкуренты) 3 видами продукта (В1-более низкая цена,В2-распрастранение антиреклама,В3-лучшие качества товара)

А - пытается реализовать товар на рынке, а В - пытается препятствовать.

Найти оптимальные стратегии и решение игры.

Ход решения:

1.Составить платежную матрицу

	В1	В2	В3
А1	0,8	0,2	0,4
А2	0,4	0,5	0,6
А3	0,1	0,7	0,3

 

Сократим матрицу от дробей (*10).

	В1	В2	В3
А1	8	2	4
А2	4	5	6
А3	1	7	3

 

            

             2.Составить систему уравнения

8x1 + 2x2 + 4x3≥1 
4x1 + 5x2 + 6x3≥1 
x1 + 7x2 + 3x3≥1

F(X) = x1 + x2 + x3

 

3.Составить линейную функцию

Симплекс методом решить систему (предоставить электронное решение)

 
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. 
Определим минимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений. 
8x1 + 2x2 + 4x3≥1 
4x1 + 5x2 + 6x3≥1 
x1 + 7x2 + 3x3≥1 
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). 
В 1-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус. В 3-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус.  
8x1 + 2x2 + 4x3-1x4 + 0x5 + 0x6 = 1 
4x1 + 5x2 + 6x3 + 0x4-1x5 + 0x6 = 1 
1x1 + 7x2 + 3x3 + 0x4 + 0x5-1x6 = 1 
Умножим все строки на (-1) и будем искать первоначальный опорный план. 

-8x1-2x2-4x3 + 1x4 + 0x5 + 0x6 = -1 
-4x1-5x2-6x3 + 0x4 + 1x5 + 0x6 = -1 
-1x1-7x2-3x3 + 0x4 + 0x5 + 1x6 = -1 
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =	-8 -2 -4 1 0 0 -4 -5 -6 0 1 0 -1 -7 -3 0 0 1

 
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. 
Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана. 
Решим систему уравнений относительно базисных переменных: x4, x5, x6 
Полагая, что свободные переменные равны 0, получим первый опорный план: 
X1 = (0,0,0,-1,-1,-1) 
Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6
x4	-1	-8	-2	-4	1	0	0
x5	-1	-4	-5	-6	0	1	0
x6	-1	-1	-7	-3	0	0	1
F(X0)	0	1	1	1	0	0	0

 

 
1. Проверка критерия  оптимальности. 
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 
2. Определение новой свободной переменной. 
Среди отрицательных значений базисных переменных выбираем наибольший по модулю. 
Ведущей будет 1-ая строка, а переменную x4 следует вывести из базиса. 
3. Определение новой базисной переменной. 
Минимальное значение θ соответствует 3-му столбцу, т.е. переменную x3 необходимо ввести в базис. 
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-4).

Базис	B	x1	x2	x3	x4	x5	x6
x4	-1	-8	-2	-4	1	0	0
x5	-1	-4	-5	-6	0	1	0
x6	-1	-1	-7	-3	0	0	1
F(X0)	0	1	1	1	0	0	0
θ		1 : (-8) = -1/8	1 : (-2) = -1/2	1 : (-4) = -1/4	-	-	-

 

 
4. Пересчет симплекс-таблицы. 
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/4	2	1/2	1	-1/4	0	0
x5	1/2	8	-2	0	-3/2	1	0
x6	-1/4	5	-11/2	0	-3/4	0	1
F(X0)	-1/4	-1	1/2	0	1/4	0	0

 

 
Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
-1 : -4	-8 : -4	-2 : -4	-4 : -4	1 : -4	0 : -4	0 : -4
-1-(-1 • -6):-4	-4-(-8 • -6):-4	-5-(-2 • -6):-4	-6-(-4 • -6):-4	0-(1 • -6):-4	1-(0 • -6):-4	0-(0 • -6):-4
-1-(-1 • -3):-4	-1-(-8 • -3):-4	-7-(-2 • -3):-4	-3-(-4 • -3):-4	0-(1 • -3):-4	0-(0 • -3):-4	1-(0 • -3):-4
0-(-1 • 1):-4	1-(-8 • 1):-4	1-(-2 • 1):-4	1-(-4 • 1):-4	0-(1 • 1):-4	0-(0 • 1):-4	0-(0 • 1):-4

 

 
1. Проверка критерия  оптимальности. 
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. 
2. Определение новой свободной переменной. 
Среди отрицательных значений базисных переменных выбираем наибольший по модулю. 
Ведущей будет 3-ая строка, а переменную x6 следует вывести из базиса. 
3. Определение новой базисной переменной. 
Минимальное значение θ соответствует 4-му столбцу, т.е. переменную x4 необходимо ввести в базис. 
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-3/4).

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/4	2	1/2	1	-1/4	0	0
x5	1/2	8	-2	0	-11/2	1	0
x6	-1/4	5	-51/2	0	-3/4	0	1
F(X0)	-1/4	-1	1/2	0	1/4	0	0
θ		-	1/2 : (-51/2) = -1/11	-	1/4 : (-3/4) = -1/3	-	-

 

 
4. Пересчет симплекс-таблицы. 
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/3	1/3	7/3	1	0	0	-1/3
x5	1	-2	9	0	0	1	-2
x4	1/3	-20/3	22/3	0	1	0	-4/3
F(X1)	-1/3	2/3	-4/3	0	0	0	1/3

 

 
Представим расчет каждого элемента в виде таблицы:

 

B	x 1	x 2	x 3	x 4	x 5	x 6
1/4-(-1/4 • -1/4):-3/4	2-(5 • -1/4):-3/4	1/2-(-51/2 • -1/4):-3/4	1-(0 • -1/4):-3/4	-1/4-(-3/4 • -1/4):-3/4	0-(0 • -1/4):-3/4	0-(1 • -1/4):-3/4
1/2-(-1/4 • -11/2):-3/4	8-(5 • -11/2):-3/4	-2-(-51/2 • -11/2):-3/4	0-(0 • -11/2):-3/4	-11/2-(-3/4 • -11/2):-3/4	1-(0 • -11/2):-3/4	0-(1 • -11/2):-3/4
-1/4 : -3/4	5 : -3/4	-51/2 : -3/4	0 : -3/4	-3/4 : -3/4	0 : -3/4	1 : -3/4
-1/4-(-1/4 • 1/4):-3/4	-1-(5 • 1/4):-3/4	1/2-(-51/2 • 1/4):-3/4	0-(0 • 1/4):-3/4	1/4-(-3/4 • 1/4):-3/4	0-(0 • 1/4):-3/4	0-(1 • 1/4):-3/4

 

 
В базисном столбце все элементы положительные. 
Переходим к основному алгоритму симплекс-метода. 
Итерация №0. 
1. Проверка критерия оптимальности. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
2. Определение новой базисной переменной. 
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. 
3. Определение новой свободной переменной. 
Вычислим значения Di по строкам как частное от деления: bi / ai2 
и из них выберем наименьшее: 
min (1/3 : 21/3 , 1 : 9 , 1/3 : 71/3 ) = 1/22 
Следовательно, 3-ая строка является ведущей. 
Разрешающий элемент равен (71/3) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x3	1/3	1/3	21/3	1	0	0	-1/3	1/7
x5	1	-2	9	0	0	1	-2	1/9
x4	1/3	-62/3	71/3	0	1	0	-11/3	1/22
F(X1)	-1/3	2/3	-11/3	0	0	0	1/3	0