Рассмотрим вектор F(х) с компонентами F(x)|Foi из (15) и составим квадрат евклидовой нормы
… (17)
вектора F(x) - Fo, определенного для всех xєW .
Заметим, что Fo будет представлять собой единичный вектор в пространстве вектора F(x). Назовем его идеальным значением вектора F(x). Поставленная задача теперь сформулируется так: дана система целевых функций (11) и даны условия задачи (12) – (14). Требуется определить точку xєW, в которой функция R(x) достигает минимума.
Таким образом, отыскание векторно-оптимального плана xєW в данной задаче сведено к оптимизации выражения (17) на решениях системы линейных неравенств (12) – (14). Поскольку выражение (17) представляет собой квадратичную функцию переменных х1, …, хп, то задача отыскания векторно-оптимального плана свелась к задаче выпуклого программирования:
Задана выпуклая функция R(x), определенная на множестве xєW. Требуется отыскать точку xєW, обеспечивающую выполнение условия R(x*) = minR(x), xєW.
Таким образом, алгоритм решения задачи (11) – (14) состоит из двух основных этапов:
этап 1: maxFi(x), i=1, m;
этап 2: min R(x).
2.4. Метод квазиоптимизации локальных критериев (метод последовательных уступок)
В этом случае осуществляется поиск не единственного точного оптимума, а некоторой области решений, близких к оптимальному, – квазиоптимального множества. При этом уровень допустимого отклонения от точного оптимума определяется с учетом точности постановки задачи (например, в зависимости от точности вычисления величины критериев), а также некоторых практических соображений (например, требований точности решения задачи). [7]
Вначале производится качественный анализ относительной важности критериев; на основании такого анализа критерии располагаются и нумеруются в порядке убывания важности, так что главным считается критерий F1, менее важен F2, затем следуют остальные локальные критерии F3, F4,.. ., Fm. Максимизируется первый по важности критерий F1 и определяется его наибольшее значение M1. Затем назначается …
… (18)
Такой подход позволяет значительно сузить первоначальную допустимую область X, когда переходим к следующему по важности критерию.
После этого находим наибольшее значение М2 второго критерия F2 на множестве X(1), т. е. при условии, что значение первого критерия должно быть не меньше, чем M1-d1. Снова назначается значение уступки d2>=0, но уже по второму критерию, которое вместе с первым используется при нахождении условного максимума третьего критерия, и т. д. Наконец, максимизируется последний по важности критерий Fm при условии, что значение каждого критерия Fr из m—1 предыдущих должно быть не меньше соответствующей величины Мr - dг; получаемые стратегии считаются оптимальными:
…
Таким образом, оптимальной считается всякая стратегия, являющаяся решением последней задачи из следующей последовательности задач:
1) найти M1= …
2) найти M2= … (19)
3) …
m) найти Mm= …
Если критерий Fm на множестве стратегий, удовлетворяющих ограничениям задачи m) из (19) не достигает своего наибольшего значения Мm, то решением многокритериальной задачи считают максимизирующую последовательность {xk} из последовательности множеств
Xm-1ÌXm-2Ì … ÌX1Ì X
Практически подобные максимизирующие последовательности имеет смысл рассматривать и для того случая, когда верхняя грань в задаче m достигается, так как для решения экстремальных задач широко применяются итеративные методы.
Алгоритм решения задачи векторной оптимизации включает следующие шаги.
Шаг 1. Пусть х01 — решение задачи (19)
max Fl(x), xєX
Шаг 2. Пусть xok - решение задачи
max Fk(x), xєX(k-1)
где Xk определяется из (19).
Шаг 3. Если k<m, то устанавливаем k=k+1 и повторяем шаг 2. Если k = m, то
хom считаем оптимальным решением.
Алгоритм закончен.
Значения уступок di (i=1,m) последовательно назначаются при изучении взаимосвязи частных критериев.
Вначале решается вопрос о назначении допустимого снижения d1 первого критерия от наибольшего …
…обычно ограничиваются нахождением одной такой стратегии).
Таким образом, хотя формально при использовании метода последовательных уступок достаточно решить лишь от задач (19), однако для назначения значения уступок с целью выяснения взаимосвязи частных критериев фактически приходится решать существенно большее число таких задач.
Для решения многокритериальной задачи нужно так ранжировать критерии, чтобы потом удобнее было выбирать значения уступок.
Учитывая вышеизложенное, можно сделать следующий вывод. Метод последовательных уступок целесообразно применять для решения тех многокритериальных задач, в которых все частные критерии естественным образом упорядочены по степени важности, причем каждый критерий настолько существенно более важен, чем последующий, что можно ограничиться учетом только попарной связи критериев и выбирать допустимое снижение очередного критерия с учетом поведения лишь одного следующего критерия.
Особенно удобным является случай, когда уже в результате предварительного анализа многокритериальной задачи выясняется, что можно допустить уступки лишь в пределах «инженерной» точности (5-10% от наибольшей величины критерия).
2.5. Метод свертывания векторного критерия в суперкритерий
Одним из распространенных методов решения многокритериальных задач является метод сведения многокритериальной задачи к однокритериальной путем свертывания векторного критерия в суперкритерий. При этом каждый критерий умножается на соответствующий ему весовой коэффициент (коэффициент важности). [6]
…
При этом возникают трудности с правильным подбором весовых коэффициентов аi. Существуют различные способы выбора коэффициентов аi. Одним из них является назначение аi в зависимости от относительной важности критериев. Такой подбор указанных коэффициентов можно выполнять согласно таблице:
Таблица 2.1.
Шкала относительной важности.
…
…
Здесь были рассмотрены лишь некоторые методы многокритериальной оптимизации в ИО. Их существует гораздо больше и каждый имеет свои привлекательные стороны в выборе принятия решений в различных ситуациях. Но, несмотря на свою существенность среди методов принятия решения в ИО, данная методика имеет свои проблемы.
Глава 3. Существующие проблемы многокритериальной оптимизации и пути их решения
3.1. Существующие проблемы многокритериальной оптимизации
В ходе проделанной работы был собран материал о существующих методах многокритериальной оптимизации с систематизацией его по разделам. На сегодняшний день существуют такие проблемы многокритериальной оптимизации.
Первая проблема связана с …
… Это объясняется тем, что приходится сравнивать векторы эффективности на основе некоторой схемы компромисса.
В математическом отношении эта проблема эквивалентна задаче упорядочения векторных множеств, а выбор принципа оптимальности – выбору отношения порядка.
Вторая проблема связана с нормализацией векторного критерия эффективности F. Она вызвана тем, что очень часто локальные критерии, являющиеся компонентами вектора эффективности, имеют различные масштабы измерения, что и затрудняет их сравнение. Поэтому приходится приводить критерии к единому масштабу измерения, т. е. нормализовать их.
Третья проблема связана с учетом приоритета (или различной степени важности) локальных критериев. Хотя при выборе решения и следует …
… с помощью которого корректируется принцип оптимальности или проводится дифференциация масштабов измерения критериев.
К вышесказанному можно добавить также то, что трудности вызывает одновременное наличие в задаче многокритериального программирования качественных и количественных критериев, а именно – перевод из качественных в количественные критерии для дальнейшей оптимизации построенной математической модели. Да и сам правильный подбор весовых коэффициентов иногда сделать не так просто.
3.2. Возможные пути решения проблем многокритериальной оптимизации
С рассмотренными выше проблемами связаны основные трудности многокритериальной оптимизации, и от того, насколько успешно они будут преодолены, во многом зависят успех и правильность выбора решения. Поэтому здесь непременно должно участвовать ответственное за принятие решения лицо или орган. Таким образом, нужно разрабатывать …
… после последнего проделанного шага алгоритма оптимизации.
Возможными путями решения рассмотренных выше проблем многокритериальной оптимизации может быть применение рассмотренных в главе 1 пункте 1.2. сверток и способов нормализации.
Также одним из возможных вариантов решения задач многокритериальной оптимизации является использование эволюционных (генетических) алгоритмов. Эта область является перспективной, так как при построении эволюционных методов решения нет четких предписаний, а используются лишь эволюционные принципы построения генетических алгоритмов, то есть построение алгоритма зависит как от выбора операторов мутации, кроссовера, так и от выбора принципа, по которому будут формироваться жизнеспособные хромосомы. Таким образом, можно использовать комбинацию какого-либо из рассмотренных методов многокритериальной оптимизации и генетического алгоритма для решения задачи многокритериальной оптимизации.
Итак, в данной курсовой работе, посвященной одному из методов исследования операций, коротко (насколько позволили рамки объема работы) было рассказано о методе многокритериальной оптимизации. Данный метод, касающийся математических аспектов ситуаций, когда имеется несколько критериев, — необходимая часть сведений, которыми должен быть вооружен менеджер, но только часть сведений, касающихся принятия решений при большом числе альтернативных вариантов выбора и значительном числе разнородных критериев, когда ЛПР не может, вообще говоря, в одиночку, самостоятельно составить целостную картину качества альтернативных вариантов. Есть различные методы организации деятельности ЛПР в таких условиях, ни один из них не претендует на универсальность.