загрузка...
загрузка...
На головну

Графічний спосіб побудови безлічі Парето

Алгоритм формування безлічі Парето

Нехай є n альтернатив, кожна з яких характеризується набором приватних критеріїв. Алгоритм складається з n циклів порівняння кожної альтернативи з уже ввійшли в безліч Парето

У кожному циклі порівняння можливі три результати:

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

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

приклад Нехай є 9 альтернатив, кожна з яких характеризується двома «хорошими» приватними критеріями в1 і в2. Процес побудови безлічі Парето за описаним вище алгоритмом відображається наступною таблицею

 альтернативи y1, y2  цикли порівняння  безліч Парето  пояснення
 3, 10  Перша альтернатива входить до складу безлічі Парето автоматично.
 2, 9  А2 не включена в Парето, так як гірше А1 за обома критеріями
 9, 5  1, 3  А3 додана в Парето, так як краще А1 по в1, але гірше за у2
 6, 7  1, 3, 4  А4 додана в Парето, так як не гірше і не лучще А1 і А3
 4, 4  1, 3, 4  А5 не включена в Парето, так як гірше А3 і А4 за обома критеріями
 6, 4  1, 3, 4  А6 не включена в Парето, так як гірше А3 за обома критеріями
 8, 3  1, 3, 4  А7 не включена в Парето, так як гірше А3 за обома критеріями
 7, 8  1, 3, 8  А8 включена в Парето, так як не гірше і не лучще А1 і А3. А4 виключена з Парето, так як гірше А8 за обома критеріями
 10, 6  1, 8, 9  А9 включена в Парето, так як не гірше і не лучще А1 і А8. А3 виключена з Парето, так як гірше А9 за обома критеріями

Важливо зауважити, що описаний алгоритм побудови множини Парето застосуємо тільки для сформульованого умови компромісу - альтернативи рівноцінні, якщо хоча б по одному приватному критерієм одна краща за іншу. Для інших умов компромісу алгоритми побудови безлічі Парето будуть іншими.

Безліч Парето для двох критеріїв можна побудувати графічно. Для кожної альтернативи, представленої на графіку точкою, будується прямокутник. На малюнку такі прямокутники побудовані для точок 1, 2 і 6. Очевидно, кутова точка кожного прямокутника є найкращою точкою по відношенню до всіх інших, які опинилися всередині цього прямокутника, так як у цій кутовий точки значення критеріїв в1 і в2 найбільші. Тому всі точки, які опинилися всередині побудованих прямокутників, наприклад, точки 8, 4, 5 для прямокутника з вершиною в точці 6 і точка 2 для прямокутника з вершиною в точці 1, виключаються з розгляду. Процес триває до тих пір, поки не будуть побудовані прямокутники для всіх точок. Незвільнені точки (в даному випадку це точки 1, 3, 9) утворюють безліч Парето. Зауважимо, що при інших напрямках поліпшення критеріїв y1, y2 правила побудови прямокутників (точніше, кутів) і виключення точок будуть іншими. Наприклад, на наведеному нижче малюнку кращою буде кутова точка кута 1, а кутові точки для кутів 2 і 3 будуть виключені.

Види множин Парето. Правило вітрила. «-- попередня | наступна --» Безліч Парето і критерій задоволення ТЗ
загрузка...
© om.net.ua