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

Общая схема решения

Основной принцип решения задачи многокритериальной оптимизации с помощью теоретико-игрового подхода состоит в поиске компромиссного вектора X ₀ в следующем виде:

, (2.2.1)

где – вектор, оптимальный для i -го критерия, l _i – весовые коэффициенты.

Можно выделить следующую последовательность шагов решения задачи.

1. Решаем k задач линейного программирования (с помощью симплекс-метода), в которых имеется по одной функции цели и общая область ограничения. Таким образом, получаем k оптимальных векторов (для каждого критерия). Подробнее решение задач линейного программирования с помощью симплекс-метода рассмотрено в [2, 5].

Примечание. Если в системе ограничений имеются ораничения-равенства, то при решении задачи оптимизации с помощью симплекс-метода сначала требуется исключить все 0-строки.

2. Найдем меру неоптимальности каждого вектора X*_i для остальных целевых функций:

(2.2.2)

где C_j ‑ вектор коэффициентов j-го критерия,
X^*_i – вектор, оптимальный для i-го критерия. Таким образом, q_ij – мера неоптимальности вектора для j -го критерия. Например, мера неоптимальности вектора для 2-го критерия

где ,

3. Сформируем квадратную матрицу, строки которой соответствуют k оптимальным векторам X*_i , а столбцы ‑ k целевым функциям C_jX ®ext .

Теперь сформулируем задачу в виде игровой. В качестве игрока P₁ выберем совокупность оптимальных векторов X*_i , а в качестве игрока P2 – совокупность критериев оптимальности Z_j . Тогда матрица (2.2.3) (с обратным знаком элементов) может рассматриваться как платежная матрица прямоугольной (матричной) игры двух партнеров X* и Z с нулевой суммой, которая определена множеством стратегий X* ={ X* ₁, …, X*_k } первого игрока и множеством стратегий Z ={ C ₁ X, …, C_kX } второго игрока. Элементы платежной матрицы должны иметь отрицательные знаки, так как они имеют смысл меры неоптимальности вектора, оптимального для какого-то из критериев, полученной при его подстановке в другой критерий, т.е. в игровой постановке – проигрыш первого игрока.

Тогда задача формулируется следующим образом: необходимо найти смешанную стратегию первого игрока, она и будет представлять искомые весовые коэффициенты l _i для компромиссного вектора X ₀.

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

При составлении платежной матрицы 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)