Вторник, 06.12.2016, 17:09
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 56
Гостей: 56
Пользователей: 0
» »
19:37
Множество Парето

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

   Пусть на плоскости (или в пространстве) дано некоторое множество точек M. Точка  называется внутренней точкой множества М, если существует такая окрестность этой точки, которая целиком состоит из точек данного множества.

Если же в любой окрестности точки  имеются точки, как принадлежащие, так и не принадлежащие множеству М, то точка  называется граничной точкой множества М.

Совокупность всех граничных точек данного множества М называется его границей.Иллюстрацией служит рис. 1.

  

Если множество М не содержит ни одной своей граничной точки, то оно называется открытым (то есть любая точка открытого множества является внутренней).

Если множество М содержит все свои граничные точки, то оно называется замкнутым. В дальнейшем будут рассматриваться только замкнутые множества.

Если множество М не содержит ни одной своей граничной точки, то оно называется открытым (то есть любая точка открытого множества является внутренней).

Если множество М содержит все свои граничные точки, то оно называется замкнутым. В дальнейшем будут рассматриваться только замкнутые множества.

Рассмотрим на плоскости  множество М. Пусть Р — произвольная точка этого множества. Возможно ли во множестве М перемещение точки Р в близкую ей точку так, чтобы при этом увеличились обе ее координаты? Если Р — внутренняя точка, то такое перемещение возможно. Если Р — граничная точка, то такое перемещение не всегда возможно. Иллюстрацией служит рис. 2

Требуемое перемещение точек P1, P2 , P3,P4 возможно, а ни одна из точек как отрезков  P5P6 и P7P8, так и дуги  P6P7 такому перемещению подвергнута быть не может. Действительно, при перемещении любой точки

  • вертикального отрезка  P5P6 может увеличиваться лишь координата  L2 этой точки (координата L1 при этом останется неизменной);
  • горизонтального отрезка P7P8  может увеличиваться лишь координата L1 (координата  L2 при этом останется неизменной);
  • дуги  P6P7 увеличение одной координаты влечет уменьшение другой.

Таким образом, каждая точка множества М попадает в один из трех следующих классов.

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

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

Категория: Линейное программирование | Просмотров: 1524 | Добавил: Admin | Теги: ОР и ОДР, симплекс метод, транспортная задача, линейное програмирование | Рейтинг: 0.0/0



Всего комментариев: 0
avatar
  .