- •1. Понятие модели. Принципы моделирования
- •9. Двойственные задачи
- •10. Теорема двойственности и экономическая интерпретация двойственных задач
- •16. Задача о нахождении кратчайшего пути от заданного узла до всех остальных узлов в графе и метод её решения- алгоритм Дейкстры
- •19. Задача о максимальном потоке и алгоритм Форда-Фалкерсона
- •Вершины — работы, дуги — зависимости
- •Событие
- •26 Задача о назначении. Венгерский алгоритм
- •30. Матричные игры. Верхняя чистая цена игры. Принцип минимакса-максимина
26 Задача о назначении. Венгерский алгоритм
Задача о назначениях – одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.
В наиболее общей форме задача формулируется следующим образом:
Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.
Приведём несколько вариантов постановки:
Есть
рабочих
и
заданий.
Для каждого рабочего известно, сколько
денег он запросит за выполнение того
или иного задания. Каждый рабочий может
взять себе только одно задание. Требуется
распределить задания по рабочим так,
чтобы минимизировать суммарные расходы.Дана матрица
размера
.
Требуется в каждой её строке выбрать
по одному числу так, чтобы в любом
столбце также было выбрано ровно по
одному числу, и при этом сумма выбранных
чисел была бы минимальной.Дана матрица размера . Требуется найти такую перестановку
длины
,
что величина
—
минимальна.Дан полный двудольный граф с вершинами; каждому ребру приписан некоторый вес. Требуется найти совершенное паросочетание минимального веса.
Отметим, что все
приведённые выше постановки "квадратны":
в них обе размерности всегда совпадают
(и равны
).
На практике часто встречаются аналогичные
"прямоугольные"
постановки, когда
,
и надо выбрать
элементов.
Впрочем, как легко заметить, от
"прямоугольной" задачи всегда
можно перейти к "квадратной",
добавив строки/столбцы с нулевыми/бесконечными
значениями соответственно.
Также заметим, что
по аналогии с поиском минимального решения
также можно ставить задачу
поиска максимального решения.
Впрочем, эти две задачи эквивалентны
друг другу: достаточно все веса умножить
на
.
Имеется n рабочих мест на некотором конвейере и n рабочих, которых нужно на эти рабочие места расставить; известна производительность cij рабочего i на рабочем месте j. Тот факт, что при некотором распределении на рабочие места рабочий ik попадает на рабочее место jk можно описать следующей таблицей:
Имея способ s назначения
на рабочие места, можно найти конкретную
для этого способа минимальную
производительность
и
заметить, что именно эта минимальная
производительность и определяет скорость
и производительность конвейера. То
рабочее место, на котором реализуется
минимальная производительность и
называют узким
местом в назначении.
Задача состоит в
том, чтобы максимизировать
Шаг 0. Фиксируем
матрицу производительностей
и
любое назначение на рабочие места.
Пусть s -
минимальная производительность при
этом назначении. Построим рабочую
таблицу тех же размеров, что и матрица C;
в клетку с номером (ij)
в этой таблице проставим символ «´»,
если
;
в противном случае эту клетку оставим
пустой.
Шаг 1. Рассматривая рабочую таблицу, построенную на предыдущем шагу, как рабочую таблицу в алгоритме для выбора наибольшего паросочетания в двудольном графе, найдем соответствующее наибольшее паросочетание. Если в нем окажется n ребер, то по ним восстанавливается новое назначение на рабочие места и с новой, более высокой, минимальной производительностью. Обозначим ее снова через s и вернемся к Шагу 0. Если же число ребер окажется меньше n, то имеющееся назначение на рабочие места уже оптимально.
27. Основные понятия теории игр и классификация игр
В ней используются методы для решения задач с конфликтной ситуацией. Игра представляет собой математическую модель реальной конфликтной ситуации.
Игроки - стороны, участвующие в конфликте.
Выигрыш - это исход конфликта.
Игра может быть парной (в ней участвует два игрока) и множественной (игроков больше двух).
Стратегия игрока - совокупность правил, определяющих выбор варианта действий при каждом личном ходе игрока в зависимости от ситуации, сложившейся в процессе игры.
Игра называется конечной, если число стратегий конечно. Бесконечной - если, хотя бы у одного игрока число стратегий бесконечно.
Стратегия игрока называется оптимальной, если она обеспечивает данному игроку максимально возможный средний выигрыш или минимально возможный средний проигрыш независимо от поведения противника.
В игре принимают участие два игрока, каждый из них может независимо друг от друга записать число 1, 2, 3.
Пример: если разность между числами, записанным игроком 1 и 2, положительна, то игрок 1 выигрывает количество очков, равное разности чисел. Если разность отрицательна, то выигрывает игрок 2 (игрок 1 проигрывает). Игра состоит из трех ходов. У игрока 1 три стратегии. Результат игры можно представить в виде матриц.
Рассмотрим матричную игру mxn. M стратегий у первого игрока, n - у другого.
Альфа - нижняя цена игры, т. е. гарантированный выигрыш, который может обеспечить себе игрок 1. Альфа = max (I) min (j) aij. Стратегия, которая обеспечивает получение нижней цены игры для игрока 1, называется максиминной. Если игрок 1 придерживается этой стратегии, то ему гарантированный выигрыш не меньше альфа при любом поведении игрока 2. Игрок 2 заинтересован в получении наименьшего проигрыша (минимизировать выигрыш игрока 1). Бета - это верхняя цена игры для второго игрока. Если альфа = бета, то игра имеет седловую точку. Общее значение верхней и нижней цены игры называется чистой ценой игры. А стратегии, позволяющие достичь этого значения, называется оптимальным чистыми значениями. Гамма = альфа = бета, называется седловым элементом платёжной матрицы. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.
Если платёжная матрица имеет седловую точку, то применяется максимальные и максиминные стратегии. Если нет седловой точки, то применяются сложные стратегии.
Сложная стратегия состоит в случайном применении двух и более чистых стратегий с определёнными частотами.
Pi = (p1, p2,..., pn)
Q2 = (q, Q2, qn)
Pi, Qi - вероятность применения чистой стратегии I.
Применение оптимальных стратегий обеспечивает игроку максимальный выигрыш или минимальный средний проигрыш, равный цене игры Гамма.
P1 = (p1, p2)
Q2 = (q1, Q2)
P1, P2 - вероятности выбора первой и второй стратегии для игрока 1.
{а11 x p1 + a21 x p2 = Y
{a21 x p1 + a22 x p2 = Y
{p1 + p2 = 1
Первая строчка - это цена игры для первого игрока при условии, что второй игрок выбрал первую стратегию
{a11 g1 + a12 g2 = Y
{a21 g1 + a22 g2 = Y
{g1 + g2 = 1
Упрощение игр
Если в матрице все элементы строки равны соответствующим элементам другой строки, то соответствующие строки (столбцы) называются дублирующими. Можно тогда одну из строк (столбец) убрать.
Если в матрице все элементы меньше или равны соответствующим элементам другой строки, то соответствующая строка называется заведомо невыгодной.
Если в матрице все элементы столбца больше или равны соответствующим элементам другого столбца, то такой столбец называется заведомо невыгодным.
Задача: Матричная игра задана следующей платежной матрицей :
|
Стратегии "B" |
|||||||
Стратегии "A" |
B1 |
B2 |
||||||
A1 |
3 |
5 |
||||||
A2 |
6 |
|
||||||
Найти решение матричной игры, а именно: - найти верхнюю цену игры; - нижнюю цену игры; - чистую цену игры; - указать оптимальные стратегии игроков; - привести графическое решение (геометрическую интерпретацию), при необходимости.
Шаг:1
Определим нижнюю цену игры - α
Нижняя цена игры α — это максимальный выигрыш, который мы можем гарантировать себе, в игре против разумного противника, если на протяжении всей игры будем использовать одну и только одну стратегию (такая стратегия называется "чистой"). Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец ( Выделен желтым цветом см. Табл.1 ). Затем найдем максимальный элемент дополнительного столбца (отмечен звездочкой), это и будет нижняя цена игры.
Таблица 1
|
Стратегии "B" |
|
|||||||||||||
Стратегии "A" |
B1 |
B2 |
Минимумы строк |
||||||||||||
A1 |
3 |
5 |
3* |
||||||||||||
A2 |
6 |
|
|
||||||||||||
В нашем случае нижняя цена игры равна: α = 3, и для того чтобы гарантировать себе выигрыш не хуже чем 3 мы должны придерживаться стратегии A1 Шаг:2
Определим верхнюю цену игры - β
Верхняя цена игры β — это минимальный проигрыш, который может гарантировать себе игрок "В", в игре против разумного противника, если на протяжении всей игры он будет использовать одну и только одну стратегию. Найдем в каждом столбце платежной матрицы максимальный элемент и запишем его в дополнительную строку снизу ( Выделена желтым цветом см. Табл.2 ). Затем найдем минимальный элемент дополнительной строки (отмечен плюсом), это и будет верхняя цена игры.
Таблица 2
|
Стратегии "B" |
|
|||||||||||||
Стратегии "A" |
B1 |
B2 |
Минимумы строк |
||||||||||||
A1 |
3 |
5 |
3* |
||||||||||||
A2 |
6 |
|
|
||||||||||||
Максимумы столбцов |
6 |
5+ |
|
||||||||||||
В нашем случае верхняя цена игры равна: β = 5, и для того чтобы гарантировать себе проигрыш не хуже чем 5 противник ( игрок "B") должен придерживаться стратегии B2 Шаг:3 Сравним нижнюю и верхнюю цены игры, в данной задаче они различаются, т.е. α ≠ β, платежная матрица не содержит седловой точки. Это значит, что игра не имеет решения в чистых минимаксных стратегиях, но она всегда имеет решение в смешанных стратегиях. Смешанная стратегия, это чередуемые случайным образом чистые стратегии, с определенными вероятностями (частотами). Смешанную стратегию игрока "А" будем обозначать
SA = |
|
где A1, A2 - стратегии игрока "A", а p1, p2 - соответственно вероятности (частоты), с которыми эти стратегии применяются, причем p1 + p2 = 1. Аналогично смешанную стратегию игрока "В" будем обозначать
SB = |
|
где B1, B2 - стратегии игрока "B", а q1, q2 - соответственно вероятности, с которыми эти стратегии применяются, причем q1 + q2 = 1. Оптимальная смешанная стратегия для игрока "А" та, которая обеспечивает ему максимальный выигрыш. Соответственно для "B" - минимальный проигрыш. Обозначаются эти стратегии SA* и SB* соответственно. Пара оптимальных стратегий образует решение игры.
28. Игры с нулевой и ненулевой суммой
Игра может быть с нулевой суммой. В игре с нулевой суммой интересы игроков противоположны и выигрыш одного игрока равен проигрышу другого.
28.Игра с нулевой суммой - особая разновидность игр с постоянной суммой, то есть таких, где игроки не могут увеличить или уменьшить имеющиеся ресурсы, или фонд игры. В этом случае сумма всех выигрышей равна сумме всех проигрышей при любом ходе.
Примерами таких игр может служить покер, где один выигрывает все ставки других; реверси, где захватываются фишки противника; либо банальное воровство.
В играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. Исход такой игры может быть меньше или больше нуля. Такие игры могут быть преобразованы к нулевой сумме — это делается введением фиктивного игрока, который “присваивает себе” излишек или восполняет недостаток средств.
Ещё игрой с отличной от нуля суммой является торговля, где каждый участник извлекает выгоду. Сюда также относятся го, шашки и шахматы; в двух последних игрок может превратить свою рядовую фигуру в более сильную, получив преимущество. Во всех этих случаях сумма игры увеличивается. Широко известным примером, где она уменьшается, является война.
29 Матричные игры. Примеры игр с седловыми точками в матрицах и без седловых точек
Игра – это математическая модель реальной конфликтной ситуации. Конфликтная ситуация двух игроков называется парной игрой. Парную игру с нулевой суммой удобно исследовать, если она описана в виде матрицы. Такая игра называется матричной; матрица, составленная из чисел aij, называется платежной.
0 -1 -2
1 0 4
2 1 0
Математической моделью антагонистической игры является матричная игра с матрицей A, в которой ходы (стратегии) игрока A расположены по строкам, а ходы (стратегии) игрока B расположены по столбцам. В самой матрице записаны выигрыши игрока A при соответствующих ходах игроков A и B (отрицательный выигрыш – это проигрыш).
Алгоритм решения матричной игры
На основании анализа платёжной матрицы следует определить, существуют ли в ней доминируемые стратегии, и исключить их.
Найти верхнюю и нижнюю цены игры и определить, имеет ли данная игра седловую точку (нижняя цена игры должна быть равна верхней цене игры).
Если седловая точка существует, то оптимальными стратегиями игроков, являющимися решением игры, будут их чистые стратегии, соответствующие седловой точке. Цена игры равна верхней и нижней цены игры, которые равны между собой.
Если игра не имеет седловой точки, то решение игры следует искать в смешанных стратегиях. Для определения оптимальных смешанных стратегий в играх m × n следует использовать симплекс-метод, предварительно переформулировав игровую задачу в задачу линейного программирования.
Представим алгоритм решения матричной игры графически.
Методы решения матричной игры в смешанных стратегиях
Итак, если седловая точка отсутствует, решение игры проводят в смешанных стратегиях и решают следующими методами:
Решение игры через систему уравнений.
Если задана квадратная матрица nxn (n=m), то вектор вероятностей можно найти, решив систему уравнений. Этот метод используется не всегда и применим только в отдельных случаях (если матрица 2x2, то решение игры получается практически всегда). Если в решении получаются отрицательные вероятности, то данную систему решают симплекс-методом.
Решение игры графическим методом.
В случаях, когда n=2 или m=2, матричную игру можно решить графически.
Решение матричной игры симплекс-методом.
В этом случае матричная игра сводится к задаче линейного программирования.
