4. Метод свертывания

При описании метода уступок и метода идеальной точки предполагалось, что заданные критерии равноправны. На практике часто приходится сталкиваться с ситуациями, в которых равноправие критериев нарушено, и у каждого из них есть «свой вес». Метод свертывания применяется для решения многокритериальных задач с критериями, разными по степени важности. Рассмотрим идею метода в условиях линейной многокритериальной задачи.

Пусть задано множество M значений переменных x₁, x₂, …, x_n с помощью системы линейных уравнений и неравенств и набор целевых линейных функций f₁, f₂, …, f_m от этих переменных: f_i = , где c_k  R, i  [1..m]. Во множестве M требуется найти такой набор значений переменных x₁, x₂, …, x_n, при котором для каждой целевой функции f_i достигалось бы максимальное значение.

Метод свертывания заключается в следующем. Лицо, принимающее решение, из доступных для него соображений назначает веса целевых функций:

w₁, w₂, …, w_m , w_i ≥ 0, i  [1..m], .

Теперь все целевые функции сворачиваются в один глобальный критерий

F = w₁f₁ + w₂f₂ +…+ w_mf_m, (1)

и исходная задача заменяется задачей с одним глобальным критерием: найти во множестве M такой набор значений переменных x₁, x₂, …, x_n, при котором глобальный критерий F достигал бы максимального значения.

Рассмотрим «технический» способ (не назначаемый ЛПР) определения весов w_i, изложенный в [23].

Сначала в области допустимых решений M системы ограничений задачи выполняется оптимизация отдельно по каждой целевой функции f_i, i  [1..m]. Затем для каждого найденного решения X_i = (x_1i, x_2i, …, x_ni) при этой однокритериальной оптимизации вычисляются значения всех целевых функций.

Обозначим через f_ip (p  [1..m]) значение целевой функции f_p для i –того решения X_i и составим таблицу (1) чисел f_ip:

	f1	…	fi	…	fm
X1	f11	…	f1i	…	f1m
…	…	…	…	…	…
Xi	fi1	…	fii	…	f1m
…	…	…	…	…	…
Xm	fm1	…	fmi	…	fmm

Таблица 1

Очевидно, в i − той строке таблицы 1 максимальным числом является f_ii.

Далее проводится нормировка найденных значений целевых функций в промежутке [0, 1] по формулам:

В результате получаем относительные значения F_ip всех целевых функций в найденных точках X_i, которые составляют таблицу 2:

	f1	…	fi	…	fm
X1	1	…	F1i	…	F1m
…	…	…	…	…	…
Xi	Fi1	…	1	…	F1m
…	…	…	…	…	…
Xm	Fm1	…	Fmi	…	1

Таблица 2

Из формулы (2) следует, что после нормировки наибольшее значение каждой целевой функции будет равно единице.

По таблице 2 вычисляются веса w_i целевых функций. Пусть _i − среднее арифметическое чисел i − того столбца, кроме единицы. Вес w_i целевой функции f_i вычисляется по формуле (3):

. (3)

Теперь проводится оптимизация по глобальному критерию (1).

Пример. Множество M допустимых значений переменных x и y задано системой неравенств:

Требуется найти во множестве M такую точку, в которой каждая из трех функций f₁, f₂ и f₃ достигают максимального значения, если

f₁ = 2x − 7y + 35, f₂ = −2x + 19y + 25, f₃ = −14x − 3y + 95.

Решение. Найдем оптимальное решение для каждой целевой функции f_i , используя пакет Maple:

> with(simplex);

> s:={2*x + y − 13 <= 0, x − 3*y + 11 >= 0, x >= 1, 2*x + 5*y − 17 >= 0};

> f1:=2*x − 7*y +35;

> maximize(f,s);

Получаем ответ: X₁ = (6,1). В этой точке maxf₁ = 40.

Аналогично находим maxf₂ = 112 в точке X₂ = (4,5) и maxf₃ =72 в точке X₃ = (1, 3).

Вычисляем в каждой из этих трех точек значения целевых функций:

	f1	f2	f3
X1	40	32	8
X2	8	112	24
X3	16	80	72

Таблица 3

Пронормируем значения функций в таблице 3 по формулам (2):

	F1	F2	f3
X1	1	0	0
X2	0	1	0,25
X3	0,25	0,6	1

Таблица 4

Вычислим средние значения элементов в каждом из столбцов таблицы 4, исключая элементы, равные единице:

Находим технические веса целевых функций по формуле (3):

,

Составляем глобальный критерий:

F = = .

Находим во множестве M точку, в которой глобальный критерий имеет максимум, используя пакет Maple:

> with(simplex);

> s:={2*x + y − 13 <= 0, x − 3*y + 11 >= 0, x >= 1, 2*x + 5*y − 17 >= 0};

> F:=(−34*x + 13*y +375)/7;

> maximize(f,s);

Получаем ответ: глобальный критерий F достигает максимального значения в точке X₀ = (1, 4).

Найдем значения целевых функций в точке X₀: f₁ = 9, f₂ = 99, f₃ = 69.

Вектор (9, 99, 69), составленный из полученных значений целевых функций, отличается от вектора утопии (40, 112, 72).

Вопросы и упражнения

1. Множество M допустимых значений переменных x и y задано системой неравенств:

Используя метод свертывания, найти во множестве M такую точку, в которой каждая из трех функций f₁, f₂ и f₃ достигает максимального значения, если f₁ = x + 2y, f₂ = −2x + 3y + 15, f₃ = 2x − 2y + 20.