Основных этапа многокритериальной оптимизации.

Постановка задачи критериального анализа: ЛПР имеет несколько вариантов выбора, несколько альтернатив u€U (U – мн-во возможных альтернатив, u - альтернатива), U должно содержать не меньше двух альтернатив.

Существует 2 вида принятия решения:

1. стратегическое планирование (U всегда дискретно и конечно).

2. тактическое планирование (U м.б. как дискретным, так и непрерывным).

Мнгокритериальная оптимизация - задача принятия решения, когда невозможно использовать теорию оптимизации. Она проходит в 2 этапа:

1 этап оптимизации: определение множеств эффективных векторных оценок (безусловная оптимизация). Она дает нам возможность отбросить изначально заведомо невыгодные альтернативы. При это весовые коэффициенты не учитываются. Пример: аксиома Парето.

Перед 2 этапом оптимизации критерии обычно приводят к 1 размерности и 1му диапазону измерений (нормализуют). Частные критерии считаются нормализованными, если области их изменения [Нi = 1 : m] совпадают.

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

Одна из распространенных форм нормализации:

[Она удобна тем, что все , причем min k'_i(v) = 0, max k'_i(v) = 1. Т.о., нормализованный частный критерий показывает, на какую часть всего диапазона изменений [0; 1] данный частный критерий превосходит мин значен.]

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

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

Дополнительная информация о важности критерия может задаваться отношениями, аналогичными:

k(u)Pk(v)<=> u >v (u предпочтительнее v)

k(u)Ik(v)<=> u эквивалентно v (*)

k(u)Nk(v)<=> u и v – несравнимы

, и эта дополнительная информация д.б. полной и непротиворечивой.

Полнота доп.информации требует, чтобы для любой пары частных критериев можно было выделить одно из трех допустимых отношений (*), а непротиворечивость – для любой пары критериев, не д.б. справедливы несколько отношений одновременно.

С помощью нормализации частных критериев строятся пошаговые математические алгоритмы сужения исходного множества векторных критериев до единственного решения, которое можно оценить с заданной точностью. На каждом новом шаге обычно требуется новая уточняющая информация о важности критериев, что делает эти (многошаговые) методы трудоемкими («-» - трудоемки, «+» - гибкие). Более удобными для использования на практике, но менее точными являются одношаговые методы («-» - не гибкие, «+» - легкие).

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

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

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

Имеется некоторый критерий: W¯={W1,W2,……,Wn} – скалярный набор критериев.

Существует 4 эвристических метода скалярной оптимизации:

1. метод скаляризации – строится некоторая скалярная ф-ия всех аргументов:

W0=f (W1,W2,……,Wn)

[Простой пример – взвешенная сумма: W0'= 1/n∑αiWi (∑ - по i = 1 до n)

Скользящая сумма ∑αi=1 (∑ - по i=1 до n)]

Критерии д.б. предварительно нормализованы.

Каждому критерию присваивается весовой коэф-т (по важности – чем важнее критерий, тем выше вес.коэффициент. Сумма весовых коэффициентов равна 1).

2. Метод главного критерия – предварительный этап – упорядочивание критериев по важности (и в последующих методах). Задача сводится к скалярной – решаем задачу только для самого важного критерия, а остальные используются как ограничения.

W1→max (max-ем самый важный критерий )

W2≤C2

W3≤C3

…

Wn≤Cn

При определении const-ты исходят из оптимальных значений критериев.

3. Методы уступок (компромисов) – применяется чаще всего.

а) На первом шаге оптимизируем только 1ый критерий: W1→max=>W1*=>∆W1

Затем назначаем уступку ∆W1 по первому критерию.

б) оптимизируем второй критерий, (рассматривая 1ый), который будет меняться в интервале:

W2→max=>W2=>∆W2

W*1-∆W1≤W1≤W*1

Рассматриваем 2ой критерий при ограничении 1го критерия.

Получаем W2 и назначаем уступку (W2=>∆W2)

в) W3→max

W*1-∆W1≤W1≤W*1

W*2-∆W2≤W2≤W*2

…

Варианты этого метода:1) строится пр-во критерия – в нем строится утопическая точка, у кот. координаты имеют оптимальное значения;2) вводится метрика в этом пр-ве китериев (напр., *); 3) наилучшая точка определяется по min-му расстоянию до утопической точки W¯*.

4. Метод последовательной оптимизации (группу критериев оптимизируют поочередно, если получили не единственное решение, то то на след. iаге ищут max 2-го критерия и т.д. Для всех альтернатив по 1му критерию):

а) W1→max=>{a1,a2,..}=A1 решение оказалось не единственным.

б) W2→max=>A2 ai€A1

Если опять содержит не единственный элемент, то переходим к 3-му шагу:

в) W3→max ai€A2

….

Принципиальная разница – по этому методу нельзя учитывать все критерии («оправдание» - они менее важные).

Аксиома Парето и эффективные варианты. Определение множества Парето в дискретном и непрерывном случаях

Есть векторный критерий, который представляет собой мн-во частных критериев K={K₁,…,Kn}. Есть мн-во альтернатив: U={u,v,t,s}. Каждый критерий принимает свое значение при каждой из альтернатив.

Хотим, чтобы ki →max.

Варианты V и S – доминируемые: k(u)Pk(v); k(u)Pk(s).

Варианты U и T – несравнимые: k(u)Nk(t).

Т.е. если вариант имеет абсолютный max по к.-л. из показателей, то он не м.б. доминирован.

Альтернатива эффективная, если она не хуже др. альтернатив по каждому из критериев и лучше хотя бы по 1 из них. Альтернативы, которые не доминируют друг друга образуют множество эффективных альтернатив (Эджворта-Парето) H⁰. Их оценки образуют множество эффективных оценок V.

Аксиома Парето: пусть даны 2 векторные оценки K(U)={K₁(U),…,Kn(U)} и K(V)={K₁(V),…,Kn(V)} . Альтернатива K(u) предпочтительнее K(v), если каждый из показателей 1й оценки не хуже соответствующего показателя 2й оценки, а для какого-то он лучше.

k(u)Pk(v): сущ-ет i=1..m: для всех j≠i Kj(u) I Kj(v) и Ki(u) P Ki(v).

[Аксиома Парето: для любого векторного критерия k(u) из любого набора альтернатив u и для любых 2х оценок выполняется одно из трех отношений P, I, N.

k(u)Pk(v) - u предпочтительнее v; k(u)Ik(v) - u эквивалентно v; k(u)Nk(v) - u и v – несравнимы]

Анализ на доминирование – 1 этап многокрит. оптимизации (уменьшает мн-во альтернатив).

Определение множества Парето (св-во – все оптимальные точки обязательно будут на границе)