Безліч парето, лінійне програмування, приклади рішень завдань
Нехай на площині (або в просторі) дано деякий безліч точок M. Точка називається внутрішньою точкою множини М. якщо існує така околиця цієї точки, яка цілком складається з точок даної множини.
Якщо ж в будь-який околиці точки є точки, як належать, так і не належать множині М. то точка називається граничною точкою множини.
Сукупність усіх граничних точок даного безлічі М називається його кордоном. Ілюстрацією служить рис. 1.
Якщо безліч М не містить жодної своєї граничної точки, то воно називається відкритим (тобто будь-яка точка відкритого безлічі є внутрішньою).
Якщо безліч М містить всі свої граничні точки, то воно називається замкнутим. Надалі будуть розглядатися тільки замкнуті безлічі.
Якщо безліч М не містить жодної своєї граничної точки, то воно називається відкритим (тобто будь-яка точка відкритого безлічі є внутрішньою).
Якщо безліч М містить всі свої граничні точки, то воно називається замкнутим. Надалі будуть розглядатися тільки замкнуті безлічі.
Розглянемо на площині безліч М. Нехай Р - довільна точка цієї множини. Чи можливо в безлічі М переміщення точки Р в близьку їй точку так, щоб при цьому збільшилися обидві її координати? Якщо Р - внутрішня точка, то таке переміщення можливо. Якщо Р - гранична точка, то таке переміщення не завжди можливо. Ілюстрацією служить рис. 2
Необхідну переміщення точок P1. P2. P3, P4 можливо, а жодна з точок як відрізків P5 P6 і P7 P8. так і дуги P6 P7 такому переміщенню піддана бути не може. Дійсно, при переміщенні будь-якої точки
- вертикального відрізка P5 P6 може збільшуватися лише координата L2 цієї точки (координата L1 при цьому залишиться незмінною);
- горизонтального відрізка P7 P8 може збільшуватися лише координата L1 (координата L2 при цьому залишиться незмінною);
- дуги P6 P7 збільшення однієї координати спричиняє зменшення іншого.
Таким чином, кожна точка безлічі М потрапляє в один з трьох наступних класів.
- Перший клас містить точки, кожну з яких можна перемістити так, щоб при цьому збільшилися обидві її координати, а сама точка залишилася у багатьох М (в цей клас потрапляють всі внутрішні точки безлічі М і деякі його граничні точки (наприклад, P2)).
- Другий клас містить точки, кожну з яких можна перемістити в безлічі М лише за умови збільшення тільки однієї з її координат при збереженні значення другої (точки вертикального відрізка P5 P6 і точки горизонтального відрізка P7 P8).
- Третій клас містить точки, кожну з яких можна перемістити в безлічі М лише за умови зменшення хоча б однієї з координат (точки дуги P6 P7).
Безліч точок третього класу називають кордоном (безліччю) Парето даної множини М. Часто говорять, що межа Парето безлічі М - це безліч точок, з яких не можна переміститися на «північ», «схід» або «північний схід», залишаючись в безлічі М. Вважається, що найкращі рішення багатокритеріальної задачі слід шукати саме серед безлічі Парето . Тому побудова безлічі Парето нерідко вважають першим необхідним кроком у вирішенні будь-багатокритеріальної задачі.