Алгоритм решения векторной задачи

Рассматривается выпуклая векторная задача математического программирования (ВЗМП) с неоднородными (т. е. имеющие различное направление оптимизации) критериями:

opt F(X) = {max F₁(X) = {f_k(X), k = }, (5.5.1)

min F₂(X) = {f_k(X), k = }}, (5.5.2)

G(X)£ B, (5.5.3)

X³0, (5.5.4)

где X = {x_j, j = } - вектор переменных; F(X) = {f_k(X), k = } - векторный критерий, K - множество (число) индексов критерия;

F₁(X) = {f_k(x), k = } - векторный критерий максимизации, каждую компоненту которого желательно максимизировать, K₁ - множество (число) индексов критерия, K₁ Ì K, (заметим, что (5.5.1), (5.5.3), (5.5.4) представляют собой ВЗМП с однородными критериями максимизации), f_k(X), k = - вогнутые функции;

F₂(X) = {f_k(X), k = } - векторный критерий минимизации, K₂ - множество (число) индексов критерия, K₂ÌK (заметим, что (5.5.1)-(5.5.4) представляют собой ВЗМП с однородными критериями минимизации), выпуклые функции - f_к(X), k = ;

G(X) B - стандартные ограничения, имеющие знаки , =, ³..

Множество допустимых точек S, представленных ограничениями (5.5.3)-(5.5.4) является не пустым.

S = {X Î R^N|X ³ 0, G(X) £ B} ¹ Æ

и представляет собой компакт.

Алгоритм решения ВЗМП (5.5.1)-(5.5.4) с равнозначными критериями выполнен в соответствии с принципом оптимальности 1 и представлен в виде ряда шагов.

Алгоритм.

Шаг 1. Решается задача (5.5.1)-(5.5.4) по каждому критерию отдельно, т.е. для "k Î K₁ ищется максимум, а для "k Î K₂ ищется минимум. В результате решения получим:

X , f = f_k(X ), k = .

Шаг 2. Определяем наихудшую неизменяемую часть критерия f , k = . Для чего решается задача (5.5.1)-(5.5.4) для каждого критерия k = на минимум: f = min f_k(X), G(X) £ B, X ³ 0, k = .

Решается задача (5.5.1)-(5.5.4) для каждого критерия на максимум: f = max f_k(X), G(X) £ B, X ³ 0, k = .

Шаг 3. От каждого критерия отнимается его наихудшая неизменяемая часть. f_k(X) - f , k = , X Î S.

В результате получили критерии, которые при переходе от наихудшей точки к оптимальной лежат в пределах:

0 £ (f_k(X) - f ) £ (f - f ), k = ,

0 ³ (f_k(X) - f ) ³ (f - f ), k = .

Шаг 4. Выполняется стандартная нормализация критериев:

l_k(X) = (f_k(X) - f )/(f - f ), k = , X Î S, .

где l_k(X) - относительная оценка k–го критерия f_k(X), k = .

Замечание: "k Î К₁, (f_k(X) - f )>0, (f - f )>0, поэтому l_k(X)>0; "kÎК₂, (f_k(X) - f )<0, но меньше нуля и (f - f )<0, поэтому l_k(X) > 0, "k Î К₂.

В целом по задаче "k Î К относительная оценка l_k(X), k = лежит в пределах 0 £ l_k(X) £ 1, "k Î К.

Шаг 5. Построение l-задачи.

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

а) Любую точку допустимого множества XÎS можно определить набором (множеством) допустимых оценок l_k(X), k= . Определим минимальный уровень l среди множества всех относительных оценок l_k(X):

l = l_k(X), "XÎS. (5.5.5)

Полученный минимальный уровень l максимизируем по XÎS, в результате получим максиминную задачу оптимизации с нормализованными критериями:

l^o = l_k(X), G(X) £ B, X ³ 0, (5.5.6)

которая в результате решения дает максимальный уровень l^o (среди всех минимальных уровней). Эту же задачу можно представить в стандартном (однокритериальном) виде. Для этого ипользуется второй этап.

б) На втором этапе, используя взаимосвязь выражений l= l_k(X) и l£l_k(X), k= , преобразуем максиминную задачу (5.5.6) в стандартную задачу математического программирования:

l^o = max l, (5.5.7)

l - (f_k(X) - f )/(f - f ) £ 0, k = , (5.5.8)

G(X) £ B, X ³ 0. (5.5.9)

Полученную задачу назовем l-задача.

Шаг 6. Решение l-задачи.

Шаг 7. Конец.

В результате решения l-задачи получаем точку оптимума X^o и максимальную относительную оценку l^o, такую, что l^o £ l_k(X^o), k= , X^oÎS, т. е. является максимальным нижним уровнем для всех относительных оценок l_k(X^o), гарантированным результатом в относительных единицах, а в соответствии с теоремой 3, точка {X^o, l^o} оптимальна по Парето.

Определим величину каждого критерия в точке X^o из соотношения:

l_k(X^o) = (f_k(X^o) - f )/(f - f ), k= , отсюда

f_k(X^o) = f + l_k(X^o)(f - f ), k= , (5.5.10)
т.е. величина любого критерия в оптимальной точке складывается из наихудшей неизменяемой части f , k= , увеличенной на изменяемую часть критерия на допустимом множестве точек S. Причем для всех критериев увеличение осуществляется на величину не хуже максимального нижнего уровня в относительных единицах от изменяемой части критерия.

Заметим, что для критериев k = идет увеличение от f , k = на l_k(X^o)(f - f ), т.к. (f - f ) > 0, а для k = - идет уменьшение от f k = , на l_k(X^o)(f - f ), т.к. (f - f ) < 0, k = .

Алгоритм решения ВЗМП (5.5.1)-(5.5.4) с неоднородными критериями покажем на тестовом примере решения векторной задачи линейного (годового плана производственной фирмы).