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).
|
Bj Ai |
B1 |
B2 |
B3 |
B4 |
B5 |
|
A1 |
|
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. Таким образом, получаем цену исходной игры: .
| < Предыдущая | Следующая > |
|---|
|
|
Матрица – таблица элементов. Сложение 2-х одноразмерных матриц – A+B=( ). Можно умножить матрицу на число. Для этого необходимо умножить все элементы матрица на это число. Для того, чтобы умножать матрицы между собой, число столбцов в первой матрице должно быть равно числу строк во второй (элементы строки первой матрицы умножаются на элементы столбца второй матрицы и складываются меду собой , матрицу и перемножить нельзя). A*B!=B*A Нулевой матрицей, называется матрица соответствующего порядка, состоящая из нулей. Единичной матрицей, называется матрица, в главной диагонали которой стоят единицы . Можно использовать операцию транспонирования. Транспонированная матрица — матрица , полученная из исходной матрицы A, заменой строк на столбцы. и . Эквивалентные преобразования. · Строки можно умножить на любое число, отличное от 0. · Можно добавить (убавить) к элементам строки соответствующие элементы другой строки, домноженные на одно и то же число. · Можно вычеркнуть нулевую строчку или столбец. · Две матрицы, названные эквивалентными, если одна получается из другой путем эквивалентных преобразований. Определитель характеризует содержание матрицы. Это многочлен, комбинирующий элементы квадратной матрицы таким образом, что его значение сохраняется при транспонировании и линейных комбинациях строк или столбцов. Вычисление определителей. Для матрицы первого порядка, значение детерминанта, равно единственному элементу этой матрицы. Для матрицы второго порядка, значение определителя вычисляется так: . Для матриц более высокого порядка, применяем подобные вичисления;
Свойства определителей. (все, что сказано относительно строк, относится и к столбцам). · Определитель основной матрицы равен определителю транспонированной матрицы. · Общий множитель в строке можно выносить за знак определителя. · Если матрицу n-го порядка, умножить на ненулевое число, то определитель будет равен произведению определителя исходной матрицы на это число в степени порядка матрицы. · Если каждый элемент в какой-то из строк определителя равен сумме 2-х слагаемых, то исходный определитель равен сумме двух определителей, в которых вместо этой строки стоят первые и вторые слагаемые соответственно, а остальные строки совпадают с исходным определителем. · Если 2 строки определителя поменять местами, то определитель поменяет знак. · Определитель с 2-я равными строками, равен 0. · Определитель с двумя пропорциональными строками, равен 0. · Определитель, содержащий нулевую строку, равен 0. · Определитель не изменится, если к какой-то его строке прибавить другую строку, умноженную на некоторое число. · Определитель верхней (нижней) треугольной матрицы равен произведению его диагональных элементов . · Определитель произведения матриц равен произведению определителей: .
Решение систем алгебраических уравнений методом Крамера. Матричный метод решения систем уравнений. В линейных алгебраических уравнениях из коэффициентов, стоящих перед неизвестным радикалом можно составить матрицу, если добавить к ней еще один столбец (составленный из значений, расположенных справа от знака равенства), то получим расширенную матрицу. Система уравнений считается совместной, если имеет минимум одно решение, только тогда, когда ранг матрицы, равен рангу расширенной матрицы. Совместная система имеет одно решение – определенная. Совместная система имеет несколько решений – неопределенная. Если решений нет система– не совместная. Метод Крамера. , где – исходный определитель матрицы, – i-ый столбец заменяем на свободные члены справа. , , , , , , , . Матричный метод. , , Ex= , , , , , ,
Миноры матрицы. Ранг матрицы. Элементарные преобразования матриц. Теорема о сохранении ранга матрицы при элементарных преобразованиях. Миноры матрицы. Минорами первого порядка являются сами элементы матрицы. Миноры второго порядка – определители, которые получаются следующим образом: выбирают любые две строки с любых двух столбцов и вычеркивают их.Из них ищут определитель второго порядка. Пример. Как оптимизировать работу по поиску миноров, отличных от нуля? 1. По определителю 2. По окаймляющим минорам 3. Метод Гаусса-Жордана (Предпочтительный) Пример. Сколько единиц – такой и ранг. Ранг матрицы. Рангом матрицыAназывают число, которое является наивысшим порядком минора матрицы, отличного от нуля. Для чего ранг: Если мы решаем СЛАУ и записываем основную матрицу для этой матрицы, окажется вычисленным ранг основной матрицы и делаем вывод: сколько строк входит в этот минор наивысшего порядка (а определитель называется базисным минором), столько и уравнений, их нужно оставить. То есть уравнения, коэффициенты которых не вошли в базисный минор, эти уравнения надо отбросить. |
|
линейная алгебра – Можете ли вы добавить несколько строк матрицы к себе?
Задавать вопрос
спросил
Изменено 6 лет, 4 месяца назад
Просмотрено 5к раз
$\begingroup$
Заранее извиняюсь, так как кажется, что это может быть один из тех вопросов, которые настолько ошеломляют и очевидны для тех, кто знает ответ, что большинство даже не думает его рассматривать. Я искал вверх и вниз информацию об операциях с элементарными строками матрицы, но ни одна из них не додумалась явно обрабатывать добавление кратного строки матрицы к самой себе.
Все они говорят, что можно прибавить кратное одной строки матрицы к другой строке, но является ли прибавление кратной строки матрицы к самой себе особым случаем? Это законно? Я полагаю, что это относительно простой вопрос, но я не смог найти подтверждения так или иначе по этой теме. 🙁
Большое спасибо за ваше время.
- линейная алгебра
- матрицы
$\endgroup$
3
$\begingroup$
Да, в контексте исключения по Гауссу (когда разрешается добавлять несколько строк к другой строке) существует исключение для добавления к одной и той же строке; вместо этого разрешено умножать строку на ненулевое число 9.0034 константа. Для исключения есть веская причина: если бы кто-то разрешил добавлять кратное количество строк к себе, можно было бы взять кратное в $-1$, умноженное на строку, и в результате строки просто заменялись бы нулем. Это не допускается, так как это заведомо необратимая операция; это в общем случае расширит набор решений рассматриваемой системы. Можно было бы разрешить добавление кратного на любой множитель $\alpha\neq-1$, но это уже подпадает под правило, разрешающее умножение на ненулевую константу (оно имеет тот же эффект, что и умножение на $1+\alpha$). Исключение $0$ в качестве коэффициента умножения легче сформулировать и понять, чем исключить $-1$ в качестве коэффициента при добавлении множителя, но только если назначением является сама строка. 9{\top}$$
, чтобы умножить $i$-ю строку на $1+\alpha$.
$\endgroup$
3
$\begingroup$
Каждый шаг исключения Гаусса можно смоделировать путем умножения матрицы на так называемую элементарную матрицу, см. здесь.
Все они говорят, что можно сложить кратную строку матрицы в другую строку, но добавляет к себе кратное значение строки матрицы представить частный случай? Это законно?
Конечно, это допустимо, добавление $i$-й строки $A$ к строке $i$ с использованием приведенного выше определения будет операцией
$$
L_{i,i}(1) А
$$
с
$$
L_{i,i}(1) = \begin{bmatrix} 1 & & & & & & & & \\ & \ddots & & & & & & & & \\ & & 2 & & & & & & \\ & & & \ ddots & & & & \\ & & & & 1 & & \\ & & & & & & & \ddots & \\ & & & & & & & & & 1\end{bmatrix}
$$
Обратите внимание, что эта элементарная матрица такая же, как $D_i(2)$, скалярная, умножающая строку на $2$.
$\endgroup$
Создание, печать, добавление столбца и среза
Дэниел Джонсон
ЧасыОбновлено
Матричная функция в R
Матричная функция в R представляет собой двумерный массив, содержащий m строк и n столбцов. Другими словами, матрица в R-программировании представляет собой комбинацию двух или более векторов с одинаковым типом данных.
Примечание: Можно создавать более двухмерных массивов с матричной функцией в R.
Как создать матрицу в R
Мы можем создать матрицу с помощью функции matrix(). Ниже приведена функция для создания матрицы в R, которая принимает три аргумента:
matrix(data, nrow, ncol, byrow = FALSE)
Аргументы:
- данные : Набор элементов, которые R разместит в строках и столбцах матрицы \
- nrow : Количество строк
- ncol : Количество столбцов
- byrow : Строки заполняются слева направо.
Мы используем `byrow = FALSE` (значения по умолчанию), если мы хотим, чтобы матрица заполнялась столбцами, т.е. значения заполнялись сверху вниз.
Давайте построим две матрицы 5×2 с последовательностью чисел от 1 до 10, одну с построкой = ИСТИНА, а другую с построкой = ЛОЖЬ, чтобы увидеть разницу.
# Построить матрицу из 5 строк, содержащих числа от 1 до 10, и byrow = TRUE matrix_a <-matrix(1:10, byrow = TRUE, nrow = 5) matrix_a
Вывод:
Вывести размер матрицы с помощью dim()
Теперь давайте напечатаем размер матрицы в R с помощью dim(). Синтаксис для печати матрицы в R с использованием dim():
# Печать размера матрицы с помощью dim() dim(matrix_a)
Вывод:
## [1] 5 2
Построить матрицу из 5 строк, содержащих числа от 1 до 10, и byrow = FALSE
# Построить матрицу из 5 строк, содержащих числа от 1 до 10 числа от 1 до 10 и по ряду = FALSE matrix_b <-matrix(1:10, byrow = FALSE, nrow = 5) matrix_b
Вывод:
Вывести размер матрицы с помощью dim()
Снова вывести размер матрицы с помощью dim(). Ниже приведен синтаксис R печати размера матрицы:
# Печать размера матрицы с помощью dim() dim(matrix_b)
Вывод:
## [1] 5 2
Примечание : Использование команды matrix_b <-matrix(1:10, byrow = FALSE, ncol = 2) будет иметь тот же эффект, что и выше .
Вы также можете создать матрицу 4×3, используя ncol. R создаст 3 столбца и заполнит строку сверху вниз. Проверьте пример
matrix_c <-matrix(1:12, byrow = FALSE, ncol = 3) matrix_c
Вывод:
## [1] [2] [3] ## [1,] 1 5 9 ## [2,] 2 6 10 ## [3,] 3 7 11 ## [4,] 4 8 12
Пример:
dim(matrix_c)
Вывод:
## [1] 4 3
Добавить столбец в матрицу с помощью cbind()
Вы можете добавить столбец в матрицу R с помощью команды cbind(). cbind() означает привязку столбца. cbind() может объединить столько матриц или столбцов, сколько указано. Например, в нашем предыдущем примере была создана матрица 5×2. Мы объединяем третий столбец и проверяем размерность 5×3
Пример:
# соединить c(1:5) с matrix_a matrix_a1 <- cbind(matrix_a, c(1:5)) # Проверить размер тусклый (matrix_a1)
Вывод:
## [1] 5 3
Пример:
matrix_a1
Вывод
] [2, 188] [#,] ## [1,] 1 2 1 ## [2,] 3 4 2 ## [3,] 5 6 3 ## [4,] 7 8 4 ## [5,] 9 10 5Пример:
Мы также можем добавить столбец в матрицу R более одного раза. Давайте посмотрим следующую последовательность чисел в матрице matrix_a2. Размерность новых матриц в R будет 4×6 с номерами от 1 до 24.
matrix_a2 <-matrix(13:24, byrow = FALSE, ncol = 3)
Вывод:
## [ 1] [2] [3] ## [1,] 13 17 21 ## [2,] 14 18 22 ## [3,] 15 19 23 ## [4,] 16 20 24
Пример:
matrix_c <-matrix(1:12, byrow = FALSE, ncol = 3) matrix_d <- cbind (matrix_a2, matrix_c) тусклый (matrix_d)
Вывод:
## [1] 4 6
ПРИМЕЧАНИЕ : Количество строк матриц в R должно быть равно для работы cbind
cbind() объединяет столбцы, rbind() добавляет строки.