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

Многокритериальная оптимизация или программирование — это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.

Задача многокритериальной оптимизации формулируется следующим образом:^[3]

где это () целевых функций. Векторы решений относятся к непустой области определения .

Задача многокритериальной оптимизации состоит в поиске вектора целевых переменных, удовлетворяющего наложенным ограничениям и оптимизирующего векторную функцию, элементы которой соответствуют целевым функциям. Эти функции образуют математическое описание критерия удовлетворительности и, как правило, взаимно конфликтуют. Отсюда, «оптимизировать» означает найти такое решение, при котором значение целевых функций были бы приемлемыми для постановщика задачи.

Рассмотрим один из методов, использующий множество Парето - метод идеальной точки.

Пусть у нас есть некоторое множество е, каждая точка которого описывается двумя функциям U=Ф(х;у) и V=Ψ(х;у) (U и V - средние выигрыши игроков А и В соответственно, а х и у - вероятности выбора стратегий для получения этого выигрыша).

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

Точка, в которой функции U и V достигают своих максимальных значений, называется точкой утопии.

Поэтому строится множество Парето и на нем ищется точка, ближайшая к точке утопии - идеальная точка (см. рис.).

Значения функций U и V в идеальной точке и есть оптимальные средние выигрыши для каждого игрока.

Пусть Н_A(р, q) и Нв (р, q) — средние выигрыши игроков А и В с платежными матрицами

Ситуация (p*q*) в биматричной игре А и В называется оптимальной по Парето, если из того, что

вытекают равенства: Р =Р*, q=q*.

20. Принятие решений по многим критериям: Метод последовательных уступок

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

СППР находит = , где -значение логической функции по самой важной характеристике, ее индекс i=1, j- номер альтернативы.

Руководитель определяет величину уступки

СППР в пределах уступки находит =

Если таких вариантов нет – руководитель увеличивает уступку и в ее пределах СППР выбирает вариант, имеющий максимум по третьей логической функции и.т.д до полного перебора всех .

Такой способ построения компромиссного решения имеет то преимущество, что руководитель имеет возможность наглядно видеть цену (уступки) по каждому критерию.

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

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

1- Критерии ранжируются в порядке важности;

2- Находим max первого показателя;

3- Назначается уступка

4- Отбрасываются «невошедшие» альтернативы;

5- Находим max по 2-ому критерии;

6- Уступка

Полученное оптимальное решение обеспечивает значение показателей эффективности в пределах величин заданных уступок.

21. Принятие решений по многим критериям: Парето оптимальное решение

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

Рассмотрим отношение ≥ (>) между оценками х, у ϵ Х: х≥ у (х>у), если Ui(х)>Ui(у) (Ui (х)>Ui(у)) для i= 1,n. Здесь Ui(x) - функция полезности (предпочтения). Оценка х° ϵ X называется максимальной по ≥ (по >) относительно X, если не существует оценки х ϵ Х такой, что х ≥ х°(х > х°). Оценка максимальная по ≥ называется эффективной, а также Парето-оптимальной. То есть, вектор х ϵ X Парето-оптимален тогда и только тогда, если не существует другого х ϵ X такого, что Ui (х) ≥ Ui (х*) для i= 1,n и строгое неравенство Uj (х) > Uj (х*) выполняется, хотя бы для одного j.

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

Оценка максимальная по > называется слабо эффективной, а также слабо оптимальной по Парето или оптимальной по Слейтеру. Множество всех таких оценок на X называется слабо эффективным.

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

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

В табл. представлены экономическая и технологическая эф­фективности различных рассмотренных в [9.4] методов воздействия на пласт с целью повышения его нефтеотдачи.

№	Метод	Себестои	Уде льн.	Прирост	Конечная
	воздейст	мость 1м	Кап. Затра-	нефтеотдачи	нефтеотдача
	вия	доп. добыт, нефти, долл. США	ты, тыс. долл. США На (м3 /сут.)	%	%
	Горение	63- 157	50-157	10-30	45-50
	Пар	63-119	50-157	15-35	45-50
	Нагнетание С02	63 - 189	63-157	8-20	55-60
	Поверхно­стно-активные вещества (ПАВ)	126-314	94-189	12-30	45-50
	Полимеры	63 - 157	63 - 189	2-10	45-50

Здесь неопределенность выражается разницей в максимальном и минимальном эффекте в зависимости от применяемого метода воз­действия.

Будем сравнивать методы воздействия на пласт по четырем по­казателям, показанным в табл. 9.6. При нахождении величины aij показатели можно сравнивать по средним значениям или по положению интервала значений на числовой оси, считая, например, что показатель "себестоимость 1 м " в интервале 63-119, лучше этого же показателя в интервале 63-157. Для сравнения методов воздействия СППР строит табл. 9.7, не показывая ее руководителям.

Таблица 9.7

№

В соответствии с табл. 9.7 лучшими методами (1 ранга) оказа­лись "пар" и "нагнетание С0₂". Вычеркивая столбцы и строки KeKs2 и 3, получаем табл. 9.8.

Таблица 9.8

№

В соответствии с табл. 9.8 методами второго ранга оказались «горение» и «поверхностно-активные вещества». Наконец, самым худшим методом (3 ранга) оказались «полимеры».

В результате ранжирования по Парето система высвечивает на дисплее табл. 9.9.

Таблица 9.9

Ранг	Метод воздействия на пласт
	Пар
	Нагнетание СОг
	Горение
	Поверхностно-активные вещества
	Полимеры

Исходя из этих оценок, руководитель выбирает метод воздейст­вия на пласт.

22. Принятие решений по многим критериям: Гарантированные достоинства и недостатки.

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

Достоинства и недостатки варианта по каждой характеристике определяются как взвешенная разность логических функций. Исходными данными является таблица μij —логических функций характеристик.

Порядок расчета по данному правилу состоит в следующем:

• для каждого варианта определяются взвешенные разности логических функций по каждой характеристике:

• если разность положительна, то речь идет о достоинстве варианта по данной характеристике. Если разность отрицательна, то речь идет о недостатках варианта по данной характеристике.

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

Достоинства варианта j по сравнению с вариантом к по i-ой характеристике:

Недостатки варианта j по сравнению с вариантом к по i-ой характеристике:

1- Попарное сравнение альтернатив. Установление достоинств с флеш-недостатков по каждому критерию, как разница их оценок.

2- Находится сумма достоинств с флеш-недостаток по каждому критерию для каждой альтернативы.

Лучшей является альтернатива с наибольшей разницей суммарных достоинств и недостатков (наибольшие достоинства и немаксимальные недостатки)

23. Принятие решений по многим критериям: Правило Борда.

Согласно этой процедуре подсчитывается, по скольким парамет­рам данное предложение превосходит все другие, результаты сумми­руются. Лучшей считается предложение, набравшее большую сумму. Эта процедура около двадцати лет применялась при выборах акаде­миков во французской академии наук.

Формально процедуру Борда можно записать следующим обра­зом.

Всем x A (А - множество предложений) припишем значения r_i (x) определяемым по правилу:

r_i (x) = {b A: Pi (x) < Pi(b)+ε_i }, где b - предложения, у которых значение i-го параметра P_i(b) лучше значения P_i(x) - i-го параметра предложения x, s_i - характеристика «чувствительности».

Сумма этих значений образует так называемую шкалу альтерна­тив Борда:

r(x) =

i

Поясним правило примером. Пусть требуется выбрать двигатель для некоторого насоса. Характеристики двигателей показаны в таблице

Параметры	Название фирм
	А	B	С	D
Мощность двигателя
Расход горючего
Вес двигателя

По правилу Борда для выбора лучшего двигателя надо использо­вать следующий алгоритм:

• для каждого двигателя подсчитать число параметров, по ко­торым он превосходит остальные двигатели, т.е. определить величи­ну r(x);

• сравнить значения r(x) всех двигателей;

• лучшим считается двигатель, набравший большую сумму.

В нашем примере при допущении ε = 0.00 значения r_i(x) и r(x) показаны в табл. 9.2. По табл. 9.2 лучшим двигателем оказался дви­гатель фирмы A.

24. Принятие решений по многим критериям: Принцип Беллмана-Заде

Многокритериальная оптимизация или программирование — это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.

Задача многокритериальной оптимизации формулируется следующим образом:^[3]

где это () целевых функций. Векторы решений относятся к непустой области определения .

Задача многокритериальной оптимизации состоит в поиске вектора целевых переменных, удовлетворяющего наложенным ограничениям и оптимизирующего векторную функцию, элементы которой соответствуют целевым функциям. Эти функции образуют математическое описание критерия удовлетворительности и, как правило, взаимно конфликтуют. Отсюда, «оптимизировать» означает найти такое решение, при котором значение целевых функций были бы приемлемыми для постановщика задачи.

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

принятие решения по принципу Беллмана-Заде

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