Добавлен: 22.05.2023
Просмотров: 266
Скачиваний: 2
Введение
Почти всякая сложная практическая задача принятия решения индивидуального (а тем более группового) является многокритериальной.
Концепция принятия решения в качестве первичного элемента деятельности рассматривает решение как сознательный выбор одного из ряда альтернатив, называемых, в зависимости от их конкретного содержания, стратегиями, планами, вариантами и т.д. Этот выбор производит лицо, принимающее решение и стремящееся к достижению определенных целей. В роли такого лица выступают отдельные люди (группы людей), обладающие правами выбора решения и несущие ответственность за его последствия.
Применение математических методов при принятии решений предполагает построение подходящей математической модели, формализовано представляющей проблемную ситуацию, т.е. ситуацию выбора решений. Для задач принятия решений (задач оптимизации) в условиях определенности, когда случайные и неопределенные факторы отсутствуют, компонентами такой модели являются множество всех (альтернативных) решений, из которых и делается выбор одного наилучшего, или оптимального решения, и описание предпочтений лица, принимающего решение. Для того чтобы была обеспечена возможность выбора, множество должно содержать не менее двух решений.
Методы решения задач математического программирования с одним критерием интенсивно разрабатывались последние 40 лет. Изучение таких методов, однако, отражало самый ранний и простой этап в развитии математического программирования. Жизнь оказалась значительно сложнее. По мере того как мы постепенно вступаем в век информатики, становится ясно, что практически любая серьезная реальная задача характеризуется больше чем одним критерием. Лица, принимающие решения (ЛПР), в значительно большей степени, чем когда бы то ни было, ощущают необходимость оценивать альтернативные решения с точки зрения нескольких критериев.
Результаты исследования задач планирования и управления показывают, что в реальной постановке эти задачи являются многокритериальными. Так, часто встречающееся выражение «достичь максимального эффекта при наименьших затратах» уже означает принятие решения при двух критериях. Оценка деятельности предприятий и планирования как системы принятия решений производится на основе более десятка критериев: выполнение плана производства по объему, по номенклатуре, плана реализации, прибыли по показателям рентабельности, производительности труда и т.д.
Ранее, при исследовании проблемы многокритериальности часто все критерии, кроме одного, выбранного доминирующим, принимались в качестве ограничений. Впервые проблема оптимизации векторного критерия была сформулирована экономистом Парето в 1896 г.
В задачах математического программирования с одним критерием нужно определить значение целевой функция, соответствующее, например, минимальным затратам или максимальной прибыли. Однако, немного подумав, мы практически в любой реальной ситуации обнаружим несколько целей, противоречащих друг другу.
Приведем пример того, насколько широк диапазон проблем, которые могут быть адекватно сформулированы как многокритериальные, и какие характеристики следует использовать в качестве критериев.
1. Оптимальность по Парето
Для облегчения результатов полезно всё время проводить аналогию с однокритериальным (классическим) случаем. Пусть имеется область D и задана функция f – целевая функция (критерий). Задача оптимизации имеет вид
min f(X)
X∈D
Точка X1∈D называется оптимальной (недоминируемой, неулучшаемой), если не существует точки X2∈D, для которой f(X1)>f(X2) (целевая функция минимизируется). Аналогично в МЗО можно исключить из области D точки, которые заведомо не могут оказаться наилучшими.
Очевидно, что в обобщённом смысле определение оптимальности можно трактовать как описание (выделение) в подмножестве D некоторого нового подмножества D0, т.е. некоторое сужение D до D0 ⊂D. В зависимости от характера описания, подмножество D0 может оказаться пустым, состоять из одного элемента, содержать более одного элемента. Описание D0 можно проводить либо только с помощью критериев Fi, либо использовать дополнительные условия. Здесь мы рассмотрим направление, которое связано с определением оптимальности по Парето[1].
1.1 Отношение доминирования по Парето. Парето-оптимальность
Как было сказано раньше для всякого решения X∈D набор его оценок по всем критериям, т.е. набор (F1(X), F2(X), . . .,Fm(X)), есть векторная оценка решения X. Векторная оценка X содержит полную информацию о ценности (полезности) этого решения для ЛПР и сравнение любых двух решений заменяется сравнение их векторных оценок. Пусть в МЗО требуется получить меньшие значения каждого частного критерия (минимизировать частные критерии) Fi(X).
Опр. Пусть имеются два решения X1 и X2. Говорят, что решение X1 лучше (предпочтительнее, эффективнее, доминирует) решения X2, если Fi(X1)<=Fi(X2) для всех i=1,m, и хотя бы для одного j - го критерия выполняется строгое неравенство Fi(X1)<Fi(X2). или
Опр. Решение X2 называется доминируемым, если существует решение X1, не хуже чем X2, т.е. для любой оптимизируемой функции Fi, I=1, 2, …, m,
Fi(X2)≤Fi(X1) при максимизации функции Fi,
Fi(X2)≥Fi(X1) при минимизации Fi.
В случае доминирования при переходе от X2 к X1 ничего не будет проиграно ни по одному из частных критериев, но в отношении j - го частного критерия точно будет получен выигрыш. Говорят, что решение X1 лучше (предпочтительнее) решения X2.
Опр. Стратегия X1∈D называется эффективной (оптимальной по Парето), если не существует стратегии X2∈D такой, что Fi(X2) ≤Fi(X1), i=1, . . ., m, F(X2)≠F(X1), или
Опр. Если решение не доминируемо никаким другим решением, то оно называется недоминируемым или оптимальным в смысле Парето.
Очевидно, тогда в составе множества D нет смысла сохранять решение X2, оно вытесняется (или, как говорят, “доминируется”) решением X1. Ладно, выбросим, решение X2 как неконкурентоспособное и перейдём к сравнению других решений по всем критериям. В результате такой процедуры отбрасывания заведомо непригодных, невыгодных решений множество D обычно сильно уменьшается: в нём сохраняются только так называемые эффективные (иначе “паретовские”) решения, характерные тем, что ни для одного из них не существует доминирующего решения. Множество таких точек и называется множеством точек оптимальных по Парето. Множество точек оптимальных по Парето лежат между точками оптимумов, полученных при решении задачи математического программирования для каждого частного критерия. В литературе множество точек оптимальных по Парето, как правило, обозначают буквой P (P⊂D).
Опр. Множество векторных оценок, соответствующих множеству эффективных точек, называют областью компромиссов (переговорным множеством) или множеством Парето в области критериев. Будем обозначать YP (YP ⊆YD).
Опр. Множество векторных оценок, соответствующих множеству неэффективных точек (доминируемых решений), называют областью согласия Yc.
В области Yc нет противоречия между частными критериями оптимальности, т.к. каждая точка X∈D может быть изменена таким образом, что будет одновременно улучшены все частные критерии.
Если область критериев YD состоит только из области согласия Yc, то существует единственная точка Xopt∈D, в которой все частные критерии согласованны между собой в том смысле, что при движении к точке Xopt все Fi(X) i=1, 2, . . ., m, одновременно улучшаются. Все частные критерии достигают минимума в т. Xopt (см. рис. 1). Такую точку называют оптимальным решение и при этом значения всех частных критериев достигают в ней минимума.
Рис. 1. Критерии F1 и F2 непротиворечивы
Однако такая ситуация встречается крайне редко. Наиболее типичным является случай, когда частные критерии являются противоречивыми и минимум по каждому из них достигается в различных точках. В этом случае уменьшение одного частного критерия приводит к увеличению других частных критериев (рис. 2).
Рис. 2. Критерии F1 и F2 противоречивы на отрезке [1; 2]
Оптимальность по Парето означает, что нельзя дальше улучшать значение одного критерия, не ухудшая при этом хотя бы одного из остальных.
Проиллюстрируем приём выделения паретовских решений на примере задачи с двумя критериями F1 и F2 (оба требуется максимизировать). Множество D состоит из 11 возможных решений. Каждому решению соответствуют определённые значения показателей F1 и F2. Пусть имеются следующие векторные оценки: F(X1)=(2;4), F(X2)=(3;5), F(X3)=(3;3), F(X4)=(5;2), F(X5)=(4;3), F(X6)=(1;3), F(X7)=(2;3), F(X8)=(3;2), F(X9)=(2;2), F(X10)=(3;1), F(X11)=(2;1). Векторные оценки исходов представим точками координатной плоскости (по оси абсцисс откладываем значения критерия F1, а по оси ординат – значения критерия F2). Используем принцип оптимальности по Парето для выделения эффективных решений. Решение X1 вытесняется решением X2, решение X2 лучше решений X3, X7, X8, X9, X10 и X11. Решение X4 по первому критерию лучше решения X5, а по второму наоборот, т.е. имеем неулучшаемые решения, и т.д. После проведённого анализа у нас остались три решения X2,X4, X5 оптимальных по Парето.
Построим критериальное пространство для нашей задачи. Как известно паре чисел соответствует точка на плоскости. Занумеруем точки соответственно номеру решения (рис 3). Из рисунка видно, что эффективные точки лежат на правой верхней границе области возможных решений (Ауд. решить данную задачу, когда оба критерия нужно минимизировать).
Рис. 3. Множество Yk
Когда из множества возможных решений выделены эффективные, "переговоры" могут вестись уже в пределах этого "эффективного" множества. На рис. 3 образуют три решения X2, X4, X5; из них X4 лучше по критерию F1, а решение X2 по критерию F2. Дело ЛПР, выбрать тот вариант, который для него предпочтителен и “приемлем” по обоим критериям.
Замечание. Точка Y1 выбирается в YD в том и только в том случае, когда любая другая точка Y2 из YD имеет хотя бы по одной координате значение больше чем Y1 (критерии минимизируются).
Замечание. Для определения эффективных точек используют правило “уголка”. Уголок вида ∟ используется для определения компромиссных точек в критериальном пространстве, когда критерии максимизируются, а уголок ┐когда критерии минимизируются.
В случае, когда множество допустимых исходов является непрерывным, их векторные оценки "заполняют" некоторую область YD на плоскости и получается "картинка" вроде изображённой на рис. 4. В этом случае множество Парето-оптимальных оценок (красная линия) представляет собой часть границы YD, образно говоря, её "юго-западную" границу". Если критерии максимизируются то – "северо-восточную" границу области YD.
Рис. 4. Пространство оценок YD и компромиссная кривая (красный цвет)
Замечание. В случае невыпуклой области её Парето-оптимальная граница может иметь более "экзотический" вид, например, состоять из отдельных линий и/или точек. Для данного примера (критерии максимизируются) — это правый пик.
Замечание. Экономисты так определяют оптимальность по Парето. Состояние называется оптимальным по Парето, если выполняется следующее условие: ничьё благосостояние не может быть улучшено без ухудшения благосостояния кого-либо другого (см. История экономических учений. /Под ред. В. Автономова: Учеб. Пособие. – М.: ИНФА – М, 2000. – 784 с. (стр. 242)).
Таким образом, под оптимально-компромиссным решением будем понимать одну из эффективных точек, являющуюся предпочтительней с точки зрения ЛПР. Задача векторной оптимизации не позволяет однозначно ответить на вопрос, получено ли оптимальное решение. Положительный ответ на этот вопрос зависит от качественной информации о важности частных критериев, которая имеется у ЛПР.
1.2 Аналитические методы построения множества Парето
Компромиссная кривая
Особый интерес для практики — m=2. В этом случае множество паретовских точек представляет собой одномерное многообразие на плоскости и допускает удобное графическое представление.
Опр. Множество паретовских точек в двухмерном пространстве критериев называют компромиссной кривой.
Она может состоять из несвязных кусков и содержать изолированные точки (см. рис. 5). Компромиссная кривая (КК) строго монотонно убывает в следующем смысле. Пусть Y1 и Y2 произвольные точки, принадлежащие КК. Обозначим их координаты Y1(y1,y2) и Y2(y3,y4), если y1<y3, то y2>y4. Таким образом, КК не содержит ни горизонтальных, ни вертикальных отрезков и её уравнение может быть представлено в форме F2=u(F1) и F1=v(F2).