Указания к выполнению задания
Задача имеет следующую математическую формулировку:
,
, 
, 
где n и m – количество складов и магазинов, вектор a – наличие на складах, b – потребность в магазинах, 
– матрица затрат на перевозки.
Исходные данные a, b, C считаются известными и их нужно самостоятельно задать в виде таблиц, строк и столбцов, а матрицу оптимальных перевозок X требуется найти. Пример исходных данных представлен на рис. 12, где матрица C сформирована генератором случайных чисел.
Рис. 12. Исходные данные a , b , C для транспортной задачи.
На рис. 13 представлено решение. При внимательном рассмотрении на первый взгляд возникают сомнения в его оптимальности, поскольку решение предполагает перевозки в магазин 4 со склада 1, хотя гораздо выгодней возить со склада 2.
Рис. 13. Решение транспортной задачи с исходными данными на рис. 12.
Легко, однако, убедиться, что любое исправление этой ситуации приводит лишь увеличению общей себестоимости перевозок. Действительно, давайте в магазин 4 всё перевозить со склада 2. Тогда со склада 2 мы не сможем завозить в магазин 2 и в него придётся возить со склада 1 (см. рис. 14). Если в магазин 2 возить со склада 3, то придётся переделывать план перевозок по магазину 3 с ещё большим ухудшением общей себестоимости.
Рис. 14. Попытка улучшить решение по магазину 4 приводит к ухудшению по магазину 2 и общему ухудшению.
Задание 4. Игра с нулевой суммой в матричной форме
|
|
|
Постановка задачи.
Задать произвольную платёжную матрицу игры 5х4 такой, чтобы она не давала решения в чистых стратегиях. Найти решение игры в смешанных стратегиях для обоих игроков.
1.4.2 Контрольные вопросы:
1. Внести изменения в платёжную матрицу, приводящее к появлению решения в чистых стратегиях.
2. В каком диапазоне изменяется цена игры при отсутствии решения в чистых стратегиях.
3. Выявить доминирующие стратегии игроков или показать, что таковые отсутствуют.
4. Раскрыть стратегии игроков как решения взаимно-двойственной задачи.
5. Внести изменения в платёжную матрицу, изменяющие количество стратегий.
6. Внести изменения в платёжную матрицу, изменяющие цену игры, приближая её к противоположной границе диапазона.
Указания к выполнению задания
Зададим платёжную матрицу V с положительными значениями с помощью генератора случайных чисел. Пусть для игрока А она является матрицей выигрышей, и тогда он будет решать задачу максимизации результата, а для игрока В – матрицей проигрышей, тогда он будет решать задачу минимизации.
На основании полученной матрицы определим лучшие ответы игроков (см. рис. 15): в столбце справа – это лучшие ответы игрока А на каждую стратегию игрока В, а в строке снизу – лучшие ответы игрока В на каждую стратегию игрока А. Видно, что лучшей стратегией игрока В – это В2, на что последует ответ А3. Если же первый «ход» будет у игрока А, то он выберет А3 и получит ответ В1. Значит результат зависит от очерёдности хода и равновесия в игре в чистых стратегиях нет.
|
|
|
Рис. 15. Игра в матричной форме и лучшие ответы игроков. Равновесие в чистых стратегиях отсутствует.
Отсутствие решения в чистых стратегиях требует обращения к задаче поиска равновесия в смешанных стратегиях. Она формулируется как специфическая задача линейного программирования[2]. Для игрока А, максимизирующего результат, это задача:
а для игрока В, минимизирующего результат, это двойственная к ней задача:
где x, y ненормированные вероятности стратегий игроков, соответственно А и В. После перенормировки вероятности для оптимальных стратегий игрока А это 
, а для игрока В это 
(см. рис. 16).
Рис. 16. Нахождение равновесных стратегий как решение взаимно двойственных задач для игроков А и В.
Анализируя полученное решение, мы видим, что стратегии А1, В3 и В4 никогда использоваться не будут. Такой результат виден и непосредственно из анализа исходной матрицы. Действительно, стратегия А1 является доминируемой, поскольку стратегия А3 везде лучше неё. После удаления стратегии А1 доминируемыми становятся стратегии В3 и В4, поскольку стратегия В2 везде их лучше.
|
|
|
Несложно также увидеть, что небольшое изменение в исходной матрице приводит к появлению решения в чистых стратегиях. Для этого требуется сделать так, чтобы в столбце А3 значение 8 стало минимальным, т.е. изменить элемент В1А3 с 6 на, скажем, 9.
Дата добавления: 2019-11-25; просмотров: 119; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!