лекции, учебные пособия / конспект лекций / Lekcii / Лекция 3 (Шарин А

Лекция 3. Шарин А.

Многокритериальная оптимизация.

Функция полезности F(a).

Первым функцию полезности ввел Леонтьев (США).

Функция полезности – это числовая функция, определяемая на множестве альтернатив и такая, что выполняется следующее условие:

Если одна альтернатива лучше другой, то функция полезности от этой альтернативы должна быть больше, чем от другой альтернативы, т.е. она дает возможность численно сопоставить некоторые альтернативы:

Если Ai и Aj эквивалентны, то их функции равны

Ai~Aj F(Ai)=F(Aj) для любого Aj, принадлежащего А

Ai>Aj F(Ai)>F(Aj) (не сравнимы = эквивалентны)

Для любого Ai и Aj, принадлежащих А таких, что:

Ai>Aj Aj>Ai Aj~Ai

На множестве альтернатив должно выполняться бинарное отношение транзитивности.

Вид функции полезности.

Рассмотрим на некоторых примерах, как выразить полезность.

1. Разные частоты передачи Ethernet – как они отражаются на полезности.

2. Разработка кластерной RAID – системы.

Зависимость полезности от частоты обмена:

3. Освещенность на рабочем месте:

Для аппроксимации используется такое понятие, как кривая безразличия.

Кривая безразличия - если х₁~х₂ , то они лежат на одной кривой безразличия. Если же х₃ более предпочтительно, чем х₁, то х₃ лежит на кривой, соответствующей более предпочтительной альтернативы.

Хс - решение

Хс принадлежит области решений такой, что: для любого Х принадлежащего области решений Хс>Х.

2 функции полезности V₁ и V₂ (V₁~V₂) стратегически эквивалентны, если они имеют одни и те же кривые безразличия. Если нас есть любая монотонно возрастающая функция Т, то выполняется следующая закономерность:

T(V1)=~V2

T – преобразование, выполняемое над V₁

Задачи векторной (многокритериальной) оптимизации.

Возникает:

• Если много целей

• Если много объектов, каждый из которых оценивается по своим параметрам (например, построение корпоративной сети, каждый этап построения которой оценивается по своим параметрам)

• Если объект функционирует в различных условиях, в каждых из которых свои требования (например, Notebook, который работает и от сети, и на батарее)

• Если система многофункциональна

• Если система циклически выполняет различные задачи

Трудности:

• Противоречия между критериями

• Выбор принципа оптимальности

• Учет приоритетов различных критериев

• Различные критерии измеряются в различных единицах, которые трудно согласовать

Чтобы согласовать различные единицы измерения, надо произвести нормирование:

V – значение параметра

Сq^h – нормированное идеальное значение параметра

Т.е. берется некоторое значение и делится на идеальное значение. Это получается безразмерная величина.

Три варианта нормировки:

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

2. В качестве нормирующего значения выбирается максимальное значение показателя:

Е1/maxE или E1/(maxE–minE)

А вообще каждый как хочет, так и нормирует!

Сопоставление по важности: КОЭФФИЦИЕНТ ЗАМЕЩЕНИЯ.

Есть 2 параметра х и у. Если у увеличить на ∆, то на сколько можно уменьшить х, чтобы это компенсировать?

λ – предельный коэф. замещения (характеризует готовность уступки по одному параметру ради выигрыша в другом).

Эффективность решения:

A^'_x=(x^’₁, x^’₂, x^’_m) x^’≥x^”,если для любого i (x^'_i≥x^”_i) Λ (существует i x^’_i>x^”_i)

A^”_x=(x^”₁, x^”₂, x^”_m)

Доминирование по Парето

Если для некоторой точки у0 принадлежит У не существует более предпочтительного решения по Парето, то это решение называется эффективным или Парето - оптимальным решением.

Если для любого i (x^'_i ≥x^”_i), то такое решение называют слабоэффективным решением многокритериальной задачи или решением оптимальности по Слейтеру. Любой исход не может быть улучшен сразу по всем критериям.

Примеры оптимальной точки:

при переходе 5-1, 1-2, 3-4, 4-5 улучшается только один критерий. При 2-3 эти решения не доминируют по Парето, т.к. один параметр лучше, а др. хуже.

{1,2,3,4} - слабоэффективное решение, {2,3} – эффективное решение

ABCD – S – решение

BC – Р - решение

5