Алгоритм 2. Решение задач векторной оптимизации с заданным приоритетом критерия

(Ю.К. Машунин [29])

Рассматривается векторная задача (9.1.1)-(9.1.4).

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

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

Алгоритм решения представим для ВЗМП с приоритетом q е К критерия.

Под решением понимаем получение оптимальной точки из области приоритета критерия в соответствии с аксиомами 2, 3 и заданным вектором приоритетов.

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

В предлагаемой методике за лицом, принимающим решения, оставляют выбор приоритетов критерия, а процедуры получения оптимального решения при равнозначных критериях, расчет пределов изменения компонент вектора приоритетов и решения q-задачи осуществляют на ЭВМ, то есть выполняется человеко-машинная процедура принятия решений по моделям, представленным векторной задачей математического программирования.

Выбор точки Х° G S осуществляется по двум схемам:

• • вектор приоритетов PjJ,k = 1,К, Vq G К задается, и находится соответствующая точка оптимума Х°, у которой величина f(X°) приближается к заданной f ° (см. теоремы 3, 4, 5);
• • по заданной величине целевой функции f ° ищется вектор приоритетов Р J , k = 1, К, q е К и определяется Х° е S (см. теорему 6).

Алгоритм 2.

Шаг 1. Решается ВЗМП с равнозначными критериями (см. алгоритм 7).

В результате решения получим:

• точки оптимума X *, k = 1, К и величины целевых функций в этих точках f*, к = 1,К, которые представляют собой границу множества Парето;

• • наихудшую неизменяемую часть критерия f°, k = 1, К;
• • при решении максиминной задачи и построенной на ее основе Х-задачи получили Х° - точку оптимума решения ВЗМП при равнозначных критериях и максимальную оценку Х°, которая является гарантированным уровнем для всех критериев в относительных единицах.

В каждой точке X*, к = 1,К вычислим величины всех критериев q= Гк:

{Г(х;),ч=Гк},к=Гк, (11.2.1)

которые показывают величины каждого из q е К критериев при переходе от одной оптимальной точки к другой.

В точке Х° вычислим величины критериев f_k(X°) и относительных оценок Х_к(Х°), к = 1,К, которые удовлетворяют неравенству Х° < X_k(X°), k = 1, К, Х° G S. В ней все критерии больше или равны Х°. В других точках X е S⁰ меньший из критериев в относительных единицах X = min X, (X) всегда меньше Х°.

keK ^k

Из (11.2.1) вычислим величины относительных оценок в точках оптимума:

{(х; = (f (XJ) - Р)/(Г - Р), q = Гк}, к = 1Л • (11.2.2)

Матрица (11.2.2) показывает величины всех критериев в относительных единицах на границе множества Парето.

Эта информация и является основой для дальнейшего изучения структуры множества Парето. На ее основе выбирается приоритетный критерий q G К.

Запоминаются данные Х-задачи (11.1.2).

Шаг 2. Определяются пределы изменения величины приоритета критерия q G К, для чего в точках Х° и X* определяются приоритеты критерия qeK.no отношению к другим критериям:

Р2(х») = к(х»)/(х«)> р;(х;)=(х;)/(х;),к=кк

и устанавливаются пределы изменения задаваемого вектора приоритетов

Шаг 3. Полученные результаты выдаются на печать (на дисплей): fj, f_k, (11.2.4)

f,(X«), f₂(X»),..., f_k(X«),

f,(xp, f₂(x;),..„ f_k(xp,

(XJ), (XJ),..., (XJ)

и пределы изменения задаваемого вектора приоритетов (11.2.3).

Эти результаты и служат основой для принятия решения.

Шаг 4. Лицо, принимающее решения, проводит анализ результатов решения ВЗМП при равнозначных критериях (11.2.4). Выявляет наиболее противоречивые критерии. Предполагается, что у ЛПР имеется представление об приоритетном критерии в виде его числовой величины f. Он сравнивает эту величину с показателями по q-му критерию f *, f (Х°) (на первой итерации расчета) или результатами решения на шаге 6 (на последующих итерациях расчета).

Если f (Х°) отвечает требованиям ЛПР, задача решена и следует переход к шагу 7. Если нет, выбирается новое значение коэффициентов задаваемого вектора приоритетов PJ, k = l,K,Vqe К из (11.2.3) таким образом, чтобы вновь задаваемый вектор приоритетов был больше вектора приоритетов на предыдущей итерации в точке оптимума X®.

Pj>Pj(X°),k = kK,X°G S°cS. (11.2.5)

Шаг 5. В данные Х-задачи (11.1.2) вводим заданный вектор приоритетов (11.2.5), в результате получим Х-задачу с приоритетами:

Х° = max X,

X-PjX_k(X)<0,k = Гк,

G(X)0 (11.2.6)

Шаг 6. Решение Х-задачи (11.2.6).

Результаты решения:

• • X® - точка оптимума, X® - максимальная относительная оценка, такая, что X® < Р jjX_k(X®), k = 1,К, Vq е К;
• • f_k(X®), к = 1,К - величины всех критериев;
• • Х_к(Х°), к = 1,К - величины всех относительных оценок;
• • Р J(X®), k = 1, К - вектор приоритета q-ro критерия над другими критериями.

Переход к шагу 3.

Шаг 7. Конец.

В результате решения получим:

Х° - точку оптимума и максимальную относительную оценку, такую, что Х°< Р^Х_к(Х°), к = 1,К, Vq е К, где вектор приоритетов PJ, к = 1,К соответствует заданным понятиям ЛПР о приоритете q-ro критерия над остальными.

Предполагается, что в данном алгоритме каждый шаг выполняется на ЭВМ, а величины компонент вектора приоритетов задает ЛПР, при этом на шаге 4 производится сравнение полученной точки X® и максимальной X * по величине q-й целевой функции. (Понятно, что лучше точек X® вгХ* не может быть получено, то есть они оптимальны по Парето.)

Тестовые примеры см. в [58].