Лекция МПС №6 от 13.11.2012


Специальные задачи линейного программирования
Математическая модель задачи транспортного типа
Теория игр – это систематическая теория конфликтных ситуаций, которая занимается выработкой рекомендаций по рациональному образу действий участников многократно повторяющегося конфликта. Стороны, участвующие в игре, называются игроками. Принятие игроком того или иного решения в процессе игры и его реализация называется ходом. Ходы могут быть личными, т.е. сознательными, и случайными. Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при любом личном ходе игрока в зависимости от ситуации, сложившейся в процессе игры. Игра называется конечной, если число стратегий игроков конечно, и бесконечной, если хотя бы у одного из игроков число стратегий является бесконечным. Стратегия игрока называется оптимальной, если она обеспечивает данному игроку при многократном повторении игры максимально возможный средний выигрыш или минимально возможный средний проигрыш.
Игры, в которых участвуют 2 игрока, называются парными, а игры с большим числом участников – множественными. Если в парной игре выигрыш одного игрока равен проигрышу второго, то такую игру называют игрой с нулевой суммой. В зависимости от вида функций выигрышей игры подразделяются на матричные, биматричные, непрерывные, выпуклые и др.
3.2.1 Решение игры в чистых стратегиях
Пусть игроки А и В располагают конечным числом возможных действий (чистых стратегий). Обозначим их соответственно через и . Игрок А может выбрать любую чистую стратегию , , в ответ на которую игрок B может выбрать любую свою чистую стратегию , . Если игра состоит только из личных ходов, то выбор пары стратегий единственным образом определяет результат - выигрыш игрока А или проигрыш игрока В. Если известны значения выигрыша для любой пары чистых стратегий, то можно составить матрицу выигрышей игрока А (проигрышей игрока В). Эту матрицу называют платежной. Цель игрока А – максимизировать свой выигрыш, а игрока В – минимизировать свой проигрыш.
При определении наилучших стратегий игроков основой рассуждений является принцип разумности, который предполагает, что противники, участвующие в игре, одинаково разумны и любой из них делает все для того, чтобы добиться своей цели. Используя этот принцип, найдем наилучшую стратегию игрока А. Для этого проанализируем последовательно все его стратегии. Выбирая стратегию , игрок А должен рассчитывать, что игрок В ответит на нее той из своих стратегий , для которой выигрыш игрока А будет минимальным. Поэтому найдем в любой строке платежной матрицы минимальное число , т.е.
(3.6)
Зная число , игрок А должен предпочесть другим стратегиям ту, для которой максимально, т.е.
(3.7)
Величина называется гарантированным (минимальным) выигрышем, который может себе обеспечить игрок А при любых стратегиях игрока В или нижней ценой игры (максимином).
Игрок В заинтересован уменьшить свой проигрыш или обратить в минимальный выигрыш игрока А. Поэтому в любом столбце находим максимальное значение выигрыша и среди них выбираем наименьшее, т.е.
(3.8)
Величину называют верхней ценой игры (минимаксом). Она показывает максимальный проигрыш, которого может достигать игрок В при любых стратегиях игрока А.
Теорема. В матричной игре нижняя чистая цена игры не превосходит верхней чистой цены игры, т.е. , поскольку
.(3.9)
Если для чистых стратегий , игроков А и В соответственно имеет место равенство , то пару чистых стратегий называют седловой точкой матричной игры, а число − чистой ценой игры. Элемент матрицы называют седловым элементом платежной матрицы. Он является наименьшим элементом в строке l и наибольшим в столбце k, т.е.
, , (3.9)
Так как отклонение игрока А от максимальной стратегии ведет к уменьшению его выигрыша, а отклонение игрока В от минимальной стратегии ведет к увеличению его проигрыша, то стратегии и являются оптимальными чистыми стратегиями соответственно игроков А и В. Тройку называют решением игры. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.
Пример 10. Два банка А и В осуществляют капитальные вложения в пять строительных объектов. С учетом особенностей вкладов и местных условий прибыль банка А в зависимости от объема финансирования выражается элементами платежной матрицы А (тыс. руб.). Для упрощения задачи принять, что убыток банка В равен прибыли банка А. Найти решение матричной игры в чистых стратегиях, если оно существует.

Решение.

Так как , то игра неразрешима в чистых стратегиях (игра не имеет седловой точки).
3.2.2 Смешанные стратегии и их свойства
Если матричная игра не имеет седловой точки, т.е. , то применение минимаксных стратегий приводит к тому, что для любых из игроков выигрыш не меньше , а проигрыш не больше . Решение находят, применяя смешанные стратегии.
Смешанной стратегией игрока А называется вектор , где
и , ,(3.9)
- вероятность, с которой игрок А выбирает свою чистую стратегию .
Смешанной стратегией игрока B называется вектор , где
и , ,(3.10)
- вероятность, с которой игрок B выбирает свою чистую стратегию .
Чистые стратегии являются частным случаем смешанных. Например, если – чистая стратегия игрока А, то вероятность её выбора равна 1, т.е. . Так как игроки выбирают свои чистые стратегии случайно и независимо друг от друга, то игра принимает случайный характер. Случайной становится и величина выигрыша игрока А (проигрыша игрока В). Поэтому говорить можно лишь о средней величине выигрыша. Эта величина является функцией смешанных стратегий и определяется по формуле математического ожидания:
(3.11)
Функция называется платежной функцией игры с матрицей .
Смешанные стратегии и называют оптимальными, если они образуют седловую точку для платежной функции т.е. удовлетворяют неравенству
(3.12)
Значение платежной функции при оптимальных смешанных стратегиях и , т.е. называют ценой игры. Совокупность оптимальных стратегий и цены игры составляет решение игры.
Стратегия является доминирующей над стратегией , если все элементы l-й строки не меньше соответствующих элементов i-й строки, т.е. , ( стратегия доминируемая).
Стратегия является доминирующей над стратегией , если все элементы k-го столбца меньше или равны соответствующим элементам j-го столбца, т.е. , ( стратегия доминируемая).
Исключение из платежной матрицы доминируемых стратегий (ими игрокам пользоваться заведомо невыгодно) позволяет уменьшить ее размерность, а это упрощает решение игры. Вероятность применения доминируемых стратегий равна нулю.
Теорема 1. Оптимальные смешанные стратегии и соответственно игроков А и В в матричной игре с ценой будут оптимальными и в матричной игре с ценой , где .
Следовательно, платежную матрицу, имеющую отрицательные числа, можно преобразовать в матрицу с положительными числами. В последней матричной игре цена игры будет положительная: .
Теорема 2. Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.
Теорема 3. Для того чтобы смешанные стратегии и были оптимальными для игроков А и В в игре с матрицей и выигрышем , необходимо и достаточно выполнение неравенств
, (3.13)
, (3.14)
Следствия.
1. Если игрок А применяет оптимальную смешанную стратегию , а игрок В любую чистую стратегию , то выигрыш игрока А будет не меньше цены игры .
2. Если игрок В использует оптимальную смешанную стратегию , а игрок А – любую чистую стратегию , то проигрыш игрока В не превысит цену игры .
Пример 11. Упростить платежную матрицу:

Решение:



3.2.3 Решение матричных игр в смешанных стратегиях путем сведения к паре двойственных задач
Рассмотрим игру с платежной матрицей . Будем полагать, что все элементы платежной матрицы неотрицательны, т.е. , , (в противном случае можно ко всем элементам матрицы добавить достаточно большое число ; при этом по теореме 1 цена игры увеличится на L, а смешанные стратегии игроков не изменятся). Тогда можно считать . И пусть платежная матрица не содержит седловой точки, т.е. игра решается в смешанных стратегиях и .
Если - оптимальная смешанная стратегия игрока В, то по теореме 3 должны выполняться неравенства (3.14):
, .
Преобразуем эту систему неравенств, разделив обе части на число , и введем новое обозначение , . Тогда
, , (3.15)
А так как , то .
Поскольку игрок В стремится минимизировать цену игры (свой проигрыш), то величина будет максимизироваться. Поэтому оптимальная стратегия игрока В определится из задачи ЛП следующего вида:
найти
.(3.16)
при ограничениях
, ;(3.17)
, ;(3.18)
Аналогично рассуждая с позиции игрока А (используя неравенства (3.13) теоремы 3
,
и, обозначив , , получим, что оптимальная стратегия игрока А определится решением задачи ЛП следующего вида:
найти
.(3.19)
при ограничениях
, ;(3.20)
, ;(3.21)
Задачи (3.16) – (3.18) и (3.19) – (3.21) являются парой симметричных взаимно двойственных задач ЛП. Решив одну из них, автоматически получают решение другой. При этом оптимальные смешанные стратегии и соответственно игроков А и В находят по формулам
, ;(3.22)
, ;(3.23)
а цену игры - по формуле
(3.24)
3.2.4 Этапы решения матричной игры
Проверить, имеет ли игра решение в чистых стратегиях.
Упростить платежную матрицу.
Если среди элементов платежной матрицы есть отрицательные, то ко всем элементам матрицы необходимо прибавить такое число , чтобы все элементы стали неотрицательными. При этом цена игры увеличится на L, а оптимальные смешанные стратегии не изменятся.
Составить пару взаимно двойственных задач ЛП (3.16) – (3.18) и (3.19) – (3.21), эквивалентных данной матричной игре.
Определить оптимальные планы двойственных задач.
Найти решение игры, используя формулы (3.22) – (3.24).
Пример 12. Найти оптимальные стратегии банков для задачи из примера 10 с платежной матрицей А:

Решение.
Проверим, имеет ли игра решение в чистых стратегиях (см. пример 10).
Упростим платежную матрицу (см. пример 11) и подпишем над столбцами матрицы смешанные стратегии банка B, которые остались после исключения доминируемых стратегий , , вероятности применения которых равны нулю: , . Рядом со строками матрицы подпишем смешанные стратегии банка А, которые остались после исключения доминируемых стратегий , , , вероятности применения которых также равны нулю: , , .

Так как среди элементов упрощенной матрицы есть отрицательные, то ко всем элементам А прибавим такое число , чтобы все значения стали неотрицательными. В нашем примере возьмем . При этом цена игры увеличится на и станет равной , а оптимальные смешанные стратегии банков не изменятся.
Подпишем над столбцами матрицы переменные , соответствующие смешанным стратегиям банка В, а рядом со строками матрицы − переменные , соответствующие смешанным стратегиям банка А.

Составим пару взаимно двойственных задач, эквивалентную матричной игре с платежной матрицей А


,


,
Решим прямую задачу симплекс-методом:


,
, .




, .
, .
Найдем решение игры в смешанных стратегиях.

,
,

Следовательно, из общей суммы средств, выделяемых банком А на строительство пяти объектов, на долю 3-го объекта следует выделить 60%, на долю 4-го – 40%. На остальные строительные объекты деньги выделять нецелесообразно.
,
,
,

Из общей суммы средств, выделяемых банком В на строительство пяти объектов, на долю 3-го объекта следует выделить 80 %, а на долю 4-го − 20 % всей суммы. В остальные строительные объекты деньги вкладывать нецелесообразно.
Такое распределение денежных средств банками А и В на строительство пяти объектов позволит им получить максимальную прибыль 0,6 тыс. ден. ед.

Приложенные файлы

  • docx 8981825
    Размер файла: 308 kB Загрузок: 0

Добавить комментарий