§4. Метод одновременного решения двойственных задач линейного программирования

Используемые в этом пункте обозначения не следует связывать с обозначениями в игровых задачах.

Пусть требуется найти решения следующей двойственной пары задач:

Задача  Задача 

, ,

где матрица имеет строк и столбцов, , , , – -мерный вектор-столбец свободных членов.

Обратим внимание, что задача  и задача  имеют формы задач

(3.8) – (3.10) , (3.12) – (3.14) , соответственно.

Чтобы решить задачу  симплексным методом нужно ввести дополнительные не отрицательные переменные и построить следующую вспомогательную задачу

, (4.1)

где , – нулевой -мерный вектор-строка. Заметим, что матрицей основных ограничений задачи (4.1) является где – единичная матрица.

Пусть задача (4.1) решена симплексным методом и – ее решение, тогда – решение задачи . Пусть далее в заключительной симплексной таблице базис составляют векторы-столбцы матрицы . Обозначим через матрицу, столбцами которой являются эти базисные векторы. Тогда, т.к. решалась задача максимизации, оценками в заключительной симплексной таблице будут числа

(4.2)

(см. ,с.16). Обозначим . Тогда первые неравенств (4.2) запишем в виде

, (4.3)

но это означает, что вектор удовлетворяет основным ограничениям задачи . Для столбцами матрицы задачи  являются векторы , в которых единица стоит на -ом месте, а . Следовательно, неравенства (4.2) при имеют вид

. (4.4)

А это, учитывая условия (4.3), означает, что вектор является допустимым решением задачи .

Кроме того, , а это означает, что для допустимых решений и двойственных задач  и  значения линейных форм совпадают. Но тогда по лемме двойственности допустимые решения являются оптимальными планами.

Итак, в силу (4.4) решением двойственной задачи  является вектор .

§5. Метод решения матричных игр с положительной ценой сведением к решению задачи линейного программирования

На основе принципа отыскания оптимальных смешанных стратегий матричных игр с положительной ценой, сформулированного в конце третьего параграфа, и метода одновременного решения двойственной пары задач линейного программирования сформулируем теперь

А Л Г О Р И Т М 5.1.

Пусть игра Г определена матрицей , имеющей строк и столбцов.

1) Проверяется наличие седловой точки матрицы А. Если – седловая точка, то – номера чистых оптимальных стратегий первого и второго игроков, соответственно, – цена игры. Задача решена. Если седловой точки нет, следует переход к следующему пункту.

2) Ко всем элементам матрицы А прибавляется такое число , чтобы все элементы матрицы были положительными (это обеспечивает положительность цены игры с матрицей ). Если цена игры с матрицей А положительна, то можно полагать .

3) Для игры с матрицей строится задача

,

,

линейного программирования типа (3.8) – (3.10).

4) Для решения задачи пункта 3) вводятся дополнительные переменные , строится и решается симплексным методом вспомогательная задача

,

,

.

Пусть – решение и – максимальное значение линейной формы этой задачи. Тогда – решение задачи пункта 3).

5) Находится цена игры с матрицей .

6) Находится оптимальная смешанная стратегия второго игрока по формулам .

7) Находится оптимальная смешанная стратегия первого игрока по формулам , где –

оценки заключительной симплексной таблицы, полученной при решении задачи пункта 4).

8) Находится цена игры с матрицей А.

Решение задачи окончено.

Пример 5.1. Найти решение игры , заданной матрицей

.

1) Матрица не содержит элемента, который был бы одновременно

наименьшим в строке и наибольшим в столбце. Поэтому матрица не имеет седловой точки.

2) Поскольку матрица содержит несколько отрицательных элементов, то есть подозрение, что цена игры отрицательна. Поэтому прибавим ко всем элементам матрицы положительное число 2. Тогда образуется вспомогательная игра с матрицей

.

Хотя в этой матрице не все элементы положительны, но легко понять, что функция выигрыша (1.2) для любых смешанных стратегий (отличных от чистых стратегий), в том числе и для ее седловой точки будет положительной. Следовательно, цена игры положительна, и для ее решения может применяться алгоритм 5.1.

3) Запишем задачу линейного программирования

4) Введем дополнительные переменные и построим вспомогательную задачу

Построим исходную симплексную таблицу

1 1 1 0 0

Базис
	0	1	4 0 1 0
	0	1	1 0 4 0 1
		0	–1 –1 –1 0 0

Согласно правилу симплексного перехода к новому базису введем в базис вектор вместо вектора (в скобки заключен ведущий элемент). Получим новую симплексную таблицу

1 1 1 0 0

Базис
	1	1/2	1 2 0 1/2 0
	0	1/2	0 –2 –1/2 1
		1/2	0 1 –1 1/2 0

Вводя теперь вместо , получим заключительную симплексную таблицу

1 1 1 0 0

Базис
	1	1/2	1 2 0 1/2 0
	1	1/8	0 –1/2 1 –1/8 1
		5/8	0 1/2 0 3/8 1/4

Вспомогательная задача решена .

5) Находим цену вспомогательной игры с матрицей .

6) Находим .

7) Так как , т.е. , то .

8) Находим цену игры , заданной матрицей А.

Пример 5.1 решен. Подведем итоги. В этой игре второй игрок не должен пользоваться своей второй чистой стратегией, а вторую должен использовать в 4 раза чаще, чем третью, а первый игрок должен пользоваться своей первой чистой стратегией в 1,5 раза чаще, чем второй стратегией, при этом первый игрок проиграет 2/5 каких-то условных единицы. Обратим внимание, что цена игры отрицательна, и без процедуры, проделанной в соответствии со вторым пунктом алгоритма, а именно, прибавления числа 2 ко всем элементам матрицы А, применять алгоритм 5.1 нельзя.