Основные методы решения многокритериальных задач

⇐ ПредыдущаяСтр 7 из 9Следующая ⇒

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

Выделяют ряд методов решения задач многокритериальной оптимизации:

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

2) сведение многих критериев к одному введением экспертных весовых коэффициентов для каждого из критериев таким образом, что более важный критерий получает более высокий вес;

3) упорядочение заданного множества критериев и последовательная оптимизация по каждому из них (этот подход лежит в основе метода последовательных уступок).

Доминирование и оптимальность по Парето. Эффективные решения и паретова граница

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

Определение. Вектор называется эффективным (оптимальным по Парето) решением задачи (1), (2), если не существует такого вектора , что

причем хотя бы для одного значения i имеет место строгое неравенство.

Пример. Метод «стоимость – эффективность»

Пусть заданы два критерия: – стоимость, – эффективность. Рассмотрим задачу

Множество допустимых вариантов U в пространстве критериев графически представлено на рисунке 1.

Рисунок 1. Множество допустимых вариантов U в пространстве критериев

Рассмотрим два допустимых варианта 1 и 2. Вариант 1 имеет большую эффективность и меньшую стоимость, чем 2, следовательно, вариант 1 лучше. Если сравнивать варианты 1 и 3, то видно, что вариант 1 имеет меньшую стоимость, но вариант 3 более эффективен. В этом случае можно сказать, что варианты 1 и 3 несравнимы.

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

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

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

Свертка критериев с весовыми коэффициентами. Метод обобщенного критерия

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

Методы параметрического программирования.

⇐ Предыдущая 1 2 3 4 5 678 9 Следующая ⇒