Эксперт по сдаче вступительных испытаний в ВУЗах
Контрольная работа №4
Вариант 1
Найти решение матричной игры в чистых или смешенных стратегиях (вероятности стратегий игроков и цену игры). Матрица игры имеет вид:
Находим решение игры в смешанных стратегиях.
Математические модели пары двойственных задач линейного программирования можно записать так:
Найти минимум функции F(x) при ограничениях (для игрока II):
5x
1+2x
2 ≥ 1
6x
1+x
2 ≥ 1
4x
1+7x
2 ≥ 1
F(x) = x
1+x
2 → min
Найти максимум функции Z(y) при ограничениях (для игрока I):
5y
1+6y
2+4y
3 ≤ 1
2y
1+y
2+7y
3 ≤ 1
Z(y) = y
1+y
2+y
3 → max
Определим максимальное значение целевой функции Z(Y) = y
1+y
2+y
3 при следующих условиях-ограничений.
5y
1+6y
2+4y
3≤1
2y
1+y
2+7y
3≤1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
5y
1 + 6y
2 + 4y
3 + 1y
4 + 0y
5 = 1
2y
1 + 1y
2 + 7y
3 + 0y
4 + 1y
5 = 1
Решим систему уравнений относительно базисных переменных: y
4, y
5
Полагая, что свободные переменные равны 0, получим первый опорный план:
Y0 = (0,0,0,1,1)
| Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
| y4 |
1 |
5 |
6 |
4 |
1 |
0 |
| y5 |
1 |
2 |
1 |
7 |
0 |
1 |
| Z(Y0) |
0 |
-1 |
-1 |
-1 |
0 |
0 |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y
3, так как это наибольший коэффициент по модулю.
Вычислим значения D
i по строкам как частное от деления: b
i / a
i3
и из них выберем наименьшее:
min (1 : 4 , 1 : 7 ) =
1/
7
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (7) и находится на пересечении ведущего столбца и ведущей строки.
| Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
min |
| y4 |
1 |
5 |
6 |
4 |
1 |
0 |
1/4 |
| y5 |
1 |
2 |
1 |
7 |
0 |
1 |
1/7 |
| Z(Y1) |
0 |
-1 |
-1 |
-1 |
0 |
0 |
|
Формируем следующую часть симплексной таблицы. Вместо переменной y
5 в план 1 войдет переменная y
3.
| Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
| y4 |
3/7 |
27/7 |
38/7 |
0 |
1 |
-4/7 |
| y3 |
1/7 |
2/7 |
1/7 |
1 |
0 |
1/7 |
| Z(Y1) |
1/7 |
-5/7 |
-6/7 |
0 |
0 |
1/7 |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y
2, так как это наибольший коэффициент по модулю.
Вычислим значения D
i по строкам как частное от деления: b
i / a
i2
и из них выберем наименьшее:
min (
3/
7 : 5
3/
7 ,
1/
7 :
1/
7 ) =
3/
38
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (5
3/
7) и находится на пересечении ведущего столбца и ведущей строки.
| Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
min |
| y4 |
3/7 |
27/7 |
53/7 |
0 |
1 |
-4/7 |
3/38 |
| y3 |
1/7 |
2/7 |
1/7 |
1 |
0 |
1/7 |
1 |
| Z(Y2) |
1/7 |
-5/7 |
-6/7 |
0 |
0 |
1/7 |
|
Формируем следующую часть симплексной таблицы. Вместо переменной y
4 в план 2 войдет переменная y
2.
| Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
| y2 |
3/38 |
27/38 |
1 |
0 |
7/38 |
-2/19 |
| y3 |
5/38 |
7/38 |
0 |
1 |
-1/38 |
3/19 |
| Z(Y2) |
4/19 |
-2/19 |
0 |
0 |
3/19 |
1/19 |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y
1, так как это наибольший коэффициент по модулю.
Вычислим значения D
i по строкам как частное от деления: b
i / a
i1
и из них выберем наименьшее:
min (
3/
38 :
27/
38 ,
5/
38 :
7/
38 ) =
1/
9
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (
27/
38) и находится на пересечении ведущего столбца и ведущей строки.
| Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
min |
| y2 |
3/38 |
27/38 |
1 |
0 |
7/38 |
-2/19 |
1/9 |
| y3 |
5/38 |
7/38 |
0 |
1 |
-1/38 |
3/19 |
5/7 |
| Z(Y3) |
4/19 |
-2/19 |
0 |
0 |
3/19 |
1/19 |
|
Формируем следующую часть симплексной таблицы. Вместо переменной y
2 в план 3 войдет переменная y
1.
| Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
| y1 |
1/9 |
1 |
38/27 |
0 |
7/27 |
-4/27 |
| y3 |
1/9 |
0 |
-7/27 |
1 |
-2/27 |
5/27 |
| Z(Y3) |
2/9 |
0 |
4/27 |
0 |
5/27 |
1/27 |
Конец итераций: индексная строка не содержит отрицательных элементов — найден оптимальный план
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
| y1 |
1/9 |
1 |
38/27 |
0 |
7/27 |
-4/27 |
| y3 |
1/9 |
0 |
-7/27 |
1 |
-2/27 |
5/27 |
| Z(Y4) |
2/9 |
0 |
4/27 |
0 |
5/27 |
1/27 |
Оптимальный план можно записать так:
y
1 =
1/
9, y
2 = 0, y
3 =
1/
9
Z(Y) = 1•
1/
9 + 1•0 + 1•
1/
9 =
2/
9
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
x
1=
5/
27, x
2=
1/
27
Это же решение можно получить, применив теоремы двойственности.
Из теоремы двойственности следует, что X = C*A
-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу D = А
-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A
-1 расположена в столбцах дополнительных переменных.
Тогда X = C*A
-1 =
Оптимальный план двойственной задачи равен:
x
1 =
5/
27, x
2 =
1/
27
F(X) = 1*
5/
27+1*
1/
27 =
2/
9
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
q
i = g*y
i; p
i = g*x
i.
Цена игры: g = 1 :
2/
9 =
9/
2
p
1 =
9/
2 •
5/
27 =
5/
6
p
2 =
9/
2 •
1/
27 =
1/
6
Оптимальная смешанная стратегия игрока I:
P = (
5/
6;
1/
6)
q
1 =
9/
2 •
1/
9 =
1/
2
q
2 =
9/
2 • 0 = 0
q
3 =
9/
2 •
1/
9 =
1/
2
Оптимальная смешанная стратегия игрока II:
Q = (
1/
2; 0;
1/
2)
Цена игры: v=
9/
2
Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑a
ijq
j ≤ v
∑a
ijp
i ≥ v
M(P
1;Q) = (5•
1/
2) + (6•0) + (4•
1/
2) = 4.5 = v
M(P
2;Q) = (2•
1/
2) + (1•0) + (7•
1/
2) = 4.5 = v
M(P;Q
1) = (5•
5/
6) + (2•
1/
6) = 4.5 = v
M(P;Q
2) = (6•
5/
6) + (1•
1/
6) = 5.167 ≥ v
M(P;Q
3) = (4•
5/
6) + (7•
1/
6) = 4.5 = v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.
Ссылка на первоисточник:
http://www.krstc.ru
