Оптимизация решений по Парето(Отношение доминирования по Парето. Парето-оптимальность)

Содержание:

Введение

промиссный множество

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

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

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

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

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

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

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

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

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, либо использовать дополнительные условия. Здесь мы рассмотрим направление, которое связано с определением оптимальности по Парето^[1].

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

Как было сказано раньше для всякого решения 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₁ и 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)). но

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

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

Компромиссная со кривая

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

Опр. Множество ты паретовских точек из в двухмерном мы пространстве критериев за называют компромиссной вы кривой.

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

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

1. же 3 Расчёт от компромиссных кривых еще

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

Последнее во векторное уравнение со равносильно n ли скалярным алгебраическим при уравнениям которые без определяет кривую он в пространстве на параметров x_{1 что} =ϕ₁(λ), ..., x_{n тот} =ϕ_n(λ). Если это участок этой как кривой, на по котором λ≥0 но принадлежит множеству они D, то ты он принадлежит из и множеству мы P (P за - множество Парето). вы Участок КК так в этом же случае определяется от параметрическими уравнениями: еще

F₁=F₁(ϕ бы ₁(λ), ..., ϕ_n(λ)), уже

F₂=F₁(ϕ для ₁(λ), ..., ϕ_n(λ)), вот λ≥0.

Пример кто 1. В да квадрате D до ={-1≤ x_{1 ни} ≤ 1, -1≤ ну x₂ ≤ 1} под заданы два где критерия

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

1. Находим два минимумы функций там F₁ и чем F₂ . Абсолютные во минимумы находятся со в точках ли (0,0) при и (-1, без 1) и он принадлежат области на D.

2. что Находим частные тот производные

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

4x₁=-λ (x_{1 по} +1)

x_{2 но} =-λ (x₂-1). они

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

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

Приравнивая правые да части и до разрешая относительно ни x₂, получим ну уравнение паретовской под кривой P: где .

Параметрическое уравнение сам КК будет раз иметь следующий два вид

F₁(λ)= там

F₂(λ)=.

Закономерность чем КК: F₁ во возрастает от со 0 до ли 5, а при F₂ убывает без от 2 он до 0. на

Построим графики что паретовских кривых тот в области это D и как пространстве критериев по (рис. 6 но и 7). они

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

Пример так 2. В же области D от ={-0.5 еще ≤ x₁ ≤ 0. бы 5, 0 уже ≤ x₂ ≤ 1} для заданы два вот критерия

которые кто нужно минимизировать да с учетом до функциональных ограничений ни ⎥x₂-x_{1 ну} -0.375⎥ под ≥ 0.125. где

а) рассмотрим сам сначала случай раз без функциональных два ограничений

1. там Находим минимумы чем функций F₁ во и F₂. со Абсолютные минимумы ли находятся в при точках X_{1opt без} =(0,0) он и X_{2opt на} =(-1,1) что и первая тот точка принадлежат это D, а как вторая нет. по Находим условный но минимум для они функции F₂: ты X_2услов=(-0. из 5, 1); мы находим значения за F2(-0. вы 5,1)= так 0.25, же F1(-0. от 5,1)= еще 4.25. бы

2. Находим уже частные производные для

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

2x_{1 кто} =-λ (x₁+1), да

8x₂=-λ (x_{2 до} -1).

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

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

Приравнивая он правые части на и разрешая что относительно x₂, тот получим уравнение это паретовской кривой как P: . Найдём по точку пересечения но кривой с они x₁=-0. ты 5. Получим из Xп=(-0. мы 5; 0. за 2). Это вы соответствует случаю, так когда λ же меняется от от 0 до еще 1 (0 бы ≤ λ≤1). уже

Параметрическое уравнение для КК будет вот иметь следующий кто вид (когда да точки X_{1opt до} =(0,0) ни и X_{2opt ну} =(-1,1) под принадлежат области где D)

F₁(λ)= сам

F₂(λ)=.

Закономерность раз КК: F₁ два возрастает от там 0 до чем 4.25, во а F₂ со убывает от ли 2 до при 0.

Построим без графики паретовских он кривых в на области D что и пространстве тот критериев (рис. это 8 и как 9).

Xп

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

Рис. 10. за Пространство оценок вы и компромиссная так кривая

б) же введём функциональные от ограничения. Область еще D в бы этом случае уже будет иметь для вид (рис. вот 11). Находим кто условный минимум да для функции до F₁ и ни F₂ . Они ну лежат в под точках X_{1opt где} =(0,0) сам и X_{2opt раз} =(-0.5, два 1). Как там видно из чем полученных результатов во точки минимумов со не изменились. ли

Рис. 11. при Область D без Рис. 12. он Пространство оценок на

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

1.3 Способы сужения Парето-оптимального множества

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

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

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

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

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

Первый подход. да Для заданной до многокритериальной задачи ни оптимизации находится ну множество её под Парето-оптимальных где решений, а сам выбор конкретного раз оптимального варианта два из множества там Парето-оптимальных чем предоставляется ЛПР. во

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

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

Указание раз верхних границ два критериев. Дополнительная там информация об чем оптимальном исходе во X_opt∈D со в этом ли случае имеет при вид

(1) без

Число C_i он рассматривается здесь на как верхняя что граница по тот i – му это критерию.

Отметим, как что указание по верхних границ но по критериям они не может ты быть "извлечено" из из математической мы модели задачи за принятия решения; вы набор ограничений так (C₁, C₂, же , C_m) представляет от собой дополнительную еще информацию, полученную бы от ЛПР. уже

Задача. Выбор для места работы вот

Предположим, что кто Вам предстоит да выбрать место до работы из ни девяти вариантов, ну представленных в под табл.1. где В качестве сам основных критериев раз взяты: зарплата два З, длительность там отпуска Д, чем время поездки во на работу со В. Из ли смысла задачи при следует, что без критерии З он и Д на следует максимизировать, что а критерий тот В – минимизировать. это Какой вариант как является оптимальным? по

Таблица 1 но

Варианты	Критерий они
	Зарплата, (руб.) ты	Длительность отпуска, из (дни)	Время мы поездки, (мин) за
1	900 вы	20	60 так
2	500 же	30	20 от
3	700 еще	36	40 бы
4	800 уже	40	50 для
5	400 вот	60	15 кто
6	600 да	30	10 до
7	900 ни	35	60 ну
8	600 под	24	10 где
9	650 сам	35	40 раз

Решение. Выделим два вначале Парето там -оптимальные варианты. чем Отбрасывая доминируемые во по Парето со варианты {1, ли 2, 8, при 9}, получаем без Парето-оптимальное он множество {3, на 4, 5, что 6, 7}. тот При отсутствии это информации об как относительной важности по рассматриваемых критериев, но а также они о каких ты -либо дополнительных из свойствах оптимального мы решения дальнейшее за сужение Парето вы -оптимального множества так произвести нельзя. же Тогда формальный от анализ заканчивается еще указанием Парето бы -оптимального множества уже и окончательный для выбор оптимального вот варианта производится кто ЛПР из да этих пяти до вариантов на ни основе каких ну -то дополнительных под соображений.

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

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

зарплата это — не менее как 600 рублей; по

длительность отпуска но — не менее они 30 дней; ты

время поездки из — не более мы 40 минут. за

Варианты, удовлетворяющие вы этим дополнительным так ограничения: {3, же 6, 9}; от из них еще оптимальными по бы Парето являются уже варианты 3 для и 6. вот Остаётся сделать кто окончательный выбор да между вариантами до 3 и ни 6.

б) ну Субоптимизация. Пусть под в качестве где выделенного (главного, сам важнейшего) критерия раз выступает критерий два зарплата; ограничения там длительность отпуска чем — не менее во 30 дней, со время поездки ли — не более при 40 минут. без Отбросим варианты, он которые не на удовлетворяют данным что ограничениям; остаются тот варианты: {2, это 3, 5, как 6, 9}. по Из них но максимальную зарплату они имеет вариант ты 3. Этот из вариант и мы будет оптимальным. за

в) Лексикографическая вы оптимизация. Упорядочим так критерии по же относительной важности. от Например, следующим еще образом: (т. бы е. важнейший уже критерий — зарплата, для следующий за вот ним по кто важности время да поездки, наименее до важный критерий ни длительность отпуска). ну Максимальное значение под по критерию где З имеют сам варианты 1 раз и 7. два Далее сравниваем там эти варианты чем по второму во по важности со критерию В. ли Так как при время поездки без для этих он вариантов одинакова, на переходим к что третьему критерию тот Д; по это критерию длительность как отпуска лучшим по является вариант но 7, который они и является ты здесь оптимальным. из

2. Численные методы получения множеств Парето 

Часто используют так следующий подход. же Во множестве от D выбирается еще некоторая сетка, бы например, координаты уже которой определяются для с помощью вот датчика случайных кто чисел, распределённых да по равномерному до закону. Потом ни вычисляют значения ну векторного критерия под F в где точках этой сам сетки, после раз чего за два конечное число там сравнений, используя чем функцию выбора во по Парето, со строится множество ли Парето на при указанной сетке, без являющееся при он большом N на приближением множества что Парето относительно тот D (N это – число точек как сетки).

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

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

Пусть это f _{l как} ( z ) ( l по = 1, ..., L но ) целевые функции, они соответствующие системе ты L целей из производственного объекта, мы определенные на за множестве Z вы . При этом так большему значению же f _{l от} отвечает более еще высокая степень бы достижения l уже -той цели. для Можно сказать, вот что требуется кто найти решение да задачи векторной до оптимизации

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

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

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

Заключение

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

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

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

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

Список по литературы

1. но Под редакцией они д-ра ты экон. наук, из проф. В. мы А. Колемаева. за Математические методы вы и модели так исследования операций. же Издательство ЮНИТИ от -ДАНА. 2008 еще  г.

2. бы В.В. уже  Подиновский, В. для М. Гаврилов. вот Оптимизация по кто последовательно применяемым да критериям. М. до  Советское радио. ни 1975 г. ну

3. T. под В. Алесинская. где Основы логистики. сам Общие вопросы раз логистического управления. два Учебное пособие. там Таганрог: Изд чем -во ТРТУ, во 2005.

4.  со  Шепелева А. ли Ю. Логистика при  . Издательство Юнити без -дана.2010 он г.

1. Наименование указанного понятия связано с именем итальянского экономиста Вильфредо Парето [1848 – 1923 гг.]. ↑