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

Основной принцип решения задачи многокритериальной оптимизации с помощью теоретико-игрового подхода состоит в поиске компромиссного вектора 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 ₀.

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