Принцип слабой оптимальности по Парето

Вектор х1єХ называется слабо оптимальным по Парето решением (оптимальным по Слейтеру), если не существует вектора х1єХ, такого, что

…

Пусть xoj (i=1,m) есть оптимальные решения для обычных скалярных оптимизационных задач, каждая из которых максимизирует компоненту Fi(х) вектора F (х):

…                                                                                                 (4)

Если они являются максимальными решениями для каждой i, то считаем, что Fj(xoj) >Fi(xj) (i=1,m), где xoj — оптимальное решение задачи (4).

Положим, что Soj изображает множество решений, каждое из которых соответствует компоненту Fj, и Soj = …                                     (5)

где aj представляет допустимое количество ограничений соответствующей области по отношению к Fj. Тогда оптимальное достаточное решение это такое решение, при котором минимальный компонент (наихудший компонент) максимизируется на множестве, удовлетворяющем достаточному условию хєХ и хєSo1nSo2n…,Som. Оно может быть сформулировано как

…                                                                                                  (6)

х, z при

…                                                                                                  (7)

…                                                                                                  (8)

хєХ.                                                                                                    (9)

Здесь задача (6) – (9) неразрешима, если аj не настолько велико, что пересечение {S°j} непусто. Величины аj должны быть определены на основе значений Fj(xoj) или анализа точности. Можно доказать, что оптимальное решение задачи (6) – (9) есть оптимальное решение по Парето.

Алгоритм решения задачи имеет следующие этапы.

Шаг 1. Полагаем l=1 и решаем задачу

max z                                                                                           (10)

х, z при

Fj(x)>=z;

Fi(x)>=Fj(x)oj—aj, i=1,m; хєХ.

Вызываем исходное решение x1 и оцениваем целевую функцию F(x1).

Шаг 2. Когда хl задано, разлагаем F(хl) на удовлетворительные и неудовлетворительные компоненты. Обозначим их соответственно через Sl и Sl.

Если Sl, тогда эта задача считается неразрешимой, а если Sl ºÆ, то х1 — оптимальное, отвечающее требованиям решение. Если S <> Æ и Sl <> Æ, то для jєSl определяется аlj>0, допустимое по отношению к Fj(xl) [аlj=0 означает, что j-я целевая функция fj(x) не может принимать значение, отличное от fj (xl)].

Ш а г 3. Решаем задачу

max z

х, z

при условии

Fj(x)єz, jє Sl;

Fi(x)>=Fj(x)oj—aj, jєSl; хєХ.

Вызываем исходное решение xl+l. Если xl+1=xl, то задача будет неразрешимой; если xl+1<>xl, то полагаем 1 = 1+1 и возвращаемся к шагу 2. При этом алгоритм заканчивается.