Файл: Оптимизация решений по Парето (Теоретические аспекты решений Парето).pdf

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

Эффективность экономики по Парето предполагает выполнение трех условий:

- эффективность распределения

- эффективность производства

- эффективность выпуска

Глава 2. Анализ оптимизации решений по Парето

2.1 Оптимальность по Парето

Для облегчения результатов полезно всё время проводить аналогию с однокритериальным (классическим) случаем. Пусть имеется область D и задана функция f – целевая функция (критерий). Задача оптимизации имеет вид

min f(X)

X∈D

Точка X₁∈D называется оптимальной (недоминируемой, неулучшаемой), если не существует точки X₂∈D, для которой f(X₁)>f(X₂) (целевая функция минимизируется). Аналогично в МЗО можно исключить из области D точки, которые заведомо не могут оказаться наилучшими.

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

Как было сказано раньше для всякого решения X∈D набор его оценок по всем критериям, т.е. набор (F₁(X), F₂(X), . . .,Fm(X)), есть векторная оценка решения X. Векторная оценка X содержит полную информацию о ценности (полезности) этого решения для ЛПР и сравнение любых двух решений заменяется сравнение их векторных оценок. Пусть в МЗО требуется получить меньшие значения каждого частного критерия (минимизировать частные критерии) Fi(X).

Опр. Пусть имеются два решения 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.

В области Y_c нет противоречия между частными критериями оптимальности, т.к. каждая точка X∈D может быть изменена таким образом, что будет одновременно улучшены все частные критерии.

Если область критериев Y_D состоит только из области согласия Y_c, то существует единственная точка X_opt∈D, в которой все частные критерии согласованны между собой в том смысле, что при движении к точке X_opt все F_i(X) i=1, 2, . . ., m, одновременно улучшаются. Все частные критерии достигают минимума в т. X_opt (см. рис. 1). Такую точку называют оптимальным решение и при этом значения всех частных критериев достигают в ней минимума.

---

Рис. 1. Критерии F₁ и F₂ непротиворечивы

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

Рис. 2. Критерии F₁ и F₂ противоречивы на отрезке [1; 2]

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

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

Построим пространство нашей Как паре соответствует на Занумеруем соответственно решения 3). рисунка что точки на верхней области решений решить задачу, оба нужно

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

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

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

Замечание. определения точек правило Уголок ∟ для компромиссных в пространстве, критерии а ┐когда минимизируются [6,

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

Рис. Пространство Y_D и кривая цвет)

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

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

---

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

Компромиссная [2,

Особый для — В случае паретовских представляет одномерное на и удобное представление.

Опр. паретовских в пространстве называют компромиссной .

Она состоять несвязных и изолированные (см. 5). кривая строго убывает следующем Пусть ₁ и ₂ точки, КК. их Y₁(y1,y2) Y₂(y3,y4), y1<y3, y2>y4. образом, не ни ни отрезков её может представлено форме ₂=u(F₁) F₁=v(F₂).

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

Аналитический . функции ₁(X) F₂(X) то попытаться геометрическое точек поверхностей F₁(X)=b1 F₂(X)=b2. таких gradF₁=-gradFλ₂, .≤λ<∞

Последнее уравнение n алгебраическим которые кривую пространстве x₁=ϕ₁(), xλ_n=ϕ_n(). участок кривой, котором принадлежит D, он и P - Парето). КК этом определяется уравнениями:λλ≥

F₁=F₁(ϕ₁(), λϕ_n()),λ

F₂=F₁(ϕ₁(), λϕ_n()), λλ≥

Пример В D={-1 ≤₁ ≤ -1 ≤₂ ≤ заданы критерия

которые минимизировать.

1. минимумы F₁ F₂ Абсолютные находятся точках и и области

2. частные

составляем уравнений

4x₁=- λ₁+1)

x₂=- λ₂-1).

Отсюда параметрическое кривой пространстве

В случае получить этой в прямоугольных Для решаем уравнения параметра Получимλ

Приравнивая части разрешая x₂, уравнение кривой .

Параметрическое КК иметь вид

F₁()=λ

F₂()=.λ

Закономерность F₁ от до а ₂ от до

Построим паретовских в D пространстве (рис. и

Рис. Область D множество P 7. кривая

Пример . области x≤₁ ≤ 0 ≤₂ ≤ заданы критерия

которые минимизировать учетом ограничений ⎥₂-x₁-0.375 ⎥≥

---

а) сначала без ограничений

1. минимумы F₁ и ₂. минимумы в X_1opt=(0,0) X_2opt=(-1,1) первая принадлежат а нет. условный для F₂: X_2услов=(-0.5, находим F2(-0.5,1)=0.25, F1(-0.5,1)=4.25.

2. частные

составляем уравнений

2x₁=- λ₁+1),

8x₂=- λ₂-1).

Отсюда параметрическое кривой пространстве

В случае получить этой в прямоугольных Для решаем уравнения параметра Получимλ

Приравнивая части разрешая x₂, уравнение кривой . точку кривой x₁=-0.5. Xп=(-0.5; Это случаю, λ от до (0≤

Параметрическое КК иметь вид точки X_1opt=(0,0) X_2opt=(-1,1) области

F₁()=λ

F₂()=.λ

Закономерность F₁ от до а ₂ от до

Построим паретовских в D пространстве (рис. и [7,

Xп

Рис. Область D множество P Рис. Компромиссная

Рис. Пространство и кривая

б) функциональные Область в случае иметь (рис. Находим минимум функции ₁ F₂ Они в X_1opt=(0,0) X_2opt=(-0.5, Как из результатов минимумов изменились.

Рис. Область Рис. Пространство

Из примера что множества в виде сложной Поэтому настоящее широко численные построения оптимальных Парето раздел методы множеств

Выделение Парето часто является решением. связано тем, при большом множестве множество оказывается большим того, ЛПР бы состоянии выбор Таким выделение Парето рассматривать как этап и проблема сокращения множества.

Для одной стратегии множества решений каждой многокритериальной необходимо дополнительную о операции, ту которая задании критерия неформализованной потому

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

Необходимо что сужения Парето существенным многих многокритериальной Многокритериальная Математические /Б.А Ю.М. и - Наука, - с.

---