Решение игровой задачи путем сведения ее к паре взаимно-двойственных задач линейного программирования

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

(2.3.1)

В платежной матрице (2.3.1) все элементы, кроме диагональных, меньше нуля, что не позволяет использовать симплекс-метод для нахождения оптимального решения после сведения матричной игры к задаче линейного программирования. Поэтому предварительно матрицу Q (2.3.1) заменим эквивалентной ей матрицей с неотрицательными элементами, для чего к каждому элементу матрицы (2.3.1) прибавим одно и то же число, равное , т.е. число, равное максимальному по модулю элементу матрицы (2.3.1). В результате получаем матрицу с неотрицательными элементами:

, (2.3.2)

в которой диагональные элементы равны и имеют максимальное значение и i ¹ j. Такая замена не изменит решения игры, изменится только ее цена (см. доказательство теоремы фон Неймана). Эквивалентная этой игре пара двойственных задач линейного программирования может быть представлена в совмещенной таблице вида

		v 1=	v 2=	…	vk =	W=
		-	-	…	-
u 1	=			…
u 2	=			…			(2.3.3)
…	…	.	.	.	.	.
uk	=			…
	Z =	-1	-1	…	-1

Решив с помощью симплекс-метода пару двойственных задач, представленных таблицей (2.3.3), получим max Z = min W, которые будут достигаться при каких-то определенных значениях . Оптимальную смешанную стратегию первого игрока можно определить из полученных оптимальных решений данной пары двойственных задач по формуле

. (2.3.4)

При этом удовлетворяет условию .

Таким образом, искомый наилучший компромиссный вектор входных сигналов относительно заданных критериев оптимальности представляет собой выпуклую линейную комбинацию из оптимальных векторов входных параметров и имеет вид:

. (2.3.5)

Контрольні запитання

1. Задачи многокритериальной оптимизации

2. Критерий выбора компромиссного решения.

3. Игровой подход.

4. Сведение игровой задачи к паре двойственных задач.

Рекомендована література: [9, 10, 13]

Тема 7.