Методи послідовної оптимізації, Контент-платформа
Методи послідовної оптимізації
Недоліки згортання кількох критеріїв змушують шукати інші підходи вирішення завдань багатокритеріального вибору. У цій лекції ми розглядатимемо методи послідовної оптимізації.
До методів послідовної оптимізації відносятьметод послідовних поступокі як окремий випадок даного методу -метод головного критерію,лексикографічний критерійтаметод рівності приватних критеріїв.
Метод головного критерію
Існує один, часто застосовуваний спосіб звести багатокритеріальну завдання до однокритеріальної - це виділити один (головний, основний) критерій F1 і прагнути його звернути до максимуму (мінімум), а на інші F2, F3, . . Fm приватні критерії накласти лише деякі обмеження, зажадавши, щоб вони були не меншими (більше) якихось заданих величин. Таким чином, ідея методу головного критерію полягає в тому, що приватні критерії зазвичай нерівнозначні між собою (одні з них важливіші за інші) і це дозволяє виділити головний критерій, а інші (критерії) розглядати як додаткові, супутні. Наприклад, при оптимізації плану роботи підприємства можна вимагати, щоб прибуток був максимальним, план за асортиментом – виконаний або перевиконаний, а собівартість продукції – не вище заданої. За такого підходу всі показники, крім одного – головного, перетворюються на розряд обмежень. Така відмінність дозволяє сформулювати завдання багатокритеріальної оптимізації як завдання знаходження умовного екстремуму основного (головного) критерію:
Метод послідовних поступок
Трапляються випадки, коли користувач готовий на деяке зниження величин важливіших критеріїв, щобпідвищити величину менш важливих. У таких ситуаціях можна скористатисяметодом поступок. Ідею цього можна викласти так.
Таким чином, оптимальним вважається будь-яке рішення, яке є рішенням останньої задачі з наступної послідовності задач
1) Знайти F1 min = min F1 (X)
2) Знайти F2 min.=min F2(X) (1)
m) Знайти Fm min.=min Fm(X)
Величини поступок вибирають у межах інженерної точності, тобто 5-10% від найменшого значення критерію.
приклад. Нехай у ділянці D= задані два критерії F1(x)=(x-1)2+1 F2(x)=(x-2)2+2, які потрібно мінімізувати (рис.1). Критерій F1 важливіший за критерій F2 (F1 переважно F2).
Рис.1. Графіки функцій F1 та F2
1. Згідно з алгоритмом мінімізуємо перший за важливістю критерій і визначається його найменше значення F1min Формулюємо завдання оптимізації
знайти min F1(x)=min[x-1)2+1]
Мінімум для першого критерію досягається в точці x1opt=1 і дорівнює F1(x1opt)=1
2. Потім призначається величина поступки D1=0.1 критерію F1 і шукається найменше значення критерію F2 за умови, що значення F1 має бути не більше ніж F1min+D1. Таким чином ми отримали наступне завдання оптимізації.
Для вирішення скористаємося методом множників Лагранжа. В результаті отримаємо безумовне завдання оптимізації.
Знаходимо приватні похідні та прирівнюємо їх до нуля. В результаті отримаємо систему рівнянь
Вирішуючи цю систему, отримаємо x2opt=1.32.
Згідно з алгоритмом, рішення, отримане на останньому етапі і вважається оптимальним, тобто xopt = 1.32.
Вирішимо це завдання, використовуючи систему MathCad.
f(x):=(x-2)2+2 цільова функція
x:=1 початкове наближення
p:=Minimize(f, x) p=1.316.
Зам. Методпослідовних поступок доцільно застосовувати на вирішення тих інженерних завдань, у яких всі приватні критерії впорядковані за рівнем важливості, причому кожен критерій настільки важливіший, ніж наступний, що можна обмежитися врахуванням лише попарного зв'язку критеріїв і вибирати величину допустимого зниження чергового критерію з урахуванням поведінки наступного критерію.
Як бачимо, у методі поступок передбачається, що різниця у важливості критеріїв не надто велика. Можна припустити, що величина поступок якось пов'язана з нашим відчуттям цієї різниці.
Протилежним крайнім випадком є ситуація, в якій різниця між упорядкованими критеріями настільки велика, що наступний у цьому ряду критерій розглядається тільки в тому випадку, порівнювані альтернативи невиразні за старшими критеріями. Про жодні поступки при цьому не може бути й мови. У цій ситуації вибір досить часто закінчується на першому ж кроці, а до останнього критерію справа зазвичай не доходить (точніше він "винаходиться" у тому надзвичайно рідкісному екзотичному випадку, коли прийняті раніше критерії не виділили єдиної альтернативи). Такий вибір отримав назвулексикографічного впорядкуванняальтернатив, оскільки цей метод використовується при упорядкуванні слів у різних словниках (перевага визначається алфавітним рангом чергової літери в даному слові).
Метод рівності приватних критеріїв
Критерії працюють за принципом компромісу, заснованого на ідеї рівномірності. Грунтуючись ідеї рівномірного компромісу, намагаються знайти такі значення змінних X, у яких нормовані значення всіх приватних критеріїв стають рівними між собою, тобто.
fi(X)=K, i=1, 2, . . ., m (3)
або в іншій формі f1(X)= f2(X)=… = fm (X). .
З урахуванням вагових коефіцієнтів важливості приватних критеріїв вираз (1) запишеться у вигляді
li fi (X) = K, i = 1, 2, . . ., m (4).
Зам. При великій кількості приватних критеріїв через складність взаємозв'язків іноді важко домогтися виконання співвідношень (
приклад. Застосуємо метод рівності приватних критеріїв визначення оптимальних параметрів переносного автомата. Вважатимемо, що приватні критерії однакові за важливістю, тоді
, .
Виразимо F2 через F1. Отримаємо або підставимо в рівняння для маси автомата Зробимо заміну Отримаємо квадратне рівняння 1.6x2+c·x-4=0. Вирішуємо це рівняння і вибираємо, позитивний корінь x=1.024. Враховуючи заміну, отримаємо L=1.05 м. Таким чином, отримаємо наступні значення оптимальних параметрів: Nopt=46, Lopt=1.05м, Vopt=152 м/сек (K=0.697) .