- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 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.5. Чистые и смешанные стратегии и их свойства
Различают стратегии чистые и смешанные. Чистая стратегия первого игрока (чистая стратегия второго игрока) – это возможный ход первого (второго) игрока, выбранный им с вероятностью, равной 1.
Если первый игрок имеет m стратегий, а второй – n стратегий, то для любой пары стратегий первого и второго игроков чистые стратегии можно представить в виде единичных векторов. Например, для пары стратегий ,чистые стратегии первого и второго игроков запишутся в виде: , . Для пары стратегий ,чистые стратегии можно записать в виде:
,
.
Теорема: В матричной игре нижняя чистая цена игры не превосходит верхней чистой цены игры, т. е. .
Определение: Если для чистых стратегий ,игроковA и В соответственно имеет место равенство , то пару чистых стратегий (,) называют седловой точкой матричной игры, элементматрицы, стоящий на пересеченииi-й строки и j-го столбца – седловым элементом платежной матрицы, а число — чистой ценой игры.
Пример: Найти нижнюю и верхнюю чистые цены, установить наличие седловых точек матричной игры
.
Решение.
Определим нижние и верхние чистые цены игры: , , .
|
В1 |
В2 |
В3 |
В4 | |
А1 |
9 |
5 |
6 |
7 |
5 |
А2 |
1 |
4 |
3 |
8 |
1 |
А3 |
6 |
3 |
2 |
-4 |
-4 |
9 |
5 |
6 |
8 |
|
В данном случае имеем одну седловую точку (А1; В2), а седловой элемент равен 5. Этот элемент является наименьшим в 1-й строке и наибольшим во 2-м столбце. Отклонение игрока А от максиминной стратегии А1 ведет к уменьшению его выигрыша, а отклонение игрока В от минимаксной стратегии В2 ведет к увеличению его проигрыша. Иными словами, если в матричной игре имеется седловой элемент, то наилучшими для игроков являются их минимаксные стратегии. И эти чистые стратегии, образующие седловую точку и выделяющие в матрице игры седловой элемент a12=5, есть оптимальные чистые стратегии исоответственно игроков А и В.
Если же матричная игра не имеет седловой точки, то решение игры затрудняется. В этих играх . Применение минимаксных стратегий в таких играх приводит к тому, что для каждого из игроков выигрыш не превышает , а проигрыш — не меньше . Для каждого игрока возникает вопрос увеличения выигрыша (уменьшение проигрыша). Решение находят, применяя смешанные стратегии.
Определение: Смешанной стратегией первого (второго) игрока называется вектор , где и(, где и).
Вектор p(q) означает вероятность применения i-й чистой стратегии первым игроком (j-й чистой стратегии вторым игроком).
Поскольку игроки выбирают свои чистые стратегии случайно и независимо друг от друга, игра имеет случайный характер и случайной становится величина выигрыша (проигрыша). В таком случае средняя величина выигрыша (проигрыша) – математическое ожидание – является функцией от смешанных стратегий р, q:
.
Определение: Функция f(р, q) называется платежной функцией игры с матрицей .
Определение: Стратегии , называются оптимальными, если для произвольных стратегий , выполняется условие
.
(3.3)
Использование в игре оптимальных смешанных стратегий обеспечивает первому игроку выигрыш, не меньший, чем при использовании им любой другой стратегии р; второму игроку – проигрыш, не больший, чем при использовании им любой другой стратегии q.
Совокупность оптимальных стратегий и цены игры составляет решение игры.