- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 1
- •Блок 1.
- •1.1. Предмет и задачи исследования операций
- •1.2. Основные понятия и принципы исследования операций
- •1.3. Математические модели операций
- •1.4. Понятие линейного программирования
- •1.5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов
- •1.6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий
- •1.7. Примеры экономических задач линейного программирования. Задача о смесях
- •1.8. Примеры экономических задач линейного программирования. Транспортная задача
- •1.9. Основные виды записи задач линейного программирования
- •1.10. Способы преобразования
- •1.11. Переход к канонической форме
- •1.12. Переход к симметричной форме записи
- •Блок 2.
- •2.1. Геометрическая интерпретация задачи линейного программирования
- •2.2. Решение задач линейного программирования графическим методом
- •2.3. Свойства решений задачи линейного программирования
- •2.4. Общая идея симплексного метода
- •2.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом
- •2.6. Признак оптимальности опорного плана. Симплексные таблицы
- •2.7. Переход к нехудшему опорному плану.
- •2.8. Симплексные преобразования
- •2.9. Альтернативный оптимум (признак бесконечности множества опорных планов)
- •2.10. Признак неограниченности целевой функции
- •2.11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание
- •2.12. Понятие двойственности для симметричных задач линейного программирования
- •3.1. Несимметричные двойственные задачи
- •3.2. Открытая и закрытая модели транспортной задачи
- •3.3. Построение начального опорного плана. Правило "Северо-западного угла"
- •3.4. Построение начального опорного плана. Правило минимального элемент
- •3.5. Построение начального опорного плана. Метод Фогеля
- •3.6. Метод потенциалов
- •3.7. Решение транспортных задач с ограничениями по пропускной способности
- •3.8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении
- •3.9. Сущность методов дискретной оптимизации
- •3.10. Задача выпуклого программирования
- •3.11. Метод множителей Лагранжа
- •3.12. Градиентные методы
- •4.1. Методы штрафных и барьерных функций
- •4.2. Динамическое программирование. Основные понятия. Сущность методов решения
- •4.3. Стохастическое программирование. Основные понятия
- •4.4. Матричные игры с нулевой суммой
- •4.5. Чистые и смешанные стратегии и их свойства
- •4.6. Свойства чистых и смешанных стратегий
- •4.7. Приведение матричной игры к злп
- •4.8. Задачи теории массового обслуживания. Классификация систем массового обслуживания
- •4.9. Потоки событий
- •4.10. Схема гибели и размножения
- •4.11. Формула Литтла
- •4.12. Простейшие системы массового обслуживания
- •2. Одноканальная система массового обслуживания с неограниченной очередью.
- •Список рекомендуемой литературы
4.6. Свойства чистых и смешанных стратегий
Значение платежной функции при оптимальных стратегиях определяет цену игры v, т. е. .
Теорема: В смешанных стратегиях любая конечная матричная игра имеет седловую точку.
Пусть имеем матричную игру и некоторые смешанные оптимальные стратегии , игроков А и В, обеспечивающие сумму выигрыша v. Вопрос поставим так: как проверить, что набор является решением игры? Для этого нужно проверить справедливость неравенства для любых смешанных стратегий, среди которых и будут стратегии , . Однако, различных смешанных стратегий, среди которых и оптимальные, имеем бесчисленное множество. И в таком случае проверить справедливость этого неравенства невозможно. Поэтому рассмотрим следующую теорему, которая позволит ответить на поставленный выше вопрос.
Теорема: Для того чтобы смешанные стратегии и были оптимальными для игроков А и В в игре с матрицей и выигрышем v, необходимо и достаточно выполнения неравенств:
,
(3.4) (3.5)
.
На основании данной теоремы можно сделать вывод: если игрок А применяет оптимальную смешанную стратегию , а игрок В – любую чистую стратегию Вj, то выигрыш игрока А будет не меньше цены игры v. Аналогично: если игрок В использует оптимальную смешанную стратегию , а игрок А – любую чистую стратегию Ai, то проигрыш игрока В не превысит цены игры v.
Чистые стратегии игрока, входящие в его оптимальную смешанную стратегию с вероятностями, отличными от нуля, называются активными стратегиями игрока. Рассмотрим теорему об активных стратегиях.
Теорема: Если один из игроков придерживается своей оптимальной смешанной стратегии, то его выигрыш остается неизменным и равным цене игры независимо от того, какую стратегию применяет другой игрок, если только тот не выходит за пределы своих активных стратегий.
На основании данной теоремы решение матричной игры можно упростить, выявив при этом доминирование одних стратегий над другими. Так, рассматривая стратегии игрока А, сравниваем элементы строк s и t, а именно: с элементами аtj для . Если , то выигрыш игрока А при стратегии Аs будет больше, чем при стратегии At. В этом случае стратегия Аs доминирует над стратегией At. Стратегию Аs называют доминирующей, а стратегию At — доминируемой.
Поскольку игрок В заинтересован в минимизации проигрыша, доминирующим будет столбец с наименьшими элементами. Например, сравниваем элементы r-гo и l-го столбцов. Если все элементы , то игроку В свой выбор выгодно сделать по l-му столбцу. В этом случае стратегия Вl игрока В доминирует над стратегией Вr. Стратегия Вl называется доминирующей, а стратегия Вr — доминируемой.
Если в матричной игре имеем строки (столбцы) с одними и теми же элементами, то строки (столбцы), а соответственно и стратегии игроков А и В, называются дублирующими.
В матричной игре доминируемые и дублирующие строки (столбцы) можно опускать, что не влияет на решение игры.
Теорема: Оптимальные смешанные стратегии и соответственно игроков А и В в матричной игре с ценой v будут оптимальными и в матричной игре с ценой , где .
На основании данной теоремы платежную матрицу, имеющую отрицательные числа, можно преобразовать в матрицу с положительными числами.
Пример: Выполнить всевозможные упрощения матричной игры
Решение.
Поскольку соответствующие элементы второй и четвертой строк матрицы игры равны, т. е. имеем две дублирующие строки, опустим, например, четвертую строку.
Сравним соответствующие элементы столбцов. Элементы первого столбца доминируют над элементами третьего и шестого столбцов, а элементы второго столбца доминируют над соответствующими элементами четвертого столбца. Игроку В невыгодно применять стратегии В3, B4 и В6. Опускаем третий, четвертый и шестой столбцы и получаем матрицу вида
Элементы второй строки меньше соответствующих элементов третьей строки. Следовательно, игроку А невыгодна стратегия А2. Опуская вторую строку, получаем упрощенную матрицу
Если требуется получить матрицу с положительными элементами, то достаточно прибавить к ее элементам, например, число 2.
На примере покажем один из методов нахождения решения игры, заданной матрицей.
Пример: Найти решение игры, заданной матрицей
Решение.
Проверим наличие седловых точек. Найдем минимальные элементы в каждой из строк (2; 4) и максимальные в каждом из столбцов (6; 5). Значит, нижняя цена игры α=max(2; 4)=4 и β=min(6;5)=5. Так как α≠β, то решением игры являются смешанные оптимальные стратегии, а цена игры заключается в пределах от 4 до 5.
Предположим, что для игрока А стратегия задается вектором . Тогда средний выигрыш при первой и второй стратегии будет равен:
,
.
Вероятность выбора той или иной стратегии равна 1, т.е.
.
Получим систему из трех уравнений с тремя неизвестными. Решив ее получим ,и.
Построим геометрическую иллюстрацию данного метода решения.
Откладываем на оси 0u единичный отрезок. Строим линию параллельно оси 0z. Строим прямые через точки (2; 6) и (5; 4). Линии пересекаются в точке М.
Полученные линии и разбиение единичного отрезка на две части дает возможность составления системы уравнений, которую мы приводили выше.
Ответ: ,и.
Обобщая изложенные выше результаты нахождения решения игры , можно указать основные этапы нахождения решения игрыили.
Строим прямые, соответствующие стратегиям одного игрока.
Определяем нижнюю (верхнюю) границу выигрыша.
Находят две стратегии этого игрока, которым соответствуют две прямые, пересекающиеся в точке с максимальной (минимальной) координатой.
Определяем цену игры и оптимальные стратегии.