Методы отыскания эффективных решений (оптимальных по парето) в пространстве исходов и в пространстве критериев. Формализация выбора эффективных решений на множестве векторных оценок.

Очевидно, что в обобщённом смысле определение оптимальности можно трактовать как описание (выделение) в подмножестве D некоторого нового подмножества D₀, т.е. некоторое сужение D до D₀ ÌD. В зависимости от характера описания, подмножество D₀ может оказаться пустым, состоять из одного элемента, содержать более одного элемента. Описание D₀ можно проводить либо только с помощью критериев Fi, либо использовать дополнительные условия. Здесь мы рассмотрим направление, которое связано с определением оптимальности по Парето^[1].

Опр. Пусть имеются два решения X₁ и X₂. Говорят, что решение X₁ лучше (предпочтительнее, эффективнее, доминирует) решения X₂, если F_i(X₁)<=F_i(X₂) для всех i=1,m, и хотя бы для одного j - го критерия выполняется строгое неравенство F_i(X₁)<F_i(X₂). или

Опр. Решение X₂ называется доминируемым, если существует решение X₁, не хуже чем X₂, т.е. для любой оптимизируемой функции Fi, I=1, 2, …, m,

Fi(X₂)£Fi(X₁) при максимизации функции Fi,

Fi(X₂)³Fi(X₁) при минимизации Fi.

В случае доминирования при переходе от X₂ к X₁ ничего не будет проиграно ни по одному из частных критериев, но в отношении j - го частного критерия точно будет получен выигрыш. Говорят, что решение X₁ лучше (предпочтительнее) решения X₂.

Опр. Стратегия X₁ÎD называется эффективной (оптимальной по Парето), если не существует стратегии X₂ÎD такой, что Fi(X₂) £Fi(X₁), i=1,..., m, F(X₂)¹F(X₁), или

Опр. Если решение не доминируемо никаким другим решением, то оно называется недоминируемым или оптимальным в смысле Парето.

Очевидно, тогда в составе множества D нет смысла сохранять решение X₂, оно вытесняется (или, как говорят, “доминируется”) решением X₁. Ладно, выбросим, решение X₂ как неконкурентоспособное и перейдём к сравнению других решений по всем критериям. В результате такой процедуры отбрасывания заведомо непригодных, невыгодных решений множество D обычно сильно уменьшается: в нём сохраняются только так называемые эффективные (иначе “паретовские”) решения, характерные тем, что ни для одного из них не существует доминирующего решения. Множество таких точек и называется множеством точек оптимальных по Парето. Множество точек оптимальных по Парето лежат между точками оптимумов, полученных при решении задачи математического программирования для каждого частного критерия. В литературе множество точек оптимальных по Парето, как правило, обозначают буквой P (PÌD).

Опр. Множество векторных оценок, соответствующих множеству эффективных точек, называют областью компромиссов (переговорным множеством) или множеством Парето в области критериев. Будем обозначать Y_P (Y_P ÍY_D).

Опр. Множество векторных оценок, соответствующих множеству неэффективных точек (доминируемых решений), называют областью согласия Y_c.

Оптимальность по Парето означает, что нельзя дальше улучшать значение одного критерия, не ухудшая при этом хотя бы одного из остальных.

Проиллюстрируем приём выделения паретовских решений на примере задачи с двумя критериями F₁ и F₂ (оба требуется максимизировать). Множество D состоит из 11 возможных решений. Каждому решению соответствуют определённые значения показателей F₁ и F₂. Пусть имеются следующие векторные оценки: F(X₁)=(2;4), F(X₂)=(3;5), F(X₃)=(3;3), F(X₄)=(5;2), F(X₅)=(4;3), F(X₆)=(1;3), F(X₇)=(2;3), F(X₈)=(3;2), F(X₉)=(2;2), F(X₁₀)=(3;1), F(X₁₁)=(2;1). Векторные оценки исходов представим точками координатной плоскости (по оси абсцисс откладываем значения критерия F₁, а по оси ординат – значения критерия F₂). Используем принцип оптимальности по Парето для выделения эффективных решений. Решение X₁ вытесняется решением X₂, решение X₂ лучше решений X₃, X₇, X₈, X₉, X₁₀ и X₁₁. Решение X₄ по первому критерию лучше решения X₅, а по второму наоборот, т.е. имеем неулучшаемые решения, и т.д. После проведённого анализа у нас остались три решения X₂,X₄, X₅ оптимальных по Парето.

Построим критериальное пространство для нашей задачи. Как известно паре чисел соответствует точка на плоскости. Занумеруем точки соответственно номеру решения (рис 3). Из рисунка видно, что эффективные точки лежат на правой верхней границе области возможных решений (Ауд. решить данную задачу, когда оба критерия нужно минимизировать).

Рис. 3. Множество Y_k

Когда из множества возможных решений выделены эффективные, "переговоры" могут вестись уже в пределах этого "эффективного" множества. На рис. 3 образуют три решения X₂, X₄, X₅; из них X₄ лучше по критерию F₁, а решение X₂ по критерию F₂. Дело ЛПР, выбрать тот вариант, который для него предпочтителен и “приемлем” по обоим критериям.

Замечание. Точка Y₁ выбирается в Y_D в том и только в том случае, когда любая другая точка Y₂ из Y_D имеет хотя бы по одной координате значение больше чем Y₁ (критерии минимизируются).

Замечание. Для определения эффективных точек используют правило “уголка”. Уголок вида ∟ используется для определения компромиссных точек в критериальном пространстве, когда критерии максимизируются, а уголок ┐когда критерии минимизируются.

В случае, когда множество допустимых исходов является непрерывным, их векторные оценки "заполняют" некоторую область Y_D на плоскости и получается "картинка" вроде изображённой на рис. 4. В этом случае множество Парето-оптимальных оценок (красная линия) представляет собой часть границы Y_D, образно говоря, её "юго-западную" границу". Если критерии максимизируются то – "северо-восточную" границу области Y_D.

 

Рис. 4. Пространство оценок Y_D и компромиссная кривая (красный цвет)

Замечание. В случае невыпуклой области её Парето-оптимальная граница может иметь более "экзотический" вид, например, состоять из отдельных линий и/или точек. Для данного примера (критерии максимизируются) — это правый пик.

Замечание. Экономисты так определяют оптимальность по Парето. Состояние называется оптимальным по Парето, если выполняется следующее условие: ничьё благосостояние не может быть улучшено без ухудшения благосостояния кого-либо другого (см. История экономических учений. /Под ред. В. Автономова: Учеб. Пособие. – М.: ИНФА – М, 2000. – 784 с. (стр. 242)).

Таким образом, под оптимально-компромиссным решением будем понимать одну из эффективных точек, являющуюся предпочтительней с точки зрения ЛПР. Задача векторной оптимизации не позволяет однозначно ответить на вопрос, получено ли оптимальное решение. Положительный ответ на этот вопрос зависит от качественной информации о важности частных критериев, которая имеется у ЛПР.

26. Метод последовательных уступок.

Метод последовательных уступок

Встречаются случаи, когда пользователь готов на некоторое снижение величин более важных критериев, чтобы повысить величину менее важных. В таких ситуациях можно воспользоваться методом уступок. Идею этого метода можно изложить следующим образом.

Метод последовательных уступок. Согласно этому методу локальные критерии предварительно ранжируются по важности. Затем ищется наилучшее решение по наиболее важному критерию. На следующем шаге ищется решение наилучшее по следующему по важности критерию, причем допускается потеря в значении первого критерия не более чем на некоторую обусловленную величину, т.е. делается уступка по первому критерию. На третьем шаге оптимизируется решение по третьему кри­терию, при заданных уступках по первому и второму и т.д., пока не будет рассмотрен последний по важности критерий.

При решении многокритериальных задач методом последовательных уступок вначале нужно определить важность частных критериев, т.е. расположить частные критерии в порядке убывания важности. Таким образом, главным считается критерий F₁, менее важным F₂,..., F_m. Минимизируется первый по важности критерий и определяется его наименьшее значение F_1min. Затем назначается величина допустимого снижения уступки D₁³0 критерия F₁ и ищется наименьшее значение критерия F₂ при условии, что значение F₁ должно быть не больше, чем F_1min+D₁. Снова назначается уступка D₂³0, но уже по второму критерию, которая вместе с первой используется при нахождении условного минимума F₃ и т.д. Наконец, минимизируется последний по важности критерий F_m при условии, что значения каждого критерия F_i из m-1 предыдущих должны быть не больше соответствующей величины F_imin+D_i.Получаемое в итоге решение считается оптимальным.

Таким образом, оптимальным считается всякое решение, являющимся решением последней задачи из следующей последовательности задач

 

1) Найти F_{1 min}=min F₁(X)

XÎD

 

2) Найти F_{2 min}.=min F₂(X) (1)

XÎD

F₁£ F_1min+D₁

·

·

·

m) Найти F_{m min}.=min F_m(X)

XÎD

F_i£ F_imin+D_i

i=1,2,...,m-1

Величины уступок выбирают в пределах инженерной точности, т.е. 5-10% от наименьшего значения критерия.

Пример. Пусть в области D={0;4} заданы два критерия F₁(x)=(x-1)²+1 F₂(x)=(x-2)²+2, которые нужно минимизировать (рис.1). Критерий F₁важнее критерия F₂ (F₁ предпочтительнее F₂).

Рис.1. Графики функций F₁ и F₂

 

1. Согласно алгоритму минимизируем первый по важности критерий, и определяется его наименьшее значение F_1minФормулируем задачу оптимизации

найти min F₁(x)= min[x-1)²+1]

при ограничениях

xÎ{0;4}

Минимум для первого критерия достигается в точке x_1opt=1 и равен F₁(x_1opt)=1

2. Затем назначается величина уступки D₁=0.1 критерия F₁ и ищется наименьшее значение критерия F₂ при условии, что значение F₁ должно быть не больше, чем F_1min+D₁. Таким образом, мы получили следующую задачу оптимизации

minF₂(x)=min[(x-2)²+2]

при ограничениях

xÎ{0;4}

(x-1)²+1£ 1+0.1

Для решения воспользуемся методом множителей Лагранжа. В результате получим безусловную задачу оптимизации

Ф(x, λ)= (x-2)²+2+ λ((x-1)²-0.1).

Находим частные производные и приравниваем их к нулю. В результате получим систему уравнений

Решая эту систему, получим x_2opt=1.32.

Согласно алгоритму, решение, полученное на последнем этапе и будет считается оптимальным, т.е. x_opt=1.32.

Решим данную задачу, используя систему MathCad.

f(x):=(x-2)²+2 целевая функция

x:=1 начальное приближение

Given

ограничения

0≤x≤4

(x-1)²≤0.1

p:=Minimize(f,x) p=1.316.

Ответ:. x_opt=1.32.

Зам. Метод последовательных уступок целесообразно применять для решения тех инженерных задач, в которых все частные критерии упорядочены по степени важности, причём каждый критерий настолько более важен, чем последующий, что можно ограничиться учётом только попарной связи критериев и выбирать величину допустимого снижения очередного критерия с учётом поведения лишь одного следующего критерия.

Недостатком метода являются трудности с назначением и согласованием величин уступок, возрастающие с ростом размерности векторного критерия, а также необходимость формирования неизменного для всей задачи априорного ранжирования критериев.

Как видим, в методе уступок предполагается, что разница в важности критериев не слишком велика. Можно предположить, что величина уступок как-то связана с нашим ощущением этой разницы.

 

Лексикографический критерий

Противоположным крайним случаем является ситуация, в которой разница между упорядоченными критериями настолько велика, что следующий в этом ряду критерий рассматривается только в том случае, сравниваемые альтернативы неразличимы по старшим критериям. Ни о каких уступках при этом не может быть и речи. В этой ситуации выбор довольно часто заканчивается на первом же шаге, а до последнего критерия дело обычно не доходит (точнее он “изобретается” в том чрезвычайно редком экзотическом случае, когда принятые ранее критерии не выделили единственной альтернативы). Такой выбор получил название лексикографического упорядочивания альтернатив, поскольку этот метод используется при упорядочивании слов в различных словарях (предпочтительность определяется алфавитным рангом очередной буквы в данном слове).

27.Методы «сканирования» паретовской границы на основе метода идеальной точки.

См. стр. 134 – 141 документа «ответ на вопр. 27-30»