Множество Парето

Рассмотрим на плоскости (U, V) произвольное множество Ω (рис. 1).

Каждая точка плоскости обладает одним из следующих трех свойств:

1) все точки, ближайшие к ней, принадлежат множеству Ω (такая точка

называется внутренней точкой множества Ω);

2) все точки, ближайшие к ней, множеству Ω не принадлежат (такая точка называется внешней точкой по отношению к множеству Ω);

3) сколь угодно близко от нее расположены как точки множества Ω, так и точки, множеству Ω не принадлежащие (такие точки называются граничными точками множества Ω). Множество всех граничных точек множества называется его границей, которая обозначается ∂ Ω.

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

Пусть М — произвольная точка множества Ω, внутренняя или граничная, и U и V— ее координаты. Пытаясь ответить на вопрос: можно ли, оставаясь во множестве Ω, переместиться из точки М в близкую точку так, чтобы при этом одновременно увеличились обе координаты, все точки множества Ω разобьем на три класса.

1. К первому классу относятся точки, которые, оставаясь во множестве Ω, можно сдвинуть так, чтобы одновременно увеличились обе координаты (в этот класс попадают все внутренние точки множества Ω и часть его граничных точек, см. рис. 2а, 2б).

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

3. В третий класс попадут граничные точки, перемещение которых по множеству ∂Ω, уменьшает одну из координат при одновременном увеличении другой (дуга BD границы ∂Ω, см. рис. 3).

Множество точек третьего класса принято называть границей (множеством) Парето данного множества Q (выделено на рис. 4).

На рис. 5 жирной линией указаны границы Парето некоторых простейших множеств.

Укажем простое геометрическое правило, посредством которого можно выделять из заданного плоского множества его границу Парето.

Рассмотрим пробный прямой угол, стороны которого сонаправлены

координатным осям U и V (рис. 6).

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

Совокупность всех таких точек и будет искомой границей Парето для множества Q.

Замечание. Границу Парето множества Q можно определить и в пространстве Rn .

Поиск по сайту: