 |
|
Многокритериальные задачи оптимизации
Многокритериальная задача оптимизации – математическая модель принятия оптимального решения одновременно по нескольким критериям.
Эти критерии могут отражать оценки различных качеств объекта (или процесса), по поводу которого принимаются решения.
Можно привести много примеров, когда требуется найти решение, для которого достигались наилучшие значения сразу по нескольким критериям. Наиболее распространенная задача, которую мы решаем очень часто (не облекая ее в термины оптимизации) - это поиск покупки, которая была как можно качественнее и как можно дешевле.
Многокритериальные задачи, которые не просто решить исходя только из интуитивных соображений, возникают в разнообразных видах человеческой деятельности. Например, при проектировании компьютера может быть поставлена задача, в рамках которой формируется конфигурация, при которой одновременно достигаются максимальное быстродействие, наибольшая оперативная память и наименьший вес компьютера. При создании электрической машины проектировщик пытается подобрать такие ее параметры, при которых достигается максимум коэффициента полезного действия, при этом расходуется минимальное количество дорогих электротехнической стали и меди.
Математическая постановка многокритериальной задачи (далее МЗ) представляется следующим образом:
необходимо определить такой вектор переменных x = (x1, x2, … , xn) из множества допустимых решений D, при котором значение векторной функции векторного аргумента F(x1,x2,…,xn)={f1 (x1,x2, … , xn), f2(x1,x2, … , xn), … , fk (x1,x2, … , xn)}(где fi(x1,x2, … , xn) – i-ая скалярная целевая функция, i=1,k) достигает своего максимума (или минимума).
,
, (5.1)
где x = (x1,x2, … , xn) – вектор искомых переменных, а D – множество допустимых решений, заданное с помощью тех или иных ограничений.
(первая) (5.2)
где F(x) - векторная функция векторного аргумента. Поскольку в записи модели (5.2) используется векторная функция, многокритериальную задачу часто называют задачей векторной оптимизации.
Сущность многокритериальной задачи (5.1) (или (5.2) состоит в нахождении такого решения, принадлежащего области допустимых решений (т. е. такого x Î D), которое в том или ином смысле максимизирует (или минимизирует) значения всех целевых функций f i(x), где i = 1, …, k.
Существование решения, буквально максимизирующего (или минимизирующего) одновременно все целевые функции, является редким исключением. (Если вспомнить пример о поиске одновременно очень качественной и очень дешевой покупки, то становится понятным, что нахождение такого решения – редкая удача, но, гораздо более часто, это неразрешимая задача).
Так как многокритериальная не имеет в общем случае строго математического решения, то есть, как правило, невозможно найти решение при котором достигается максимум (минимум) сразу по всем критериям, то приходится приходить к какому-то соглашению о том, какое решение будет наиболее предпочтительным в заданных условиях. Отсюда следует, что, во-первых, в теории многокритериальных задач понятие оптимальности получает различные и притом нетривиальные истолкования, а, во-вторых, то, что многокритериальная задача в общем случае решается с привлечением неформальной субъективной информации того, кто принимает окончательное решение или по терминологии теории принятия решений – лица, принимающего решения (ЛПР).
Пример
5. Классическая задача оптимизации. Эта задача состоит в нахождении минимума целевой функции q х, где х х 1 х т - точка в пространстве R т при наличии ограничений типа равенств 16 fi x 0, i 1,m, m n Если ограничения 16 имеют место, то минимум функции q х называют условным минимумом.
Если ограничения 16 отсутствуют, то говорят о безусловном минимуме, нахождение которого сводится к определению и исследованию стационарных точек функции q х. Классический способ решения данной задачи состоит в том, что уравнение 16 используется для исключений из рассмотрения m - переменных.
При этом целевая функция приводится к виду 17 q x 1 , ,x т q1 y 1 y т, где через у 1 у т обозначены не исключенные переменные.
Задача состоит теперь в нахождении значений у 1 , ,у т которые обращают в минимум функцию q1 и на которые не наложено ни каких ограничений, т.е. сводится к задаче на безусловный экстремум.