lr12

Лабораторная работа №12.

Многокритериальные задачи. Построение множеств Парето.

Цель работы: изучение парето-эффективных множеств.

Постановка задачи: Построить множество Парето для

а) заданного множества оценок ;

б) заданного множества решений и двух критериев f₁(x), f₂(x).

1. Теоретические сведения к выполнению лабораторной работы.

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

;

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

Рассмотрим сначала множество оценок Y.

Сильная Аксиома Парето. Если для двух оценок выполняется соотношение y¹  y², то .

Аксиома Парето позволяет перейти от абстрактного отношения предпочтения к вполне конкретному и легко проверяемому отношению ≥.

Оценку y*, будем называть парето-оптимальной (в сильном смысле), если не существует такой оценки , что y y*.

Через P(Y) будем обозначать множество оптимальных оценок на Y.

Рассмотрим вопрос о геометрической интерпретации парето-оптимальных точек и построении их множества P(Y) при m=2. Прежде всего отметим, что если y¹  y², то геометрически это означает, что оценка y¹ находится в створе угла, построенного по точке y² (внутри угла или на его сторонах и не совпадает с y²):

Рис. 1. Геометрическая интерпретация отношения y¹  y².

Отсюда вытекает, что парето-оптимальная оценка – это такая оценка, что в створ построенного по ней угла, не попадают другие оценки из множества Y. Поэтому внутренняя точка множества Y не может быть парето-оптимальной: в створ угла, построенной по внутренней точке, обязательно попадают другие оценки. Таким образом, парето-оптимальная оценка – граничная точка множества оценок. При этом это не любая граничная точка, а «северо-восточная» граничная точка:

Рис. 2. Геометрическая интерпретация множества P(Y).

Если множество Y строго выпуклое, то P(Y) строится достаточно просто. В случае невыпулого множества или множества со сложной конфигурацией границы появляются проблемы. Их «создают» оценки, лежащие на одной вертикали или одной горизонтали. В соответствии с сильной аксиомой Парето из двух оценок, лежащих на одной горизонтали, «лучшей» является та, которая находится правее. Аналогично, из двух оценок, лежащих на одной вертикали, лучшей является та, которая находится выше. Поэтому парето-оптимальные в сильном смысле оценки не могут находиться на горизонтальных или вертикальных промежутках границы (точнее, внутри этих промежутков). Они могут располагаться только на концах таких промежутков (на правом конце горизонтального промежутка или верхнем конце вертикального промежутка). Примеры построения Парето-оптимальных множеств для множеств со сложной границей приведены на рис. 3.

Рис 3. Построение Парето-оптимальных множеств для множеств со сложной конфигурацией границы.

Слабая Аксиома Парето. Если для двух оценок выполняется соотношение y¹ > y², то .

Оценку y*, будем называть парето-оптимальной (в слабом смысле), если не существует такой оценки , что y> y*.

Через S(Y) будем обозначать множество парето-оптимальных оценок (в слабом смысле) на Y.

Слабая аксиома Парето отличается от сильной всего лишь одним значком: вместо отношения «больше либо равно, но не совпадает» ( ≥ ) используется отношение «больше» ( >). Однако смена операции отношения существенно влияет в ряде случаев на построение множества парето-оптимальных точек.

Рассмотрим сначала отношение y¹ > y² и его геометрическую интерпретацию. Оценка y¹ «лучше» y² в том случае, если она находится внутри угла, построенного по точке y². Она не может находиться на стороне угла, так как с точки зрения отношения «>» такие точки являются неразличимыми с y² (см. рис. 4).

Рис. 4. Геометрическая интерпретация отношения y¹ > y².

На рис. 5 приведен пример, который наглядно иллюстрирует разницу между множествами P(Y) и S(Y).

Рис. 5. Геометрическая интерпретация множеств P(Y) и S(Y).

Более сложный случай представлен на рис. 6.

Рис. 6. Различие между P(X) и S(Y) в случае множества со сложной границей.

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

Сильная Аксиома Парето. Если для двух решений выполняется соотношение f(x¹) f( x²), то .

Слабая Аксиома Парето. Если для двух решений выполняется соотношение f(x¹) >f( x²), то .

Решение x*, будем называть парето-оптимальным (в сильном смысле), если не существует такого другого решения , что f(x) f(x*).

Решение x*, будем называть парето-оптимальным (в слабом смысле), если не существует такого другого решения , что f(x)> f(x*).

Дадим геометрическую интерпретацию этим аксиомам и определениям при n=1 и m=2 (одна переменная , 2 критерия).

Вначале рассмотрим сильную аксиому. Отношение f(x¹) f(x²) выполняется только в том случае, если значение обоих критериев в точке x¹ не меньше значений критериев в точке x². Это означает, что парето-оптимальные решения не могут находиться на промежутках монотонного возрастания или убывания обоих критериев. Поэтому в примере, представленном на рис. 7 а), множество P(X)={b}, а на рисунке 7 б) - P(X)={а}.

а)

б)

Рис. 7. Парето-оптимальные множества в случае одинакового поведения критериев.

В то же время промежутки, на которых критерии ведут себя по-разному, являются подозрительными на парето-оптимальность. В простейшем случае (см. рис. 8) P(X)=X.

Рис. 8. Парето-оптимальное множества в случае разного поведения монотонных критериев.

На рис. 9 приведены примеры, когда один из критериев является монотонным, а второй - немонотонным.

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

Алгоритм построения множества P(X), если один из критериев монотонен, можно описать следующим образом. Допустим, что f₁(x) монотонно убывает.

1. По графику f₂(x) найдем подмножество значений X_в, на котором функция f₂(x) монотонно возрастает (т.е. удалим из множества X промежутки, на которых f₂(x) убывает и образует впадины). Максимальное из всех подмножеств X_в и будет парето-оптимальным множеством решений.

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

Рис. 10. Анализ точек на концах отрезков парето-оптимальных множеств.

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

Множество слабо-парето-оптимальных точек S(X) в рассматриваемых случаях совпадает или почти совпадают с P(X). Отличие только на концах отрезков. В силу свойств отношения “>” смежные точки на концах отрезков неразличимы. Поэтому S(X) содержит концы всех своих отрезков.

2. Варианты заданий к лабораторной работе

№	К заданию а)	К заданию б)
1
2
3
4
5
6

7
8
9

10
11
12

13
14
15

16
17
18
19
20
21
22
23
24
25
26
27

3. Требования к отчету по лабораторной работе. Отчет должен включать:

• титульный лист установленной формы.

• постановку задачи с конкретизированным данными.

• рисунки множеств с выделенными на них оптимальными точками по Парето.