13. Упрощение матричных игр
Решение матричных игр тем сложнее, чем больше размерность платежной матрицы. Поэтому для игр с платежными матрицами большой размерности отыскание оптимального решения можно упростить, если уменьшить их размерность путем исключения дублирующих и заведомо невыгодных (доминируемых) стратегий.
Определение 1. Если в платежной матрице игры все элементы строки (столбца) равны соответствующим элементам другой строки (столбца), то соответствующее этим строкам (столбцам) стратегии называются дублирующими.
Определение 2. Если в платежной матрице игры все элементы некоторой строки, определяющей стратегию АI игрока А, не больше (меньше или некоторые равны) соответствующих элементов другой строки, то стратегия АI называется доминируемой (заведомо невыгодной).
Определение 3. Если в платежной матрице игры все элементы некоторого столбца, определяющего стратегию ВI Игрока В не меньше (больше или некоторые равны) соответствующих элементов другого столбца, то стратегия В
Правило. Решение матричной игры не изменится, если из платежной матрицы исключить строки и столбцы, соответствующие дублирующим и доминируемым стратегиям.
Пример. Упростить матричную игру, платежная матрица которой имеет вид:
Bj Ai | B1 | B2 | B3 | B4 | B5 |
A1 | 5 | 9 | 3 | 4 | 5 |
A2 | 4 | 7 | 7 | 9 | 10 |
A3 | 4 | 6 | 3 | 3 | 9 |
A4 | 4 | 8 | 3 | 4 | 5 |
A5 | 4 | 7 | 7 | 9 | 10 |
Из платежной матрицы видно, что стратегия А2 дублирует стратегию А5, потому любую из них можно отбросить (отбросим стратегию А5).
Сравнивая почленно стратегии А1 и А4, видим, что каждый элемент строки А4 не больше соответствующего элемента строки А1. Поэтому применение игроком А доминирующей над А4 стратегии А1 всегда обеспечивает выигрыш, не меньший того, который был бы получен при применении стратегии А4. Следовательно, стратегию А4 можно отбросить. Таким образом, имеем упрощенную матричную игру с платежной матрицей вида:
Bj Ai | B1 | B2 | B3 | B4 | B5 |
A1 | 5 | 9 | 3 | 4 | 5 |
A2 | 4 | 7 | 7 | 9 | 10 |
A3 | 4 | 6 | 3 | 3 | 9 |
Из этой матрицы видно, что в ней некоторые стратегии игрока В доминируют над другими: В3 над В2, В4 и В5.
Отбрасывая доминируемые стратегии В2, В4 и В5, получаем игру 3×2, имеющей платежную матрицу вида:
Bj Ai | B1 | B3 |
A1 | 5 | 3 |
A2 | 4 | 7 |
A3 | 4 | 3 |
В этой матрице стратегия А3 доминируется как стратегией А1, так и стратегией А2. Отбрасывая стратегию А3, окончательно получаем игру 2×2 с платежной матрицей
Bj Ai | B1 | B3 |
A1 | 5 | 3 |
A2 | 4 | 7 |
Эту игру уже упростить нельзя, ее надо решать рассмотренным выше алгебраическим или геометрическим методом.
Необходимо отметить, что отбрасывая дублируемые и доминируемые стратегии в игре с седловой точкой, мы все равно придем к игре с седловой точкой, т. е. к решению в чистых стратегиях. Но лучше сразу проверить, не обладает ли игра седловой точкой — это проще, чем сравнивать почленно все строки и все столбцы платежной матрицы.
Алгебраические методы решения матричных игр иногда производить проще, если использовать также следующие свойства матричных игр.
Свойство 1. Если ко всем элементам платежной матрицы прибавить (вычесть) одно и тоже число С, то оптимальные смешанные стратегии игроков не изменятся, а только цена игры увеличится (уменьшится) на это число С.
Свойство 2. Если каждый элемент платежной матрицы умножить на положительное число k, то оптимальные смешанные стратегии игроков не изменятся, а цена игры умножится на k.
Отметим, что эти свойства верны и для игр, имеющих седловую точку. Эти два свойства матричных игр применяются в следующих случаях:
1) если матрица игры наряду с положительными имеет и отрицательные элементы, то ко всем ее элементам прибавляют такое число, чтобы исключить отрицательные числа в матрице;
2) если матрица игры имеет дробные числа, то для удобства вычислений элементы этой матрицы следует умножить на такое число, чтобы все выигрыши были целыми числами.
Пример. Решить матричную игру 2х2 с платежной матрицей вида:
Bj Ai | B1 | B2 |
A1 | 0.5 | -0.2 |
A2 | 0.1 | 0.3 |
Умножая все элементы платежной матрицы на 10, а затем прибавляя к ним число 2, получаем игру с платежной матрицей
Bj Ai | B1 | B2 |
A1 | 7 | 0 |
A2 | 3 | 5 |
Решая эту игру алгебраическим методом, получаем
; ;
; ;
.
В соответствии со свойствами 1 и 2, исходная матричная игра имеет те же оптимальные смешанные стратегии: и . А для получения исходной цены игры необходимо из полученной цены игры вычесть 2, а затем разделить на 10.
Таким образом, получаем цену исходной игры: .
| < Предыдущая | Следующая > |
|---|
5.3 Упрощение матрицы игры. Графический метод решения.
Гуманитарные науки / Теория системного анализа и принятия решений / 5.3 Упрощение матрицы игры. Графический метод решения.
Перед тем, как решать игру, нужно, прежде всего, попытаться ее упростить, избавившись от лишних стратегий. Введем понятие доминирования. Стратегия Aiигрока А называется доминирующей над стратегией Ak, если в строке Ai стоят выигрыши не меньшие, чем в соответствующих клетках строки Ak, и из них, по крайней мере, один действительно больше, чем в соответствующей клетке строки Ak. Если все выигрыши строки Ai равны соответствующим выигрышам строки Ak, то стратегия Ai называется дублирующей стратегию Ak.
Аналогично определяются доминирование и дублирование для стратегий игрока В: доминирующей называется та его стратегия, при которой везде стоят выигрыши не большие, чем в соответствующих клетках другой, и, по крайней мере, один из них действительно меньше; дублирование означает полное повторение одного столбца другим.
Естественно, что если для какой-то стратегии есть доминирующая, то эту стратегию можно отбросить; также отбрасываются и дублирующие стратегии.
Пример 1
Пусть игра задана матрицей табл. 5.6.
Прежде всего, заметим, что в ней стратегия А5 дублирует стратегию А2, поэтому любую из них можно отбросить. Отбрасывая A5, замечаем, что в строке А1 все выигрыши больше (или равны) соответствующим выигрышам строки А4, значит А1 доминирует над А4. Отбросим А4 и получим матрицу (табл.
5.7).
Таблица 5.6 Заданная матрица игры
В1 | В2 | В3 | В4 | В5 | |
А1 | 4 | 7 | 2 | 3 | 4 |
А2 | 3 | 5 | 6 | 8 | 9 |
А3 | 4 | 4 | 2 | 2 | 8 |
А4 | 3 | 6 | 1 | 2 | 4 |
А5 | 3 | 5 | 6 | 8 | 9 |
Таблица 5.
7 Удаление дублирующих стратегий
В1 | В2 | В3 | В4 | В5 | |
А1 | 4 | 7 | 2 | 3 | 4 |
А2 | 3 | 5 | 6 | 8 | 9 |
А3 | 4 | 4 | 2 | 2 | 8 |
Замечаем, что некоторые стратегии игрока В доминируют над другими: например, В3 над В4 и В5, a B1 – над стратегией В2 (В стремиться отдать поменьше).
Отбрасывая столбцы В2, В4, В5, получаем игру (табл. 5.8).
Таблица 5.8 Удаление не доминирующих стратегий
В1 | В3 | |
А1 | 4 | 2 |
А2 | 3 | 6 |
А3 | 4 | 2 |
Наконец, в табл.
5.8 строка А3 дублирует A1, поэтому ее можно отбросить. Окончательно получим игру (табл. 5.9).
Таблица 5.9 Упрощенная матрица игры
В1 | В3 | |
А1 | 4 | 2 |
А2 | 3 | 6 |
Эту игру уже не упростить.
Заметим, что, отбрасывая лишние (дублирующие и заведомо невыгодные) стратегии в игре с седловой точкой, мы придем к решению в чистых стратегиях. Но лучше сразу проверить, не обладает ли игра седловой точкой – это проще, чем сравнивать почленно все строки и все столбцы.
Для простых игр размером или вполне пригоден графический метод, который мы сейчас рассмотрим.
Пусть задана игра с платежной матрицей (табл. 5.10).
Таблица 5.10 Платежная матрица
В1 | В2 | ¼ | Вn | |
А1 | a11 | a12 | ¼ | a1n |
А2 | a21 | a22 | ¼ | a2n |
Смешанная стратегия первого игрока представляет собой совокупность двух чисел p1 и p2, в сумме дающих единицу.
Геометрически ее можно представить точкой на единичном отрезке (рис. 5.1), при этом левая крайняя точка отрезка соответствует чистой стратегии A2 (p1= 0, p2= 1), а правая – чистой стратегии А1 (p1= 1, p2= 0).
Выберем прямоугольную систему координат и отложим на оси абсцисс единичный отрезок для представления смешанных стратегий первого игрока (рис. 5.2). На концах этого отрезка восстановим два перпендикуляра, на которых будем откладывать выигрыши первого игрока, когда он использует чистые стратегии А2 и А1.
Пусть второй игрок выбрал стратегию В1. Тогда при использовании первым игроком чистой стратегии А2 он получает выигрыш а21 (соответствующая точка на левом перпендикуляре), а при использовании чистой стратегии А1 – выигрыш а11 (точка на правом перпендикуляре).
Соединив эти две точки отрезком прямой, мы получаем график зависимости выигрыша первого игрока М(р,В1) от смешанной стратегии при условии, что второй игрок использует чистую стратегию В1(рис. 5.2). Точно такие же прямые можно построить для В1, В2,…,Вn.
Рис. 5.1. Геометрическое представление смешанной стратегии
Рис. 5.2. График зависимости выигрыша первого игрока от смешанной стратегии
Далее мы должны для каждой смешанной стратегии р, то есть для каждой точки единичного отрезка на оси абсцисс, найти , т.е. нижнюю границу множества n прямых. Эта нижняя граница отмечена (см. рис. 5.2) жирной линией. Та точка отрезка, при которой нижняя граница достигает максимума, соответствует искомой смешанной стратегии , высота максимума дает при этом значение нижней цены игры .
Аналогично можно найти оптимальную смешанную стратегию второго игрока и нижнюю цену игры в играх с той лишь разницей, что здесь нужно искать не максимум нижней границы, а минимум верхней границы.
Согласно основной теореме матричных игр решение в смешанных стратегиях существует всегда и .
Для уточнения и , и нужно найти точку пересечения соответствующих прямых, что в, свою очередь, сводится к решению системы. Рассмотрим это подробно на следующем примере.
Пример 2
Найдем пару оптимальных смешанных стратегий в матричной игре, размером (табл. 5.11). Графическим методом можно найти стратегии как для первого, так и для второго игрока.
Таблица 5.11 Матрица игры
В1 | В2 | |
А1 | 1 | –1 |
А2 | -2 | 2 |
Соответствующие построения приведены на рис.
5.3.
Рис. 5.3. Графический метод поиска стратегий:
а – для первого игрока, б – для второго игрока
Для уточнения и , и , а также v решаем системы уравнений:
Чтобы составить системы, нужно найти и , приравнять их к v с учетом того, что компоненты и в сумме дают единицу. Из решения систем получим, что:
; ; v = 0.
Как упростить операции с матрицами
Обновлено 25 апреля 2017 г.
Автор Damon Verial
Работа с операциями с матрицами поначалу может быть сложной из-за общего ощущения, что вы должны отслеживать большое количество чисел. Некоторые ученики пытаются складывать и умножать матрицы методом грубой силы, держа все числа в уме. Однако упрощение процессов может не только упростить матричные операции, но и повысить точность их вычисления.
Технически скаляр — это матрица с одним элементом, поэтому у него есть специальное название — скаляр — несмотря на то, что он так знаком студентам, как «просто число». Но когда вы слышите слово «скаляр» в матричной алгебре, вы можете просто подумать о «числе», если это поможет.
Умножить скаляры — одиночные числа перед матрицами — сначала. Ищите числа сами по себе, а не в самих матрицах, сидящих рядом с матрицами. Скаляр — это просто число, подобное тем, с которыми вы привыкли иметь дело в математике более низкого уровня. Когда вы видите выражение 2×3, вы умножаете два скаляра, чтобы получить новый скаляр 6. В матричной алгебре скаляр работает так же, но умножает всю матрицу, то есть каждый элемент внутри матрицы. Например, если B представляет матрицу, 2B является скаляром, умноженным на матрицу. В этом случае вы должны умножить каждый элемент в B на число 2, получив новую матрицу. Например, если первая строка матрицы B равна [3, 4], новая строка будет [6, 8].
Перепишите матричную задачу с матрицами, умноженными на скаляры. Замените старую матрицу на новую в задаче. Например, если ваша задача — AB + 2B, где A и B — матрицы, сначала выполните 2B и замените ее новой матрицей, в которой все элементы удвоены. Теперь задача становится AB + C, где C — новая матрица.
Выполнение умножения путем «выстраивания» строк и столбцов. Умножьте AB, взяв первую строку A, «выровняв» ее с первым столбцом B. Умножьте по строкам и сложите. Это дает вам первый элемент новой матрицы. Например, если первая строка A равна [5, 0], а первый столбец B равен [4, 1], при выравнивании строки и столбца 5 и 4 будут располагаться рядом друг с другом, а 0 и 1 рядом с каждым. Другие. Затем умножение становится более очевидным: 5_4 = 20 и 0_1 = 0. Их сложение дает 20, первый элемент новой матрицы.
Перепишите матричную задачу с перемножением матриц. В задаче AB + C перепишите AB как D, что является матрицей, которую вы получите после умножения A и B.
Сложите или вычтите матрицы, поместив все числа отдельных матриц в уравнения в одной большой матрице. Перепишите задачу, например A + B, как единую матрицу, которая берет элементы из A и элементы из B, помещая их в большую матрицу. Используйте знаки плюс, чтобы разделить числа для сложения и знаки минус для вычитания.
Например, если первая строка A равна [2, 1], а первая строка B равна [10, 4], поместите эти числа в первую строку новой большой матрицы как [2+10, 1+4 ]. Выполните сложение после того, как вы переписали матрицу. Это может помочь вам избежать мелких ошибок при сложении или вычитании в уме.
Статьи по теме
Ссылки
- Purplemath.Com: скалярное и матричное умножение
- Purplemath.Com: сложение и вычитание матриц
Советы
- Технически скаляр представляет собой матрицу с одним элементом, поэтому у него есть специальное название — скаляр — несмотря на то, что он так знаком студентам, как «просто число». Но когда вы слышите слово «скаляр» в матричной алгебре, вы можете просто подумать о «числе», если это поможет.
Об авторе
Получив степень магистра психологии в Восточной Азии, Деймон Вериал с 2010 года применяет свои знания в смежных темах. С 2001 года он профессионально пишет статьи и публикуется в финансовых изданиях, таких как SafeHaven и Портфолио Макмиллиана. Он также ведет финансовый информационный бюллетень в Stock Barometer.
Упрощение определителей — Концепция — Предварительное исчисление Видео от Brightstorm
Нахождение определителя квадратной матрицы 3×3 или большей квадратной матрицы может потребовать большого количества вычислений. Чтобы уменьшить объем вычислений, мы можем использовать методы , упрощающие определители . Эти методы упрощения определителей включают использование операций со строками или столбцами для замены некоторых элементов матрицы нулями.
определитель операции со строками операции со столбцами перестановка строк общие факторы добавление кратного одной строки к другой
Вычисление определителей может быть очень сложным, когда вы имеете дело с определителями 3 на 3 или выше, и поэтому вы определенно хотите упростить определитель перед его вычислением, и есть 3 правила, которые позволяют вам это сделать.
Вот первое, с любым определителем вы можете факторизовать константу из строки или столбца, поэтому, например, здесь у меня есть много общих множителей в каждой строке, взгляните на последнюю строку, у меня есть общий множитель 10 вы можете вытащить это прямо и поместить его впереди, поэтому, когда я вычисляю этот определитель, вместо этого я могу вычислить этот более простой определитель и просто умножить результат на 10, и вы заметите, что я мог бы на самом деле разложить больше, я могу разложить 16 из вершины row, затем я получаю 160 раз, и так далее, и так далее, а затем продолжайте делать это, пока ваш определитель не станет красивым и простым.
Второе, что вы могли бы сделать, вы можете добавить кратность одной строки к другой, и то же самое касается столбцов, поэтому, например, вы, вероятно, уже заметили, что нам нравится расширяться по строкам или столбцам с большим количеством нулей, где вы можете создать больше нулей, умело добавляя кратные числа одной строки или столбца к другой.
Теперь вот что я сделал: я умножил первый столбец на 4 и добавил его к третьему столбцу, так что теперь этот столбец равен 4 умножить на с1 плюс с3 справа, 4 умножить на 16 — это 64, добавить это к этому отрицательному 64, и вы получите 0 мы делаем это для всего столбца. Теперь, что интересно в этой операции со строкой, в данном случае это операция со столбцом, так это то, что она не меняет значение определителя. Вы всегда можете добавить кратность строки к другой строке или кратность столбца к другому столбцу, и это не изменит значение.
И третье, что вы можете сделать, это поменять местами две строки или два столбца, так что здесь, например, скажем, по каким-то причинам я хочу, чтобы этот 0 был слева, я могу просто поменять местами первые два столбца, чтобы эти два столбца были переключены. Всякий раз, когда вы переключаете две строки или два столбца, это меняет знак определителя, поэтому 3 вещи, которые вы можете сделать, чтобы упростить определитель; во-первых, вы можете вывести константу из любой строки или любого столбца, во-вторых, вы можете добавить любое число, кратное одной строке, к другой строке, и то же самое касается столбцов, а в-третьих, вы можете поменять местами два столбца или две строки, просто не забудьте изменить знак когда ты это сделаешь.