Теория игр. 2
Задача 1. Задача оптимального производства продукции.
Предприятие планирует выпуск двух видов продукции I и II, на производство которых расходуется три вида сырья А, В и С. Потребность aij на каждую единицу j-го вида продукции i-го вида сырья, запас bi соответствующего вида сырья и прибыль cj от реализации единицы j-го вида продукции заданы таблицей.
Виды сырья |
Виды продукции |
Запасы сырья | |
I |
II | ||
А |
5 |
2 |
30 |
В |
1 |
1 |
9 |
С |
2 |
2 |
18 |
прибыль |
3 |
6 |
|
план (ед.) |
х1 |
х2 |
|
Для производства двух видов продукции I и II с планом х1 и х2 единиц составить целевую функцию прибыли Z и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее n = 5 единиц обоих видов продукции.
В условиях задачи составить оптимальный план (х1; х2) производства продукции, обеспечивающий максимальную прибыль Zmax. Определить остатки каждого вида сырья. (Задачу решить симплекс-методом)
Решение.
Если производственный план – ед. продукции I и ед. продукции II, то сырья будет израсходовано ед., сырья – ед., сырья – ед. Запасы сырья составляют 30, 9 и 18 ед. соответственно. Таким образом, получаем ограничения:
Требуется изготовить в сумме не менее 5 единиц обоих видов продукции:
.
Согласно смыслу задачи, и должны быть неотрицательными:
.
План принесёт прибыль ден. ед. Поскольку надо найти такой план, при котором прибыль будет максимальна, то целевая функция будет иметь вид:
.
Запишем математическую модель задачи:
;
Решим задачу симплекс-методом.
Введём в систему ограничений дополнительные неотрицательные переменные так, чтобы получить систему уравнений:
.
Система уравнений имеет 4 независимых уравнения и 6 переменных, то есть, можно выразить 4 переменные (базисные) через 2 оставшиеся (свободные). В качестве базисных переменных выберем , , и . Тогда и − свободные.
Приведём систему к единичному базису:
.
Мы получили новую систему уравнений, эквивалентную исходной:
Выразим через свободные переменные и целевую функцию:
;
.
Запишем задачу в стандартной форме:
,
Теперь можно применять
Составим первую симплекс-таблицу.
|
Базис |
Сбаз |
Переменные |
|||||||
|
|
|||||||||
|
1 |
0 |
0 |
-3 |
1 |
0 |
0 |
5 |
5 | |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
4 | |
3 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
8 | |
4 |
3 |
1 |
1 |
0 |
0 |
0 |
-1 |
5 | |
5 |
− |
0 |
-3 |
0 |
0 |
0 |
-3 |
15 | |
Начальное базисное решение − допустимое; .
В последней строке есть отрицательные оценки − решение неоптимальное.
Отрицательные оценки одинаковые, поэтому выбираем любую оценку, например, стоящую в шестом столбце. Шестой столбец – разрешающий.
Для положительных коэффициентов
разрешающего столбца составляем оценочные
отношения – отношения
для первой строки: ;
для второй строки: ;
для третьей строки: .
В качестве разрешающей выбираем первую строку с наименьшим отношением.
Таким образом, разрешающий элемент:
.
Производим замену базиса – переводим в базис вместо .
Заполняем вторую симплекс-таблицу.
Элементы первой строки делим на разрешающий элемент:
.
Из второй строки вычитаем новую первую строку:
Из третьей строки вычитаем новую первую строку, умноженную на 2:
К четвёртой строке прибавляем новую первую строку:
К последней строке прибавляем новую первую строку, умноженную на 3:
|
|
Базис |
Сбаз |
Переменные |
||||||
|
|
|||||||||
|
1 |
0 |
0 |
-3/5 |
1/5 |
0 |
0 |
1 |
1 | |
2 |
0 |
0 |
3/5 |
-1/5 |
1 |
0 |
0 |
3 | |
3 |
0 |
0 |
6/5 |
-2/5 |
0 |
1 |
0 |
6 | |
4 |
3 |
1 |
2/5 |
1/5 |
0 |
0 |
0 |
6 | |
5 |
− |
0 |
-24/5 |
3/5 |
0 |
0 |
0 |
18 | |
Второе базисное решение − допустимое; .
В последней строке есть отрицательная оценка − решение неоптимальное.
Второй столбец – разрешающий.
Оценочные отношения:
для второй строки: ;
для третьей строки: ;
для четвёртой строки: .
Вторая строка – разрешающая.
Разрешающий элемент:
.
Производим замену базиса – переводим в базис вместо .
Заполняем третью симплекс-таблицу.
|
Базис |
Сбаз |
Переменные |
|||||||
|
|
|||||||||
|
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
4 | |
2 |
6 |
0 |
1 |
-1/3 |
5/3 |
0 |
0 |
5 | |
3 |
0 |
0 |
0 |
0 |
-2 |
1 |
0 |
0 | |
4 |
3 |
1 |
0 |
1/3 |
-2/3 |
0 |
0 |
4 | |
5 |
− |
0 |
0 |
-1 |
8 |
0 |
0 |
42 | |
Третье базисное решение − допустимое; .
В последней строке есть отрицательная оценка − решение неоптимальное.
Третий столбец – разрешающий.
Оценочные отношения:
для четвёртой строки: .
Четвёртая строка – разрешающая.
Разрешающий элемент:
.
Производим замену базиса – переводим в базис вместо .
Заполняем четвёртую симплекс-таблицу.
|
Базис |
Сбаз |
Переменные |
|||||||
|
|
|||||||||
|
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
4 | |
2 |
6 |
1 |
1 |
0 |
1 |
0 |
0 |
9 | |
3 |
0 |
0 |
0 |
0 |
-2 |
1 |
0 |
0 | |
4 |
0 |
3 |
0 |
1 |
-2 |
0 |
0 |
12 | |
5 |
− |
3 |
0 |
0 |
6 |
0 |
0 |
54 | |
Четвёртое базисное решение − допустимое; .
В последней строке нет отрицательных оценок − решение оптимальное.
Выводы:
максимальная прибыль в
при этом сырьё В и С будет использовано полностью ( , ), а остаток сырья составит ед.
Задача 2.
Игра задана матрицей
Найти вероятности применения стратегий 1-м и 2-м игроком для получения цены игры. (Задачу решить аналитическим методом.)
Решение.
Прежде, чем искать оптимальные смешанные стратегии игроков, проверим, не имеет ли игра решения в чистых стратегиях.
Находим нижнюю цену игры:
.
Находим верхнюю цену игры:
.
Так как , то седловая точка отсутствует, и игра не имеет решения в чистых стратегиях. Следовательно, оптимальное решение будем искать в смешанных стратегиях.
В данной матрице:
.
По известным формулам находим вероятности оптимальной смешанной стратегии S1 = (р1, р2) первого игрока, вероятности оптимальной смешанной стратегии S2 = (q1, q2) второго игрока и цену игры v:
;
;
;
;
.
Ответ: , , .
Задача 3.
Игра задана матрицей:
Применяя графический метод, найти смешанные оптимальные стратегии обоих игроков и определить цену игры.
Решение.
Прежде, чем искать оптимальные смешанные стратегии игроков, проверим, не имеет ли игра решения в чистых стратегиях.
Находим нижнюю цену игры: .
Находим верхнюю цену игры: .
Так как , то седловая точка отсутствует, и игра не имеет решения в чистых стратегиях. Следовательно, оптимальное решение будем искать в смешанных стратегиях.
Две стратегии имеет второй игрок, поэтому графическим методом найдём оптимальную смешанную стратегию второго игрока.
1. В декартовой системе координат строим прямую х = 1 и по оси абсцисс откладываем отрезок длиной 1. Левый конец отрезка (точка х = 0) соответствует стратегии B1, правый (x = 1) – стратегии B2. Промежуточные точки х соответствуют вероятностям S2 = (q1,q2) некоторых смешанных стратегий (q2 = x, q1 = 1 – x).
2. На оси ординат откладываем выигрыши стратегии B1 (левый столбец матрицы С2). На прямой х = 1 откладываем выигрыши стратегии B2 (правый столбец матрицы С2).
3. Решение игры проводим с позиции игрока B, придерживающегося минимаксной стратегии. Ей соответствует верхняя огибающая всех прямых.
А2, А4
А3
А1
4. Нижняя точка М ломаной находится на пересечении прямых А3А3 и А4А4. Для нахождения её координат составим систему уравнений:
;
;
.
Запишем оптимальную смешанную стратегию второго игрока:
, .
Запишем цену игры:
.
5. Находим оптимальную смешанную стратегию первого игрока.
Поскольку точка М находится на пересечении прямых А3А3 и А4А4, то стратегии А1 и А2 исключаем как заведомо невыгодные:
.
Оптимальные вероятности стратегий А3 и А4 найдём, решив систему уравнений:
;
по формулам Крамера:
;
;
;
, .
Запишем оптимальную смешанную стратегию первого игрока:
.
Ответ: , , .
Задача 4.
Найти оптимальные стратегии и цену игры, заданной платёжной матрицей А:
14. .
Решение.
Проверим, не имеет ли игра решения в чистых стратегиях.
Находим нижнюю цену игры:
.
Находим верхнюю цену игры:
.
Так как , то седловая точка отсутствует, и игра не имеет решения в чистых стратегиях. Следовательно, оптимальное решение будем искать в смешанных стратегиях.
Предварительно упростим матрицу А, убрав из рассмотрения заведомо невыигрышные (доминируемые) стратегии.
Для первого игрока 1-я стратегия доминируется 3-й стратегией (элементы 1-й строки не больше соответствующих элементов 3-й строки). Убираем 1-ю строку из матрицы, поскольку вероятность выбора этой стратегии первым игроком равна нулю. Получим матрицу:
Далее видим, что элементы 3-го столбца не больше соответствующих элементов 1-го столбца и 4-го столбца, следовательно, у второго игрока 2-я стратегия доминирует 1-ю и 4-ю стратегии. Вычёркиваем 1-й и 4-й столбцы из матрицы. Получим матрицу:
В данной матрице:
.
Эту игру решим аналитически.
Находим вероятности оптимальной смешанной стратегии S1 = (р1, р2) первого игрока, вероятности оптимальной смешанной стратегии S2 = (q1, q2) второго игрока и цену игры v по формулам:
;
;
;
;
.
Поскольку при упрощении матрицы А была убрана 1-я строка, то при возвращении к исходной матрице А получаем, что есть вероятность, с которой первый игрок выбирает 2-ю чистую стратегию, а есть вероятность, с которой первый игрок выбирает 3-ю чистую стратегию. 1-ю чистую стратегию первый игрок выбирает с нулевой вероятностью. Таким образом, оптимальная смешанная стратегия первого игрока:
.
Аналогично получаем оптимальную смешанную стратегию второго игрока:
.
Ответ: , , .