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

Решение игр m*n с помощью ЭВМ.

Задание 1.

Найти с помощью метода линейного программирования решение игры («3пальца») 
             Ход решения:

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

	В1	В2	В3
А1	2	-3	4
А2	-3	4	-5
А3	4	-5	6

 

Перейдем к положительным значениям элементам матрицы, прибавим ко всем числам одно и тоже число 5.

	В1	В2	В3
А1	7	2	9
А2	2	9	0
А3	9	0	11

 

 

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

7x1 + 2x2 + 9x3≥1 
2x1 + 9x2 + 0х3≥1 
9x1 + 0х2 +11x3≥1

 

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

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

 

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

A =	-7 -2 -9 1 0 0 -2 -9 0 0 1 0 -9 0 -11 0 0 1

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

Базис	B	x1	x2	x3	x4	x5	x6
x4	-1	-7	-2	-9	1	0	0
x5	-1	-2	-9	0	0	1	0
x6	-1	-9	0	-11	0	0	1
F(X0)	0	1	1	1	0	0	0

 

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

Базис	B	x1	x2	x3	x4	x5	x6
x4	-1	-7	-2	-9	1	0	0
x5	-1	-2	-9	0	0	1	0
x6	-1	-9	0	-11	0	0	1
F(X0)	0	1	1	1	0	0	0
θ		1 : (-7) = -1/7	1 : (-2) = -1/2	1 : (-9) = -1/9	-	-	-

 

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

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

 

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

 

 

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

 

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

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/9	7/9	2/9	1	-1/9	0	0
x5	-1	-2	-9	0	0	1	0
x6	2/9	-4/9	24/9	0	-12/9	0	1
F(X0)	-1/9	2/9	7/9	0	1/9	0	0
θ		2/9 : (-2) = -1/9	7/9 : (-9) = -7/81	-	-	-	-

 

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

Базис	B	x1	x2	x3	x4	x5	x6
x3	7/81	59/81	0	1	-1/9	2/81	0
x2	1/9	2/9	1	0	0	-1/9	0
x6	-4/81	-80/81	0	0	-11/9	22/81	1
F(X1)	-16/81	4/81	0	0	1/9	7/81	0

 

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

B	x 1	x 2	x 3	x 4	x 5	x 6
1/9-(-1 • 2/9):-9	7/9-(-2 • 2/9):-9	2/9-(-9 • 2/9):-9	1-(0 • 2/9):-9	-1/9-(0 • 2/9):-9	0-(1 • 2/9):-9	0-(0 • 2/9):-9
-1 : -9	-2 : -9	-9 : -9	0 : -9	0 : -9	1 : -9	0 : -9
2/9-(-1 • 24/9):-9	-4/9-(-2 • 24/9):-9	24/9-(-9 • 24/9):-9	0-(0 • 24/9):-9	-12/9-(0 • 24/9):-9	0-(1 • 24/9):-9	1-(0 • 24/9):-9
-1/9-(-1 • 7/9):-9	2/9-(-2 • 7/9):-9	7/9-(-9 • 7/9):-9	0-(0 • 7/9):-9	1/9-(0 • 7/9):-9	0-(1 • 7/9):-9	0-(0 • 7/9):-9

 

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

Базис	B	x1	x2	x3	x4	x5	x6
x3	7/81	59/81	0	1	-1/9	2/81	0
x2	1/9	2/9	1	0	0	-1/9	0
x6	-4/81	-80/81	0	0	-12/9	22/81	1
F(X0)	-16/81	4/81	0	0	1/9	7/81	0
θ		4/81 : (-80/81) = -1/20	-	-	1/9 : (-12/9) = -1/11	-	-