Теория матричных игр, связь с линейным программированием
Определение нижней и верхней цены игры с помощью заданных матриц, их графическое отображение в системе координат. Нахождение максиминной и минимаксной стратегий игрока. Решение матричной игры как задачи линейного программирования в смешанных стратегиях.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 16.01.2015 |
| Размер файла | 66,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Задача 1.
Зная платежную матрицу
определить нижнюю и верхнюю цены игры и найти решение матричной игры.
Решение:
|
Игроки |
B1 |
B2 |
B3 |
B4 |
B5 |
a = min(Ai) |
|
|
A1 |
4 |
5 |
6 |
7 |
9 |
4 |
|
|
A2 |
3 |
4 |
6 |
7 |
6 |
3 |
|
|
A3 |
7 |
6 |
10 |
8 |
11 |
6 |
|
|
A4 |
8 |
5 |
4 |
7 |
3 |
3 |
|
|
b = max(Bi) |
8 |
6 |
10 |
8 |
11 |
Находим нижнюю цену игры a = max(ai) = 6, которая указывает на максимальную чистую стратегию A3.
Верхняя цена игры b = min(bj) = 6.
Седловая точка (3, 2) указывает решение (A3,B2). Цена игры равна 6.
Задача 2.
Найти стратегии игроков А, В и цену игры, заданной матрицей (с помощью формул и графически)
Решение:
|
Игроки |
B1 |
B2 |
B3 |
B4 |
a = min(Ai) |
|
|
A1 |
3 |
5 |
2 |
0 |
0 |
|
|
A2 |
6 |
-1 |
3 |
5 |
-1 |
|
|
b = max(Bi) |
6 |
5 |
3 |
5 |
Нижняя цена игры a = max(ai) = 0, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 3.
Что говорит об отсутствии седловой точки, так как a ? b, тогда цена игры находится в пределах 0 ? y ? 3. Находим решение игры в смешанных стратегиях.
В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый - стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2).
На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.
Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B2B2 и B4B4, для которых можно записать следующую систему уравнений:
y = 5 + (-1 - 5)p2
y = 0 + (5 - 0)p2
Откуда
p1 = 6/11
p2 = 5/11
Цена игры, y = 25/11
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B1,B3, которая дает явно больший проигрыш игроку B, и, следовательно, q1 = 0,q3 = 0.
5q2 = y
-q2+5q4 = y
q2+q4 = 1
или
5q2 = 25/11
-q2+5q4 = 25/11
q2+q4 = 1
Решая эту систему, находим:
q2 = 5/11.
q4 = 6/11.
Цена игры: y = 25/11, векторы стратегии игроков:
Q(0, 5/11, 0, 6/11), P(6/11, 5/11)
Задача 3.
Найти оптимальный вариант электростанции по критериям Лапласа, Вальда, Гурвица с показателями 0,8 и 0,3 и Сэвиджа по заданной таблице эффективностей (Таблица эффективностей в файле).
Задача 4.
Швейное предприятие реализуется свою продукцию через магазин. Сбыт зависит от состояния погоды. В условиях теплой погоды предприятие реализует 1000 костюмов и 2300 платьев, а при прохладной погоде - 1400 костюмов и 700 платьев. Затраты на изготовление одного костюма равны 20, а платья - 5 рублям, цена реализации соответственно равна 40 рублей и 12 рублей. Определить оптимальную стратегию предприятия.
Решение:
Задача заключается в максимизации средней величины дохода от реализации выпущенной продукции, учитывая капризы погоды. Фабрика располагает в этих ситуациях двумя следующими стратегиями: в расчете на теплую погоду (стратегия А); в расчете на холодную погоду (стратегия В).
Если предприятие примет стратегию А, т.е. продукция, соответствующая теплой погоде (стратегия природы С), будет полностью реализована, то доход фабрики в этой ситуации составит:
AC = a(pb - zb) +b(pa - za)
Если продажа осуществляется в условиях прохладной погоды (стратегия природы D), то костюмы будут проданы полностью, а платья только в количестве c шт. Доход предприятия в данном случае составит:
AD = a(pb - zb) + c(pa - za) - (b - c) * za
Аналогично, определим доход предприятия в случае применения им стратегии В. Для условий теплой погоды доход фабрики определяется суммой:
BC = a(pb - zb) + c(pa - za) - (d - a) * zb
Применение той же стратегии, но в условиях холодной погоды, приведет к другим результатам:
BD = d(pb - zb) + c(pa - za)
Получим
|
Игроки |
B1 |
B2 |
a = min(Ai) |
|
|
A1 |
36100 |
13400 |
13400 |
|
|
A2 |
13400 |
29400 |
13400 |
|
|
b = max(Bi) |
36100 |
29400 |
a = max(ai) = 13400, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 29400.
так как a ? b, тогда цена игры находится в пределах 13400 ? y ? 29400. Находим решение игры в смешанных стратегиях.
В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый - стратегии A2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2).
На левой оси ординат откладываются выигрыши стратегии A1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A2.
Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B1B1 и B2B2, для которых можно записать следующую систему уравнений:
y = 36100 + (13400 - 36100)p2
y = 13400 + (29400 - 13400)p2
Откуда
p1 = 160/387
p2 = 227/387
Цена игры, y = 8817800/387
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений
36100q1+13400q2 = y
13400q1+29400q2 = y
q1+q2 = 1
или
36100q1+13400q2 = 8817800/387
13400q1+29400q2 = 8817800/387
q1+q2 = 1
Решая эту систему, находим:
q1 = 160/387.
q2 = 227/387.
Также решение можно найти по следующим формулам:
Цена игры: y = 8817800/387, векторы стратегии игроков:
Q(160/387, 227/387), P(160/387, 227/387)
Задача 5.
Найти решение и цену игры, заданной следующей платежной матрицей:
Решение:
|
Игроки |
B1 |
B2 |
a = min(Ai) |
|
|
A1 |
12 |
22 |
12 |
|
|
A2 |
32 |
2 |
2 |
|
|
b = max(Bi) |
32 |
22 |
a = max(ai) = 12, b = min(bj) = 22, так как a ? b, тогда цена игры находится в пределах 12 ? y ? 22. Находим решение игры в смешанных стратегиях. найти минимум функции F(x) при ограничениях:
12x1+32x2 ? 1
22x1+2x2 ? 1
F(x) = x1+x2 > min
найти максимум функции Ф(y) при ограничениях:
12y1+22y2 ? 1
32y1+2y2 ? 1
Ф(y) = y1+y2 > max
Решаем эти системы симплексным методом.
F(X) = x1 + x2
12x1 + 22x2?1
32x1 + 2x2?1
12x1 + 22x2 + 1x3 + 0x4 = 1
32x1 + 2x2 + 0x3 + 1x4 = 1
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
|
x3 |
1 |
12 |
22 |
1 |
0 |
|
|
x4 |
1 |
32 |
2 |
0 |
1 |
|
|
F(X0) |
0 |
-1 |
-1 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода. min (1 : 22 , 1 : 2 ) = 1/22
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
|
x2 |
1/22 |
6/11 |
1 |
1/22 |
0 |
|
|
x4 |
10/11 |
340/11 |
0 |
-1/11 |
1 |
|
|
F(X1) |
1/22 |
-5/11 |
0 |
1/22 |
0 |
min (1/22 : 6/11 , 10/11 : 3010/11 ) = 1/34
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
|
x2 |
1/34 |
0 |
1 |
4/85 |
-3/170 |
|
|
x1 |
1/34 |
1 |
0 |
-1/340 |
11/340 |
|
|
F(X2) |
1/17 |
0 |
0 |
3/68 |
1/68 |
x2 = 1/34
x1 = 1/34
F(X) = 1*1/34 + 1*1/34 = 1/17
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен:
y1 = 3/68
y2 = 1/68
Z(Y) = 1*3/68+1*1/68 = 1/17
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
qi = g*yi; pi = g*xi.
Цена игры: g = 1 : 1/17 = 17
p1 = 17 * 3/68 = 3/4
p2 = 17 * 1/68 = 1/4
Оптимальная смешанная стратегия игрока I:
P = (3/4; 1/4)
q1 = 17 * 1/34 = 1/2
q2 = 17 * 1/34 = 1/2
Оптимальная смешанная стратегия игрока II:
Q = (1/2; 1/2)
Цена игры: v=17
Задача 6.
Выполните доминирование и найдите оптимальное решение и цену игры, заданной матрицей.
Решение:
|
Игроки |
B1 |
B2 |
B3 |
B4 |
a = min(Ai) |
|
|
A1 |
1 |
2 |
1 |
2 |
1 |
|
|
A2 |
2 |
1 |
2 |
4 |
1 |
|
|
A3 |
3 |
3 |
2 |
2 |
2 |
|
|
A4 |
4 |
1 |
3 |
3 |
1 |
|
|
b = max(Bi) |
4 |
3 |
3 |
4 |
a = max(ai) = 2, b = min(bj) = 3.
a ? b, тогда цена игры находится в пределах 2 ? y ? 3. Находим решение игры в смешанных стратегиях.
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ? akj для всех j Э N и хотя бы для одного j aij > akj. В этом случае говорят также, что i-я стратегия (или строка) - доминирующая, k-я - доминируемая.
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M aij ? ail и хотя бы для одного i aij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю - доминируемой.
Стратегия A3 доминирует над стратегией A1 (все элементы строки 3 больше или равны значениям 1-ой строки), следовательно исключаем 1-ую строку матрицы. Вероятность p1 = 0.
|
2 |
1 |
2 |
4 |
|
|
3 |
3 |
2 |
2 |
|
|
4 |
1 |
3 |
3 |
С позиции проигрышей игрока В стратегия B2 доминирует над стратегией B1 (все элементы столбца 2 меньше элементов столбца 1), следовательно исключаем 1-й столбец матрицы. Вероятность q1 = 0.
С позиции проигрышей игрока В стратегия B3 доминирует над стратегией B4 (все элементы столбца 3 меньше элементов столбца 4), следовательно исключаем 4-й столбец матрицы. Вероятность q4 = 0.
|
1 |
2 |
|
|
3 |
2 |
|
|
1 |
3 |
Стратегия A2 доминирует над стратегией A1 (все элементы строки 2 больше или равны значениям 1-ой строки), следовательно исключаем 1-ую строку матрицы. Вероятность p1 = 0.
|
3 |
2 |
|
|
1 |
3 |
Мы свели игру 4 x 4 к игре 2 x 2.
Решим задачу геометрическим методом
минимаксный стратегия игрок матричный
Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B1B1 и B2B2, для которых можно записать следующую систему уравнений:
y = 3 + (1 - 3)p2
y = 2 + (3 - 2)p2
Откуда
p1 = 2/3
p2 = 1/3
Цена игры, y = 7/3
Теперь можно найти минимаксную стратегию игрока B, записав соответствующую систему уравнений
3q1+2q2 = y
q1+3q2 = y
q1+q2 = 1
или
3q1+2q2 = 7/3
q1+3q2 = 7/3
q1+q2 = 1
Решая эту систему, находим:
q1 = 1/3.
q2 = 2/3.
Также решение можно найти по следующим формулам:
Цена игры: y = 7/3, векторы стратегии игроков:
Q(1/3, 2/3), P(2/3, 1/3)
Задача 7.
Дана матрица игры. Привести игру к задаче линейного программирования. Найти решение матричной игры в смешанных стратегиях:
Решение:
|
Игроки |
B1 |
B2 |
B3 |
B4 |
a = min(Ai) |
|
|
A1 |
2 |
4 |
8 |
5 |
2 |
|
|
A2 |
6 |
2 |
4 |
6 |
2 |
|
|
A3 |
3 |
2 |
5 |
4 |
2 |
|
|
b = max(Bi) |
6 |
4 |
8 |
6 |
a = max(ai) = 2, b = min(bj) = 4.
a ? b, тогда цена игры находится в пределах 2 ? y ? 4. Находим решение игры в смешанных стратегиях.
С позиции проигрышей игрока В стратегия B1 доминирует над стратегией B4 (все элементы столбца 1 меньше элементов столбца 4), следовательно исключаем 4-й столбец матрицы. Вероятность q4 = 0.
С позиции проигрышей игрока В стратегия B2 доминирует над стратегией B3 (все элементы столбца 2 меньше элементов столбца 3), следовательно исключаем 3-й столбец матрицы. Вероятность q3 = 0.
|
2 |
4 |
|
|
6 |
2 |
|
|
3 |
2 |
Стратегия A2 доминирует над стратегией A3 (все элементы строки 2 больше или равны значениям 3-ой строки), следовательно исключаем 3-ую строку матрицы. Вероятность p3 = 0.
|
2 |
4 |
|
|
6 |
2 |
Мы свели игру 3 x 4 к игре 2 x 2.
найти минимум функции F(x) при ограничениях:
2x1+6x2 ? 1
4x1+2x2 ? 1
F(x) = x1+x2 > min
найти максимум функции Ф(y) при ограничениях:
2y1+4y2 ? 1
6y1+2y2 ? 1
Ф(y) = y1+y2 > max
Решаем эти системы симплексным методом.
F(X) = x1 + x2
2x1 + 4x2?1
6x1 + 2x2?1
2x1 + 4x2 + 1x3 + 0x4 = 1
6x1 + 2x2 + 0x3 + 1x4 = 1
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
|
x3 |
1 |
2 |
4 |
1 |
0 |
|
|
x4 |
1 |
6 |
2 |
0 |
1 |
|
|
F(X0) |
0 |
-1 |
-1 |
0 |
0 |
min (1 : 4 , 1 : 2 ) = 1/4
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
|
x2 |
1/4 |
1/2 |
1 |
1/4 |
0 |
|
|
x4 |
1/2 |
5 |
0 |
-1/2 |
1 |
|
|
F(X1) |
1/4 |
-1/2 |
0 |
1/4 |
0 |
min (1/4 : 1/2 , 1/2 : 5 ) = 1/10
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
|
x2 |
1/5 |
0 |
1 |
3/10 |
-1/10 |
|
|
x1 |
1/10 |
1 |
0 |
-1/10 |
1/5 |
|
|
F(X2) |
3/10 |
0 |
0 |
1/5 |
1/10 |
Оптимальный план можно записать так:
x2 = 1/5
x1 = 1/10
F(X) = 1*1/5 + 1*1/10 = 3/10
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен:
y1 = 1/5
y2 = 1/10
Z(Y) = 1*1/5+1*1/10 = 3/10
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
qi = g*yi; pi = g*xi.
Цена игры: g = 1 : 3/10 = 31/3
p1 = 31/3 * 1/5 = 2/3
p2 = 31/3 * 1/10 = 1/3
Оптимальная смешанная стратегия игрока I:
P = (2/3; 1/3)
q1 = 31/3 * 1/10 = 1/3
q2 = 31/3 * 1/5 = 2/3
Оптимальная смешанная стратегия игрока II:
Q = (1/3; 2/3)
Цена игры: v=31/3
Размещено на Allbest.ru
...Подобные документы
Основные положения теории игр. Терминология и классификация игр. Решение матричных игр в чистых и в смешанных стратегиях. Сведение матричной игры к задаче линейного программирования. Применение теории игр в задачах экономико-математического моделирования.
курсовая работа [184,5 K], добавлен 12.12.2013Предмет и задачи теории игр. Сведение матричной игры к задачам линейного программирования. Основные принципы разработки деловых игр для исследования экономических механизмов. Деловая игра "Снабжение". Решение матричной игры в смешанных стратегиях.
курсовая работа [1,8 M], добавлен 15.10.2012Элементы теории матричных игр. Способы решения матричных игр. Различия в подходах критериев оптимальности при определении оптимальной стратегии в условиях статистической неопределенности. Нахождение седловой точки игры. Графическое решение матричной игры.
контрольная работа [366,9 K], добавлен 12.05.2014Рассмотрение содержания и методов решения матричной игры в смешанных стратегиях, способы ее сведения к задачам линейного программирования. Анализ геометрической интерпретации биматричных и бескоалиционных игр. Природа и структура кооперативных игр.
курс лекций [1,2 M], добавлен 11.07.2010Определение нижней и верхней цены игры, заданной платежной матрицей. Имеет ли игра седловую точку? Решение геометрически задачи линейного программирования. Построение графа состояний случайного процесса. Предельные вероятности для заданной системы.
контрольная работа [280,0 K], добавлен 04.02.2011Решение задачи линейного программирования симплекс-методом. План перевозок при минимальных затратах на них. Определение оптимального значения изменения численности работников. Решение матричной игры двух лиц с применением чистой и смешанной стратегий.
контрольная работа [152,3 K], добавлен 16.05.2013Расчет количества изделий для изготовления на предприятии, чтобы прибыль от их реализации была максимальной (решение графическим способом и в среде MS Excel). Определение равновесной цены спроса-предложения на товар, нижней и верхней цены матричной игры.
контрольная работа [352,0 K], добавлен 13.09.2013Определение чистых стратегий холдинга. Составление платежной матрицы игры, ее верхней и нижней цены. Принятие оптимального решения об инвестиции в банк для получения наибольшей выгоды при улучшении финансового состояния металлургическому консорциуму.
курсовая работа [85,3 K], добавлен 19.05.2014Основы теории матричных игр. Причины неопределенности результата. Смешанные стратегии в матричных играх. Свойства решений. Определение смешанных стратегий с использованием геометрической интерпретации. Нахождение неотрицательных решений неравенств.
контрольная работа [132,8 K], добавлен 13.04.2014Определение доминирующей стратегии в игре; равновесия в смешанных, осторожных и чистых стратегиях; совершенного подыгрового равновесия методом обратной индукции. Платежная матрица игры. Равновесный уровень заработной платы и занятости в статической игре.
контрольная работа [60,6 K], добавлен 04.02.2011Конфликтные ситуации в управленческой деятельности. Использование математического моделирования для решения управленческих задач. Определение биматричной игры и общий принцип ее решения. Состояние равновесия в смешанных стратегиях в биматричных матрицах.
реферат [26,9 K], добавлен 21.12.2010- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Теория игр в контексте теории принятия решений. Игры без седловых точек. Использование линейной оптимизации при решении матричных игр. Критерии, используемые для принятия решений в играх с природой. Решение парных матричных игр с нулевой суммой.
контрольная работа [437,2 K], добавлен 14.02.2011Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.
контрольная работа [40,0 K], добавлен 04.05.2014Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.
курсовая работа [105,5 K], добавлен 02.10.2014Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.
курсовая работа [106,0 K], добавлен 05.10.2014Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012Решение задач при помощи пакета прикладных программ MatLab. Загрузка в MatLab матриц A и P. Нахождение оптимальной стратегии для заданных матриц с использованием критериев принятия решений в условиях неопределённости Вальда, Гурвица, Лапласа, Сэвиджа.
лабораторная работа [80,2 K], добавлен 18.03.2015Разработка экономико-математической модели и решение задачи линейного программирования с использованием математических методов. Транспортная задача в матричной постановке и ее свойства. Построение исходного допустимого плана. Критерий оптимальности.
курсовая работа [111,1 K], добавлен 16.01.2011
