Файл: Оптимизация решений по Парето (Численные методы получения множеств Парето).pdf

Введение

Почти всякая сложная практическая задача принятия решения индивидуального (а тем более группового) является многокритериальной.

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

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

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

Результаты исследования задач планирования и управления показывают, что в реальной постановке эти задачи являются многокритериальными. Так, часто встречающееся выражение «достичь максимального эффекта при наименьших затратах» уже означает принятие решения при двух критериях. Оценка деятельности предприятий и планирования как системы принятия решений производится на основе более десятка критериев: выполнение плана производства по объему, по номенклатуре, плана реализации, прибыли по показателям рентабельности, производительности труда и т.д.

Актуальность курсовой работы: исследование сущности оптимальности по Парето.

Цель курсовой работы — исследование сущности оптимальности по Парето, а также того, что можно предпринять, чтобы более эффективно принимать решения.

Для достижения поставленной цели необходимо решить ряд задач:

1) Понятие оптимальности по Парето;

2)Отношение доминирования по Парето. Парето-оптимальность;

3) Изучить аналитические методы построения множества Парето и тд.

Объектом данной курсовой работы является оптимальность решений по Парето, а предметом умение эффективно принимать решения по оптимальности Парето.

Ранее, при исследовании проблемы многокритериальности часто все критерии, кроме одного, выбранного доминирующим, принимались в качестве ограничений. Впервые проблема оптимизации векторного критерия была сформулирована экономистом Парето в 1896 г.

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

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

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

1.1 Отношение доминирования по Парето. Парето-оптимальность

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

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₁)<=(X₂) для всех i=1,m, и бы для j - го критерия строгое неравенство (X₁)<F_i(X₂). или

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

(X₂)≤Fi(X₁) при функции Fi,

(X₂)≥Fi(X₁) при Fi.

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

Определение: X₁∈D называется эффективной ( по Парето), не существует X₂∈D такой, что (X₂) ≤Fi(X₁), i=1, . . ., m, F(X₂)≠F(X₁), или:

: Если решение доминируемо никаким решением, то называется недоминируемым оптимальным в смысле .^[2]

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

.^[3] Множество векторных , соответствующих множеству точек, называют компромиссов (переговорным ) или множеством в области критериев. обозначать Y_P ( ⊆Y_D).

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

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

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

. 1

Критерии F1 и F2 непротиворечивы

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

Рис. 2

F1 и F2 противоречивы на [1; 2]

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

приём выделения решений на задачи с двумя 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₅ по Парето.^[5]

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

Рис. 3

Множество

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

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

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

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

. 4

Пространство оценок и компромиссная кривая ( цвет)

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

. Экономисты так оптимальность по . Состояние называется по Парето, выполняется следующее : ничьё благосостояние может быть без ухудшения кого-либо .

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

1.2 Аналитические методы множества Парето

кривая:^[7]

Особый для практики — m=2. В случае множество точек представляет одномерное многообразие плоскости и допускает графическое представление.

. ^[8]Множество паретовских в двухмерном пространстве называют компромиссной .

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

Рис. 5

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

1.3 Примеры компромиссных кривых

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

Последнее векторное равносильно n скалярным уравнениям которые кривую в пространстве x₁=ϕ₁(λ), ..., x_n=ϕ_n(λ). Если этой кривой, котором λ≥0 принадлежит D, то он и множеству P (P - множество ). Участок КК в случае определяется уравнениями:^[9]