Метод оптимизации по Парето

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО РЫБОЛОВСТВУ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Курсовая работа на тему

Метод оптимизации по Парето

Выполнил: Студент 4 курса

Группы ЛОГ-402

Панюшкин В.А.

Проверил: Яретенко Н.И.

Мурманск 2014

Содержание

Введение

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

1.1 Отношение доминирования по Парето

1.2 Аналитические методы построения по Парето. Парето-оптимальность

1.3 Расчет компромисных кривых

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

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

Заключение

Список использованной литературы

Введение

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

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

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

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

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

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

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

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

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

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

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

min f(X)

XD

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

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

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

Как было сказано раньше для всякого решения XD набор его оценок по всем критериям, т.е. набор (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 (PD).

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

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

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

Если область критериев Y_D состоит только из области согласия Y_c, то существует единственная точка X_optD, в которой все частные критерии согласованны между собой в том смысле, что при движении к точке 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₁ (критерии минимизируются).

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

В случае, когда множество допустимых исходов является непрерывным, их векторные оценки "заполняют" некоторую область 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₂=u(F₁) и F₁=v(F₂).

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

1.3 Расчёт компромиссных кривых

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

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

F₁=F₁(₁(), ..., _n()),

F₂=F₁(₁(), ..., _n()), 0.

Пример 1. В квадрате D={-1 x₁ 1, -1 x₂ 1} заданы два критерия

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

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

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

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

4x₁=- (x₁+1)

x₂=- (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₁-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₁=- (x₁+1),

8x₂=- (x₂-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).

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

(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 г.

Размещено на Allbest.ru

...