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

Объектом исследования является задачи многокритериальной оптимизации.

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

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

Сформулированная цель предопределила совокупность решаемых задач:

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

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

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

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

5. Провести сравнительный анализ методов.

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

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

В заключении сделаны выводы по всей выпускной квалификационной работе.

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

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

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

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

Сравнение допустимых решений в многокритериальной задаче. Оценкой допустимого решения х X задачи (10.1.1) называется вектор

Смысл сравнения различных допустимых решений в многокритериальной задаче состоит в сравнивании их векторных оценок. То есть предпочтительность на множестве X можно заменить предпочтительностью оценок на множестве Rm. Однако, на множестве Rm элементы сравнимы далеко не всегда. Часто встречается ситуация, когда среди двух допустимых решений одно лучше по одному критерию, а второе — по другому критерию. Например, в задаче (Пример 1) векторная оценка решения (20; 0) имеет вид (200; 20), а векторная оценка решения (0; 40) — (160; 40). По этим оценкам видно, что рассматриваемые решения несравнимы.

3. Эффективные решения многокритериальных задач Математически отношения между объектами, когда некоторые из них можно сравнивать, а некоторые несравнимы, называются отношениями частичного порядка или отношениями строго частичного порядка. В задаче многокритериальной оптимизации (1.1) на множестве Х допустимых решений можно ввести отношение строго частичного порядка. Пусть х, у — два допустимых решения задачи (1.1), т.е. х X и у X . Говорят, что x строго предпочтительнее у, если решение х лучше решения по всем критериям. Такое отношение строгого предпочтения на множестве X записывают х у.

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

Отношение доминирования, введенное на множестве допустимых решений X, называется также доминированием по Парето.

Рассмотрим задачу (1.1) на нахождение максимума по всем критериям. Решение х0 е X называется оптимальным по Парею или эффективным, если не существует 'такого другого решения х X . что

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

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

Проиллюстрируем прием выделения эффективных решений на примере с двумя критериями: W1,. W2 (оба требуется максимизировать). Множество X состоит из конечного числа п возможных решений х1, х2,…хn. Каждому решению соответствуют определенные значения показателей W1, W2: будем изображать решение точкой на плоскости с координатами значений показателей W1, W2 и занумеруем точки соответственно решению (рис 1).

Очевидно, из всего множества X эффективными будут только х1,х2,х3,

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