6. Взаимно-двойственные злп.
Двойственная задача линейного программирования.
Рассмотрим задачу ЛП
(1)
или, в матричной записи,
(2)
Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных вида
(3)
или, в матричной записи,
(4)
где .
Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных столько же, сколько строк в матрице задачи (1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.
Теорема двойственности. Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение.
13. Смешанные стратегии. Цена игры.
Смешанные стратегии
Если в матричной игре отсутствует седловая точка в чистых стратегиях, то находят верхнюю и нижнюю цены игры. Они показывают, что игрок 1 не получит выигрыша, превосходящего верхнюю цену игры и что игроку 1 гарантирован выигрыш, не меньший нижней цены игры. В примере 6.5 игрок 1 получил по своей оптимальной стратегии A1, отличной от максиминной , выигрыш, равный верхней цене игры. Такова плата за информированность о стратегии игрока 2. Это крайний случай. Не улучшится ли результат игрока 1, если информация о действиях противной стороны будет отсутствовать, но игрок будет многократно применять чистые стратегии случайным образом с определенной вероятностью?
В такой ситуации, оказывается, можно получать выигрыши, в среднем большие нижней цены игры, но меньшие верхней.
Смешанная стратегия игрока – это полный набор применения его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Подведем итоги сказанного и перечислим условия применения смешанных стратегий:
игра без седловой точки;
игроки используют случайную смесь чистых стратегий с заданными вероятностями;
игра многократно повторяется в сходных условиях;
при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;
- допускается осреднение результатов игр. Применяются следующие обозначения смешанных стратегий.
Чистые стратегии игрока являются единственно возможными несовместными событиями. В матричной игре, зная матрицу А (она относится и к игроку 1, и к
средний
выигрыш
(математическое ожидание эффекта) игрока 1:
–
компоненты
векторов.
Путем применения своих смешанных стратегий игрок 1 стремится максимально увеличить свой средний выигрыш, а игрок 2 – довести этот эффект до минимально возможного значения. Игрок 1 стремится достигнуть
.
Игрок 2 добивается того, чтобы выполнялось условие
векторы,
соответствующие оптимальным смешанным
,
при которых будет
выполнено равенство
Цена игры - ^-средний выигрыш игрока 1 при использовании обоими игроками смешанных стратегий. Следовательно, решением матричной игры являются:
оптимальная
смешанная стратегия игрока 1;
оптимальная
смешанная стратегия игрока 2;
-
цена игры.
,
если они образуют
.
Существует основная теорема математических игр (принимается без доказательства).
Теорема. Для матричной игры с любой матрицей А величины
существуют и равны между собой: а = 0 = у.
Следует отметить, что при выборе оптимальных стратегий игроку 1 всегда будет гарантирован средний выигрыш, не меньший, чем цена игры, при любой фиксированной стратегии игрока 2 (и наоборот, для игрока 2). Активными стратегиями игроков 1 и 2 называют стратегии, входящие в состав оптимальных смешанных стратегий соответствующих игроков с вероятностями, отличными от нуля. Значит, в состав оптимальных смешанных стратегий игроков могут входить не все априори заданные их стратегии.