Методы многокритериальной оптимизации. Многокритериальная оптимизация

1.2. Многокритериальная оптимизация

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

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

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

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

1. Разработка концепции оптимальности.

2. Доказательство существования решения, оптимального в соответствующем смысле.

3. Разработка методов нахождения оптимального решения.

Обозначим i-й частный критерий через, а область допустимых решений черезQ. Учтем, что изменением знака функции всегда можно свести задачу минимизации к задаче максимизации, и наоборот, мы можем сформулировать кратко задачу векторной оптимизации следующим образом:

, при (1.5)

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

Например, выбирая работу, человек, как правило, руководствуется несколькими критериями. Допустим, кому-то хочется, чтобы одновременно выполнялись такие условия:

- заработная плата была как можно выше;

- условия работы были как можно комфортнее;

- место работы было как можно ближе к дому.

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

Еще один пример – выбор инвестиционного решения, когда хочется получить максимальный доход (или доходность) при наименьшем риске [51].

Примеры многокритериальности в экономике

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

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

1. Планирование производства: – mах – суммарный чистый доход, минимальный чистый доход за любой период; – min – число невыполненных заказов, сверхурочное время, запасы готовой продукции.

2. Выбор портфеля ценных бумаг: – mах – доход, дивиденды; – min – риск, отклонения от желаемого уровня разнообразия бумаг.

3. Составление сметы капиталовложений: – mах – наличие средств, инвестиции в проекты, связанные с охраной окружающей среды, инвестиция в проекты в заданном регионе, инвестиции в проекты по заданной товарной специализации;

– min – спрос на капитальные вложения, ежегодные эксплуатационные расходы.

4. Управление лесным хозяйством: – max – устойчивый урожай древесины, человеко-дни отдыха в лесу, человеко-дни охоты в лесу, ареал распространения диких животных, число месяцев выпаса домашних животных; – min – превышения бюджета.

5. Управление попусками водохранилищ: – max – выгоды от рекреации на водохранилище № 1, выгоды от зарегулирования стока ниже водохранилища № 1, количество энергии, вырабатываемой в бассейне реки, выгоды от рекреации на водохранилище № 2, прибыль от орошения земель ниже водохранилища № 2;

– min – недопоставки воды на коммунальные нужды в бассейне реки.

6. Формирование ревизионной службы в фирме: – max – доход, время, отведенное на профессиональный рост – min – рост численности персонала службы, уменьшение численности персонала службы, избыточные сверхурочные, недоиспользование квалификации кадров;

7. Транспортировка: – max – производство по заданной технологии;

– min – стоимость, среднее время доставки грузов приоритетным клиентам, расход топлива.

Конечно, решения, которое одновременно удовлетворяло бы всем противоречивым требованиям, как правило, не существует. Но математика может помочь и при решении таких задач. Помощь эта состоит не в нахождении несуществующего решения, одновременно обращающего все критерии в максимум, а в отбрасывании заведомо плохих решений [28,37,51].

Оптимизация по Парето

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

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

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

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

Проиллюстрируем это на примере, где нужно выбрать стратегию развития предприятия, критерии - ожидаемая прибыль в год (в смысле мат. ожидания из теории вероятностей), надёжность стратегии (вероятность того, что будет приемлемая для нас прибыль, хоть сколько-нибудь солидный доход) [37]. Допустим, у нас есть 5 стратегий:

Рис. 1.2. График оптимального плана развития предприятий

Стратегия 2 в среднем даёт больше прибыли, чем стратегия 1, при той же надёжности. Стало быть, стратегия 1 не может быть лучшей. Стратегия 3 по ожидаемой прибыли равноценна стратегии 2, но надёжнее. Стало быть, стратегия 2 тоже невыгодна. Стратегия 3 прибыльнее стратегии 4 при той же надёжность, то есть стратегия 4 тоже неоправданно. Остаются только стратегии 3 и 5. По одному критерию превосходит одна, по другому - другая.

Операции, оптимальные по Парето, не обязательно являются «самыми лучшими» - эти операции не являются худшими. Чтобы выбрать конкретное решение из Парето-оптимального множества, нужны дополнительные данные [21]. Выделение множества Парето ещё не даёт ответа на вопрос, какое решение оптимальное, но оно значительно упрощает применение алгоритмов, работающих с дополнительной информацией, поскольку сужает множество возможных вариантов [37,51].

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

studfiles.net

Многокритериальная оптимизация - это... Что такое Многокритериальная оптимизация?

Многокритериальная оптимизация или программирование (англ. Multi-objective optimization),[1][2] — это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.

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

Определение

Задача многокритериальной оптимизации формулируется следующим образом:[3]

где это () целевых функций. Векторы решений относятся к непустой области определения .

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

Эталонные точки

Для возможности оценки качества найденных решений обычно рассматривают такие точки в области значения целевой функции:

идеальная точка ,
утопическая точка ,
надир .

В некоторых случаях эти точки могут быть решениями.

Идеальная точка определяется как вектор , каждая из координат которого имеет оптимальное значение соответствующей составляющей целевой функции:[5]

Точка надир определяется как вектор:

Утопическую точку вычисляют на основе идеальной:[6]

где , — единичный вектор.

Критерий Парето

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

Множество оптимальных по Парето векторов является подмножеством оптимальных по Парето в слабом смысле векторов. Вектор является слабым оптимумом по Парето тогда, когда не существует вектора такого, что для всех .

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

Множество оптимальных по Парето решений также называют Парето-фронтом (англ. Pareto-frontier).

Лексикографический порядок

Если одни целевые функции важнее других, критерий оптимальности можно определить по лексикографическому порядку.

Отношение лексикографического порядка между векторами и выполняется, если , где . То есть, первая компонента вектора меньше компоненты вектора , а компоненты — уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным.

Вектор является лексикографическим решением, если не существует вектора , такого, что .

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

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

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

Скаляризация

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

Пусть - функция скаляризации, что превращает векторную функцию в скалярную. Если сохраняет упорядоченность по Парето , то есть, если для произвольных выполняется:

тогда решение , что минимизирует до , является решением по Парето.[7] Если сохраняет отношение порядка в , то есть, если для произвольных выполняется:

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

Взвешенная сумма

Приведенная функция сохраняет упорядоченность по Парето для . Поэтому решения, минимизирующие до для произвольных являются оптимальными по Парето. Однако не сохраняет упорядоченность по Парето для , а сохраняет лишь отношение , поэтому решения, минимизирующие на для являются слабыми по Парето.[7]

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

Функция скаляризации Чебышева

Взвешенная функция скаляризации Чебышева сохраняет отношения и поэтому минимум является слабым по Парето.[7]

Метод изменения ограничений (ε-ограничения)

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

при условиях

Значения могут рассматриваться как допустимые уровни для .

Методы решения

Интерактивность

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

Эволюционные методы

Упоминания о применении генетических алгоритмов для решения задачи многокритериальной оптимизации относятся к концу 1960-х [8].

Примечания

↑ Steuer R.E. Multiple Criteria Optimization: Theory, Computations, and Application. — New York: John Wiley & Sons, Inc. — ISBN 047188846X
↑ Sawaragi Y. Theory of Multiobjective Optimization (vol. 176 of Mathematics in Science and Engineering). — Orlando, FL: Academic Press Inc. — ISBN 0126203709
↑ 1 2 Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen та Roman Slowinski Multiobjective Optimization: Interactive and Evolutionary Approaches (Lecture Notes in Computer Science). — Springer. — ISBN 3-540-88907-8
↑ A. Osyzka. «Multicriteria optimization for engineering design». Design Optimization (Academic Press): 193-227.
↑ (Ehrgott, c. 34)
↑ (Jürgen et al, с. XI)
↑ 1 2 3 Sequential Approximate Multiobjective Optimization Using Computational Intelligence (Vector Optimization). — Springer. — ISBN 978-3-540-88909-0
↑ R. S. Rosenberg Simulation of genetic populations with biochemical properties. — University of Michigan, 1967.

См. также

Литература

Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. — М: Радио и связь, 1981. — 560 с.
Matthias Ehrgott Multicriteria Optimization. — Springer. — ISBN 3-540-21398-8
M. Ehrgott and X. Gandibleux (2004). «Approximative Solution Methods for Multiobjective Combinatorial Optimization». TOP (Sociedad de Estadística e Investigación Operativa) 12 (1).

Ресурсы интернета

dic.academic.ru

Многокритериальная оптимизация - n1.doc

приобрестиМногокритериальная оптимизацияскачать (440.5 kb.)Доступные файлы (1):

n1.doc

Многокритериальная оптимизация.

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

Задачи подобного рода принято называть многокритериальными задачами, или задачами с векторным критерием.

Множество Парето.

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

Пусть М – произвольная точка множества , внутренняя или граничная, и (U,V) – ее координаты. Поставим следующий вопрос: можно ли оставаясь на множестве , переместиться из точки М в близкую точку так, чтобы при этом увеличились обе ее координаты? Если М – внутренняя точка, то это, бесспорно, возможно. Если же М – граничная точка, то такое возможно не всегда (рис. 2). Из точек М1, М2 и М3 это сделать можно, но уже из точек вертикального отрезка АВ можно переместиться, увеличивая лишь координату V (координата U при этом остается неизменной). Перемещая точку горизонтального отрезка PQ вправо, мы увеличиваем координату U (при этом координата V сохраняет свое значение). Что же касается дуги BQ, то перемещение вдоль нее способно лишь увеличить одну из координат при одновременном уменьшении другой.

Тем самым точки множества можно разбить на три класса:

Множество точек третьего класса называется границей (множеством) Парето данного множества (выделено на рис. 3).

Говоря нестрого, граница Парето множества - это точки, из которых нельзя сдвинуться на «север», «восток» либо «северо-восток», оставаясь в том же множестве .

На рисунке 4 указаны границы Парето некоторых множеств. 1.2. Методы решения задач многокритериальной оптимизации.

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

Перечислим некоторые из подходов к задачам многокритериальной оптимизации.

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

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

Метод свертывания – лицо, принимающее решения (руководитель), сводит многокритериальную задачу к задаче с одним критерием.

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

Метод анализа иерархий – на основании суждений экспертов оценивается вклад в общую оценку каждого критерия.

1.2.1. Метод идеальной точки.

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

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

Рассмотрим конкретный пример поиска идеальной точки.

Пример 1. Пусть на множестве плоскости , определяемом системой неравенств

заданы две линейные функции

1.1.

Требуется найти решение задачи

при условии, что .

Множество представляет собой квадрат (рис. 5), вершины которого имеют координаты

А (0,0), В (0,2), С (2,2), D (2,0).

В силу линейности критериев U и V квадрат ABCD переходит в параллелограмм PQRS (рис. 6), координаты вершин которого вычисляются по формулам 2.1. и равны:

P (2, 2), Q (0, 8), R (10, 6), S (12, 0).

Точка утопии М* (12,8) считается заданной (ее координаты равны наибольшим значениям U и V).

Граница Парето параллелограмма PQRS состоит из двух отрезков – QR и RS (рис. 7).

Точка, ближайшая к точке утопии М*, принадлежит множеству Парето и должна лежать на одном из составляющих его отрезков – или на отрезке QR, или на отрезке RS.

Чтобы найти на отрезке QR точку, ближайшую к точке М*, воспользуемся прямой, проходящей через точки Q и R.

Подставляя в общее уравнение прямой

координаты точек Q и R,

Найдем соответствующие значения параметров и

Из первого равенства получаем, что а из второго, что

Предположим, что Тогда и U+5V=40 – уравнение искомой прямой.

Теперь стоит напомнить, что ищется расстояние между точками, заданными своими координатами.

Пусть (U1,V2) и (U2,V2) – точки на плоскости (U,V). Для того, чтобы найти расстояние между ними, достаточно вычислить длину гипотенузы построенного прямоугольного треугольника (рис. 8).

Воспользовавшись теоремой Пифагора, получим, что расстояние между этими точками равно

Чтобы отыскать на прямой, описываемой уравнением

U+5V=40,

Точку М0(U0,V0), ближайшую к точке М*(12, 8), нужно решить экстремальную задачу

1.2.

при условии, что U+5V=40.

Заменяя в формуле 1.2. U на 40-5V, приходим к задаче

Возводя в квадрат и приводя подобные, получаем, что

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

Из рисунка 9 видно, что точка на прямой QR, ближайшая к точке утопии М*, лежит вне отрезка QR: справа от точки R (U>10) и ниже ее (V

Поиск точки, ближайшей к точке утопии М*, на прямой RS приводит к аналогичному результату: .

Найденная точка лежит вне отрезка RS:U6.

Возьмем окружность с центром в точке М* столь малого радиуса, чтобы она не пересекалась с множеством , и будем постепенно увеличивать радиус этой окружности (сохраняя центр в точке М*) до тех пор, пока она не коснется множества . Из полученных выше результатов ясно, что эта окружность встретит ломаную QRS в точке R(10,6), которая и будет ближайшей к точке утопии М*, то есть идеальной точкой.

Найденная идеальная точка отстоит от точки утопии М* (12,8) на расстоянии , равном радиусу построенной окружности (рис.10).

Соответствующие значения x* и y* легко находятся из системы линейных уравнений

Имеем x*=2, y*=2.Пример 2. Пусть на множестве

(Рис )заданы две линейные функции:

и (2. 2)

Требуется найти решение задачи

, (2. 3)

при условии, что точка утопии М* имеет координаты (2,-2).

Рис. 11 а, б, в.

Введем новую функцию

(2.4).

Тогда требование (2.3) можно записать так:

Соответственно изменится и точка утопии - N*(2,2).

Функции и

линейны и преобразуют единичный квадрат в параллелограмм (рис 11 а, б), при этом вершины квадрата (0,0), (1,0), (1,1), (0,1) переходят в вершины параллелограмма (0,1), (2,0), (2,1), (0,2).

Множество Парето образуют точки отрезка с концами А(0,2) и В(2,1) (рис 11, в). Проведем через эти точки прямую и найдем коэффициенты ее уравнения .

Подставляя в него координаты точек А и В, получаем, что и .

Предположим, что . Тогда и . Тем самым уравнение искомой прямой имеет вид: U+2W=4.

Пусть О* (U,W) – точка этой прямой, ближайшая к точке N*(2,2). Это значит, что должно выполняться условие

Так как U=4-2W, то оно принимает следующий вид:

Рис. 12.

Чтобы найти минимальное значение функции (рис. 12), приравняем к нулю ее производную. Имеем: .

Отсюда , .

Соответствующие значения и находятся из уравнений (2.2).

Получаем, что , а .

Расстояние от найденной точки О* до точки утопии N*(2,2) равно 2/.

Ответ: идеальная точка находится от заданной точки утопии

М*(2,-2) на расстоянии 2/.

Обычно идеальная точка не принадлежит множеству F. Если она все-таки принадлежит множеству F, то именно точка будет решением многокритериальной задачи в пространстве критериев Rm. Введем понятие расстояния между двумя точками ?(a,b) в пространстве Rm

При s=1 получаем (метрика 1).

При s=? получим равномерную (нормальную) метрику:

Теперь решение многокритериальной задачи можно свести к решению обычной однокритериальной задачи оптимизации (*).

Отсюда можно сделать вывод, что для всякого s?[1,?) любое решение задачи (*) является эффективной точкой, то есть множество оптимальных решений задачи (*) вложено во множество Парето.

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

Пример 3. Используя равномерную метрику, методом идеальной точки найдем решение следующей двухкритериальной задачи:

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

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

Графическое решение задачи представлено на рисунке 13.

Как видно из рисунка, линии уровня функции имеют вид квадратов с центром в идеальной точке =(7,14). Интересующая нас точка удовлетворяет условию и принадлежит отрезку в пространстве критериев, а соответствующая ей в пространстве решений точка x0- отрезку (x3,x4). Исходя из этих условий, находим x0=(19/5;3), f0=(26/5;61/5).

1.2.1. Ранжирование критериев.

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

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

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

Ищем максимальное значение f1* первого критерия f1(x) на всем множестве допустимых решений. Затем назначаем величину «допустимого» снижения (уступки) ?1 критерия f1(x) и определяем наибольшее значение f2* второго критерия f2(x) при условии, что значение первого критерия должно быть не меньше, чем f1* - . Затем назначаем величину «допустимого» снижения (уступки) ?2 критерия f2(x) и определяем наибольшее значение f3* третьего критерия f=f3(x) при условии, что значение второго критерия должно быть не меньше, чем f2* - и т.д.

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

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

;

для i=1,2,...,5.

Упорядочим критерии согласно их нумерации, то есть будем в начале работать с критерием f1(x), а затем с критерием f2(x).

Применив симплекс – метод и вычислив относительные оценки для функции f=f1(x), получаем симплекс таблицу (табл. 1 а):

Таблица 1 а, б.

Далее переходим к решению задачи

при ограничениях исходной задачи, к которым добавлено новое ограничение :

;

для i=1,2,...,5.

Новое ограничение преобразуем в равенство и заменим переменные , используя таблицу 1б, выражениями:

В результате этих преобразований дополнительно введенное ограничение примет вид: .

Итак, получили задачу параметрического программирования с параметром в правой части ограничений.

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

Из этой системы неравенств получаем 0 ? ? ? 9. При любом фиксированном значении параметра ? из отрезка [0,9] единственным решением задачи является точка x*=(1+(-1/9)?, 0, 3+(-1/9)?, 0+1/3?, 3+1/3?). Эта точка принадлежит множеству Парето.

Таблицы 2,3.

Ответ: при 0 ? ? ? 9 точка из множества Парето (эффективная точка)

x* = (1+(-1/9)?, 0, 3+(-1/9)?, 0+1/3?, 3+1/3?).

nashaucheba.ru

Методы многокритериальной оптимизации

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

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

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

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

В задачах 2, 3, 4-го типа частные критерии имеют обычно единую размерность.

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

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

для критериев, которые стремятся увеличивать, и

для критериев, которые стремятся уменьшить. При этом иозначают соответственно максимальное или минимальное значениеp-го критерия оптимальности.

Таким образом, после нормировки вместо матрицы , в который элементы столбцов имели различную размерность, получается матрица, размерность элементов которой от 0 до 1:.

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

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

критерий справедливости абсолютной уступки

;

критерий справедливой относительной уступки

где – нормированное значениеp-го критерия оптимальности;λp– коэффициент важности сверткиp-го критерия.

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

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

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

Укрупненный алгоритм модифицированной процедуры следующий.

1.Ввод исходной информации для расчета значений критериев и ограничений математической модели.

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

3. Решение задачи отыскания оптимального решения (базового) решения модели на основе единой целевой функции

. (3.9)

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

Например, при наличии трех критериев оптимальности возможно формирование трех вариантов (), близких к базовому по критериям

если предполагается увеличение на величину епервого критерия;

если увеличивается второй критерий, и

при увеличении третьего критерия.

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

6. Анализ базового или близких к нему вариантов решения ЛПР и ввод парных предпочтений для каждого из вариантов решений по отношению к базовому («+» – вариант более предпочтителен, чем базовое решения; «-» – вариант менее предпочтителен, чем базовое решение).

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

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

. (3.10)

При этом ограничения при максимизации единой целевой функции имеют вид:

а) для каждого k-го варианта, который признан ЛПР более предпочтительным, чем базовый,

, (3.11)

где ξ –некое достаточно малое число, например,ξ=0,001;– значениеp-го критерия дляk- го и базового вариантов соответственно;

б) для каждого k-го варианта, который признан ЛПР менее предпочтительным, чем базовый, записываются ограничения вида

; (3.12)

В) получивший набор значений должен соответствовать условию

. (3.13)

Получение новых значений коэффициентов свертки критериев () при решении математической модели (3.10) – (3.13) с помощью симплекс-метода и переход к блоку 3.

При минимизации единой целевой функции (3.9) ограничения (3.11) и (3.12) меняются местами.

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

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

studfiles.net

Многокритериальная оптимизация Википедия

Многокритериальная оптимизация, или программирование (англ. Multi-objective optimization)[1][2] — это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения.

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

Определение[ | код]

Задача многокритериальной оптимизации формулируется следующим образом:[3]

minx→{f1(x→),f2(x→),…,fk(x→)},{\displaystyle \min _{\vec {x}}\{f_{1}({\vec {x}}),f_{2}({\vec {x}}),\dots ,f_{k}({\vec {x}})\},} x→∈S{\displaystyle {\vec {x}}\in S}

где fi:Rn→R{\displaystyle f_{i}:R^{n}\to R} это k{\displaystyle k} (k⩾2{\displaystyle k\geqslant 2}) целевых функций. Векторы решений x→=(x1,x2,…,xn)T{\displaystyle {\vec {x}}=(x_{1},x_{2},\dots ,x_{n})^{T}} относятся к непустой области определения S{\displaystyle S}.

Эталонные точки[ | код]

идеальная точка yI{\displaystyle y^{I}}

ru-wiki.ru

Многокритериальная оптимизация — Википедия (с комментариями)

Материал из Википедии — свободной энциклопедии

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

Определение

Задача многокритериальной оптимизации формулируется следующим образом:[3]

где <math>f_i: R^n \to R</math> это <math>k</math> (<math>k\geqslant 2</math>) целевых функций. Векторы решений <math>\vec x = (x_1, x_2, \dots, x_n)^T</math> относятся к непустой области определения <math>S</math>.

Эталонные точки

идеальная точка <math>y^I</math>,
утопическая точка <math>y^U</math>,
надир <math>y^N</math>.

В некоторых случаях эти точки могут быть решениями.

Идеальная точка определяется как вектор <math>y^I = (y_1^I, \dots, y_p^I)</math>, каждая из координат которого имеет оптимальное значение соответствующей составляющей целевой функции:[5]

Точка надир <math>y^N = (y_1^N, \dots, y_p^N)</math> определяется как вектор:

<math>y^N_k = \max_{x\in X_E} y_k(x) = \max_{y\in Y_N} y_k, \qquad k = 1, \dots, p.</math>

Утопическую точку <math>y^U</math> вычисляют на основе идеальной:[6]

<math>y^U = y^I - \varepsilon U,</math>

где <math>\varepsilon > 0</math>, <math>U</math> — единичный вектор.

Критерий Парето

Вектор решения <math>\vec x'\in S</math> называется оптимальным по Парето, если не существует <math>\vec x\in S</math> такого, что <math>f_i(\vec x) \leqslant f_i(\vec x')</math> для всех <math>i=1, \dots, k</math> и <math>f_i(\vec x') < f_i(\vec x) </math> для хотя бы одного <math>i</math>. Множество оптимальных по Парето решений можно обозначить как <math>P(S)</math>. Целевой вектор является оптимальным по Парето, если соответствующий ему вектор из области определения также оптимален по Парето. Множество оптимальных по Парето целевых векторов можно обозначить как <math>P(Z)</math>.

Множество оптимальных по Парето векторов является подмножеством оптимальных по Парето в слабом смысле векторов. Вектор <math>\vec x'\in S</math> является слабым оптимумом по Парето тогда, когда не существует вектора <math>\vec x\in S</math> такого, что <math>f_i(\vec x) < f_i(\vec x')</math> для всех <math>i=1, 2, \dots, k</math>.

Диапазон значений оптимальных по Парето решений в области допустимых значений дает полезную информацию об исследуемой задаче, если целевые функции ограничены областью определения. Нижние границы оптимального по Парето множества представлены в «идеальном целевом векторе» <math>\vec z \in R^k</math>. Его компоненты <math>z_i</math> получены путём минимализации каждой целевой функции в пределах области определения.

Множество оптимальных по Парето решений также называют Парето-фронтом (англ. Pareto-frontier).

Лексикографический порядок

Отношение лексикографического порядка <math><_{\mathrm{lex}}</math> между векторами <math>\vec a</math> и <math>\vec b</math> выполняется, если <math>a_q < b_q</math>, где <math>q = \min \left\{k : a_k \neq b_k\right\}</math>. То есть, первая <math>q</math> компонента вектора <math>\vec a</math> меньше компоненты вектора <math>\vec b</math>, а компоненты <math>q+1</math> — уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным.

Вектор <math>\vec x \in X</math> является лексикографическим решением, если не существует вектора <math>\vec x' \in X</math>, такого, что <math>f(\vec x') <_{\mathrm{lex}} f(\vec x)</math>.

Поскольку отношение лексикографического порядка является линейным, можно доказать, что вектор <math>\vec x</math> является лексикографическим решением, если для всех <math>\vec x' \in X</math> выполняется:

Основной особенностью решений по лексикографическому порядку является существование выбора между критериями. Лексикографическая упорядоченность требует ранжирования критериев в том смысле, что оптимизация по критерию <math>f_k</math> возможна лишь тогда, когда был достигнут оптимум для предыдущих критериев. Это означает, что первый критерий имеет наибольший приоритет, и только в случае существования нескольких решений по этому критерию будет поиск решений по второму и остальным критериям.

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

Скаляризация

Скалярное ранжирование

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

Пусть <math>F</math> — функция скаляризации, что превращает векторную функцию <math>\vec y = \vec f (\vec x)</math> в скалярную. Если <math>F</math> сохраняет упорядоченность по Парето <math>\vec y</math>, то есть, если для произвольных <math>\vec y^1, \vec y^2 \in \vec f(X)</math> выполняется:

<math>\vec y^1 \leqslant \vec y^2 \implies F (\vec y^1 ) < F (\vec y^2),</math>

тогда решение <math>\vec x^0</math>, что минимизирует <math>F</math> до <math>X</math>, является решением по Парето.[7] Если <math>F</math> сохраняет отношение порядка <math><</math> в <math>\vec y</math>, то есть, если для произвольных <math>\vec y^1, \vec y^2 \in \vec f(X)</math> выполняется:

тогда решение <math>\vec x^0</math>, что минимизирует <math>F</math> до <math>X</math>, является слабым по Парето. Если <math>F</math> непрерывна на <math>\vec y</math> и <math>\vec x^0</math> единственная точка минимума <math>F</math> на <math>X</math>, тогда <math>\vec x^0</math> является решением по Парето.

Взвешенная сумма

Приведенная функция <math>F_1</math> сохраняет упорядоченность по Парето для <math>w > 0</math>. Поэтому решения, минимизирующие <math>F_1</math> до <math>X</math> для произвольных <math>w > 0</math> являются оптимальными по Парето. Однако <math>F_1</math> не сохраняет упорядоченность по Парето для <math>w \geqslant 0</math>, а сохраняет лишь отношение <math><</math>, поэтому решения, минимизирующие <math>F_1</math> на <math>X</math> для <math>w \geqslant 0</math> являются слабыми по Парето.[7]

Функция скаляризации Чебышёва

<math>F_\infty (\vec f(\vec x)) = \max_{1\leqslant i \leqslant r} w_i f_i(\vec x).</math>

Взвешенная функция скаляризации Чебышёва сохраняет отношения <math><</math> и поэтому минимум <math>F_\infty</math> является слабым по Парето.[7]

Метод изменения ограничений (ε-ограничения)

По методу изменения ограничений одну из целевых функций оставляют в качестве целевой, а остальные превращают в ограничения. То есть, пусть <math>f_r</math> будет целевой, а остальные <math>f_1, \dots, f_{r-1}</math> представим как ограничение неравенства:

<math>\min_x f_r(\vec x),</math> при условиях <math>f_i(\vec x) \leqslant \varepsilon_i, i = 1, \dots, r - 1,</math> <math>\vec x \in X.</math>

Значения <math>\varepsilon_1, \dots, \varepsilon_{r-1}</math> могут рассматриваться как допустимые уровни для <math>f_1, \dots, f_{r-1}.</math>.

Методы решения

Интерактивность

Эволюционные методы

Метод исследования пространства параметров

Метод основан на построении допустимого и Парето-оптимального множеств решений. Позволяет решать задачи проектирования, идентификации[9].

См. также

Напишите отзыв о статье "Многокритериальная оптимизация"

Примечания

↑ Steuer R.E. Multiple Criteria Optimization: Theory, Computations, and Application. — New York: John Wiley & Sons, Inc. — ISBN 047188846X.
↑ Sawaragi Y. Theory of Multiobjective Optimization (vol. 176 of Mathematics in Science and Engineering). — Orlando, FL: Academic Press Inc. — ISBN 0126203709.
↑ 1 2 Jürgen Branke, Kalyanmoy Deb, Kaisa Miettinen та Roman Slowinski. Multiobjective Optimization: Interactive and Evolutionary Approaches (Lecture Notes in Computer Science). — Springer. — ISBN 3-540-88907-8.
↑ A. Osyzka. «Multicriteria optimization for engineering design». Design Optimization (Academic Press): 193-227.
↑ (Ehrgott, c. 34)
↑ (Jürgen et al, с. XI)
↑ 1 2 3 Sequential Approximate Multiobjective Optimization Using Computational Intelligence (Vector Optimization). — Springer. — ISBN 978-3-540-88909-0.
↑ R. S. Rosenberg. Simulation of genetic populations with biochemical properties. — University of Michigan, 1967.
↑ Соболь И.М. Выбор оптимальных параметров в задачах со многими критериями. — М.: Дрофа, 2006. — 175 с. — ISBN 5-7107-7989-X.

Литература

Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. — М: Радио и связь, 1981. — 560 с.
Matthias Ehrgott. Multicriteria Optimization. — Springer. — ISBN 3-540-21398-8.
M. Ehrgott and X. Gandibleux (2004). «[www.lania.mx/~ccoello/EMOO/ehrgott04a.pdf.gz Approximative Solution Methods for Multiobjective Combinatorial Optimization]». TOP (Sociedad de Estadística e Investigación Operativa) 12 (1).

Ресурсы интернета

Трифонов А. Г. [matlab.exponenta.ru/optimiz/book_1/16.php Многокритериальная оптимизация] (рус.)
[www.iosotech.com/ru/products.htm IOSO технология многокритериальной оптимизации] (рус.)

Отрывок, характеризующий Многокритериальная оптимизация

– Ожиг, жиг, ожиг, жиг… – свистела натачиваемая сабля. И вдруг Петя услыхал стройный хор музыки, игравшей какой то неизвестный, торжественно сладкий гимн. Петя был музыкален, так же как Наташа, и больше Николая, но он никогда не учился музыке, не думал о музыке, и потому мотивы, неожиданно приходившие ему в голову, были для него особенно новы и привлекательны. Музыка играла все слышнее и слышнее. Напев разрастался, переходил из одного инструмента в другой. Происходило то, что называется фугой, хотя Петя не имел ни малейшего понятия о том, что такое фуга. Каждый инструмент, то похожий на скрипку, то на трубы – но лучше и чище, чем скрипки и трубы, – каждый инструмент играл свое и, не доиграв еще мотива, сливался с другим, начинавшим почти то же, и с третьим, и с четвертым, и все они сливались в одно и опять разбегались, и опять сливались то в торжественно церковное, то в ярко блестящее и победное. «Ах, да, ведь это я во сне, – качнувшись наперед, сказал себе Петя. – Это у меня в ушах. А может быть, это моя музыка. Ну, опять. Валяй моя музыка! Ну!..» Он закрыл глаза. И с разных сторон, как будто издалека, затрепетали звуки, стали слаживаться, разбегаться, сливаться, и опять все соединилось в тот же сладкий и торжественный гимн. «Ах, это прелесть что такое! Сколько хочу и как хочу», – сказал себе Петя. Он попробовал руководить этим огромным хором инструментов. «Ну, тише, тише, замирайте теперь. – И звуки слушались его. – Ну, теперь полнее, веселее. Еще, еще радостнее. – И из неизвестной глубины поднимались усиливающиеся, торжественные звуки. – Ну, голоса, приставайте!» – приказал Петя. И сначала издалека послышались голоса мужские, потом женские. Голоса росли, росли в равномерном торжественном усилии. Пете страшно и радостно было внимать их необычайной красоте. С торжественным победным маршем сливалась песня, и капли капали, и вжиг, жиг, жиг… свистела сабля, и опять подрались и заржали лошади, не нарушая хора, а входя в него. Петя не знал, как долго это продолжалось: он наслаждался, все время удивлялся своему наслаждению и жалел, что некому сообщить его. Его разбудил ласковый голос Лихачева. – Готово, ваше благородие, надвое хранцуза распластаете. Петя очнулся. – Уж светает, право, светает! – вскрикнул он. Невидные прежде лошади стали видны до хвостов, и сквозь оголенные ветки виднелся водянистый свет. Петя встряхнулся, вскочил, достал из кармана целковый и дал Лихачеву, махнув, попробовал шашку и положил ее в ножны. Казаки отвязывали лошадей и подтягивали подпруги. – Вот и командир, – сказал Лихачев. Из караулки вышел Денисов и, окликнув Петю, приказал собираться.

Быстро в полутьме разобрали лошадей, подтянули подпруги и разобрались по командам. Денисов стоял у караулки, отдавая последние приказания. Пехота партии, шлепая сотней ног, прошла вперед по дороге и быстро скрылась между деревьев в предрассветном тумане. Эсаул что то приказывал казакам. Петя держал свою лошадь в поводу, с нетерпением ожидая приказания садиться. Обмытое холодной водой, лицо его, в особенности глаза горели огнем, озноб пробегал по спине, и во всем теле что то быстро и равномерно дрожало. – Ну, готово у вас все? – сказал Денисов. – Давай лошадей. Лошадей подали. Денисов рассердился на казака за то, что подпруги были слабы, и, разбранив его, сел. Петя взялся за стремя. Лошадь, по привычке, хотела куснуть его за ногу, но Петя, не чувствуя своей тяжести, быстро вскочил в седло и, оглядываясь на тронувшихся сзади в темноте гусар, подъехал к Денисову. – Василий Федорович, вы мне поручите что нибудь? Пожалуйста… ради бога… – сказал он. Денисов, казалось, забыл про существование Пети. Он оглянулся на него. – Об одном тебя пг'ошу, – сказал он строго, – слушаться меня и никуда не соваться. Во все время переезда Денисов ни слова не говорил больше с Петей и ехал молча. Когда подъехали к опушке леса, в поле заметно уже стало светлеть. Денисов поговорил что то шепотом с эсаулом, и казаки стали проезжать мимо Пети и Денисова. Когда они все проехали, Денисов тронул свою лошадь и поехал под гору. Садясь на зады и скользя, лошади спускались с своими седоками в лощину. Петя ехал рядом с Денисовым. Дрожь во всем его теле все усиливалась. Становилось все светлее и светлее, только туман скрывал отдаленные предметы. Съехав вниз и оглянувшись назад, Денисов кивнул головой казаку, стоявшему подле него. – Сигнал! – проговорил он. Казак поднял руку, раздался выстрел. И в то же мгновение послышался топот впереди поскакавших лошадей, крики с разных сторон и еще выстрелы. В то же мгновение, как раздались первые звуки топота и крика, Петя, ударив свою лошадь и выпустив поводья, не слушая Денисова, кричавшего на него, поскакал вперед. Пете показалось, что вдруг совершенно, как середь дня, ярко рассвело в ту минуту, как послышался выстрел. Он подскакал к мосту. Впереди по дороге скакали казаки. На мосту он столкнулся с отставшим казаком и поскакал дальше. Впереди какие то люди, – должно быть, это были французы, – бежали с правой стороны дороги на левую. Один упал в грязь под ногами Петиной лошади. У одной избы столпились казаки, что то делая. Из середины толпы послышался страшный крик. Петя подскакал к этой толпе, и первое, что он увидал, было бледное, с трясущейся нижней челюстью лицо француза, державшегося за древко направленной на него пики. – Ура!.. Ребята… наши… – прокричал Петя и, дав поводья разгорячившейся лошади, поскакал вперед по улице. Впереди слышны были выстрелы. Казаки, гусары и русские оборванные пленные, бежавшие с обеих сторон дороги, все громко и нескладно кричали что то. Молодцеватый, без шапки, с красным нахмуренным лицом, француз в синей шинели отбивался штыком от гусаров. Когда Петя подскакал, француз уже упал. Опять опоздал, мелькнуло в голове Пети, и он поскакал туда, откуда слышались частые выстрелы. Выстрелы раздавались на дворе того барского дома, на котором он был вчера ночью с Долоховым. Французы засели там за плетнем в густом, заросшем кустами саду и стреляли по казакам, столпившимся у ворот. Подъезжая к воротам, Петя в пороховом дыму увидал Долохова с бледным, зеленоватым лицом, кричавшего что то людям. «В объезд! Пехоту подождать!» – кричал он, в то время как Петя подъехал к нему. – Подождать?.. Ураааа!.. – закричал Петя и, не медля ни одной минуты, поскакал к тому месту, откуда слышались выстрелы и где гуще был пороховой дым. Послышался залп, провизжали пустые и во что то шлепнувшие пули. Казаки и Долохов вскакали вслед за Петей в ворота дома. Французы в колеблющемся густом дыме одни бросали оружие и выбегали из кустов навстречу казакам, другие бежали под гору к пруду. Петя скакал на своей лошади вдоль по барскому двору и, вместо того чтобы держать поводья, странно и быстро махал обеими руками и все дальше и дальше сбивался с седла на одну сторону. Лошадь, набежав на тлевший в утреннем свето костер, уперлась, и Петя тяжело упал на мокрую землю. Казаки видели, как быстро задергались его руки и ноги, несмотря на то, что голова его не шевелилась. Пуля пробила ему голову. Переговоривши с старшим французским офицером, который вышел к нему из за дома с платком на шпаге и объявил, что они сдаются, Долохов слез с лошади и подошел к неподвижно, с раскинутыми руками, лежавшему Пете. – Готов, – сказал он, нахмурившись, и пошел в ворота навстречу ехавшему к нему Денисову. – Убит?! – вскрикнул Денисов, увидав еще издалека то знакомое ему, несомненно безжизненное положение, в котором лежало тело Пети. – Готов, – повторил Долохов, как будто выговаривание этого слова доставляло ему удовольствие, и быстро пошел к пленным, которых окружили спешившиеся казаки. – Брать не будем! – крикнул он Денисову. Денисов не отвечал; он подъехал к Пете, слез с лошади и дрожащими руками повернул к себе запачканное кровью и грязью, уже побледневшее лицо Пети. «Я привык что нибудь сладкое. Отличный изюм, берите весь», – вспомнилось ему. И казаки с удивлением оглянулись на звуки, похожие на собачий лай, с которыми Денисов быстро отвернулся, подошел к плетню и схватился за него. В числе отбитых Денисовым и Долоховым русских пленных был Пьер Безухов.

О той партии пленных, в которой был Пьер, во время всего своего движения от Москвы, не было от французского начальства никакого нового распоряжения. Партия эта 22 го октября находилась уже не с теми войсками и обозами, с которыми она вышла из Москвы. Половина обоза с сухарями, который шел за ними первые переходы, была отбита казаками, другая половина уехала вперед; пеших кавалеристов, которые шли впереди, не было ни одного больше; они все исчезли. Артиллерия, которая первые переходы виднелась впереди, заменилась теперь огромным обозом маршала Жюно, конвоируемого вестфальцами. Сзади пленных ехал обоз кавалерийских вещей. От Вязьмы французские войска, прежде шедшие тремя колоннами, шли теперь одной кучей. Те признаки беспорядка, которые заметил Пьер на первом привале из Москвы, теперь дошли до последней степени. Дорога, по которой они шли, с обеих сторон была уложена мертвыми лошадьми; оборванные люди, отсталые от разных команд, беспрестанно переменяясь, то присоединялись, то опять отставали от шедшей колонны. Несколько раз во время похода бывали фальшивые тревоги, и солдаты конвоя поднимали ружья, стреляли и бежали стремглав, давя друг друга, но потом опять собирались и бранили друг друга за напрасный страх. Эти три сборища, шедшие вместе, – кавалерийское депо, депо пленных и обоз Жюно, – все еще составляли что то отдельное и цельное, хотя и то, и другое, и третье быстро таяло. В депо, в котором было сто двадцать повозок сначала, теперь оставалось не больше шестидесяти; остальные были отбиты или брошены. Из обоза Жюно тоже было оставлено и отбито несколько повозок. Три повозки были разграблены набежавшими отсталыми солдатами из корпуса Даву. Из разговоров немцев Пьер слышал, что к этому обозу ставили караул больше, чем к пленным, и что один из их товарищей, солдат немец, был расстрелян по приказанию самого маршала за то, что у солдата нашли серебряную ложку, принадлежавшую маршалу.

wiki-org.ru

Многокритериальная оптимизация - Большая Энциклопедия Нефти и Газа, статья, страница 1

Многокритериальная оптимизация

Cтраница 1

Многокритериальная оптимизация предназначена в основном для минимизации многоцелевых функций с учетом некоего набора ограничений. В Optimization Toolbox реализованы два типа задач многокритериальной оптимизации: задача достижения цели и задача минимакса. [1]

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

Схема многокритериальной оптимизации по ряду критериев показана на рис. IV-1. Приведенные здесь рекомендации получены на практике и могут уточняться по мере проведения дополнительных исследований для различных ГТС, необходимость которых очевидна. [3]

Исследование методов многокритериальной оптимизации позволило сделать вывод о том, что практически все известные методы векторного синтеза оптимальной системы непосредственно или косвенно сводятся к скалярному синтезу. [4]

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

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

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

Итак, методы многокритериальной оптимизации позволяют тем или иным образом преодолеть трудности, связанные с неединственностью критерия. При этом, однако, приходится решать задачу, значительно более сложную, чем задача оптимизации. Поэтому задачи многокритериального выбора удается решить в случае относительно простых моделей. Что же следует делать, если модели сложны. Ведь достаточно адекватная математическая модель некоторой экономической системы может оказаться настолько сложна, что и обычную оптимизационную задачу решить не удается. В этом случае для исследования экономических систем применяются имитационные эксперименты. [8]

Для решения задач многокритериальной оптимизации находят применение методы зондирования пространства параметров оптимизации. К таким методам относится Лгг-поиск, в соответствии с которым производится вычисление значений k критериев оптимизации в точках, равномерно распределенных в и-мерном пространстве параметров оптимизации. [9]

Методологические принципы решения многокритериальных оптимизации сформулированы, разрабатывается и мате-лматическое обеспечение. Это относится и к выработке и применению интегрального критерия оптимальности системы СО. Применительно к этой задаче такой критерий может быть представлен как соотношение затрат на создание и функционирование системы СО ( как некоторого множества их типов и экземпляров и всего, что относится к их созданию и применению - см. разд. [10]

Еще один подход к многокритериальной оптимизации связан с разделением популяции на подгруппы одинакового размера ( sub-populations), каждая из которых отвечает за одну оптимизируемую функцию. [11]

Сущность другой группы методов многокритериальной оптимизации состоит в последовательном выявлении предпочтений одновременно с получением и исследованием допустимого множества альтернатив. В целом этот подход отличается большей объективностью при сопоставлении различных вариантов проекта одновременно по нескольким показателям качества. [12]

Рассмотрим более подробно алгоритм многокритериальной оптимизации, объединяющий особенности методов сканирования и последовательных уступок и предусматривающий нормирование частных критериев с использованием понятий нечеткого математического программирования. [13]

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

Существуют две крайности в процессе многокритериальной оптимизации: векторная оптимизация, включающая громадный объем расчетов и на дающая однозначного решения, и оптимизация по свернутому в скаляр векторному критерию путем линейной комбинации составляющих критериев, что чрезмерно упрощает задачу и часто не приводит к получению глобального оптимума. [15]

Страницы: 1 2 3 4