Выбор точки из множества Парето в ВЗМП

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

Алгоритм 3. Выбор точки из множества Парето

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

Шаг 1. Аналогично шагу 1 алгоритма 2.

Шаг 2. Указывается приоритетный критерий (обозначим его q G К).

После решения ВЗМП при равнозначных критериях (см. алгоритм 7) получена его максимальная величина Г с соответствующей точкой оптимума X * и величина f (Х°), полученная при равнозначных критериях, то есть f (X) следует выбирать в заданных пределах:

f (Х°) < f (X) < f", q 6 К. (11.3.1)

Эти данные сообщают ЛПР (выдаются на дисплей). Кроме того, вычисляются и выдаются на дисплей значения других критериев в точках Х°, X *:

’ q

f_k(X»)>f_k(X)>f_k(X*),k= l,K,qe К,

(11.3.2)

с тем чтобы ЛПР знал, насколько ухудшаются остальные показатели (критерии).

Дополнительно вычислим:

• относительные оценки критериев в точках X ”, X*, для чего из (11.3.1), (11.3.2) вычтем f® и результат разделим на (f* - f’), к= Гк,

X(X»)q(X)=l,qe К, (11.3.3)

Х_к(Х°) > Х_к(Х) > Х_к(Х*), к = , q К;

• вычислим вектор приоритетов q-ro критерия над остальными критериями k = 1, К в точках Х°, X *, аналогично шагу 2 алгоритма 2.

Шаг 3. ЛПР, анализируя приоритетный критерий, указывает его числовую величину f, которую желательно получить из соотношения (11.3.1), то есть оперирует с критериями, измеренными в натуральных единицах.

Шаг 4. Вычисляется относительная оценка X_q = (f - f °)/(f * - f_q), qe К, которая лежит в пределах (11.3.3).

Шаг 5. Предполагая линейный характер изменения критерия f(X) в (11.3.1) и, соответственно, относительной оценки X_q(X) в

(11.3.3), вычислим коэффициент пропорциональности между X_q(X°), X_q, X_q(X_q), которые назовем р, р*:

Р = (-(Х°))/(1 -(Х°)), qe К, р* = (X (Хр - ))/(1 - Х(Х»)), q е К,

взаимосвязь их очевидна р = 1 - р*.

Шаг 6. Предполагаялинейный характер изменения вектора приоритетов Р?(Х), к = 1,К в (11.2.3), вычислим его для X, используя полученные коэффициенты пропорциональности р, р*.

р; = р 2 (х°) + Р(Р J (X J) - Р 2 (х°)), к = Гк, q е к. (11 .з.4)

Шаг 7. Построение Х-задачи с приоритетом q-ro критерия, аналогично (11.2.6).

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

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

• точку оптимума Х° = {х®, j = 1, N } и максимальную относительную оценку Х° такую, что Х° < Р ? (Х°)Х_к(Х°), к = 1, К;

• величины целевых функций f (Х°), к = 1,К и относительных оценок X_k(X°), k = 1, К.

Величина f_k(X°), q G К обычно не равна заданной f_q. Ошибка выбора f определяется ошибкой линейной аппроксимации действительного изменения относительных оценок X_k(X), к = 1,К и вектора приоритетов PJ(X), k = l,K,qe К, выполненной на шагах 5 и 6.

Если ошибка Af = |f (Х°) - f | меньше заданной Af, то переход к шагу 10. Если Af > Af, выполняется следующий шаг.

Шаг 9. В точке Х° определяется вектор приоритетов критерия qe К.

Р’(Х») = X_q(X°)/X_k(X°), к = и, q 6 К.

Строится новый вектор приоритетов:

Pkw ⁼ (P_k + P_k(X°))/2, k = fK, q Хе К.

Переход к шагу 7. При этом Х-задача строится с новым вектором приоритетов PJ_w,k = 1, К, q е К вместо Р k = 1, К, q е К.

Шаг 10. Будет ли решаться ВЗМП для другой величины приоритетного критерия? Если да, то переход к шагу 3, если нет, выполняется следующий шаг.

Шаг И. Будет ли решаться ВЗМП с другим приоритетным критерием? Если да, то переход к шагу 2, иначе следующий шаг.

Шаг 12. Конец.

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

X⁰⁰ - точку оптимума и Х° - максимальную относительную оценку, такую, что Х° < Р jX_k(X⁰⁰), k = 1, К, q 6 К, где вектор приоритетов Р?, к = 1,К соответствует требованиям ЛПР о приоритете qe К критерия.

Предполагается, что шаги 1, 4-9 выполняются на ЭВМ, а шаги 2, 3, 10, 11 - ЛПР (пользователем), который ведет анализ одного из К критериев в естественных (ему понятных) единицах. ЛПР не обязательно знать об относительных единицах Х_к(Х), о приоритетах критерия Р J (X), к = 1,К. Они вычисляются автоматически, а на дисплей выдаются только получившаяся величина q-ro критерия и соответствующая точка оптимума X⁰⁰.

Таким образом, впервые предложен метод выбора из множества Парето любой точки, которая определена заранее заданной величиной приоритетного критерия. Точность выбора определена заранее заданной ошибкой.

Пример выбора точки из множества Парето

Иллюстрацию изложенного алгоритма покажем на линейной ВЗМП, текст которой приведен в примере 1 (с. 318).

Пример 2.

Шаг 1. Решается ВЗМП (11.1.4)—(11.1.5) при равнозначных критериях. Результаты решения приведены в примере 2.

Сравнивая относительные оценки в точке Х°, видим, что наиболее противоречивыми критериями (см. теорему 3) являются 1,2 и 5.

Шаг 2. В качестве приоритетного выберем второй критерий. Об этом сообщается с дисплея. ЭВМ обрабатывает те данные, которые связаны со вторым критерием, и выдает на дисплей:

f_k(xp < f_k(X) < f_k(X°), (хр < (Х) < (Х«);

• 55900 < f,(X) < 57340, 0.3834 < (Х) < 0.4181;
• 197260 > f₂(X) > 134850, 1.0 > (Х) > 0.4181;
• 50800 > f₃(X) > 40800, 1.0 > (Х) > 0.5656;
• 50250 < f₄(X) < 55360, 0.318 < %„(Х) < 0.4295;
• 2050 > f₅(X) > 1666, 0.4810 < (Х) <0.4181;
• 5025 < f₆(X) < 5536, 0.682 < (Х) < 0.5704.

Эти данные и являются основной информацией для ЛПР.

Из второго столбца определяются пределы вектора приоритета P²_k(X) = X₂(X)/(X),k= С6:

P²(X°)2(X)2(XJ),k= ЦХ

Шаг 3. Пусть ЛПР указал желаемую величину второго критерия, равную f₂ = 175200.

Шаг 4. = (f₂ - f°)/(f; - f°) = 0.888.

Шаг 5. р = (Х₂ - (Х°))/(1 - (Х⁰)) = 0.8077.

Шаг 6. Р²Р° = {р² = 2.29, р² = 1.0, р² = 0.95, р² = 2.72, р² = 0.8х10’⁷, р^= 1.325}.

Шаг 7. Построение Х-задачи с Р², к = 1,6.

Шаг 8. Решение Х-задачи. В результате решения получаем:

= 0.965, Х° = {_Х1 = 28.68, х₂ = 0, х₃ = 376.5},

f/X⁰) = 57340, f₂(X°) = 137850, f₃(X°) = 40800,

f₄(X°) = 5536, f₅(X°) = 1666, f₆(X°) = 5535.

Шаг 9. Ошибка выбора Af ~ 20%.

На последующих итерациях (шаг 9) она снижается до 9%.

Шаги 10, 11 выполняются по мере необходимости.

Шаг 12. Конец.

Выводы по методам векторной оптимизации

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

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